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
|
extern crate crypto;
use std::collections::VecDeque;
use std::io::{self, Read};
use crypto::digest::Digest;
use crypto::md5::Md5;
#[derive(Clone, Copy)]
enum Direction {
Up,
Down,
Left,
Right,
}
const DIRECTIONS: &'static [Direction] = &[
Direction::Up,
Direction::Down,
Direction::Left,
Direction::Right,
];
impl From<Direction> for char {
fn from(direction: Direction) -> Self {
match direction {
Direction::Up => 'U',
Direction::Down => 'D',
Direction::Left => 'L',
Direction::Right => 'R',
}
}
}
#[derive(Default, Clone, Copy)]
struct Room {
x: u8,
y: u8,
}
impl Room {
fn neighbor(self, direction: Direction) -> Option<Room> {
match direction {
Direction::Up if self.y != 0 => Some(Room { x: self.x, y: self.y - 1 }),
Direction::Down if self.y != 3 => Some(Room { x: self.x, y: self.y + 1 }),
Direction::Left if self.x != 0 => Some(Room { x: self.x - 1, y: self.y }),
Direction::Right if self.x != 3 => Some(Room { x: self.x + 1, y: self.y }),
_ => None,
}
}
fn is_vault(self) -> bool {
self.x == 3 && self.y == 3
}
}
#[derive(Default, Clone)]
struct State {
room: Room,
path: Vec<Direction>,
}
impl<'a> From<&'a State> for String {
fn from(state: &'a State) -> String {
state.path.iter().cloned().map(char::from).collect()
}
}
impl State {
fn is_vault(&self) -> bool {
self.room.is_vault()
}
fn generate_states(&self, states: &mut VecDeque<State>, passcode: &str) {
let mut md5 = Md5::new();
md5.input_str(passcode);
md5.input_str(&String::from(self));
let hash = md5.result_str();
for (direction, ch) in DIRECTIONS.iter().cloned().zip(hash.chars()) {
if ch < 'b' || ch > 'f' { continue }
let room = match self.room.neighbor(direction) {
Some(r) => r,
None => continue,
};
let mut path = self.path.clone();
path.push(direction);
states.push_back(State { room: room, path: path });
}
}
}
fn solve1(passcode: &str) -> String {
let mut states = VecDeque::new();
states.push_back(State::default());
while let Some(state) = states.pop_front() {
if state.is_vault() {
return String::from(&state);
}
state.generate_states(&mut states, passcode);
}
panic!("no path to vault")
}
fn solve2(passcode: &str) -> usize {
let mut states = VecDeque::new();
states.push_back(State::default());
let mut longest = None;
while let Some(state) = states.pop_front() {
if state.is_vault() {
longest = Some(state.clone());
} else {
state.generate_states(&mut states, passcode);
}
}
longest.unwrap().path.len()
}
fn main() {
let mut input = String::new();
io::stdin().read_to_string(&mut input).unwrap();
println!("Part 1: {}", solve1(input.trim()));
println!("Part 2: {}", solve2(input.trim()));
}
#[test]
fn part1() {
assert_eq!("DDRRRD", solve1("ihgpwlah"));
assert_eq!("DDUDRLRRUDRD", solve1("kglvqrro"));
assert_eq!("DRURDRUDDLLDLUURRDULRLDUUDDDRR", solve1("ulqzkmiv"));
}
#[test]
#[ignore]
fn part2() {
assert_eq!(370, solve2("ihgpwlah"));
assert_eq!(492, solve2("kglvqrro"));
assert_eq!(830, solve2("ulqzkmiv"));
}
|