1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
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
}
|
