aoc/year2016/
day01.rs

1//! # No Time for a Taxicab
2//!
3//! The solution is short as it leverages two utility modules,
4//! [`parse`] for extracting integers from surrounding text and [`point`] for two-dimensional
5//! rotations and translations.
6//!
7//! For part two, it is faster to remember line segments and check for intersections than
8//! to store information on every intermediate point visited.
9//!
10//! [`parse`]: crate::util::parse
11//! [`point`]: crate::util::point
12use crate::util::integer::*;
13use crate::util::parse::*;
14use crate::util::point::*;
15
16type Pair = (u8, i32);
17
18// Represent the line segment between two points.
19struct Segment {
20    x1: i32,
21    x2: i32,
22    y1: i32,
23    y2: i32,
24}
25
26impl Segment {
27    fn new(first: Point, second: Point) -> Self {
28        let (x1, x2) = first.x.minmax(second.x);
29        let (y1, y2) = first.y.minmax(second.y);
30        Segment { x1, x2, y1, y2 }
31    }
32
33    // Return the point of intersection between two orthogonal segments, if there is one.
34    fn intersects(&self, other: &Segment) -> Option<Point> {
35        let overlap = other.x2 >= self.x1
36            && other.x1 <= self.x2
37            && other.y2 >= self.y1
38            && other.y1 <= self.y2;
39        overlap.then_some(Point::new(self.x1.max(other.x1), self.y1.max(other.y1)))
40    }
41}
42
43pub fn parse(input: &str) -> Vec<Pair> {
44    let first = input.bytes().filter(u8::is_ascii_uppercase);
45    let second = input.iter_signed();
46    first.zip(second).collect()
47}
48
49pub fn part1(input: &[Pair]) -> i32 {
50    let mut position = ORIGIN;
51    let mut direction = UP;
52
53    for &(turn, amount) in input {
54        direction =
55            if turn == b'L' { direction.counter_clockwise() } else { direction.clockwise() };
56        position += direction * amount;
57    }
58
59    position.manhattan(ORIGIN)
60}
61
62pub fn part2(input: &[Pair]) -> i32 {
63    let mut position = ORIGIN;
64    let mut direction = UP;
65    // Store two lists of segments, one for each orthogonal direction.
66    let mut this_axis = Vec::with_capacity(input.len() / 2);
67    let mut other_axis = Vec::with_capacity(input.len() / 2);
68
69    for &(turn, amount) in input {
70        direction =
71            if turn == b'L' { direction.counter_clockwise() } else { direction.clockwise() };
72        let target = position + direction * amount;
73        // Exclude the current location from the next segment to track.
74        let segment = Segment::new(position + direction, target);
75
76        for other in &other_axis {
77            if let Some(point) = segment.intersects(other) {
78                return point.manhattan(ORIGIN);
79            }
80        }
81        this_axis.push(segment);
82        (this_axis, other_axis, position) = (other_axis, this_axis, target);
83    }
84
85    unreachable!()
86}
aoc/year2016/day01.rs

aoc/year2016/
day01.rs
