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