AOC17
[advent-of-code-2016.git] / aoc17 / src / main.rs
1 extern crate md5;
2
3 #[derive(Clone)]
4 struct State {
5     input: String,
6     path: String,
7     x: i8,
8     y: i8
9 }
10
11 impl State {
12     fn open_directions(&self) -> Vec<(char, i8, i8)> {
13         let hash_input = format!("{}{}", self.input, self.path);
14         let hash = md5::compute(hash_input.into_bytes().as_slice());
15
16         let mut results = Vec::new();
17         if hash[0]/16 > 10 && self.y > 0 {
18             results.push(('U', 0, -1));
19         }
20         if hash[0]%16 > 10 && self.y < 3 {
21             results.push(('D', 0, 1));
22         }
23         if hash[1]/16 > 10 && self.x > 0 {
24             results.push(('L', -1, 0));
25         }
26         if hash[1]%16 > 10 && self.x < 3 {
27             results.push(('R', 1, 0));
28         }
29         
30         results
31     }
32
33     fn next_states(&self) -> Vec<State> {
34         self.open_directions().iter()
35             .map(|&(dir, dx, dy)| State {
36                 input: self.input.clone(),
37                 path: {
38                     let mut p = self.path.clone();
39                     p.push(dir);
40                     p
41                 },
42                 x: self.x + dx,
43                 y: self.y + dy
44             }).collect()
45     }
46
47     fn is_final(&self) -> bool {
48         self.x == 3 && self.y == 3
49     }
50 }
51
52 fn main() {
53     let initial = State {
54         input: "lpvhkcbi".to_string(),
55         path: String::new(),
56         x: 0,
57         y: 0
58     };
59
60     let final_state = find_final_state(initial.clone());
61     let longest_path = find_longest_path(initial);
62     
63     println!("Final State Path: {}", final_state.path);
64     println!("Longest Path: {}", longest_path);
65 }
66
67 fn find_final_state(initial: State) -> State {
68     let mut states = vec!(initial);
69     
70     loop {
71         match states.iter().find(|s| s.is_final()) {
72             Some(final_state) => {return final_state.clone();},
73             None => {}
74         };
75
76         states = states.iter().flat_map(|s| s.next_states()).collect();
77     }
78 }
79
80 fn find_longest_path(initial: State) -> u32 {
81     let mut states = vec!(initial);
82     let mut current_longest = 0;
83
84     while states.len() > 0 {
85         
86         match states.iter().find(|s| s.is_final()) {
87             Some(final_state) => {current_longest = final_state.path.len() as u32;},
88             None => {}
89         };
90
91         states = states.iter()
92             .filter(|s| !s.is_final())
93             .flat_map(|s| s.next_states())
94             .collect();
95     }
96
97     current_longest
98 }