diff options
Diffstat (limited to '2016/aoc17')
-rw-r--r-- | 2016/aoc17/Cargo.lock | 14 | ||||
-rw-r--r-- | 2016/aoc17/Cargo.toml | 7 | ||||
-rw-r--r-- | 2016/aoc17/src/main.rs | 98 |
3 files changed, 119 insertions, 0 deletions
diff --git a/2016/aoc17/Cargo.lock b/2016/aoc17/Cargo.lock new file mode 100644 index 0000000..488e59b --- /dev/null +++ b/2016/aoc17/Cargo.lock @@ -0,0 +1,14 @@ +[root] +name = "aoc17" +version = "0.1.0" +dependencies = [ + "md5 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "md5" +version = "0.2.1" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[metadata] +"checksum md5 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)" = "7df230903ccdffd6b3b4ec21624498ea64c912ce50297846907f0b8e1bb249dd" diff --git a/2016/aoc17/Cargo.toml b/2016/aoc17/Cargo.toml new file mode 100644 index 0000000..88c211c --- /dev/null +++ b/2016/aoc17/Cargo.toml @@ -0,0 +1,7 @@ +[package] +name = "aoc17" +version = "0.1.0" +authors = ["Justin Worthe <justin.worthe@gmail.com>"] + +[dependencies] +md5 = "^0.2"
\ No newline at end of file diff --git a/2016/aoc17/src/main.rs b/2016/aoc17/src/main.rs new file mode 100644 index 0000000..77fdf2e --- /dev/null +++ b/2016/aoc17/src/main.rs @@ -0,0 +1,98 @@ +extern crate md5; + +#[derive(Clone)] +struct State { + input: String, + path: String, + x: i8, + y: i8 +} + +impl State { + fn open_directions(&self) -> Vec<(char, i8, i8)> { + let hash_input = format!("{}{}", self.input, self.path); + let hash = md5::compute(hash_input.into_bytes().as_slice()); + + let mut results = Vec::new(); + if hash[0]/16 > 10 && self.y > 0 { + results.push(('U', 0, -1)); + } + if hash[0]%16 > 10 && self.y < 3 { + results.push(('D', 0, 1)); + } + if hash[1]/16 > 10 && self.x > 0 { + results.push(('L', -1, 0)); + } + if hash[1]%16 > 10 && self.x < 3 { + results.push(('R', 1, 0)); + } + + results + } + + fn next_states(&self) -> Vec<State> { + self.open_directions().iter() + .map(|&(dir, dx, dy)| State { + input: self.input.clone(), + path: { + let mut p = self.path.clone(); + p.push(dir); + p + }, + x: self.x + dx, + y: self.y + dy + }).collect() + } + + fn is_final(&self) -> bool { + self.x == 3 && self.y == 3 + } +} + +fn main() { + let initial = State { + input: "lpvhkcbi".to_string(), + path: String::new(), + x: 0, + y: 0 + }; + + let final_state = find_final_state(initial.clone()); + let longest_path = find_longest_path(initial); + + println!("Final State Path: {}", final_state.path); + println!("Longest Path: {}", longest_path); +} + +fn find_final_state(initial: State) -> State { + let mut states = vec!(initial); + + loop { + match states.iter().find(|s| s.is_final()) { + Some(final_state) => {return final_state.clone();}, + None => {} + }; + + states = states.iter().flat_map(|s| s.next_states()).collect(); + } +} + +fn find_longest_path(initial: State) -> u32 { + let mut states = vec!(initial); + let mut current_longest = 0; + + while states.len() > 0 { + + match states.iter().find(|s| s.is_final()) { + Some(final_state) => {current_longest = final_state.path.len() as u32;}, + None => {} + }; + + states = states.iter() + .filter(|s| !s.is_final()) + .flat_map(|s| s.next_states()) + .collect(); + } + + current_longest +} |