main.rs (4213B)
1 use std::collections::{HashMap, HashSet};
2
3 #[derive(Debug, Clone, Copy)]
4 enum Dir {
5 North,
6 South,
7 West,
8 East,
9 }
10
11 impl Dir {
12 fn next(&self) -> Self {
13 match self {
14 Self::North => Self::South,
15 Self::South => Self::West,
16 Self::West => Self::East,
17 Self::East => Self::North,
18 }
19 }
20
21 fn can_move(
22 &self,
23 elf: &(i32, i32),
24 elves: &HashMap<(i32, i32), (i32, i32)>,
25 ) -> Option<(i32, i32)> {
26 let (t1, t2, t3) = match self {
27 Self::North => (
28 (elf.0 - 1, elf.1 + 1),
29 (elf.0, elf.1 + 1),
30 (elf.0 + 1, elf.1 + 1),
31 ),
32 Self::South => (
33 (elf.0 - 1, elf.1 - 1),
34 (elf.0, elf.1 - 1),
35 (elf.0 + 1, elf.1 - 1),
36 ),
37 Self::West => (
38 (elf.0 - 1, elf.1 - 1),
39 (elf.0 - 1, elf.1),
40 (elf.0 - 1, elf.1 + 1),
41 ),
42 Self::East => (
43 (elf.0 + 1, elf.1 + 1),
44 (elf.0 + 1, elf.1),
45 (elf.0 + 1, elf.1 - 1),
46 ),
47 };
48 if elves.contains_key(&t1) || elves.contains_key(&t2) || elves.contains_key(&t3) {
49 None
50 } else {
51 Some(t2)
52 }
53 }
54 }
55
56 fn main() {
57 let input = std::fs::read_to_string("input.txt")
58 .unwrap()
59 .trim()
60 .split('\n')
61 .map(|s| s.to_string())
62 .collect::<Vec<String>>();
63 // 4138
64 println!("Part 1: {}", part_1(&input, Some(10)));
65 // 1010
66 println!("Part 2: {}", part_1(&input, None));
67 }
68
69 fn can_stop(elf: &(i32, i32), elves: &HashMap<(i32, i32), (i32, i32)>) -> bool {
70 for dx in -1..=1 {
71 for dy in -1..=1 {
72 if dx != 0 || dy != 0 {
73 if elves.contains_key(&(elf.0 + dx, elf.1 + dy)) {
74 return false;
75 }
76 }
77 }
78 }
79 true
80 }
81
82 fn part_1(input: &Vec<String>, round_limit: Option<i32>) -> i32 {
83 let elves_init = {
84 let mut tmp = HashMap::new();
85 for (j, s) in input.iter().enumerate() {
86 for (i, c) in s.chars().enumerate() {
87 if c == '#' {
88 tmp.insert((i as i32, -(j as i32)), (i as i32, -(j as i32)));
89 }
90 }
91 }
92 tmp
93 };
94 let mut elves_curr = elves_init.clone();
95 let mut dir_curr = Dir::North;
96 let mut round = 0;
97 loop {
98 let mut elves_next = HashMap::new();
99 let mut proposed = HashSet::new();
100 for &e in elves_curr.keys() {
101 let mut target = e;
102 if !can_stop(&e, &elves_curr) {
103 for dir in [
104 dir_curr,
105 dir_curr.next(),
106 dir_curr.next().next(),
107 dir_curr.next().next().next(),
108 ] {
109 if let Some(t) = dir.can_move(&e, &elves_curr) {
110 target = t;
111 break;
112 }
113 }
114 }
115 if proposed.contains(&target) {
116 if let Some(&prev) = elves_next.get(&target) {
117 elves_next.remove(&target);
118 elves_next.insert(prev, prev);
119 }
120 elves_next.insert(e, e);
121 } else {
122 elves_next.insert(target, e);
123 }
124 proposed.insert(target);
125 }
126 dir_curr = dir_curr.next();
127 elves_curr = elves_next;
128 round += 1;
129 if elves_curr.iter().all(|(k, v)| k == v) {
130 break;
131 }
132 if let Some(limit) = round_limit {
133 if round >= limit {
134 break;
135 }
136 }
137 }
138 let x_min = elves_curr.keys().map(|(x, _)| x).min().unwrap();
139 let x_max = elves_curr.keys().map(|(x, _)| x).max().unwrap();
140 let y_min = elves_curr.keys().map(|(_, y)| y).min().unwrap();
141 let y_max = elves_curr.keys().map(|(_, y)| y).max().unwrap();
142 if round_limit.is_some() {
143 (x_max - x_min + 1) * (y_max - y_min + 1) - elves_curr.len() as i32
144 } else {
145 round
146 }
147 }