From da115b01ba0749fb8745c1360554bbb18dd56a29 Mon Sep 17 00:00:00 2001 From: June 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') 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 une McEnroe 2018-10-28Add notification with notify-sendJune McEnroe 2018-10-28Use const char *argv[] signaturesJune McEnroe 2018-10-23Fix verbose view name in man pageJune McEnroe 2018-10-22Add more URL schemesJune McEnroe 2018-10-22Rework status lineJune McEnroe 2018-10-22Rename status and verbose tagsJune McEnroe 2018-09-16Revert "Race parallel connects"June McEnroe 2018-09-16Race parallel connectsJune McEnroe 2018-09-15Call tls_error when tls_connect_socket failsJune McEnroe 2018-09-15Try successive getaddrinfo resultsJune McEnroe 2018-09-15Render README from chatte.7June McEnroe 2018-09-14Factor out uiPrompt to call on nick changeJune McEnroe 2018-09-14Run test binaries with set -e and semicolonsJune McEnroe 2018-09-14Fail target when any test binary failsJune McEnroe 2018-09-14Run tests in default targetJune McEnroe 2018-09-14Add termEvent testsJune McEnroe 2018-09-14Check width of entire next word including codesJune McEnroe 2018-09-14Remove word handling from formatParseJune McEnroe 2018-09-14Apply consecutive formatting codes at onceJune McEnroe 2018-09-14Add tests for formatParseJune McEnroe 2018-09-13Preview with nick in input windowJune McEnroe 2018-09-13Never send PRIVMSG to TagStatus or TagVerboseJune McEnroe 2018-09-13Move color selection to format.cJune McEnroe 2018-09-13Fix len for format->split at end of stringJune McEnroe 2018-09-13Avoid uninitialized x in uiReadJune McEnroe 2018-09-13Add IRCDefault to colors enumJune McEnroe 2018-09-13Return a format->split even at the end of the stringJune McEnroe 2018-09-13Fix weird tab-complete after commaJune McEnroe 2018-09-13Rewrite UI againJune McEnroe 2018-09-12Add note about C-oJune McEnroe 2018-09-12Use formatParse split to position input cursorJune McEnroe 2018-09-12Factor out IRC formatting parsingJune McEnroe 2018-09-11Add /help equivalent to /manJune McEnroe 2018-09-11Don't render every PM as a pingJune McEnroe 2018-09-11Add urlOpenMatchJune McEnroe 2018-09-10Depend on man.sh for chroot.tar targetJune McEnroe 2018-09-10Set LESSSECURE=1 in man.shJune McEnroe 2018-09-10Add /man commandJune McEnroe 2018-09-10Install man page in chrootJune McEnroe 2018-09-10Install man pageJune McEnroe 2018-09-10Split keys into subsections and document colorsJune McEnroe 2018-09-10Add "blank" lines to chatte.1June McEnroe 2018-09-10Document key bindings in chatte.1June McEnroe 2018-09-08Document slash commands in chatte.1June McEnroe