- commit
- fada144f3d89c89b86a9b8df04e0053ebd22b1ff
- parent
- 47fe721a55f6a72468ec12d9ed90cb4235b4cde7
- Author
- Tobias Bengfort <tobias.bengfort@posteo.de>
- Date
- 2021-12-23 15:07
day 23 part 2
Diffstat
| A | 2021/23/input2.txt | 7 | +++++++ |
| A | 2021/23/part2.rs | 259 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 2021/23/test2.txt | 7 | +++++++ |
3 files changed, 273 insertions, 0 deletions
diff --git a/2021/23/input2.txt b/2021/23/input2.txt
@@ -0,0 +1,7 @@ -1 1 ############# -1 2 #...........# -1 3 ###C#A#B#D### -1 4 #D#C#B#A# -1 5 #D#B#A#C# -1 6 #B#A#D#C# -1 7 #########
diff --git a/2021/23/part2.rs b/2021/23/part2.rs
@@ -0,0 +1,259 @@
-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 const LEN: usize = 23;
-1 8
-1 9 // #############
-1 10 // #01.2.3.4.56#
-1 11 // ###7#8#9#0###
-1 12 // #1#2#3#4#
-1 13 // #5#6#7#8#
-1 14 // #9#0#1#2#
-1 15 // #########
-1 16
-1 17 fn i2xy(i: usize) -> (i64, i64) {
-1 18 match i {
-1 19 0 => (1, 1),
-1 20 1 => (2, 1),
-1 21 2 => (4, 1),
-1 22 3 => (6, 1),
-1 23 4 => (8, 1),
-1 24 5 => (10, 1),
-1 25 6 => (11, 1),
-1 26 7 => (3, 2),
-1 27 8 => (5, 2),
-1 28 9 => (7, 2),
-1 29 10 => (9, 2),
-1 30 11 => (3, 3),
-1 31 12 => (5, 3),
-1 32 13 => (7, 3),
-1 33 14 => (9, 3),
-1 34 15 => (3, 4),
-1 35 16 => (5, 4),
-1 36 17 => (7, 4),
-1 37 18 => (9, 4),
-1 38 19 => (3, 5),
-1 39 20 => (5, 5),
-1 40 21 => (7, 5),
-1 41 22 => (9, 5),
-1 42 _ => unreachable!(),
-1 43 }
-1 44 }
-1 45
-1 46 fn xy2i(x: i64, y: i64) -> Option<usize> {
-1 47 match (x, y) {
-1 48 (1, 1) => Some(0),
-1 49 (2, 1) => Some(1),
-1 50 (4, 1) => Some(2),
-1 51 (6, 1) => Some(3),
-1 52 (8, 1) => Some(4),
-1 53 (10, 1) => Some(5),
-1 54 (11, 1) => Some(6),
-1 55 (3, 2) => Some(7),
-1 56 (5, 2) => Some(8),
-1 57 (7, 2) => Some(9),
-1 58 (9, 2) => Some(10),
-1 59 (3, 3) => Some(11),
-1 60 (5, 3) => Some(12),
-1 61 (7, 3) => Some(13),
-1 62 (9, 3) => Some(14),
-1 63 (3, 4) => Some(15),
-1 64 (5, 4) => Some(16),
-1 65 (7, 4) => Some(17),
-1 66 (9, 4) => Some(18),
-1 67 (3, 5) => Some(19),
-1 68 (5, 5) => Some(20),
-1 69 (7, 5) => Some(21),
-1 70 (9, 5) => Some(22),
-1 71 _ => None,
-1 72 }
-1 73 }
-1 74
-1 75 fn path_steps(i: usize, j: usize) -> i64 {
-1 76 let (x1, y1) = i2xy(i);
-1 77 let (x2, y2) = i2xy(j);
-1 78 if x1 == x2 {
-1 79 return (y1 - y2).abs();
-1 80 } else {
-1 81 return (x1 - x2).abs() + (y1 - 1).abs() + (y2 - 1).abs();
-1 82 }
-1 83 }
-1 84
-1 85 fn path_free(map: &[u8; LEN], i: usize, j: usize) -> bool {
-1 86 let (x1, y1) = i2xy(i);
-1 87 let (x2, y2) = i2xy(j);
-1 88
-1 89 for y in 2..y1 {
-1 90 if map[xy2i(x1, y).unwrap()] != 0 {
-1 91 return false;
-1 92 }
-1 93 }
-1 94 for y in 2..y2 {
-1 95 if map[xy2i(x2, y).unwrap()] != 0 {
-1 96 return false;
-1 97 }
-1 98 }
-1 99
-1 100 let (x_min, x_max) = if x1 < x2 {(x1, x2)} else {(x2, x1)};
-1 101 for x in x_min+1..x_max {
-1 102 match xy2i(x, 1) {
-1 103 Some(a) => if map[a] != 0 {
-1 104 return false;
-1 105 },
-1 106 None => {},
-1 107 }
-1 108 }
-1 109
-1 110 return true
-1 111 }
-1 112
-1 113 fn is_final_position(map: &[u8; LEN], c: u8, x: i64, y: i64) -> bool {
-1 114 if y == 1 {
-1 115 return false;
-1 116 }
-1 117 if x / 2 != i64::from(c) {
-1 118 return false;
-1 119 }
-1 120 for yy in y+1.. {
-1 121 match xy2i(x, yy) {
-1 122 Some(a) => if map[a] != c {
-1 123 return false;
-1 124 },
-1 125 None => break,
-1 126 }
-1 127 }
-1 128 return true;
-1 129 }
-1 130
-1 131 fn legal_move(map: &[u8; LEN], i: usize, j: usize) -> bool {
-1 132 if map[j] != 0 {
-1 133 return false;
-1 134 }
-1 135
-1 136 let (x1, y1) = i2xy(i);
-1 137 let (x2, y2) = i2xy(j);
-1 138
-1 139 // cannot move from hallway to hallway
-1 140 if y1 == 1 && y2 == 1 {
-1 141 return false;
-1 142 }
-1 143
-1 144 if y2 > 1 && !is_final_position(map, map[i], x2, y2) {
-1 145 return false;
-1 146 }
-1 147
-1 148 if is_final_position(map, map[i], x1, y1) {
-1 149 return false;
-1 150 }
-1 151
-1 152 if !path_free(map, i, j) {
-1 153 return false;
-1 154 }
-1 155
-1 156 return true;
-1 157 }
-1 158
-1 159 fn get_input() -> ([u8; LEN], [u8; LEN]) {
-1 160 let path = args().nth(1).unwrap();
-1 161 let file = File::open(path).unwrap();
-1 162
-1 163 let mut map = [0; LEN];
-1 164 let mut target = [0; LEN];
-1 165
-1 166 for (y, line) in BufReader::new(file).lines().enumerate() {
-1 167 for (x, c) in line.unwrap().chars().enumerate() {
-1 168 match (xy2i(x as i64, y as i64), c) {
-1 169 (Some(i), 'A') => map[i] = 1,
-1 170 (Some(i), 'B') => map[i] = 2,
-1 171 (Some(i), 'C') => map[i] = 3,
-1 172 (Some(i), 'D') => map[i] = 4,
-1 173 _ => {},
-1 174 }
-1 175 }
-1 176 }
-1 177
-1 178 for c in 1..=4 {
-1 179 for y in 2.. {
-1 180 match xy2i(c * 2 + 1, y) {
-1 181 Some(i) => target[i] = c as u8,
-1 182 None => break,
-1 183 }
-1 184 }
-1 185 }
-1 186
-1 187 return (map, target);
-1 188 }
-1 189
-1 190 fn legal_steps(map: &[u8; LEN]) -> Vec<([u8; LEN], i64)> {
-1 191 let mut steps = vec![];
-1 192 for i in 0..LEN {
-1 193 if map[i] != 0 {
-1 194 for j in 0..LEN {
-1 195 if legal_move(&map, i, j) {
-1 196 let mut m = map.clone();
-1 197 m[j] = map[i];
-1 198 m[i] = 0;
-1 199 let e = path_steps(i, j) * 10i64.pow(u32::from(map[i]) - 1);
-1 200 steps.push((m, e));
-1 201 }
-1 202 }
-1 203 }
-1 204 }
-1 205 return steps;
-1 206 }
-1 207
-1 208 fn estimate(map: &[u8; LEN]) -> i64 {
-1 209 // lower bound for required energy
-1 210 let mut required = 0;
-1 211 for i in 0..LEN {
-1 212 let (x, y) = i2xy(i);
-1 213 if map[i] != 0 && !is_final_position(map, map[i], x, y) {
-1 214 let j = xy2i(i64::from(map[i]) * 2 + 1, 2).unwrap();
-1 215 required += path_steps(i, j) * 10i64.pow(u32::from(map[i]) - 1);
-1 216 }
-1 217 }
-1 218 return required;
-1 219 }
-1 220
-1 221 fn better(a: i64, b: Option<&i64>) -> bool {
-1 222 match b {
-1 223 Some(bb) => a < *bb,
-1 224 None => true,
-1 225 }
-1 226 }
-1 227
-1 228 fn main() {
-1 229 let (initial, target) = get_input();
-1 230 let mut queue = vec![];
-1 231 let mut energies = HashMap::new();
-1 232 let mut estimates = HashMap::new();
-1 233
-1 234 queue.push(initial);
-1 235 energies.insert(initial, 0);
-1 236 estimates.insert(initial, 0);
-1 237
-1 238 while queue.len() > 0 {
-1 239 let map = queue.remove(0);
-1 240 for (m, e_new) in legal_steps(&map) {
-1 241 let e = e_new + energies.get(&map).unwrap();
-1 242 let ee = e + estimate(&m);
-1 243 if better(e, energies.get(&m)) && better(ee, energies.get(&target)) {
-1 244 energies.insert(m, e);
-1 245 estimates.insert(m, ee);
-1 246 if m == target {
-1 247 queue = queue.into_iter().filter(|map| *estimates.get(map).unwrap() < e).collect();
-1 248 } else {
-1 249 match queue.binary_search_by_key(&ee, |map| *estimates.get(map).unwrap()) {
-1 250 Ok(i) => queue.insert(i, m),
-1 251 Err(i) => queue.insert(i, m),
-1 252 }
-1 253 }
-1 254 }
-1 255 }
-1 256 }
-1 257
-1 258 println!("{}", energies.get(&target).unwrap());
-1 259 }
diff --git a/2021/23/test2.txt b/2021/23/test2.txt
@@ -0,0 +1,7 @@ -1 1 ############# -1 2 #...........# -1 3 ###B#C#B#D### -1 4 #D#C#B#A# -1 5 #D#B#A#C# -1 6 #A#D#C#A# -1 7 #########