frog/src/main.rs

use anyhow::Result;
use bmp::Image;
use std::{fs::File, io::{self, BufRead, Cursor}};
use rand::prelude::*;
use rayon::prelude::*;

#[derive(Clone, Copy, PartialEq, PartialOrd, Debug)]
struct Radians(f64);
#[derive(Clone, Copy, PartialEq, PartialOrd, Debug)]
struct Degrees(f64);

impl From<Degrees> for Radians {
    fn from(value: Degrees) -> Self {
        Radians(value.0 * std::f64::consts::PI / 180f64)
    }
}
impl Into<f64> for Radians {
    fn into(self) -> f64 {
        self.0
    }
}
impl From<Radians> for Degrees {
    fn from(value: Radians) -> Self {
        Degrees(value.0 * (180f64 / std::f64::consts::PI))
    }
}
impl Into<f64> for Degrees {
    fn into(self) -> f64 {
        self.0
    }
}

#[derive(PartialEq, Clone, Debug)]
struct Location {
    lat: Radians,
    lon: Radians,
}
impl From<(Degrees, Degrees)> for Location {
    fn from(value: (Degrees, Degrees)) -> Self {
        Location {
            lat: value.0.into(),
            lon: value.1.into()
        }
    }
}

const IMG_NORTH_BORDER: Radians = Radians(0.9570757299); // Degrees(54.8364);
const IMG_WEST_BORDER:  Radians = Radians(0.2464911049); // Degrees(14.1229);
const IMG_SOUTH_BORDER: Radians = Radians(0.8552532214); // Degrees(49.0024);
const IMG_EAST_BORDER:  Radians = Radians(0.4214184745); // Degrees(24.1455);
const EPSILON: f64 = 0.00001f64;

struct ImageMeta {
    image: Image,
    horizontal_scale: f64,
    vertical_scale: f64
}

#[inline(always)]
fn gcd(a: &Location, b: &Location) -> f64 {
    return f64::acos(
        f64::sin(a.lat.into())*f64::sin(b.lat.into()) + 
        f64::cos(a.lat.into())*f64::cos(b.lat.into())*f64::cos(
            f64::abs(a.lon.0 - b.lon.0)
        )
    )
}

fn dist(location: &Location, shops: &Vec<Location>) -> f64 {
    shops.into_iter().map(|a| {
        gcd(a, &location)
    }).min_by(|a, b| a.partial_cmp(b).unwrap_or(std::cmp::Ordering::Greater)).unwrap()
}

fn in_poland(
    location: &Location, 
    im: &ImageMeta,
) -> bool {
    if location.lat < IMG_SOUTH_BORDER ||
       location.lat >= IMG_NORTH_BORDER || 
       location.lon < IMG_WEST_BORDER || 
       location.lon >= IMG_EAST_BORDER {
        return false
    }

    let offlat = location.lat.0 - IMG_SOUTH_BORDER.0;
    let offlon = location.lon.0 - IMG_WEST_BORDER.0;
    let ppos: (f64, f64) = (offlon * im.horizontal_scale, offlat * im.vertical_scale);
    let ppos = (ppos.0 as u32, im.image.get_height() - (ppos.1 as u32) - 1);

    return im.image.get_pixel(ppos.0, ppos.1) == bmp::consts::BLACK;
}

fn start_point(
    im: &ImageMeta
) -> Location {
    loop {
        let loc = Location {
            lat: Radians(rand::thread_rng().gen_range(IMG_SOUTH_BORDER.0 .. IMG_NORTH_BORDER.0)),
            lon: Radians(rand::thread_rng().gen_range(IMG_WEST_BORDER.0 .. IMG_EAST_BORDER.0)  )
        };
        if in_poland(&loc, im) {
            return loc;
        }
    }
}

