- commit
- 1373a55323e994d8d22f6789767311f18feafdcd
- parent
- 9b77bc242ba210404b4b4b43bfa86b1b5d241933
- Author
- Tobias Bengfort <tobias.bengfort@posteo.de>
- Date
- 2022-12-25 08:24
2022-12-24 part1
Diffstat
| A | 2022/24/input.txt | 27 | +++++++++++++++++++++++++++ |
| A | 2022/24/solution.rs | 127 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 2022/24/test.txt | 6 | ++++++ |
3 files changed, 160 insertions, 0 deletions
diff --git a/2022/24/input.txt b/2022/24/input.txt
@@ -0,0 +1,27 @@ -1 1 #.######################################################################################################################## -1 2 #<.^><>^>>>^<v^^v>v^vv<v>.<v^><>^<^.^>^><^^v^>v^v>>v><v<^vv>><^.v<^vv.v<^<^<vv<<vv>..v^><>..<<^.<v^^^vv>.<<^v>^<<v<^v^v>># -1 3 #>^><.^<^v<>^<<vv^<^<>>^v<^vvv>vvv<><v^v<>><<^>.v.>^v^^><^<v^v^v^.>v^<vvv^^.vv^^v^<^^v>>>>.v^^.>v>^<<v>vv<<v>.>>><^>>>>v># -1 4 #>v>^^^^>.^.v<>>>v>v^^v.>v^>><..v<^vv^v^><<>v<^<vv>>^.<.>>>v<>>^^v>>^<^v^<^v^v<v^>^.vvvv.<<.>^<^^>>v>v<>><^^>v^^<v^.vv<>># -1 5 #><<<>v^^v>v>v>^<<<.<^.><<<>v>>>.^<^><>^v<^^>>v.>vv^<<<>^<>>><^^.^vv^<vv<<><.vv^^v^<^><.v^^>^<^<vvv<>><<><>vv^vv^<.^<v^v># -1 6 #>>^^^>.>>><^^<<v^v^v.>^.v<v<vv>vv>^<^^^<>>vv>v^<v^vv<^v^>^>v^>>v<>>>^v>vvv>v>^<<>v^>v><<^<v<<.>v>>><^<<>^<>>v<<v>.<.v<<># -1 7 #>..<>v>^..v<v.<v<vv<><<v^>>v<^.>v^>vv^v<^v>v<vv^<<^.^^^.<^v.<vvv<<<^^^^<v<v.>.^.^>.<.^^><<^.^<>>^v>^vv<<>.^^^..v<<v<<v^.# -1 8 #>^..<v^^v^<<v<vv<^^^<>v><^><>>^<v><>vvv..^>v^v<v<.<^^<<v><<><v>vv><vvv.<><^.vv<^.v><><<^vv^v<<v^v>>^v>>>>vvv>^<<v<>^>>^># -1 9 #<<>^><^v>v<v>^^>v<>>>.^^v.>v<>^^v^v>v^v^<^^<v<<.v<^^>^v<.>.^<><<^v>^..<>>><.>^<.<<>>^^v>>v^^<^>.^v<v>>>vvv>>>>vv<vvv.v<># -1 10 #><<v<^v^^^>v>.<.>>>^^^>>..>v^^>>^<^<><.^>>^>.v><^^^>>^vv>^v^v.>v<.^^>><<.<..><>^<v>v<^<^v<^^v<.>vv^^^^<v>>v^<v<<<^vv<.^.# -1 11 #<<^><><^v.<v>.^><v<v^^>^>>vvv><<^^<><>.vv^^><v.>vv>^^v>^v>>^<^>..<<^<v<^.v^^<<>><<.<^>^>^<vv><<>^>vvv>^>^^>>>.>vv^<<^<>.# -1 12 #<..>^>vv<<^^v>^<vv<v^v<^^<v^^^v^v<^>.^.^^>>>.^<^v^^v><v^^v^^vv^<<<.....>v^<<vv>>.>><v<v>>v..v<^><>vvv<vv<^v<<>>.^^v<v^<<# -1 13 #>v>><^v.<v<v>^^>^vv>vvvv<>v><>v.^<>><>^><.<^><.>.<<^^v^^.>v>v^><><vv^><.<>><<v^v.<^^>v>.<>vv.v<^v^v^<^<>>v<><<v.^<.<<^v<# -1 14 #<<>^vvv.^<v<.vv<^.v><v<<^vv<<vv<v^v>v<vv^^<>><^v^>^^^^>v.>>.^vv.<v<>^^^><^^>>^<..<.>>^^^<<^^^v^^<v<^.vv<^v>><<^.<<>>><.<# -1 15 #..v>.>>v<^vv><vv<v>^<.>>^^>v^><<^>v<^v^..^v>^>.^vvv<v><<.<.<>v>^^<<<v^^^vvvv^.>v>^^>^>>^><<v<>^>.v.^<v<>.^^>><.v^v<.vv^<# -1 16 #>^<vv<>v<v^<.>>>v<><vv>^^<v<^v><<v^v^v>^^<>.vv>v.^^<v^v<v><v<v^vv>.<>v<<<>>><<v<<.v>v^<..^v^^<v^v.>vv.^^<>>v^<.<^>v^<^.<# -1 17 #<>>>vv.>^>.v>v<v<v><>^>v^v<>^.>>v>^^>vv>><>v.^.>^>>>^<><v^>vv<.>vvv<>^v><v>>><vvv.<v^<>>.vv^v>>>>>v<^>.v<.<<.vv>><.^<<.<# -1 18 #<^v^>>>><><v<<.^<<^><.^<^^^<.^.v><>^vv<^<><.><^<v<v<v<<<^<v^>>v<<<.<v>.>^.<><.^^<>v>>^vv<^^<>v<v<v<^<^>v.^<v><<<>>^>v^<<# -1 19 #<<><.vv^v<v>v^^<.<^<<<<<<v.v^..><v^^^^^v^<>v^<<^>v<^v^.<.<>^<v^^v<<.><>v>v.v>vv>.><v>^v>.<>>v^<.>v<vvvvvvv<><^^v>>^^<>>># -1 20 #><>v>>v.^<<<<v>>v.<<^^..^<^.v.v^<>v<^^>.^^<.^>^<.vvv.^vv^.>.>^<>v^v<<><^.v>v^^v<v>^v>>.^vv<v^^>><<<^<>v<<v<<^>><v.<v<>^># -1 21 #>><>vvv^>v<>v<v>^.<<>^^<^>>v^.<^>>.<<v<<^<^><^<>>^.vvv>v><<>><>vv.^<v>v><^>.^^^.v>>^^^vv^<^><^>>>.<^v^<vv>>^>>^>v>><.<v># -1 22 #>><<^v<>>>>^<><.<>vvv.<^>v<>.<.<<^>v>v<v^^vv^^>>v<^>^v^<^.>v><vv^^^.^v^>^><<<v^.>^<^>v<^v<>><<vv<^v><.<>^^v.^^.^>^.v<<>># -1 23 #.<<^><v>>>v^>.^v><v^>>vv>^<<v<v.>^^.<v<.<<<v<>><^<v^<v^>^vvv>^<<>>v<<.v^><<vv^<v>v<<^v>vv<<.v^<<^v^<<v<<<>><^^vvvv<v>vv<# -1 24 #><>>>^>^^><v^^^<>><>^<.<^^<>^^.>.<>.>v>vv>..><>>^<v>>vv>.v>.v^^<<^v<><^^^vv.^<>.^>v>v>v<<^<v><v.<^v<.^.<><<><>.v^^v^v^.># -1 25 #<<.^.v^><<^vv^v^.^>.<v<v.v^<v^v><.v.^vv^.>.<>>><<>^>v^>.<^>>>v<>^<>^^>..<.^>v^>^v.<<>^v^<>>>v>>v^>^.^<.vv><>^v^v><^^<^<># -1 26 #>v^><v>v<v^^>><vv^^v..>><><.<^vvv>^<>^<>v^..^v.>>v>vvv><v>>v>vv>^^v<<^<^^^>>v<^><v.v<^v^<^.>>v>^v<>^>vv^<.<.<^v<<<><^.^># -1 27 ########################################################################################################################.#
diff --git a/2022/24/solution.rs b/2022/24/solution.rs
@@ -0,0 +1,127 @@
-1 1 use std::collections::HashSet;
-1 2
-1 3 #[path = "../lib.rs"] mod lib;
-1 4
-1 5 enum Dir { Up, Right, Down, Left }
-1 6
-1 7 struct Blizzard {
-1 8 x0: usize,
-1 9 y0: usize,
-1 10 dir: Dir,
-1 11 }
-1 12
-1 13 fn get_input() -> (usize, usize, Vec<Blizzard>) {
-1 14 let mut blizzards = vec![];
-1 15 let mut width = 0;
-1 16 let mut height = 0;
-1 17
-1 18 for (y, line) in lib::iter_input().enumerate() {
-1 19 height = y;
-1 20 for (x, c) in line.chars().enumerate() {
-1 21 width = x;
-1 22 match c {
-1 23 '.' => {},
-1 24 '#' => {},
-1 25 '^' => {
-1 26 blizzards.push(Blizzard { x0: x - 1, y0: y - 1, dir: Dir::Up });
-1 27 },
-1 28 '>' => {
-1 29 blizzards.push(Blizzard { x0: x - 1, y0: y - 1, dir: Dir::Right });
-1 30 },
-1 31 'v' => {
-1 32 blizzards.push(Blizzard { x0: x - 1, y0: y - 1, dir: Dir::Down });
-1 33 },
-1 34 '<' => {
-1 35 blizzards.push(Blizzard { x0: x - 1, y0: y - 1, dir: Dir::Left });
-1 36 },
-1 37 _ => unreachable!(),
-1 38 }
-1 39 }
-1 40 }
-1 41
-1 42 return (width - 1, height - 1, blizzards);
-1 43 }
-1 44
-1 45 fn format(width: usize, height: usize, blizzards: &Vec<Blizzard>, i: usize, pos: (usize, usize)) {
-1 46 for y in 0..height {
-1 47 for x in 0..width {
-1 48 let k = blizzards.iter().filter(|b| has_pos(width, height, b, i, x, y)).count();
-1 49 if (x, y) == pos {
-1 50 assert_eq!(k, 0);
-1 51 print!("E");
-1 52 } else if k > 0 {
-1 53 print!("{}", k);
-1 54 } else {
-1 55 print!(".");
-1 56 }
-1 57 }
-1 58 print!("\n");
-1 59 }
-1 60 print!("\n");
-1 61 }
-1 62
-1 63 fn has_pos(width: usize, height: usize, blizzard: &Blizzard, i: usize, x: usize, y: usize) -> bool {
-1 64 return match blizzard.dir {
-1 65 Dir::Up => x == blizzard.x0 && y == (blizzard.y0 + (height - 1) * i) % height,
-1 66 Dir::Right => y == blizzard.y0 && x == (blizzard.x0 + i) % width,
-1 67 Dir::Down => x == blizzard.x0 && y == (blizzard.y0 + i) % height,
-1 68 Dir::Left => y == blizzard.y0 && x == (blizzard.x0 + (width - 1) * i) % width,
-1 69 };
-1 70 }
-1 71
-1 72 fn part1(width: usize, height: usize, blizzards: &Vec<Blizzard>) -> usize {
-1 73 let mut offset = 1;
-1 74 while blizzards.iter().any(|b| has_pos(width, height, b, offset, 0, 0)) {
-1 75 offset += 1;
-1 76 }
-1 77
-1 78 let mut best_i = usize::MAX;
-1 79 let mut seen = HashSet::new();
-1 80 let mut queue = vec![
-1 81 (0, 0, offset),
-1 82 ];
-1 83
-1 84 while let Some((x, y, i)) = queue.pop() {
-1 85 if seen.contains(&(x, y, i)) {
-1 86 continue;
-1 87 } else {
-1 88 seen.insert((x, y, i));
-1 89 }
-1 90
-1 91 if i + (width - 1 - x) + (height - 1 - y) >= best_i {
-1 92 continue;
-1 93 }
-1 94 if x == width - 1 && y == height - 1 {
-1 95 println!("{} {}", i, queue.len());
-1 96 best_i = i;
-1 97 continue;
-1 98 }
-1 99
-1 100 let mut moves = vec![(x, y)];
-1 101 if x > 0 {
-1 102 moves.push((x - 1, y));
-1 103 }
-1 104 if y > 0 {
-1 105 moves.push((x, y - 1));
-1 106 }
-1 107 if x + 1 < width {
-1 108 moves.push((x + 1, y));
-1 109 }
-1 110 if y + 1 < height {
-1 111 moves.push((x, y + 1));
-1 112 }
-1 113
-1 114 for (xx, yy) in moves {
-1 115 if !blizzards.iter().any(|b| has_pos(width, height, b, i + 1, xx, yy)) {
-1 116 queue.push((xx, yy, i + 1));
-1 117 }
-1 118 }
-1 119 }
-1 120
-1 121 return best_i + 1;
-1 122 }
-1 123
-1 124 fn main() {
-1 125 let (width, height, blizzards) = get_input();
-1 126 println!("part1: {}", part1(width, height, &blizzards));
-1 127 }
diff --git a/2022/24/test.txt b/2022/24/test.txt
@@ -0,0 +1,6 @@ -1 1 #.###### -1 2 #>>.<^<# -1 3 #.<..<<# -1 4 #>v.><># -1 5 #<^v^^># -1 6 ######.#