1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158

//! # Day 1: No Time for a Taxicab
//!
//! Santa's sleigh uses a very high-precision clock to guide its movements, and the clock's
//! oscillator is regulated by stars. Unfortunately, the stars have been stolen... by the Easter
//! Bunny. To save Christmas, Santa needs you to retrieve all **fifty stars** by December 25th.
//!
//! Collect stars by solving puzzles. Two puzzles will be made available on each day in the Advent
//! calendar; the second puzzle is unlocked when you complete the first. Each puzzle grants **one
//! star**. Good luck!
//!
//! You're airdropped near **Easter Bunny Headquarters** in a city somewhere. "Near", unfortunately,
//! is as close as you can get - the instructions on the Easter Bunny Recruiting Document the Elves
//! intercepted start here, and nobody had time to work them out further.
//!
//! The Document indicates that you should start at the given coordinates (where you just landed)
//! and face North. Then, follow the provided sequence: either turn left (`L`) or right (`R`) 90
//! degrees, then walk forward the given number of blocks, ending at a new intersection.
//!
//! There's no time to follow such ridiculous instructions on foot, though, so you take a moment and
//! work out the destination. Given that you can only walk on the [street grid of the city], how far
//! is the shortest path to the destination?
//!
//! For example:
//!
//! - Following `R2, L3` leaves you `2` blocks East and `3` blocks North, or `5` blocks away.
//! - `R2, R2, R2` leaves you `2` blocks due South of your starting position, which is `2` blocks
//!   away.
//! - `R5, L5, R5, R3` leaves you `12` blocks away.
//!
//! **How many blocks away** is Easter Bunny HQ?
//!
//! [street grid of the city]: https://en.wikipedia.org/wiki/Taxicab_geometry
//!
//! ## Part Two
//!
//! Then, you notice the instructions continue on the back of the Recruiting Document. Easter Bunny
//! HQ is actually at the first location you visit twice.
//!
//! For example, if your instructions are `R8, R4, R4, R8`, the first location you visit twice is
//! `4` blocks away, due East.
//!
//! How many blocks away is the **first location you visit twice?**

use std::collections::HashSet;

use anyhow::{bail, Context, Result};

pub const INPUT: &str = include_str!("d01.txt");

pub fn solve_part_one(input: &str) -> Result<i32> {
    let instructions = parse_input(input)?;
    let mut direction = Direction::North;
    let mut position = (0, 0);

    for (turn, steps) in instructions {
        direction = direction.turn(turn);
        position = match direction {
            Direction::North => (position.0, position.1 - steps),
            Direction::East => (position.0 + steps, position.1),
            Direction::South => (position.0, position.1 + steps),
            Direction::West => (position.0 - steps, position.1),
        }
    }

    Ok(position.0.abs() + position.1.abs())
}

pub fn solve_part_two(input: &str) -> Result<i32> {
    let instructions = parse_input(input)?;
    let mut direction = Direction::North;
    let mut position = (0, 0);
    let mut history = HashSet::new();

    for (turn, steps) in instructions {
        direction = direction.turn(turn);
        let stepper: fn((i32, i32)) -> (i32, i32) = match direction {
            Direction::North => |p| (p.0, p.1 - 1),
            Direction::East => |p| (p.0 + 1, p.1),
            Direction::South => |p| (p.0, p.1 + 1),
            Direction::West => |p| (p.0 - 1, p.1),
        };

        for _ in 0..steps {
            position = stepper(position);
            if history.contains(&position) {
                return Ok(position.0.abs() + position.1.abs());
            } else {
                history.insert(position);
            }
        }
    }

    bail!("no location visited twice")
}

fn parse_input(input: &str) -> Result<Vec<(Turn, i32)>> {
    input
        .lines()
        .next()
        .context("input is empty")?
        .split(", ")
        .map(|instruction| {
            let direction = match instruction.chars().next() {
                Some('L') => Turn::Left,
                Some('R') => Turn::Right,
                Some(s) => bail!("invalid direction `{}`", s),
                None => bail!("missing direction"),
            };
            let steps = instruction[1..].parse().context("invalid steps number")?;

            Ok((direction, steps))
        })
        .collect()
}

#[derive(Clone, Copy)]
enum Turn {
    Left,
    Right,
}

#[derive(Clone, Copy)]
enum Direction {
    North,
    East,
    South,
    West,
}

impl Direction {
    fn turn(self, turn: Turn) -> Self {
        match turn {
            Turn::Left => match self {
                Self::North => Self::West,
                Self::East => Self::North,
                Self::South => Self::East,
                Self::West => Self::South,
            },
            Turn::Right => match self {
                Self::North => Self::East,
                Self::East => Self::South,
                Self::South => Self::West,
                Self::West => Self::North,
            },
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn part_one() {}

    #[test]
    fn part_two() {}
}