summaryrefslogtreecommitdiff
path: root/2016/aoc17/src
diff options
context:
space:
mode:
Diffstat (limited to '2016/aoc17/src')
-rw-r--r--2016/aoc17/src/main.rs98
1 files changed, 98 insertions, 0 deletions
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
+}