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

aoc/year2019/
day03.rs
