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
|
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 solve(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 main() {
let mut input = String::new();
io::stdin().read_to_string(&mut input).unwrap();
println!("Part 1: {}", solve(input.trim()));
}
#[test]
fn part1() {
assert_eq!("DDRRRD", solve("ihgpwlah"));
assert_eq!("DDUDRLRRUDRD", solve("kglvqrro"));
assert_eq!("DRURDRUDDLLDLUURRDULRLDUUDDDRR", solve("ulqzkmiv"));
}
|