year2019/
day03.rs

1use utils::geometry::{Direction, Vec2};
2use utils::prelude::*;
3
4/// Finding path intersections.
5///
6/// This solution assumes that intersections only occur between perpendicular segments.
7#[derive(Clone, Debug)]
8pub struct Day03 {
9    part1: u32,
10    part2: u32,
11}
12
13#[derive(Clone, Debug)]
14struct Segment {
15    min: Vec2<i32>,
16    max: Vec2<i32>,
17    start: Vec2<i32>,
18    start_steps: u32,
19}
20
21impl Day03 {
22    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
23        let [(mut wire1h, mut wire1v), (wire2h, wire2v)] = parser::byte_map!(
24            b'U' => Direction::Up,
25            b'R' => Direction::Right,
26            b'D' => Direction::Down,
27            b'L' => Direction::Left
28        )
29        .then(parser::u16())
30        .repeat_fold(
31            b',',
32            1,
33            (Vec::new(), Vec::new(), Vec2::ORIGIN, 0u32),
34            |(mut horizontal, mut vertical, start, steps), (dir, dist)| {
35                let end = start + Vec2::from(dir) * dist as i32;
36                let segment = Segment {
37                    min: start.component_min(end),
38                    max: start.component_max(end),
39                    start,
40                    start_steps: steps,
41                };
42                if matches!(dir, Direction::Left | Direction::Right) {
43                    horizontal.push(segment);
44                } else {
45                    vertical.push(segment);
46                }
47                (horizontal, vertical, end, steps + dist as u32)
48            },
49        )
50        .map(|(horizontal, vertical, _, _)| (horizontal, vertical))
51        .repeat_n(parser::eol())
52        .parse_complete(input)?;
53
54        wire1h.sort_unstable_by_key(|s| s.min.y);
55        wire1v.sort_unstable_by_key(|s| s.min.x);
56
57        let (mut part1, mut part2) = (u32::MAX, u32::MAX);
58        let mut check = |horizontal: &Segment, vertical: &Segment| {
59            let intersection = Vec2::new(vertical.min.x, horizontal.min.y);
60            if intersection.x >= horizontal.min.x
61                && intersection.x <= horizontal.max.x
62                && intersection.y >= vertical.min.y
63                && intersection.y <= vertical.max.y
64                && intersection != Vec2::ORIGIN
65            {
66                part1 = part1.min(intersection.manhattan_distance());
67
68                let h_steps = horizontal.start_steps + horizontal.start.x.abs_diff(intersection.x);
69                let v_steps = vertical.start_steps + vertical.start.y.abs_diff(intersection.y);
70                part2 = part2.min(h_steps + v_steps);
71            }
72        };
73
74        for horizontal in wire2h.iter() {
75            for vertical in wire1v
76                .iter()
77                .skip(wire1v.partition_point(|s| s.min.x < horizontal.min.x))
78                .take_while(|s| s.min.x <= horizontal.max.x)
79            {
80                check(horizontal, vertical);
81            }
82        }
83        for vertical in wire2v.iter() {
84            for horizontal in wire1h
85                .iter()
86                .skip(wire1h.partition_point(|s| s.min.y < vertical.min.y))
87                .take_while(|s| s.min.y <= vertical.max.y)
88            {
89                check(horizontal, vertical);
90            }
91        }
92
93        Ok(Self { part1, part2 })
94    }
95
96    #[must_use]
97    pub fn part1(&self) -> u32 {
98        self.part1
99    }
100
101    #[must_use]
102    pub fn part2(&self) -> u32 {
103        self.part2
104    }
105}
106
107examples!(Day03 -> (u32, u32) [
108    {
109        input: "R8,U5,L5,D3\nU7,R6,D4,L4",
110        part1: 6,
111        part2: 30,
112    },
113    {
114        input: "R75,D30,R83,U83,L12,D49,R71,U7,L72\nU62,R66,U55,R34,D71,R55,D58,R83",
115        part1: 159,
116        part2: 610,
117    },
118    {
119        input: "R98,U47,R26,D63,R33,U87,L62,D20,R33,U53,R51\nU98,R91,D20,R16,D67,R40,U7,R15,U6,R7",
120        part1: 135,
121        part2: 410,
122    },
123]);
year2019/day03.rs

year2019/
day03.rs
