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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
|
use std::io;
use std::io::BufRead;
use std::iter;
use std::collections::HashMap;
const DO_COMPARE_GRIDS: bool = true;
fn parse_ch(c: char) -> u8 {
match c {
'.' => 0,
'|' => 1,
'#' => 2,
_ => unreachable!(),
}
}
fn res_value(grid: &Vec<Vec<u8>>) -> i32 {
let mut num1 = 0;
let mut num2 = 0;
for row in grid {
for cell in row {
num1 += (*cell == 1) as i32;
num2 += (*cell == 2) as i32;
}
}
return num1 * num2;
}
fn compute_step(grid: &Vec<Vec<u8>>, grid2: &mut Vec<Vec<u8>>) -> u64 {
let mut hash: u64 = 0;
let mut rotating_shift = 0;
for y in 1..grid.len()-1 {
for x in 1..grid[0].len()-1 {
let mut tots = [0, 0, 0];
for dy in -1..2 {
for dx in -1..2 {
if dy == 0 && dx == 0 { continue; }
tots[grid[(y as isize + dy) as usize][(x as isize + dx) as usize] as usize] += 1;
}
}
let v = match (grid[y][x], tots[0], tots[1], tots[2]) {
(0, _, n, _) if n >= 3 => 1,
(1, _, _, n) if n >= 3 => 2,
(2, _, n, m) if n >= 1 && m >= 1 => 2,
(2, _, _, _) => 0,
(v, _, _, _) => v,
};
grid2[y][x] = v;
hash ^= u64::from(v) << rotating_shift | (tots[0] ^ tots[1] ^ tots[2]) << rotating_shift;
rotating_shift = (rotating_shift + 1) % 64;
}
}
hash
}
fn grid_equal(grid1: &Vec<Vec<u8>>, grid2: &Vec<Vec<u8>>) -> bool {
for (row1, row2) in grid1.iter().zip(grid2.iter()) {
for (&v1, &v2) in row1.iter().zip(row2.iter()) {
if v1 != v2 {
return false;
}
}
}
true
}
fn simulate(mut grid: Vec<Vec<u8>>, nsteps: usize) -> i32 {
let mut grid2 = grid.clone();
let mut hash_vals = Vec::new();
let mut res_vals = Vec::new();
let mut res_map = HashMap::new();
let mut cycle = None;
for step in 0..nsteps {
let hash = compute_step(&grid, &mut grid2);
std::mem::swap(&mut grid, &mut grid2);
hash_vals.push(hash);
let res = res_value(&grid);
res_vals.push(res);
if let Some((cycle_start, cycle_length, ref start_grid)) = cycle {
if step - cycle_start == cycle_length {
if !DO_COMPARE_GRIDS || grid_equal(&grid, &start_grid) {
// println!("Check at {}: grids equal", step);
return res_vals[cycle_start + (nsteps - 1 - cycle_start) % cycle_length];
} else {
println!("Grids not equal");
cycle = None;
}
}
} else if let Some(&prev_step) = res_map.get(&res) {
let length = step - prev_step;
if prev_step >= length {
if (0..length).all(|i| hash_vals[prev_step - i] == hash_vals[step - i]
&& res_vals[prev_step - i] == res_vals[step - i]) {
// println!("cycle: {} length={}", step, length);
cycle = Some((step, length, if DO_COMPARE_GRIDS { grid.clone() } else { Vec::new() }));
}
}
}
res_map.insert(res, step);
}
res_value(&grid)
}
pub fn main<T: BufRead>(reader: T) -> io::Result<(String, String)> {
let mut grid = {
iter::once(vec![0; 0])
.chain(reader.lines().map(|l|
iter::once(0)
.chain(l.unwrap().chars().map(|c| parse_ch(c)))
.chain(iter::once(0)).collect()
))
.chain(iter::once(vec![0; 0]))
.collect::<Vec<Vec<_>>>()
};
let w = grid[1].len();
let h = grid.len();
grid[0].resize(w, 0);
grid[h-1].resize(w, 0);
let part1 = simulate(grid.clone(), 10);
let part2 = simulate(grid, 1000000000);
Ok((part1.to_string(), part2.to_string()))
}
|
