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
|
use std::collections::VecDeque;
fn is_space(seed: usize, (x, y): (usize, usize)) -> bool {
let sum = x*x + 3*x + 2*x*y + y + y*y + seed;
let bin = format!("{:#b}", sum);
bin.matches('1').count() % 2 == 0
}
fn solve_puzzle(seed: usize, part1_goal: (usize, usize), part2_limit: usize) -> (usize, usize) {
let mut part1_found = false;
let mut part1_depth = 0;
let mut part2_count = 1;
// Breadth-first search of the maze
let start = (1, 1);
let mut visited = vec![start];
let mut queue = VecDeque::from([(start, 0)]);
loop {
let (pos, depth) = queue.pop_front().unwrap();
// Is this the shortest path to `part1_goal'?
if pos == part1_goal && !part1_found {
part1_found = true;
part1_depth = depth;
}
// Have we found all the information we want?
if depth > part2_limit && part1_found {
return (part1_depth, part2_count);
}
// The grid extends infinitely far in the positive directions
let mut adjacents = vec![
(pos.0 + 1, pos.1),
(pos.0, pos.1 + 1),
];
if pos.0 > 0 {
adjacents.push((pos.0 - 1, pos.1));
}
if pos.1 > 0 {
adjacents.push((pos.0, pos.1 - 1));
}
for adj in adjacents {
// Is this a valid move to a space we haven't visited before?
if is_space(seed, adj) && !visited.contains(&adj) {
visited.push(adj);
queue.push_back((adj, depth + 1));
// Count locations reachable in at most `part2_limit' steps
if depth < part2_limit {
part2_count += 1;
}
}
}
}
}
fn main() {
// My personal puzzle input
let seed = 1358;
let (part1, part2) = solve_puzzle(seed, (31, 39), 50);
// Part 1 gives 96 for me
println!("Part 1 solution: {}", part1);
// Part 2 gives 141 for me
println!("Part 2 solution: {}", part2);
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn part1_example1() {
assert_eq!(solve_puzzle(10, (7, 4), 42).0, 11);
}
}
|