fn get_next_point(curr: Location, im: &ImageMeta, shops: &Vec<Location>) -> (f64, Location) {
    [
        Location {lat: Radians(curr.lat.0 + EPSILON), lon: Radians(curr.lon.0)},
        Location {lat: Radians(curr.lat.0 - EPSILON), lon: Radians(curr.lon.0)},
        Location {lat: Radians(curr.lat.0), lon: Radians(curr.lon.0 + EPSILON)},
        Location {lat: Radians(curr.lat.0), lon: Radians(curr.lon.0 - EPSILON)},
        Location {lat: Radians(curr.lat.0 + EPSILON), lon: Radians(curr.lon.0 + EPSILON)},
        Location {lat: Radians(curr.lat.0 + EPSILON), lon: Radians(curr.lon.0 - EPSILON)},
        Location {lat: Radians(curr.lat.0 - EPSILON), lon: Radians(curr.lon.0 - EPSILON)},
        Location {lat: Radians(curr.lat.0 - EPSILON), lon: Radians(curr.lon.0 + EPSILON)},
        curr
    ].into_iter().filter(|loc| {
        in_poland(loc, im)
    }).map(|loc| {
        (dist(&loc, shops), loc)
    }).max_by(|x, y| {
        x.0.partial_cmp(&y.0).unwrap()
    }).unwrap()
}

fn find_local_best(start: Location, im: &ImageMeta, shops: &Vec<Location>) -> (f64, Location) {
    let mut curr = start;
    loop {
        let next = get_next_point(curr.clone(), im, shops);
        if curr == next.1 {
            return next;
        }

        curr = next.1;
    }
}

fn search(im: &ImageMeta, shops: &Vec<Location>) -> (Location, f64) {
    let mut best_dist = 0f64;
    let mut best_point = Location {lat: Radians(0f64), lon: Radians(0f64)};
    for iter in 0..3000 {
        let start = start_point(im);
        let local = find_local_best(start, im, shops);
        if local.0 > best_dist {
            best_dist = local.0;
            best_point = local.1.clone();
            println!("At iter {}, new best", iter);
        }
    }

    return (best_point, best_dist);
}

fn main() -> Result<()> {
    let file = File::open("./pos.txt")?;
    let mut frog_shops: Vec<Location> = Vec::with_capacity(10778);
    for line in io::BufReader::new(file).lines() {
        let line = line?;
        let numbers: Vec<f64> = line.split(" ").map(str::parse::<f64>).map(Result::unwrap).collect();
        frog_shops.push(Location {
            lat: Degrees(numbers[0]).into(), 
            lon: Degrees(numbers[1]).into()
        });
    }

    let poland = include_bytes!("../poland.bmp");
    let mut cursor = Cursor::new(poland);
    let img = bmp::from_reader(&mut cursor)?;
    // println!("{:?}", img);

    // println!("{:?}", dist((
    //     radians!(52f64), radians!(19f64)
    // ), &frog_shops));

    // println!("{:?}", in_poland((radians!(52f64), radians!(19f64)), &img, p_horiz_scale, p_verti_scale));
    // println!("{:?}", degrees_but_tuple!(start_point(&img, p_horiz_scale, p_verti_scale)));
    // println!("{:?}", degrees_but_tuple!(find_local_best(
    //     (radians!(52f64), radians!(19f64)), &img, p_horiz_scale, p_verti_scale, &frog_shops
    // )));
    let imagemeta = ImageMeta {
        horizontal_scale: (img.get_width() as f64) / (IMG_EAST_BORDER.0 - IMG_WEST_BORDER.0),
        vertical_scale: (img.get_height() as f64) / (IMG_NORTH_BORDER.0 - IMG_SOUTH_BORDER.0),
        image: img
    };
    // let result = (0..100)
    //     .into_iter()
    //     .into_par_iter()
    //     .map(|_| search(&imagemeta, &frog_shops))
    //     .max_by(|a, b| {
    //         a.1.partial_cmp(&b.1).unwrap()
    //     }).unwrap();
    let result = search(&imagemeta, &frog_shops);

    let best_point: (Degrees, Degrees) = (result.0.lat.into(), result.0.lon.into());
    println!("Found best point at ({}, {}); Distance is {}", best_point.0.0, best_point.1.0, result.1);
    
    Ok(())
}