AoC2019 - 10.1

main.rs

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

struct LengthScanner {
    length: isize,
    current: (isize, isize),
    quadrant: usize,
}

impl Iterator for LengthScanner {
    type Item = (isize, isize);

    fn next(&mut self) -> Option<(isize, isize)> {
        if self.current == (0, self.length) {
            return None;
        }

        let q_value: (isize, isize);
        if self.quadrant == 0 {
            q_value = self.current;
        } else if self.quadrant == 1 {
            q_value = (self.current.1, -self.current.0);
        } else if self.quadrant == 2 {
            q_value = (-self.current.0, -self.current.1);
        } else {
            q_value = (-self.current.1, self.current.0);
            self.current = (self.current.0 - 1, self.current.1 + 1);
        }
        self.quadrant = (self.quadrant + 1) % 4;

        Some(q_value)
    }
}

fn length_scanner(length: isize) -> LengthScanner {
    LengthScanner {
        length,
        current: (length, 0),
        quadrant: 0,
    }
}

fn gcd(a: isize, b: isize) -> isize {
    let mut a = a.abs();
    let mut b = b.abs();

    while b != 0 {
        let tmp = a;
        a = b;
        b = tmp % b;
    }
    a
}

struct LineOfSight<'a> {
    position: (isize, isize),
    map: &'a HashSet<(isize, isize)>,
    max_x: isize,
    max_y: isize,
    max_length: isize,
    obstructed: HashSet<(isize, isize)>,
    current_scanner: LengthScanner,
}

impl Iterator for LineOfSight<'_> {
    type Item = (isize, isize);

    fn next(&mut self) -> Option<(isize, isize)> {
        let mut next_position: (isize, isize);
        let mut path: (isize, isize);
        loop {
            let next_move = self.current_scanner.next();
            match next_move {
                Some(v) => {
                    path = (v.0, v.1);
                }
                None => {
                    let next_length = self.current_scanner.length + 1;
                    if next_length > self.max_length {
                        return None;
                    }
                    self.current_scanner = length_scanner(next_length);
                    continue;
                }
            }

            let next_x = self.position.0 + path.0;
            let next_y = self.position.1 + path.1;
            if next_x < 0 || self.max_x < next_x {
                continue;
            }
            if next_y < 0 || self.max_y < next_y {
                continue;
            }
            next_position = (next_x, next_y);

            let gcd = gcd(path.0, path.1);
            let obstructed_view = (path.0 / gcd, path.1 / gcd);
            if self.obstructed.contains(&obstructed_view) {
                continue;
            }

            if !self.map.contains(&next_position) {
                continue;
            }

            self.obstructed.insert(obstructed_view);
            break;
        }
        Some(next_position)
    }
}

fn line_of_sight(origin: (isize, isize), map: &HashSet<(isize, isize)>) -> LineOfSight {
    let mut max_x: isize = 0;
    let mut max_y: isize = 0;
    for (x, y) in map {
        if *x > max_x {
            max_x = *x;
        }
        if *y > max_y {
            max_y = *y;
        }
    }
    let max_length = cmp::max(origin.0, max_x - origin.0) + cmp::max(origin.1, max_y - origin.1);
    LineOfSight {
        position: origin,
        map,
        max_x,
        max_y,
        max_length,
        obstructed: HashSet::<(isize, isize)>::new(),
        current_scanner: length_scanner(1),
    }
}

fn create_map(args: &[String]) -> HashSet<(isize, isize)> {
    let mut map = HashSet::new();
    let filename = &args[1];
    let file = File::open(filename).unwrap();
    let reader = BufReader::new(file);

    for (y, line) in reader.lines().filter_map(|l| l.ok()).enumerate() {
        for (x, c) in line.chars().enumerate() {
            if c == '#' {
                map.insert((x as isize, y as isize));
            }
        }
    }
    map
}

fn main() {
    let args: Vec<String> = env::args().collect();
    let map = create_map(&args);

    let mut best_position = (-1, -1);
    let mut max_detected = 0;
    for astroid in &map {
        let los = line_of_sight(*astroid, &map);
        let mut valid_path = 0;
        for _path in los {
            valid_path += 1;
        }
        if valid_path > max_detected {
            max_detected = valid_path;
            best_position = *astroid;
        }
    }

    println!("{:?}: {:?}", best_position, max_detected);
}