aoc/year2016/
day01.rs

1//! # No Time for a Taxicab
2//!
3//! The solution is short as it leverages two utility classes,
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 =
36            !(other.x2 < self.x1 || other.x1 > self.x2 || other.y2 < self.y1 || other.y1 > self.y2);
37        overlap.then_some(Point::new(self.x1.max(other.x1), self.y1.max(other.y1)))
38    }
39}
40
41pub fn parse(input: &str) -> Vec<Pair> {
42    let first = input.bytes().filter(u8::is_ascii_uppercase);
43    let second = input.iter_signed();
44    first.zip(second).collect()
45}
46
47pub fn part1(input: &[Pair]) -> i32 {
48    let mut position = ORIGIN;
49    let mut direction = UP;
50
51    for &(turn, amount) in input {
52        direction =
53            if turn == b'L' { direction.counter_clockwise() } else { direction.clockwise() };
54        position += direction * amount;
55    }
56
57    position.manhattan(ORIGIN)
58}
59
60pub fn part2(input: &[Pair]) -> i32 {
61    let mut position = ORIGIN;
62    let mut direction = UP;
63    // Store two lists of segments, one for each orthogonal direction.
64    let mut this_axis = Vec::with_capacity(input.len() / 2);
65    let mut other_axis = Vec::with_capacity(input.len() / 2);
66
67    for &(turn, amount) in input {
68        direction =
69            if turn == b'L' { direction.counter_clockwise() } else { direction.clockwise() };
70        let target = position + direction * amount;
71        // Exclude the current location from the next segment to track.
72        let segment = Segment::new(position + direction, target);
73
74        for other in &other_axis {
75            if let Some(point) = segment.intersects(other) {
76                return point.manhattan(ORIGIN);
77            }
78        }
79        this_axis.push(segment);
80        (this_axis, other_axis, position) = (other_axis, this_axis, target);
81    }
82
83    unreachable!()
84}
aoc/year2016/day01.rs

aoc/year2016/
day01.rs
