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    // Map a line into an iterator of direction and distance pairs.
35    let lines: Vec<_> = input.lines().collect();
36    let steps = |i: usize| {
37        let first = lines[i].bytes().filter(u8::is_ascii_alphabetic);
38        let second = lines[i].iter_signed::<i32>();
39        first.zip(second)
40    };
41
42    // Build two maps, one for vertical segments and one for horizontal.
43    let mut start = ORIGIN;
44    let mut distance = 0;
45    let mut vertical = BTreeMap::new();
46    let mut horizontal = BTreeMap::new();
47
48    for (direction, amount) in steps(0) {
49        let delta = Point::from(direction);
50        let end = start + delta * amount;
51        let line = Line { start, end, distance };
52
53        if start.x == end.x {
54            vertical.insert(start.x, line);
55        } else {
56            horizontal.insert(start.y, line);
57        }
58
59        start = end;
60        distance += amount;
61    }
62
63    // Trace the steps of the second wire, checking for intersections.
64    let mut start = ORIGIN;
65    let mut distance = 0;
66    let mut manhattan = i32::MAX;
67    let mut delay = i32::MAX;
68
69    for (direction, amount) in steps(1) {
70        let delta = Point::from(direction);
71        let end = start + delta * amount;
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                && signum(candidate, line.start) == signum(line.end, 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        if start.x == end.x {
91            let (lo, hi) = start.y.minmax(end.y);
92            for (&y, line) in horizontal.range(lo..=hi) {
93                update(line, Point::new(start.x, y));
94            }
95        } else {
96            let (lo, hi) = start.x.minmax(end.x);
97            for (&x, line) in vertical.range(lo..=hi) {
98                update(line, Point::new(x, start.y));
99            }
100        }
101
102        start = end;
103        distance += amount;
104    }
105
106    (manhattan, delay)
107}
108
109pub fn part1(input: &Input) -> i32 {
110    input.0
111}
112
113pub fn part2(input: &Input) -> i32 {
114    input.1
115}
116
117fn signum(a: Point, b: Point) -> Point {
118    Point::new((a.x - b.x).signum(), (a.y - b.y).signum())
119}
aoc/year2019/day03.rs

aoc/year2019/
day03.rs
