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        // Checks for intersections, ignoring the initial intersection at the origin.
72        let mut update = |line: &Line, candidate: Point| {
73            if candidate.manhattan(line.start) < line.end.manhattan(line.start)
74                && candidate.signum(line.start) == line.end.signum(line.start)
75                && candidate.manhattan(ORIGIN) > 0
76            {
77                manhattan = manhattan.min(candidate.manhattan(ORIGIN));
78                delay = delay.min(
79                    distance
80                        + candidate.manhattan(start)
81                        + line.distance
82                        + candidate.manhattan(line.start),
83                );
84            }
85        };
86
87        // BTreeMaps are sorted and can return all key/value pairs in a range.
88        match direction {
89            b'U' => {
90                for (&y, line) in horizontal.range(end.y..=start.y) {
91                    update(line, Point::new(start.x, y));
92                }
93            }
94            b'D' => {
95                for (&y, line) in horizontal.range(start.y..=end.y) {
96                    update(line, Point::new(start.x, y));
97                }
98            }
99            b'L' => {
100                for (&x, line) in vertical.range(end.x..=start.x) {
101                    update(line, Point::new(x, start.y));
102                }
103            }
104            b'R' => {
105                for (&x, line) in vertical.range(start.x..=end.x) {
106                    update(line, Point::new(x, start.y));
107                }
108            }
109            _ => unreachable!(),
110        }
111
112        start = end;
113        distance += amount;
114    }
115
116    (manhattan, delay)
117}
118
119pub fn part1(input: &Input) -> i32 {
120    input.0
121}
122
123pub fn part2(input: &Input) -> i32 {
124    input.1
125}
aoc/year2019/day03.rs

aoc/year2019/
day03.rs
