aoc/year2019/
day03.rs

1//! # Crossed Wires
2//!
3//! The input follows 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 coordinate 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 line.
17//!
18//! [`range`]: BTreeMap::range
19use crate::util::integer::*;
20use crate::util::parse::*;
21use crate::util::point::*;
22use std::collections::BTreeMap;
23
24type Input = (i32, i32);
25
26struct Line {
27    start: Point,
28    end: Point,
29    distance: i32,
30}
31
32pub fn parse(input: &str) -> Input {
33    // Map a line into an iterator of direction and distance pairs.
34    let lines: Vec<_> = input.lines().collect();
35    let steps = |i: usize| {
36        let first = lines[i].bytes().filter(u8::is_ascii_alphabetic);
37        let second = lines[i].iter_signed::<i32>();
38        first.zip(second)
39    };
40
41    // Build two maps, one for vertical segments and one for horizontal.
42    let mut start = ORIGIN;
43    let mut distance = 0;
44    let mut vertical = BTreeMap::new();
45    let mut horizontal = BTreeMap::new();
46
47    for (direction, amount) in steps(0) {
48        let delta = Point::from(direction);
49        let end = start + delta * amount;
50        let line = Line { start, end, distance };
51
52        if start.x == end.x {
53            vertical.insert(start.x, line);
54        } else {
55            horizontal.insert(start.y, line);
56        }
57
58        start = end;
59        distance += amount;
60    }
61
62    // Trace the steps of the second wire, checking for intersections.
63    let mut start = ORIGIN;
64    let mut distance = 0;
65    let mut manhattan = i32::MAX;
66    let mut delay = i32::MAX;
67
68    for (direction, amount) in steps(1) {
69        let delta = Point::from(direction);
70        let end = start + delta * amount;
71
72        // Checks for intersections, ignoring the initial intersection at the origin.
73        let mut update = |line: &Line, candidate: Point| {
74            if candidate.manhattan(line.start) < line.end.manhattan(line.start)
75                && candidate.signum(line.start) == line.end.signum(line.start)
76                && candidate.manhattan(ORIGIN) > 0
77            {
78                manhattan = manhattan.min(candidate.manhattan(ORIGIN));
79                delay = delay.min(
80                    distance
81                        + candidate.manhattan(start)
82                        + line.distance
83                        + candidate.manhattan(line.start),
84                );
85            }
86        };
87
88        // BTreeMaps are sorted and can return all key/value pairs in a range.
89        if start.x == end.x {
90            let (lo, hi) = start.y.minmax(end.y);
91            for (&y, line) in horizontal.range(lo..=hi) {
92                update(line, Point::new(start.x, y));
93            }
94        } else {
95            let (lo, hi) = start.x.minmax(end.x);
96            for (&x, line) in vertical.range(lo..=hi) {
97                update(line, Point::new(x, start.y));
98            }
99        }
100
101        start = end;
102        distance += amount;
103    }
104
105    (manhattan, delay)
106}
107
108pub fn part1(input: &Input) -> i32 {
109    input.0
110}
111
112pub fn part2(input: &Input) -> i32 {
113    input.1
114}
aoc/year2019/day03.rs

aoc/year2019/
day03.rs
