aoc/year2019/
day03.rs

1//! # Crossed Wires
2//!
3//! The input follow some implicit rules that can be used to simplify our approach:
4//!
5//! * Wires cross only at right angles to each other, so we only need to consider horizontal lines
6//!   when moving vertically and vice-versa.
7//! * There is only a single vertical line at a given x coordinates and vice-versa.
8//!
9//! This makes [`BTreeMap`] a great choice to store horizontal or vertical line segments as there
10//! are no collisions. The [`range`] method can lookup all line segments contained between two
11//! coordinates to check for intersections.
12//!
13//! First we build two maps, one vertical and one horizontal, of each line segment for the first
14//! wire. Then we trace the steps of the second wire, looking for any intersections. We calculate
15//! both part one and part two at the same time, by also including the distance so far
16//! from the starting point of each lines.
17//!
18//! [`range`]: BTreeMap::range
19use crate::util::parse::*;
20use crate::util::point::*;
21use std::collections::BTreeMap;
22
23type Input = (i32, i32);
24
25struct Line {
26    start: Point,
27    end: Point,
28    distance: i32,
29}
30
31pub fn parse(input: &str) -> Input {
32    // Map a line into an iterator of direction and distance pairs.
33    let lines: Vec<_> = input.lines().collect();
34    let steps = |i: usize| {
35        let first = lines[i].bytes().filter(u8::is_ascii_alphabetic);
36        let second = lines[i].iter_signed::<i32>();
37        first.zip(second)
38    };
39
40    // Build two maps, one for vertical segments and one for horizontal.
41    let mut start = ORIGIN;
42    let mut distance = 0;
43    let mut vertical = BTreeMap::new();
44    let mut horizontal = BTreeMap::new();
45
46    for (direction, amount) in steps(0) {
47        let delta = Point::from(direction);
48        let end = start + delta * amount;
49        let line = Line { start, end, distance };
50
51        if start.x == end.x {
52            vertical.insert(start.x, line);
53        } else {
54            horizontal.insert(start.y, line);
55        }
56
57        start = end;
58        distance += amount;
59    }
60
61    // Trace the steps of the second wire, checking for intersections.
62    let mut start = ORIGIN;
63    let mut distance = 0;
64    let mut manhattan = i32::MAX;
65    let mut delay = i32::MAX;
66
67    for (direction, amount) in steps(1) {
68        let delta = Point::from(direction);
69        let end = start + delta * amount;
70
71        // Use a block to scope the `update` lamdbas mutable borrow of `distance`.
72        {
73            // Checks for intersections, ignoring the initial intersection at the origin.
74            let mut update = |line: &Line, candidate: Point| {
75                if candidate.manhattan(line.start) < line.end.manhattan(line.start)
76                    && candidate.signum(line.start) == line.end.signum(line.start)
77                    && candidate.manhattan(ORIGIN) > 0
78                {
79                    manhattan = manhattan.min(candidate.manhattan(ORIGIN));
80                    delay = delay.min(
81                        distance
82                            + candidate.manhattan(start)
83                            + line.distance
84                            + candidate.manhattan(line.start),
85                    );
86                }
87            };
88
89            // BTreeMaps are sorted and can return all key/value pairs in a range.
90            match direction {
91                b'U' => {
92                    for (&y, line) in horizontal.range(end.y..=start.y) {
93                        update(line, Point::new(start.x, y));
94                    }
95                }
96                b'D' => {
97                    for (&y, line) in horizontal.range(start.y..=end.y) {
98                        update(line, Point::new(start.x, y));
99                    }
100                }
101                b'L' => {
102                    for (&x, line) in vertical.range(end.x..=start.x) {
103                        update(line, Point::new(x, start.y));
104                    }
105                }
106                b'R' => {
107                    for (&x, line) in vertical.range(start.x..=end.x) {
108                        update(line, Point::new(x, start.y));
109                    }
110                }
111                _ => unreachable!(),
112            }
113        }
114
115        start = end;
116        distance += amount;
117    }
118
119    (manhattan, delay)
120}
121
122pub fn part1(input: &Input) -> i32 {
123    input.0
124}
125
126pub fn part2(input: &Input) -> i32 {
127    input.1
128}
aoc/year2019/day03.rs

aoc/year2019/
day03.rs
