- commit
- afb9f7d85386897979a9d5b4ef5144ae967a13bb
- parent
- 1373a55323e994d8d22f6789767311f18feafdcd
- Author
- Tobias Bengfort <tobias.bengfort@posteo.de>
- Date
- 2022-12-25 17:01
2022-12-24 part2
Diffstat
| M | 2022/24/solution.rs | 142 | +++++++++++++++++++++++++++++++++++-------------------------- |
1 files changed, 81 insertions, 61 deletions
diff --git a/2022/24/solution.rs b/2022/24/solution.rs
@@ -1,4 +1,6 @@ 1 1 use std::collections::HashSet; -1 2 use std::collections::binary_heap::BinaryHeap; -1 3 use std::cmp::Reverse; 2 4 3 5 #[path = "../lib.rs"] mod lib; 4 6 @@ -10,15 +12,25 @@ struct Blizzard { 10 12 dir: Dir, 11 13 } 12 1413 -1 fn get_input() -> (usize, usize, Vec<Blizzard>) {-1 15 struct Map { -1 16 width: usize, -1 17 height: usize, -1 18 blizzards: Vec<Blizzard>, -1 19 } -1 20 -1 21 fn abs_diff(a: usize, b: usize) -> usize { -1 22 return a.max(b) - a.min(b); -1 23 } -1 24 -1 25 fn get_input() -> Map { 14 26 let mut blizzards = vec![];15 -1 let mut width = 0;16 -1 let mut height = 0;-1 27 let mut max_x = 0; -1 28 let mut max_y = 0; 17 29 18 30 for (y, line) in lib::iter_input().enumerate() {19 -1 height = y;-1 31 max_y = y; 20 32 for (x, c) in line.chars().enumerate() {21 -1 width = x;-1 33 max_x = x; 22 34 match c { 23 35 '.' => {}, 24 36 '#' => {}, @@ -39,89 +51,97 @@ fn get_input() -> (usize, usize, Vec<Blizzard>) { 39 51 } 40 52 } 41 5342 -1 return (width - 1, height - 1, blizzards);43 -1 }44 -145 -1 fn format(width: usize, height: usize, blizzards: &Vec<Blizzard>, i: usize, pos: (usize, usize)) {46 -1 for y in 0..height {47 -1 for x in 0..width {48 -1 let k = blizzards.iter().filter(|b| has_pos(width, height, b, i, x, y)).count();49 -1 if (x, y) == pos {50 -1 assert_eq!(k, 0);51 -1 print!("E");52 -1 } else if k > 0 {53 -1 print!("{}", k);54 -1 } else {55 -1 print!(".");56 -1 }57 -1 }58 -1 print!("\n");59 -1 }60 -1 print!("\n");61 -1 }62 -163 -1 fn has_pos(width: usize, height: usize, blizzard: &Blizzard, i: usize, x: usize, y: usize) -> bool {64 -1 return match blizzard.dir {65 -1 Dir::Up => x == blizzard.x0 && y == (blizzard.y0 + (height - 1) * i) % height,66 -1 Dir::Right => y == blizzard.y0 && x == (blizzard.x0 + i) % width,67 -1 Dir::Down => x == blizzard.x0 && y == (blizzard.y0 + i) % height,68 -1 Dir::Left => y == blizzard.y0 && x == (blizzard.x0 + (width - 1) * i) % width,-1 54 return Map { -1 55 width: max_x - 1, -1 56 height: max_y - 1, -1 57 blizzards: blizzards, 69 58 }; 70 59 } 71 6072 -1 fn part1(width: usize, height: usize, blizzards: &Vec<Blizzard>) -> usize {73 -1 let mut offset = 1;74 -1 while blizzards.iter().any(|b| has_pos(width, height, b, offset, 0, 0)) {75 -1 offset += 1;76 -1 }-1 61 fn is_blocked(map: &Map, x: usize, y: usize, i: usize) -> bool { -1 62 return map.blizzards.iter().any(|blizzard| match blizzard.dir { -1 63 Dir::Up => x == blizzard.x0 && y == (blizzard.y0 + (map.height - 1) * i) % map.height, -1 64 Dir::Right => y == blizzard.y0 && x == (blizzard.x0 + i) % map.width, -1 65 Dir::Down => x == blizzard.x0 && y == (blizzard.y0 + i) % map.height, -1 66 Dir::Left => y == blizzard.y0 && x == (blizzard.x0 + (map.width - 1) * i) % map.width, -1 67 }); -1 68 } 77 6978 -1 let mut best_i = usize::MAX;-1 70 fn find_path(map: &Map, start: (usize, usize), end: (usize, usize), offset: usize) -> usize { -1 71 let mut best_i = usize::MAX - 1; 79 72 let mut seen = HashSet::new();80 -1 let mut queue = vec![81 -1 (0, 0, offset),82 -1 ];-1 73 let mut queue = BinaryHeap::new(); -1 74 queue.push(( -1 75 Reverse(usize::MAX - 2), -1 76 usize::MAX, -1 77 usize::MAX, -1 78 offset, -1 79 )); -1 80 let mut k = 0; -1 81 -1 82 while let Some((Reverse(min_i), x, y, i)) = queue.pop() { -1 83 if min_i >= best_i { -1 84 // for some reason, continue is faster than break/return -1 85 continue; -1 86 } 83 8784 -1 while let Some((x, y, i)) = queue.pop() {85 88 if seen.contains(&(x, y, i)) { 86 89 continue; 87 90 } else { 88 91 seen.insert((x, y, i)); 89 92 } 90 9391 -1 if i + (width - 1 - x) + (height - 1 - y) >= best_i {-1 94 if is_blocked(map, x, y, i) { 92 95 continue; 93 96 }94 -1 if x == width - 1 && y == height - 1 {95 -1 println!("{} {}", i, queue.len());-1 97 -1 98 if x == end.0 && y == end.1 { 96 99 best_i = i; 97 100 continue; 98 101 } -1 102 k += 1; 99 103 100 104 let mut moves = vec![(x, y)];101 -1 if x > 0 {102 -1 moves.push((x - 1, y));103 -1 }104 -1 if y > 0 {105 -1 moves.push((x, y - 1));106 -1 }107 -1 if x + 1 < width {108 -1 moves.push((x + 1, y));109 -1 }110 -1 if y + 1 < height {111 -1 moves.push((x, y + 1));-1 105 if x == usize::MAX && y == usize::MAX { -1 106 moves.push(start); -1 107 } else { -1 108 if x + 1 < map.width { -1 109 moves.push((x + 1, y)); -1 110 } -1 111 if y + 1 < map.height { -1 112 moves.push((x, y + 1)); -1 113 } -1 114 if x > 0 { -1 115 moves.push((x - 1, y)); -1 116 } -1 117 if y > 0 { -1 118 moves.push((x, y - 1)); -1 119 } 112 120 } 113 121 114 122 for (xx, yy) in moves {115 -1 if !blizzards.iter().any(|b| has_pos(width, height, b, i + 1, xx, yy)) {116 -1 queue.push((xx, yy, i + 1));117 -1 }-1 123 queue.push(( -1 124 Reverse((i + 1) + abs_diff(xx, end.0) + abs_diff(yy, end.1)), -1 125 xx, -1 126 yy, -1 127 i + 1, -1 128 )); 118 129 } 119 130 } 120 131 -1 132 println!("{}", k); 121 133 return best_i + 1; 122 134 } 123 135 124 136 fn main() {125 -1 let (width, height, blizzards) = get_input();126 -1 println!("part1: {}", part1(width, height, &blizzards));-1 137 let map = get_input(); -1 138 let start = (0, 0); -1 139 let end = (map.width - 1, map.height - 1); -1 140 -1 141 let t1 = find_path(&map, start, end, 0); -1 142 println!("part1: {}", t1); -1 143 -1 144 let t2 = find_path(&map, end, start, t1); -1 145 let t3 = find_path(&map, start, end, t2); -1 146 println!("part2: {}", t3); 127 147 }