From da115b01ba0749fb8745c1360554bbb18dd56a29 Mon Sep 17 00:00:00 2001 From: June McEnroe Date: Sun, 18 Dec 2016 14:47:19 -0500 Subject: Day 17 --- input/day17.txt | 1 + src/bin/day17.rs | 122 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 123 insertions(+) create mode 100644 input/day17.txt create mode 100644 src/bin/day17.rs diff --git a/input/day17.txt b/input/day17.txt new file mode 100644 index 0000000..a6386c1 --- /dev/null +++ b/input/day17.txt @@ -0,0 +1 @@ +qzthpkfp 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 n>Explicitly set stdout line buffered when pagingJune McEnroe 2020-05-21Do not sort results in scoop by defaultJune McEnroe 2020-05-21Expand and clarify documentationJune McEnroe 2020-05-21Execute PAGER with the SHELLJune McEnroe 2020-05-21Automatically perform database migrations in litterboxJune McEnroe 2020-05-20Don't install rc scripts on other platformsJune McEnroe 2020-05-20Rewrite build and install like pounce 1.3June McEnroe 2020-05-20Update email addressesJune McEnroe 2020-04-23Call updateConsumer from handleError 1.2p1June McEnroe 2020-04-20Use . as ${LDLIBS.$@} separatorJune McEnroe 2020-04-05Error on invalid ISUPPORT values 1.2June McEnroe 2020-04-05Only set RCS on FreeBSDJune McEnroe 2020-04-05Log bans and unbansJune McEnroe 2020-04-05Parse mode types from ISUPPORTJune McEnroe 2020-04-05Add unscoop matchers for ban/unban eventsJune McEnroe 2020-04-05Check unscoop regexps with make testJune McEnroe 2020-04-05Add unscoop -n flag for checking regexpsJune McEnroe 2020-04-05Add Ban and Unban event typesJune McEnroe 2020-04-02Update styleJune McEnroe 2020-03-31Update unscoop catgirl matchersJune McEnroe 2020-03-31Fix writing verbose to stderrJune McEnroe 2020-03-02Include <>/-/* around nicks in scoop coloring 1.1June McEnroe 2020-03-02Replace .mk files with configure scriptJune McEnroe 2020-02-28Implement the causal.agency/consumer capabilityJune McEnroe 2020-02-22Include <>/-/* around nicks in coloringJune McEnroe 2020-02-22Use (almost) the full range of IRC colors for nicksJune McEnroe