Advent of Code 2019 - Day 3

Advent of CodeRust

Today's challenge was a bit more challenging and it did take some time for me.

We needed to find the intersections point of two wires and then return the point which was the closest to the start. The second part was then to find the intersection which can be reachted in the fewest steps. Using a HashMap it was quite easy to do but it isn't the fastest code. Using some fancy application of geometry you can definitely find a faster solution.

Code

fn calculate_wire_path(wire_path: &str) -> HashMap<Point, i32> {
    let mut path = HashMap::new();
    let mut position = Point { x: 0, y: 0 };
    let mut step = 0;
    for command in wire_path.trim().split(',') {
        let direction = command.chars().nth(0).unwrap();
        let value: i32 = command[1..].parse().unwrap();
        let mut position_change = Point { x: 0, y: 0 };
        match direction {
            'L' => position_change = Point { x: -1, y: 0 },
            'R' => position_change = Point { x: 1, y: 0 },
            'U' => position_change = Point { x: 0, y: 1 },
            'D' => position_change = Point { x: 0, y: -1 },
            _ => println!("Unknown direction: {}", direction),
        }

        for _ in 0..value {
            position.add(&position_change);
            step += 1;
            path.insert(position.clone(), step);
        }
    }

    path
}

pub fn part_one(input: &str) -> i32 {
    let lines: Vec<&str> = input.lines().collect();

    let mut path_a = calculate_wire_path(lines[0]);
    let path_b = calculate_wire_path(lines[1]);

    path_a.retain(|k, _| path_b.contains_key(k));

    let intersection = path_a
        .keys()
        .min_by_key(|value| value.manhatten_distance())
        .unwrap();

    intersection.manhatten_distance()
}

pub fn part_two(input: &str) -> i32 {
    let lines: Vec<&str> = input.lines().collect();

    let mut path_a = calculate_wire_path(lines[0]);
    let path_b = calculate_wire_path(lines[1]);

    path_a.retain(|k, _| path_b.contains_key(k));

    let steps = path_a
        .keys()
        .map(|k| path_a.get(k).unwrap() + path_b.get(k).unwrap())
        .min()
        .unwrap();

    steps
}

Benchmarks

2019 - Day 03 - Part 1 time: 36.432385ms
2019 - Day 03 - Part 2 time: 36.0294ms

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