Advent of Code 2019 - Day 10

Advent of CodeRust

Today was quite challenging compared to the last few days.

The problem had a lot to do with angles and because I didn't want to mess with floating point numbers I multiplied them by an integer. This is definitely not the best solution but it works and I'm happy I got it done.

Code

use std::collections::HashMap;
use std::f64::consts::PI;
use utils::Point;

const PRECISION: f64 = 100_000f64;

fn get_points(input: &str) -> Vec<Point> {
    let mut points = Vec::new();

    for (y, line) in input.lines().enumerate() {
        for (x, c) in line.chars().enumerate() {
            if let '#' = c {
                points.push(Point {
                    x: x as i32,
                    y: y as i32,
                });
            }
        }
    }

    points
}

fn calculate_angle(x: f64, y: f64) -> i64 {
    (y.atan2(x) * PRECISION) as i64
}

fn get_angles(point: &Point, points: &[Point]) -> HashMap<i64, Vec<Point>> {
    let mut angles: HashMap<i64, Vec<Point>> = HashMap::new();
    for other in points.iter() {
        if point == other {
            continue;
        }
        let y = other.y as f64 - point.y as f64;
        let x = other.x as f64 - point.x as f64;

        let entry = angles.entry(calculate_angle(x, y)).or_insert_with(Vec::new);
        entry.push(other.clone());
    }

    angles
}

pub fn part_one(input: &str) -> i32 {
    let points = get_points(input);
    let mut max_asteroids = 0;

    for point in points.iter() {
        max_asteroids = i32::max(max_asteroids, get_angles(point, &points).len() as i32);
    }

    max_asteroids
}

pub fn part_two(input: &str, station: Point) -> i32 {
    let points = get_points(input);
    let angle_map = get_angles(&station, &points);

    let mut angles: Vec<i64> = angle_map
        .keys()
        .copied()
        .map(|x| {
            if x < 0 {
                return x + ((PI * 2f64) * PRECISION) as i64;
            }

            x
        })
        .collect();

    angles.sort();

    // Rotate the vector so that the angle pointing to the top is the first
    // element.
    let mut angle_check = angles[0];
    let top_value = ((PI * 1.5) * PRECISION) as i64;
    while angle_check < top_value {
        angles.rotate_left(1);
        angle_check = angles[0];
    }

    // Get the 200th element
    let final_angle = angles[199] - ((PI * 2f64) * PRECISION) as i64;
    let point = angle_map.get(&final_angle).unwrap().first().unwrap();

    point.x * 100 + point.y
}

Benchmarks

2019 - Day 10 - Part 1 time: 29.264525ms
2019 - Day 10 - Part 2 time: 111.497µs

Feedback or Questions?

I don't have a direct way to leave comments on posts. But if you want to give some feedback or have some questions you can contact in other ways.

©2019–2020 Severin Kaderli