- commit
- 9e22a5add8b86c380fce103907feacc79c32e67a
- parent
- fa87a81b2c714d0d9eb99132531cacc174815c74
- Author
- Tobias Bengfort <tobias.bengfort@posteo.de>
- Date
- 2021-12-23 10:17
day 23 first approach
Diffstat
| A | 2021/23/input.txt | 5 | +++++ |
| A | 2021/23/part1.rs | 283 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 2021/23/test.txt | 5 | +++++ |
3 files changed, 293 insertions, 0 deletions
diff --git a/2021/23/input.txt b/2021/23/input.txt
@@ -0,0 +1,5 @@ -1 1 ############# -1 2 #...........# -1 3 ###C#A#B#D### -1 4 #B#A#D#C# -1 5 #########
diff --git a/2021/23/part1.rs b/2021/23/part1.rs
@@ -0,0 +1,283 @@
-1 1 use std::collections::HashMap;
-1 2 use std::env::args;
-1 3 use std::fs::File;
-1 4 use std::io::BufRead;
-1 5 use std::io::BufReader;
-1 6
-1 7 // #############
-1 8 // #10.C.D.E.AB#
-1 9 // ###2#4#6#8###
-1 10 // #3#5#7#9#
-1 11 // #########
-1 12
-1 13
-1 14 fn get_input() -> [u8; 15] {
-1 15 let path = args().nth(1).unwrap();
-1 16 let file = File::open(path).unwrap();
-1 17
-1 18 let mut map = [0; 15];
-1 19 let mut lines = BufReader::new(file).lines();
-1 20
-1 21 assert_eq!(lines.next().unwrap().unwrap(), "#############");
-1 22 assert_eq!(lines.next().unwrap().unwrap(), "#...........#");
-1 23
-1 24 let line = lines.next().unwrap().unwrap();
-1 25 map[2] = match line.chars().nth(3) {
-1 26 Some('A') => 1,
-1 27 Some('B') => 2,
-1 28 Some('C') => 3,
-1 29 Some('D') => 4,
-1 30 _ => unreachable!(),
-1 31 };
-1 32 map[4] = match line.chars().nth(5) {
-1 33 Some('A') => 1,
-1 34 Some('B') => 2,
-1 35 Some('C') => 3,
-1 36 Some('D') => 4,
-1 37 _ => unreachable!(),
-1 38 };
-1 39 map[6] = match line.chars().nth(7) {
-1 40 Some('A') => 1,
-1 41 Some('B') => 2,
-1 42 Some('C') => 3,
-1 43 Some('D') => 4,
-1 44 _ => unreachable!(),
-1 45 };
-1 46 map[8] = match line.chars().nth(9) {
-1 47 Some('A') => 1,
-1 48 Some('B') => 2,
-1 49 Some('C') => 3,
-1 50 Some('D') => 4,
-1 51 _ => unreachable!(),
-1 52 };
-1 53
-1 54 let line = lines.next().unwrap().unwrap();
-1 55 map[3] = match line.chars().nth(3) {
-1 56 Some('A') => 1,
-1 57 Some('B') => 2,
-1 58 Some('C') => 3,
-1 59 Some('D') => 4,
-1 60 _ => unreachable!(),
-1 61 };
-1 62 map[5] = match line.chars().nth(5) {
-1 63 Some('A') => 1,
-1 64 Some('B') => 2,
-1 65 Some('C') => 3,
-1 66 Some('D') => 4,
-1 67 _ => unreachable!(),
-1 68 };
-1 69 map[7] = match line.chars().nth(7) {
-1 70 Some('A') => 1,
-1 71 Some('B') => 2,
-1 72 Some('C') => 3,
-1 73 Some('D') => 4,
-1 74 _ => unreachable!(),
-1 75 };
-1 76 map[9] = match line.chars().nth(9) {
-1 77 Some('A') => 1,
-1 78 Some('B') => 2,
-1 79 Some('C') => 3,
-1 80 Some('D') => 4,
-1 81 _ => unreachable!(),
-1 82 };
-1 83
-1 84 assert_eq!(lines.next().unwrap().unwrap(), " #########");
-1 85
-1 86 return map;
-1 87 }
-1 88
-1 89 fn path_steps(i: usize, j: usize) -> i64 {
-1 90 let (x1, y1): (i64, i64) = match i {
-1 91 0 => (2, 1),
-1 92 1 => (1, 1),
-1 93 2 => (3, 2),
-1 94 3 => (3, 3),
-1 95 4 => (5, 2),
-1 96 5 => (5, 3),
-1 97 6 => (7, 2),
-1 98 7 => (7, 3),
-1 99 8 => (9, 2),
-1 100 9 => (9, 3),
-1 101 10 => (10, 1),
-1 102 11 => (11, 1),
-1 103 12 => (4, 1),
-1 104 13 => (6, 1),
-1 105 14 => (8, 1),
-1 106 _ => unreachable!(),
-1 107 };
-1 108 let (x2, y2): (i64, i64) = match j {
-1 109 0 => (2, 1),
-1 110 1 => (1, 1),
-1 111 2 => (3, 2),
-1 112 3 => (3, 3),
-1 113 4 => (5, 2),
-1 114 5 => (5, 3),
-1 115 6 => (7, 2),
-1 116 7 => (7, 3),
-1 117 8 => (9, 2),
-1 118 9 => (9, 3),
-1 119 10 => (10, 1),
-1 120 11 => (11, 1),
-1 121 12 => (4, 1),
-1 122 13 => (6, 1),
-1 123 14 => (8, 1),
-1 124 _ => unreachable!(),
-1 125 };
-1 126 if x1 == x2 {
-1 127 return (y1 - y2).abs();
-1 128 } else {
-1 129 return (x1 - x2).abs() + (y1 - 1).abs() + (y2 - 1).abs();
-1 130 }
-1 131 }
-1 132
-1 133 fn path_free(map: &[u8; 15], i: usize, j: usize) -> bool {
-1 134 if i < 12 && i % 2 == 1 && map[i - 1] != 0 {
-1 135 return false;
-1 136 }
-1 137
-1 138 // only check i < j; the other case is checked by switching i and j
-1 139 if i < 4 && j >= 4 && j != 12 && map[12] != 0 {
-1 140 return false;
-1 141 }
-1 142 if i < 6 && j >= 6 && j != 12 && j != 13 && map[13] != 0 {
-1 143 return false;
-1 144 }
-1 145 if i < 8 && j >= 6 && j != 12 && j != 13 && j != 14 && map[14] != 0 {
-1 146 return false;
-1 147 }
-1 148
-1 149 if i >= 8 && i < 10 && (j == 12 || j == 13) && map[14] != 0 {
-1 150 return false;
-1 151 }
-1 152 if i >= 6 && i < 10 && j == 12 && map[13] != 0 {
-1 153 return false;
-1 154 }
-1 155
-1 156 return true;
-1 157 }
-1 158
-1 159 fn legal_move(map: &[u8; 15], i: usize, j: usize) -> bool {
-1 160 if map[j] != 0 {
-1 161 return false;
-1 162 }
-1 163
-1 164 // cannot move from hallway to hallway
-1 165 if !(i >= 2 && i < 10) && !(j >= 2 && j < 10) {
-1 166 return false;
-1 167 }
-1 168
-1 169 // only move into own room
-1 170 if j >= 2 && j < 10 && usize::from(map[i]) != j / 2 {
-1 171 return false;
-1 172 }
-1 173
-1 174 // only move inside if other occupant is same type
-1 175 if (j == 2 || j == 4 || j == 6 || j == 8) && usize::from(map[j + 1]) != j / 2 {
-1 176 return false;
-1 177 }
-1 178
-1 179 // PERF: do not move away from a final position
-1 180 if (i == 3 || i == 5 || i == 7 || i == 9) && usize::from(map[i]) == i / 2 {
-1 181 return false;
-1 182 }
-1 183 if (i == 2 || i == 4 || i == 6 || i == 8) && usize::from(map[i]) == i / 2 && map[i + 1] == map[i] {
-1 184 return false;
-1 185 }
-1 186
-1 187 if !path_free(map, i, j) || !path_free(map, j, i) {
-1 188 return false;
-1 189 }
-1 190
-1 191 return true;
-1 192 }
-1 193
-1 194 fn map_score(map: &[u8; 15]) -> i64 {
-1 195 // lower bound for required energy
-1 196 let mut score = 0;
-1 197 for i in 0..15 {
-1 198 if map[i] != 0 {
-1 199 let j = usize::from(map[i]) * 2;
-1 200 if i != j + 1 {
-1 201 score += path_steps(i, j) * 10i64.pow(u32::from(map[i]) - 1);
-1 202 }
-1 203 }
-1 204 }
-1 205 return score;
-1 206 }
-1 207
-1 208 fn i2c(i: u8) -> char {
-1 209 match i {
-1 210 0 => '.',
-1 211 1 => 'A',
-1 212 2 => 'B',
-1 213 3 => 'C',
-1 214 4 => 'D',
-1 215 _ => unreachable!(),
-1 216 }
-1 217 }
-1 218
-1 219 fn print_map(map: &[u8; 15]) {
-1 220 println!("#############");
-1 221 println!("#{}{}.{}.{}.{}.{}{}#", i2c(map[1]), i2c(map[0]), i2c(map[12]), i2c(map[13]), i2c(map[14]), i2c(map[10]), i2c(map[11]));
-1 222 println!("###{}#{}#{}#{}###", i2c(map[2]), i2c(map[4]), i2c(map[6]), i2c(map[8]));
-1 223 println!(" #{}#{}#{}#{}#", i2c(map[3]), i2c(map[5]), i2c(map[7]), i2c(map[9]));
-1 224 println!(" #########");
-1 225 }
-1 226
-1 227 fn main() {
-1 228 let initial = get_input();
-1 229 let target = [0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 0, 0, 0, 0, 0];
-1 230 let mut queue = vec![];
-1 231 let mut energies = HashMap::new();
-1 232 let mut lower_bounds = HashMap::new();
-1 233
-1 234 queue.push(initial);
-1 235 energies.insert(initial, 0);
-1 236 lower_bounds.insert(initial, 0);
-1 237
-1 238 while queue.len() > 0 {
-1 239 let map = queue.remove(0);
-1 240 // println!("{} {} {:?}", queue.len(), energies.len(), energies.get(&target));
-1 241 // print_map(&map);
-1 242 for i in 0..15 {
-1 243 if map[i] != 0 {
-1 244 for j in 0..15 {
-1 245 if legal_move(&map, i, j) {
-1 246 let mut m = map.clone();
-1 247 m[j] = map[i];
-1 248 m[i] = 0;
-1 249 let e_prev = energies.get(&map).unwrap();
-1 250 let e_new = path_steps(i, j) * 10i64.pow(u32::from(map[i]) - 1);
-1 251 let e = e_prev + e_new;
-1 252 match energies.get(&m) {
-1 253 None => {
-1 254 energies.insert(m, e);
-1 255 lower_bounds.insert(m, e + map_score(&m));
-1 256 queue.push(m);
-1 257 },
-1 258 Some(e_old) => {
-1 259 if e < *e_old {
-1 260 // print_map(&map);
-1 261 // print_map(&m);
-1 262 // println!("{}", e_new);
-1 263 energies.insert(m, e);
-1 264 lower_bounds.insert(m, e + map_score(&m));
-1 265 queue.push(m);
-1 266 }
-1 267 },
-1 268 }
-1 269 }
-1 270 }
-1 271 }
-1 272 }
-1 273 match energies.get(&target) {
-1 274 Some(e) => {
-1 275 queue = queue.into_iter().filter(|map| lower_bounds.get(map).unwrap() <= e).collect();
-1 276 },
-1 277 None => {},
-1 278 }
-1 279 queue.sort_by_key(|map| -(energies.get(map).unwrap() + map_score(map)));
-1 280 }
-1 281
-1 282 println!("{}", energies.get(&target).unwrap());
-1 283 }
diff --git a/2021/23/test.txt b/2021/23/test.txt
@@ -0,0 +1,5 @@ -1 1 ############# -1 2 #...........# -1 3 ###B#C#B#D### -1 4 #A#D#C#A# -1 5 #########