main.rs
1 use memoize::memoize; 2 use std::collections::HashSet; 3 4 #[derive(PartialEq, Eq, Clone, Copy, Debug, Hash)] 5 enum NumTile { 6 Number(u8), 7 A, 8 Empty, 9 } 10 11 #[derive(PartialEq, Eq, Hash, Clone, Copy)] 12 enum ArrowTile { 13 Up, 14 Down, 15 Left, 16 Right, 17 A, 18 } 19 20 impl std::fmt::Debug for ArrowTile { 21 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { 22 match self { 23 ArrowTile::Up => write!(f, "^"), 24 ArrowTile::Down => write!(f, "v"), 25 ArrowTile::Left => write!(f, "<"), 26 ArrowTile::Right => write!(f, ">"), 27 ArrowTile::A => write!(f, "A"), 28 } 29 } 30 } 31 32 const MAX_DEPTH: u8 = 25; 33 34 fn main() { 35 let input = std::str::from_utf8(include_bytes!("input")) 36 .unwrap() 37 .lines() 38 .map(|l| { 39 l.chars() 40 .map(|c| match c { 41 '0' => NumTile::Number(0), 42 '1' => NumTile::Number(1), 43 '2' => NumTile::Number(2), 44 '3' => NumTile::Number(3), 45 '4' => NumTile::Number(4), 46 '5' => NumTile::Number(5), 47 '6' => NumTile::Number(6), 48 '7' => NumTile::Number(7), 49 '8' => NumTile::Number(8), 50 '9' => NumTile::Number(9), 51 'A' => NumTile::A, 52 c => todo!("{c}"), 53 }) 54 .collect::<Vec<NumTile>>() 55 }) 56 .collect::<Vec<Vec<NumTile>>>(); 57 let slices = input 58 .iter() 59 .map(|v| v.as_slice()) 60 .collect::<Vec<&[NumTile]>>(); 61 let num_map = vec![ 62 vec![NumTile::Number(7), NumTile::Number(8), NumTile::Number(9)], 63 vec![NumTile::Number(4), NumTile::Number(5), NumTile::Number(6)], 64 vec![NumTile::Number(1), NumTile::Number(2), NumTile::Number(3)], 65 vec![NumTile::Empty, NumTile::Number(0), NumTile::A], 66 ]; 67 // let mut const_num_distances = HashMap::new(); 68 // for (y, line) in num_map.iter().enumerate() { 69 // for (x, tile) in line.iter().enumerate() { 70 // const_num_distances.insert((x, y), get_all_paths(&num_map, (x as i32, y as i32))); 71 // } 72 // } 73 let mut values = vec![]; 74 for slice in &slices { 75 let numpad_robot_paths = solve_rec_numpad(&num_map, slice, 2, 3, 6).unwrap(); 76 //println!("{numpad_robot_paths:?}"); 77 let mut arrow_robot_paths = HashSet::new(); 78 for path in numpad_robot_paths { 79 // println!("{path:?}"); 80 let mut sum = 0; 81 sum += count(path[0], 2, 0, 2); 82 for (i, tile) in path[1..].iter().enumerate() { 83 let (x, y) = match path[i] { 84 ArrowTile::Up => (1, 0), 85 ArrowTile::A => (2, 0), 86 ArrowTile::Left => (0, 1), 87 ArrowTile::Down => (1, 1), 88 ArrowTile::Right => (2, 1), 89 }; 90 sum += count(*tile, x, y, 2); 91 } 92 arrow_robot_paths.insert(sum); 93 // println!("total : {sum}") 94 } 95 let shortest_path = arrow_robot_paths.iter().min().unwrap_or(&0); 96 //println!("{values:?}, path={a:?}, len={}", shortest_path.len()); 97 values.push(*shortest_path); 98 } 99 let mut sum = 0; 100 for (i, value) in values.iter().enumerate() { 101 sum += std::str::from_utf8(include_bytes!("input")) 102 .unwrap() 103 .lines() 104 .collect::<Vec<&str>>()[i][..3] 105 .parse::<u128>() 106 .unwrap() 107 * *value; 108 } 109 // println!("{values:?}"); 110 println!("Part 1 : {sum}"); 111 //assert_eq!(sum, 157230); 112 // println!("\x1bc"); 113 let mut values = vec![]; 114 for slice in &slices { 115 // println!("{slice:?}"); 116 let numpad_robot_paths = solve_rec_numpad(&num_map, slice, 2, 3, 6).unwrap(); 117 //println!("{numpad_robot_paths:?}"); 118 let mut arrow_robot_paths = HashSet::new(); 119 for path in numpad_robot_paths { 120 // println!("{path:?}"); 121 let mut sum = 0; 122 sum += count(path[0], 2, 0, MAX_DEPTH); 123 for (i, tile) in path[1..].iter().enumerate() { 124 // println!("{i}"); 125 let (x, y) = match path[i] { 126 ArrowTile::Up => (1, 0), 127 ArrowTile::A => (2, 0), 128 ArrowTile::Left => (0, 1), 129 ArrowTile::Down => (1, 1), 130 ArrowTile::Right => (2, 1), 131 }; 132 sum += count(*tile, x, y, MAX_DEPTH); 133 } 134 arrow_robot_paths.insert(sum); 135 // println!("total : {sum}") 136 } 137 let shortest_path = arrow_robot_paths.iter().min().unwrap_or(&0); 138 //println!("{values:?}, path={a:?}, len={}", shortest_path.len()); 139 values.push(*shortest_path); 140 } 141 let mut sum = 0; 142 for (i, value) in values.iter().enumerate() { 143 sum += std::str::from_utf8(include_bytes!("input")) 144 .unwrap() 145 .lines() 146 .collect::<Vec<&str>>()[i][..3] 147 .parse::<u128>() 148 .unwrap() 149 * *value; 150 } 151 // println!("{values:?}"); 152 println!("Part 2 : {sum}"); 153 } 154 155 #[memoize] 156 fn count(want: ArrowTile, comes_from_x: i32, comes_from_y: i32, depth: u8) -> u128 { 157 if let (Some(paths), _, _) = paths_from_to(want, comes_from_x, comes_from_y) { 158 let mut hs = HashSet::new(); 159 if depth == 1 { 160 let ret = paths.iter().next().unwrap().len(); 161 // println!( 162 // "{:<1$}Call want {want:?}, comes_from_x ({comes_from_x}, {comes_from_y}), depth={depth}, ret={ret}", 163 // "", 164 // ((MAX_DEPTH - depth) * 2) as usize 165 // ); 166 // println!( 167 // "{:^1$} -> ret {2}", 168 // "", 169 // ((MAX_DEPTH - depth) * 2) as usize, 170 // ret 171 // ); 172 return ret as u128; 173 } 174 for path in paths { 175 // println!( 176 // "{:<1$}Call want {want:?}, comes_from_x ({comes_from_x}, {comes_from_y}), depth={depth}, path={path:?}", 177 // "", 178 // ((MAX_DEPTH - depth) * 2) as usize 179 // ); 180 let mut sum = 0; 181 sum += count(path[0], 2, 0, depth - 1); 182 for (i, tile) in path[1..].iter().enumerate() { 183 let (x, y) = match path[i] { 184 ArrowTile::Up => (1, 0), 185 ArrowTile::A => (2, 0), 186 ArrowTile::Left => (0, 1), 187 ArrowTile::Down => (1, 1), 188 ArrowTile::Right => (2, 1), 189 }; 190 sum += count(*tile, x, y, depth - 1); 191 } 192 // println!("{:^1$}-> ret {sum}", "", ((MAX_DEPTH - depth) * 2) as usize); 193 hs.insert(sum); 194 } 195 let shortest = hs.iter().min().unwrap_or(&u128::MAX); 196 return *shortest; 197 } else { 198 todo!(); 199 } 200 } 201 202 #[memoize] 203 fn paths_from_to(want: ArrowTile, x: i32, y: i32) -> (Option<HashSet<Vec<ArrowTile>>>, i32, i32) { 204 let mut hs = HashSet::new(); 205 let (_x, _y) = match want { 206 ArrowTile::Up => (1, 0), 207 ArrowTile::A => (2, 0), 208 ArrowTile::Left => (0, 1), 209 ArrowTile::Down => (1, 1), 210 ArrowTile::Right => (2, 1), 211 }; 212 match want { 213 ArrowTile::Up => match (x, y) { 214 // (0, 0) => hs.insert(vec![ArrowTile::Right, ArrowTile::A]), 215 (1, 0) => hs.insert(vec![ArrowTile::A]), 216 (2, 0) => hs.insert(vec![ArrowTile::Left, ArrowTile::A]), 217 (0, 1) => { 218 hs.insert(vec![ArrowTile::Right, ArrowTile::Up, ArrowTile::A]) 219 // ; 220 // hs.insert(vec![ArrowTile::Up, ArrowTile::Right, ArrowTile::A]) 221 } 222 (1, 1) => hs.insert(vec![ArrowTile::Up, ArrowTile::A]), 223 (2, 1) => { 224 hs.insert(vec![ArrowTile::Left, ArrowTile::Up, ArrowTile::A]); 225 hs.insert(vec![ArrowTile::Up, ArrowTile::Left, ArrowTile::A]) 226 } 227 (_, _) => todo!(), 228 }, 229 ArrowTile::Down => match (x, y) { 230 // (0, 0) => { 231 // hs.insert(vec![ArrowTile::Right, ArrowTile::Down, ArrowTile::A]); 232 // hs.insert(vec![ArrowTile::Down, ArrowTile::Right, ArrowTile::A]) 233 // } 234 (1, 0) => hs.insert(vec![ArrowTile::Down, ArrowTile::A]), 235 (2, 0) => { 236 hs.insert(vec![ArrowTile::Left, ArrowTile::Down, ArrowTile::A]); 237 hs.insert(vec![ArrowTile::Down, ArrowTile::Left, ArrowTile::A]) 238 } 239 (0, 1) => hs.insert(vec![ArrowTile::Right, ArrowTile::A]), 240 (1, 1) => hs.insert(vec![ArrowTile::A]), 241 (2, 1) => hs.insert(vec![ArrowTile::Left, ArrowTile::A]), 242 (_, _) => todo!(), 243 }, 244 ArrowTile::Left => match (x, y) { 245 // (0, 0) => hs.insert(vec![ArrowTile::Down, ArrowTile::A]), 246 (1, 0) => { 247 hs.insert(vec![ArrowTile::Down, ArrowTile::Left, ArrowTile::A]) 248 // ; 249 // hs.insert(vec![ArrowTile::Left, ArrowTile::Down, ArrowTile::A]) 250 } 251 (2, 0) => { 252 hs.insert(vec![ 253 ArrowTile::Down, 254 ArrowTile::Left, 255 ArrowTile::Left, 256 ArrowTile::A, 257 ]); 258 hs.insert(vec![ 259 ArrowTile::Left, 260 ArrowTile::Down, 261 ArrowTile::Left, 262 ArrowTile::A, 263 ]) 264 // ; 265 // hs.insert(vec![ 266 // ArrowTile::Left, 267 // ArrowTile::Left, 268 // ArrowTile::Down, 269 // ArrowTile::A, 270 // ]) 271 } 272 (0, 1) => hs.insert(vec![ArrowTile::A]), 273 (1, 1) => hs.insert(vec![ArrowTile::Left, ArrowTile::A]), 274 (2, 1) => hs.insert(vec![ArrowTile::Left, ArrowTile::Left, ArrowTile::A]), 275 (_, _) => todo!(), 276 }, 277 ArrowTile::Right => match (x, y) { 278 // (0, 0) => { 279 // hs.insert(vec![ 280 // ArrowTile::Right, 281 // ArrowTile::Right, 282 // ArrowTile::Down, 283 // ArrowTile::A, 284 // ]); 285 // hs.insert(vec![ 286 // ArrowTile::Right, 287 // ArrowTile::Down, 288 // ArrowTile::Right, 289 // ArrowTile::A, 290 // ]); 291 // hs.insert(vec![ 292 // ArrowTile::Right, 293 // ArrowTile::Right, 294 // ArrowTile::Down, 295 // ArrowTile::A, 296 // ]) 297 // } 298 (1, 0) => { 299 hs.insert(vec![ArrowTile::Down, ArrowTile::Right, ArrowTile::A]); 300 hs.insert(vec![ArrowTile::Right, ArrowTile::Down, ArrowTile::A]) 301 } 302 (2, 0) => hs.insert(vec![ArrowTile::Down, ArrowTile::A]), 303 (0, 1) => hs.insert(vec![ArrowTile::Right, ArrowTile::Right, ArrowTile::A]), 304 (1, 1) => hs.insert(vec![ArrowTile::Right, ArrowTile::A]), 305 (2, 1) => hs.insert(vec![ArrowTile::A]), 306 (_, _) => todo!(), 307 }, 308 ArrowTile::A => match (x, y) { 309 // (0, 0) => hs.insert(vec![ArrowTile::Right, ArrowTile::Right, ArrowTile::A]), 310 (1, 0) => hs.insert(vec![ArrowTile::Right, ArrowTile::A]), 311 (2, 0) => hs.insert(vec![ArrowTile::A]), 312 (0, 1) => { 313 // hs.insert(vec![ 314 // ArrowTile::Up, 315 // ArrowTile::Right, 316 // ArrowTile::Right, 317 // ArrowTile::A, 318 // ]); 319 hs.insert(vec![ 320 ArrowTile::Right, 321 ArrowTile::Up, 322 ArrowTile::Right, 323 ArrowTile::A, 324 ]); 325 hs.insert(vec![ 326 ArrowTile::Right, 327 ArrowTile::Right, 328 ArrowTile::Up, 329 ArrowTile::A, 330 ]) 331 } 332 (1, 1) => { 333 hs.insert(vec![ArrowTile::Up, ArrowTile::Right, ArrowTile::A]); 334 hs.insert(vec![ArrowTile::Right, ArrowTile::Up, ArrowTile::A]) 335 } 336 (2, 1) => hs.insert(vec![ArrowTile::Up, ArrowTile::A]), 337 (_, _) => todo!(), 338 }, 339 }; 340 341 return (Some(hs), _x, _y); 342 //println!("a={a:?}"); 343 } 344 345 fn solve_rec_numpad( 346 map: &Vec<Vec<NumTile>>, 347 want: &[NumTile], 348 x: i32, 349 y: i32, 350 depth: u8, 351 ) -> Option<HashSet<Vec<ArrowTile>>> { 352 if !(0 <= x && x < map[0].len() as i32 && 0 <= y && y < map.len() as i32) 353 || map[y as usize][x as usize] == NumTile::Empty 354 { 355 return None; 356 } 357 if want.len() == 1 && map[y as usize][x as usize] == want[0] { 358 return Some(HashSet::from([vec![ArrowTile::A]])); 359 } 360 if map[y as usize][x as usize] == want[0] { 361 let next = solve_rec_numpad(map, &want[1..], x, y, depth + 4).unwrap(); 362 let mut new: Vec<Vec<ArrowTile>> = vec![]; 363 for path in next { 364 let mut new_vec = vec![ArrowTile::A]; 365 new_vec.extend(path); 366 new.push(new_vec) 367 } 368 let mut hs = HashSet::new(); 369 for path in new { 370 hs.insert(path); 371 } 372 return Some(hs); 373 } 374 if depth == 0 { 375 return None; 376 } 377 let mut down = HashSet::new(); 378 if want[0] != NumTile::Number(7) 379 && want[0] != NumTile::Number(8) 380 && want[0] != NumTile::Number(9) 381 { 382 for path in solve_rec_numpad(map, want, x, y + 1, depth - 1).unwrap_or(HashSet::new()) { 383 let mut new_vec = vec![ArrowTile::Down]; 384 new_vec.extend(path); 385 down.insert(new_vec); 386 } 387 } 388 let mut up = HashSet::new(); 389 if want[0] != NumTile::A && want[0] != NumTile::Empty && want[0] != NumTile::Number(0) { 390 for path in solve_rec_numpad(map, want, x, y - 1, depth - 1).unwrap_or(HashSet::new()) { 391 let mut new_vec = vec![ArrowTile::Up]; 392 new_vec.extend(path); 393 up.insert(new_vec); 394 } 395 } 396 let mut left = HashSet::new(); 397 if want[0] != NumTile::Number(9) 398 && want[0] != NumTile::Number(6) 399 && want[0] != NumTile::Number(3) 400 && want[0] != NumTile::A 401 { 402 for path in solve_rec_numpad(map, want, x - 1, y, depth - 1).unwrap_or(HashSet::new()) { 403 let mut new_vec = vec![ArrowTile::Left]; 404 new_vec.extend(path); 405 left.insert(new_vec); 406 } 407 } 408 let mut right = HashSet::new(); 409 if want[0] != NumTile::Number(7) 410 && want[0] != NumTile::Empty 411 && want[0] != NumTile::Number(4) 412 && want[0] != NumTile::Number(1) 413 { 414 for path in solve_rec_numpad(map, want, x + 1, y, depth - 1).unwrap_or(HashSet::new()) { 415 let mut new_vec = vec![ArrowTile::Right]; 416 new_vec.extend(path); 417 right.insert(new_vec); 418 } 419 } 420 let shortest_path = up 421 .iter() 422 .min_by(|a, b| a.len().cmp(&b.len())) 423 .unwrap_or(&vec![]) 424 .len(); 425 up.retain(|a| a.len() == shortest_path); 426 let shortest_path = left 427 .iter() 428 .min_by(|a, b| a.len().cmp(&b.len())) 429 .unwrap_or(&vec![]) 430 .len(); 431 left.retain(|a| a.len() == shortest_path); 432 let shortest_path = right 433 .iter() 434 .min_by(|a, b| a.len().cmp(&b.len())) 435 .unwrap_or(&vec![]) 436 .len(); 437 right.retain(|a| a.len() == shortest_path); 438 let shortest_path = down 439 .iter() 440 .min_by(|a, b| a.len().cmp(&b.len())) 441 .unwrap_or(&vec![]) 442 .len(); 443 down.retain(|a| a.len() == shortest_path); 444 down.extend(up); 445 down.extend(left); 446 down.extend(right); 447 let shortest_path = down 448 .iter() 449 .min_by(|a, b| a.len().cmp(&b.len())) 450 .unwrap_or(&vec![]) 451 .len(); 452 down.retain(|a| a.len() == shortest_path); 453 return Some(down); 454 }