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
|
use std::collections::{HashMap, HashSet};
const DIRECTIONS: [[(i64, i64); 3]; 4] = [
[(-1, 0), (-1, 1), (-1, -1)],
[(1, 0), (1, 1), (1, -1)],
[(0, -1), (1, -1), (-1, -1)],
[(0, 1), (1, 1), (-1, 1)]
];
pub fn read_from_stdin() -> (Vec<(i64, i64)>, HashMap<(i64, i64), usize>) {
let mut v = vec![];
let mut lookup = HashMap::new();
let mut line = String::new();
let mut i = 0;
while std::io::stdin().read_line(&mut line).unwrap() > 0 {
let bytes = line.as_bytes();
for j in 0..bytes.len() {
if bytes[j] == b'#' {
lookup.insert((i, j as i64), v.len());
v.push((i, j as i64));
}
}
i += 1;
line.clear();
}
(v, lookup)
}
pub fn free_around(e: (i64, i64), m: &HashMap<(i64, i64), usize>) -> bool {
for d in [
(-1, -1), (-1, 0), (-1, 1),
( 0, -1), ( 0, 1),
( 1, -1), ( 1, 0), ( 1, 1)
] {
if m.contains_key(&(e.0 + d.0, e.1 + d.1)) { return false; }
}
true
}
pub fn play(
elves: &mut Vec<(i64, i64)>,
lookup: &mut HashMap<(i64, i64), usize>,
nturns: usize
) -> Option<usize> {
let mut claimed = HashMap::<(i64, i64), usize>::new();
let mut stopped = HashSet::<(i64, i64)>::new();
for t in 0..nturns {
// First half
for i in 0..elves.len() {
let e = elves[i];
if free_around(e, &lookup) { continue; }
for j in 0..4 {
let d = DIRECTIONS[(t+j)%4].iter()
.map(|x| (e.0+x.0, e.1+x.1))
.collect::<Vec<_>>();
if !lookup.contains_key(&d[0]) &&
!lookup.contains_key(&d[1]) &&
!lookup.contains_key(&d[2])
{
if claimed.contains_key(&d[0]) { stopped.insert(d[0]); }
claimed.insert(d[0], i);
break;
}
}
}
// Second half
let mut any_moved = false;
for (moveto, i) in &claimed {
if stopped.contains(&moveto) { continue; }
any_moved = true;
lookup.remove(&elves[*i]);
elves[*i] = *moveto;
lookup.insert(elves[*i], *i);
}
if !any_moved { return Some(t); }
// Cleanup
claimed.clear();
stopped.clear();
}
None
}
|
