day10.rs

// This should be revised. It is super-ineffcient as it stands although it provides the correct answer in < 4 sec.
// Maybe later wehen there is not a christmas party the same day.

use std::io::{BufReader, BufRead};
use std::env;
use std::fs::File;

fn main() {
    let belt_size: usize = 21;
    let args: Vec<String> = env::args().collect();
    let asteroid_file = &args[1];
    let asteroids = load_asteroids(asteroid_file, belt_size);
    let mut max_coord = (0, 0);
    let mut max_count = 0;
    for ir in 0..belt_size {
        for ic in 0..belt_size {
            if asteroids[ir][ic] {
                let coord = (ir, ic);
                let count = count_visible_asteroids(ir, ic, &asteroids, belt_size);
                if count > max_count {
                    max_coord = coord;
                    max_count = count;
                }
            }
        }
   }
   println!("{:?} {}", max_coord, max_count);
   
   let station_coord = max_coord;
   let mut asteroid_coords: Vec<(usize, usize)> = vec!();
   for ir in 0..belt_size {
       for ic in 0..belt_size {
            if asteroids[ir][ic] {
                let coord = (ir, ic);
                if coord != station_coord {
                    asteroid_coords.push(coord)
                }
            }
        }   
    }
    let (station_r, station_c) = station_coord;
    // Calculate the angle (counter clockwise) to all asteroids from the station with zero as upright
    let mut aabp: Vec<((usize, usize), f64, bool)> = asteroid_coords.iter().map(
        |(r, c)| {
            let dc = *c as i64 - station_c as i64;
            let dr = -(*r as i64 - station_r as i64);
            let angle_from_upright = if dc >= 0 {
                if dr > 0 {
                    1.5 * std::f64::consts::PI + ((dr as f64)/(dc as f64)).atan()
                } else {
                    1.5 * std::f64::consts::PI - ((-dr as f64)/(dc as f64)).atan()
                }
            } else {
                if dr > 0 {
                    std::f64::consts::PI/2.0 - ((dr as f64)/(-dc as f64)).atan()
                } else {
                    std::f64::consts::PI/2.0 + (-(dr as f64)/(-dc as f64)).atan()
                }
            };
            ((*r, *c), angle_from_upright, false)
            }

    ).collect();
    // Sort circularly clockwise, i.e., reverse to how angles count
    aabp.sort_by( |a , b | 
        if a.1 != b.1 {
            (b.1).partial_cmp(&a.1).unwrap()
        } else {
            // If at equal angles sort by distance from station
            let (ar, ac) = a.0;
            let (br, bc) = b.0;
            let dasq = (ar as i64 - station_r as i64)^2 + (ac as i64 - station_c as i64)^2;
            let dbsq = (br as i64 - station_r as i64)^2 + (bc as i64 - station_c as i64)^2;
            dasq.partial_cmp(&dbsq).unwrap()
        });
    let mut n_blasted = 0;
    let mut next_ind = 0;
    loop {
        // Move forward to the first not yet blasted index
        loop {
            if !aabp[next_ind].2 {
                break
            }
            next_ind += 1;
            if next_ind >= aabp.len() {
                next_ind = 0
            }
        }
        // Blast this one
        aabp[next_ind].2 = true;
        n_blasted += 1;
        if n_blasted == 200 {
            println!("Woohoo!! {:?}", aabp[next_ind]);
            break
        }
        // Skip past asteroids at the same angle as the one that was just blasted
        let last_blasted_angle = aabp[next_ind].1;
        loop {
            next_ind += 1;
            if next_ind >= aabp.len() {
                next_ind = 0
            }
            if aabp[next_ind].1 != last_blasted_angle {
                break;
            }
        }
    }
}

fn count_visible_asteroids(r: usize, c: usize, asteroids: &Vec<Vec<bool>>, belt_size: usize) -> usize {
    let mut n_visible = 0;
    for ir in 0..belt_size {
        for ic in 0..belt_size {
            if ir != r || ic != c {
                if asteroids[ir][ic] && has_line_of_sight(r, c, ir, ic, asteroids, belt_size) {
                    n_visible += 1
                }    
            }
        }
    }
    n_visible
}

fn has_line_of_sight(r1: usize, c1: usize, r2: usize, c2: usize, asteroids: &Vec<Vec<bool>>, belt_size: usize) -> bool {
    for ir in 0..belt_size {
        for ic in 0..belt_size {
            if !((c1 == ic && r1 == ir) || (c2 == ic && r2 == ir)) {
                if asteroids[ir][ic] && blocks_line_of_sight(ir, ic, r1, c1, r2, c2) {
                    return false
                }    
            }
        }
    }
    true
}

fn blocks_line_of_sight(r: usize, c: usize, r1: usize, c1: usize, r2: usize, c2: usize) -> bool {
    let numerator_1 = r as i64 - r1 as i64;
    let denominator_1 = c as i64 - c1 as i64;
    let numerator_2 = r2 as i64 - r as i64;
    let denominator_2 = c2 as i64 - c as i64;
    if (c < c1 && c < c2 ) || (r < r1 && r < r2 ) || (c > c1 && c > c2 ) || (r > r1 && r > r2 ) {
        return false
    }
    if numerator_1 * numerator_2 < 0 || denominator_1 * denominator_2 < 0 {
        return false
    }
    numerator_1 * denominator_2 == numerator_2 * denominator_1
}

fn load_asteroids(asteroid_file: &String, belt_size: usize) -> Vec<Vec<bool>> {
    let mut asteroids: Vec<Vec<bool>> = vec!();
    let file = File::open(asteroid_file).expect("Could not open program file!");
    let reader = BufReader::new(file);
    for line in reader.lines() {
        let line = line.expect("Could not read from stdin");
        let asteroid_line: Vec<bool>= line.chars().map( |c| if c == '#' { true } else {false}).collect();
        if asteroid_line.len() != belt_size {
            panic!("Malformed asteroid belt.")
        }
        asteroids.push(asteroid_line);
     }
     if asteroids.len() != belt_size {
        panic!("Malformed asteroid belt.")
    }
 asteroids
}