From 4a15c2b72208798472932d03a8cd9603ab7bf0d2 Mon Sep 17 00:00:00 2001 From: Curtis McEnroe Date: Sun, 18 Dec 2016 14:47:19 -0500 Subject: Day 17 --- src/bin/day17.rs | 122 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 122 insertions(+) create mode 100644 src/bin/day17.rs (limited to 'src/bin') diff --git a/src/bin/day17.rs b/src/bin/day17.rs new file mode 100644 index 0000000..a80cbb8 --- /dev/null +++ b/src/bin/day17.rs @@ -0,0 +1,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 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 { + 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, +} + +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, 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")); +} -- cgit 1.4.1