- commit
- c233d563941c3a4e30efc3af97ae664ec2a6c5d6
- parent
- 005c5d2e09e5d7f5c1c573e18a20da3fb8227bea
- Author
- Tobias Bengfort <tobias.bengfort@posteo.de>
- Date
- 2023-12-23 18:48
2023-12-23
Diffstat
| A | 2023/21/input.txt | 131 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 2023/21/solution.rs | 102 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 2023/21/test.txt | 11 | +++++++++++ |
3 files changed, 244 insertions, 0 deletions
diff --git a/2023/21/input.txt b/2023/21/input.txt
@@ -0,0 +1,131 @@ -1 1 ................................................................................................................................... -1 2 ...#.......#.##......#.#........#.........#...........................#.......#.....#.#.....#.#.#.......###....#...#..........#..#. -1 3 ..#..............#.#..#........#........##.##.#.......#..#...............#..#......#.##.....#..#.........#......#......#......#.##. -1 4 ....#........##....#.....##.....#.##...#....#.#.###.......................#...#...#.#..........#...#........#.............#.....#.. -1 5 .....#.......###....#...............#.....#...#...#...##.#................#.......##...#..........#...#.......##..#........#.....#. -1 6 ..........#............................#............#.#.................................#.......#............##............#.#..... -1 7 .............#............###.#.#...............#....#.............#.......#.##.....##..#..#............##..........##............. -1 8 ...............#.#............#...#..#..#.##..#....#...........#..................##......#.#......#.#.#..........#.....#.#...#..#. -1 9 ..........##.#..#...#.......##.........#.............#.............###...................#.......#...#.#.#.....#####.........##.... -1 10 ....#....#...#..#.....#..##.....#....#.........#..###.............#.#...........#.............#.##........#.#.#....#...##......##.. -1 11 .......#.....#..#.#...........##.......##..#..#............##..#......#.......................#.......#.....#.#.................... -1 12 .#..#...#.......#....#......#..#.#..........................#..##...................##.....#.........#.#........#........#...##.... -1 13 ..#...#.#..#...#.#......#....#...........#...#...........#..#.#.#....##..........#.#....#.......##.#....#.....##..........#.....#.. -1 14 .....#..#...........#.##.#............#.#.##.............#.....##.................#............#..##.....#...........##............ -1 15 .....#.#....##....#............#......#...#............#....#.......#.#....#........#......#...#........#....#.............#....... -1 16 .....#........#.........##.#...#...#.#..#..#..............................#.........#.....................#.#..#..#.#........#..#.. -1 17 .##.....#..#..........##..#.#........#.#.....#........#............#...#.....#..................#.#.........#...#.....#....###..#.. -1 18 ...............##.....#.#.....#.....##..#..................###...............#.............#.......#....#...............#......#... -1 19 ...#......#.#.............#..#.......#...#..............#.........#....#....#.......................#...#.......#..#...##......#.#. -1 20 ..........#..#....#.#....#..#...#....##...#.......#..#.........##...#.#.##....#................#.....#.....#.........#............. -1 21 ...#..#..#...#..#..#.....................#............#............#####....#..#.........#....#....#..#.............#.#......#.#.#. -1 22 ......#....#....#.##.......#..##..#................#.....#..#.#................##.........#..##..##...........#..#................. -1 23 .....#.#..#......#......#....##...#............##...#.#.#......#.......#.......#..#.........#...#..#.....##...#.....#....#......... -1 24 ....#..#...#..#...........#..#.#..#...#.............#.#....#...##...........#.#...##........#.....#...#.....#.#...#......#..#.#.... -1 25 .....#.#...#...#.#...##...#........###.............#..#...##....#............................#..#.........##.......#.....#....#.... -1 26 ........#.##...................##......................#...#.....................#...................#..##.#....#....#.#....##...#. -1 27 .####.....#.......#........#..........................................#........#.#.#...........#........#..#....#......#....#..#... -1 28 .....#......#..###..#..##.....#.........................#..#...#....#.#.........#..#..................#..##........#....###...##.#. -1 29 ........#....#......###...#......#..............#......#.....#....#.....#.....#....##........................#.........#..#........ -1 30 ........##..#........#........##.............##.##...#..#.......#.#.......#..##......#...............##..#...#.##...#..#......#.... -1 31 ........##..#..#..##.#..................##......#.#.......##...#......#....###...#.........................#.....#..#..#.#......... -1 32 ............#......###.#......#............#..#..#...#.........#..#.....#.#...##......#.................#..........#....#.....#.... -1 33 ..#.....##.#.......##........#.......#...#..#.......#......##.#....#.......#..........#....#..............#..#...##...#.#......#.#. -1 34 ..............#..###......##............#....#.....##.##......##................#..##....................#.......#.##..........#... -1 35 ............#.#.......##............#........#.##....#..#.........##.#....##.#........#....##...............#............##.##..#.. -1 36 ..#..#..#...#...#....#.#...................###...#....#........##.........#..##......#....#................................#..#.... -1 37 .#...............##................#.#.......#........#.....#.....###..#.##....##............###.........#....#.................... -1 38 ...................#..#...........#..#.#..............#..#...............#.#.#.........##.........#...........#...####....#..#...#. -1 39 ..#...#........#.......#........#.....#..##.........##.#......##........#......#.#..#...#........#..........#..........#...#....... -1 40 ..#....#.#.##.#....##...........#.#..##.....##...##..#...##....#....#....#....###...#...#.........##..................#.#....##..#. -1 41 .##........#...#...##........#..#...#.....#.#....###....##.#........#..#.......#.........#...#....#...............#..##....#.....#. -1 42 .....#.......#....#..........###.....#..#..........#..#.......##..#......................##..##...............#.#....#..##..##..#.. -1 43 .#......#...#...#..#.............#.#....#........#......##............####.#.........#.................#..............#..#.#....#.. -1 44 ............#.#.#.............#..........#........##..##....#...............................#.#..#.....................##..##...#.. -1 45 ................................#........#........#.....##....#....#.......#......................#..........................##.... -1 46 ...##.###...#...........#..#.......#.....#................#.#..#......#...#....#..#......#....##......#..##........#..##.#......... -1 47 .#.........#...................#.....#.##.##.#.#.......#....#..#...#........##.##..#....##...##...#..#.............##.....#........ -1 48 ....#.......#.#........#.##...#.........#......##.....#....##..##...#......#..#.........#..##......##.#..............##..#....#..#. -1 49 .#.......#................#....##......#...#....#.#......#.#..#...............###.........#.##.............###..........###....#... -1 50 ............#...........#...#......#.#..##......#..##..........#........#...##.........#...#.............#..............#..#....... -1 51 .#...#..##.............#........#..###........##................#...##..#......#...#.......#.#.........................##....#..... -1 52 .......##..........#......##....#............#..##.......##....##...#.......#...#........##..#.#...##........................#...#. -1 53 ..#....#...............##...#...#.#.#.....#.#....#...#.........#..#.......#..#..#....#......##...#....##.....#..#.........#......#. -1 54 .#..#......................#..#.#....#..#.##..#......###.......................#........#.#....#........#..#....#.................. -1 55 ....#..............................#...##...............#...................#..#...##.#..#.....##......#...##................####.. -1 56 ................................#......#....#...#..#......#.....#..........#..#...##......#............#.....##....#........##..... -1 57 ...............#...........#........#.#........#.#.#...#..#....#.......#..###..........#.#.#.#......#..#.......#..##.#............. -1 58 ....................#.#....#.....#........##...#.......#....###.#.........#......#......##.#..#..#...................#.........##.. -1 59 .#.....................#.........##......#........##..................#..................##..#.........##.#............#........... -1 60 ............#...##.#..#................#........#......#...................#.#....##...#.#.....#.#.......#..#.....#.....#.......... -1 61 .................#..............#..#......#......#.........#......#.#..#...#.#....................#...#.....#........#..#........#. -1 62 ............#.........#....#.......##..#.#...##.....#...##...........#............#..#.#.............#.........#.........#......... -1 63 ........#.............#......##..#.............#........#....#.##.#....#......#..........#....#....#......#....#.......#........... -1 64 ............#.#...#..#.......#....#.....##....................#.........###....#.#........#...##.......#....#..##...#.......#...... -1 65 .........#...#........#...........#......#....#..#...#..........#..............#....#............#..#......#..#...#..#....#........ -1 66 .................................................................S................................................................. -1 67 .........#.###....#........#..##........#.##.#......#.............#..........#.#.#.......#...#..#...#...#....#......#.............. -1 68 ......#..#.....#.......#...##.###...........#..#...#.#.#..................###...#..#......##.#.##......#.......#..##.#......#...... -1 69 ............#........#......#....#...#.#....#....#......#...........#.......##..#......#...#.....#.......##.........#...#.......... -1 70 ...............#...........##.....#...#........#..#...#...........#..#..##....#.................##..#.....##..#.#......#.#......... -1 71 .........#....##..#...#.....#.....#.......#.#....#.........##..#.....##....#...#......#............#.......#....#....#...#.......#. -1 72 .......................#.#...#....#.#.....##......#............#.....#.#...##........##.....#...##.......##.#...................... -1 73 ..................##..#.#........#...#.#.....#.##........##..#.......###..##......#..........#........#....#..#.#...##.#.......#... -1 74 ............#..............####...#..#..###.#.##....#.#.##...........#.......##......#.#............#.#........................#... -1 75 .#..............#.........#......#.......##...#.......................#.......#........#.......#........#.....#....#............... -1 76 ...............#......#........#...............#........#..##......###...#.......................#....##.........#.##..........#.#. -1 77 ...#..##.......#.#...#......#.....#.#...........#..##.###.#...............#.#........#............######.##.#...#..............#... -1 78 ....##...............#.....##....#.#.....................###..#...#.#...#.#...#.##............##...#..#.#........##.......##....... -1 79 ....#.#.#............#..#......###............#.#.####............#...###.........#.#...#.....#.##....#..........#.......#...###... -1 80 ......#.#.#.............#...#....#....#.####.......#.....###........#......#.##......##..#..##.......#..#....##............#.#..... -1 81 ..##.......#..........#....###.......#.###............#.....##....#....#.#...#.........#........#.......#..#.#.............#...##.. -1 82 .........#.............#....##.........#....###.......#.....#...#.....#.#...#.#.#.....#....#...........###..#...........#.....#.... -1 83 .#...#....#.##.........#...##....#..##.#....#.....##..#.#...............#.#...#...#.#.......#.#.#........#..#...................... -1 84 .......##.#...............#...............#......#..#...##....#...#...#..#.......#.............#......#................#....###..#. -1 85 .....#.................#.............#.##.#..#...##.......#.....#........#..#.....#.......#........#..#...#...........#...#.....#.. -1 86 ..#.#....#.#.#..........#.#......#......................##.#.#.#....#....#....#...............#..#.#.................#......#...... -1 87 ...#.......#.....#........#....##...##.....#....##.....#....#..............#......#.....#.....#......#..##.............#.#.....###. -1 88 .#..............#.........#..........#..#.....##..##..#...#.......#.##......#...........##.......................#....#..#......... -1 89 ....###..........................#...#...#..###.#...#...............#...##...#...#.##...#..#...#.#...#...........#.............#... -1 90 .................##...........##.......#......#..#..................#.................#....#..#....#.#.............#.##..#....##.#. -1 91 ..#....#......#.#..................#...#..#........#.....#....#...##......#...###...........#..#..#..........#.............#....... -1 92 .#...#..#.##.#...#............#..#..#.#.....#.#..#..#.........##........#.......##.#.......#.....#.#........##..#............#..... -1 93 .##...###........#.#..............#...........#....#.##.......#.....##.........#..##.....#..#.................#.##...#...##......#. -1 94 ...#....#............#.#.........##.###.#.......#..##......##......#####.......#.............#.............#.#.#..#...#..#.....#.#. -1 95 ...#.###.....##..................#.###......#..#.#.#.#....#..#....#........##.#...#...#..#.....##.......................#.....#..#. -1 96 .......##.#..###.........................#..........#...#...#..#.....#.......#.#.....##...#....#.............#....##..#.##.#....... -1 97 .#.......#......#.##.................#.....#..#.............##....##.....#..#.#...........##.............#...##...........#........ -1 98 ....#.........##.#..#.................##...#.#.......#.......#.....#....#.....#.#.........#..#........#......#..........#.#........ -1 99 .#..#...#......#..##.....#..............##.###.......#..#.........##...............#.....#...#........#.........#....#............. -1 100 ....................#..#....................#....#..#....#..........#....#.....#.........#..#.................#.........#........#. -1 101 ....................................................#..........#....#..##....##........#............#.........#....#...#.........#. -1 102 ..#.........#.......#..#..................#.#....#.#..........#..................#..#..#...................#..#.................... -1 103 ..##...#...##....#...#..........##.........................#.#....###.....#.....#....#...........#..#.............#....##....#...#. -1 104 ....#..#...#.....##...#..#...................#...#.........#.#..#...#............................#.........#..............##.#..... -1 105 .......#.......##.#.......#.....................#.....#............####.#.....#....#...............#.#....#......#.#...#...#....... -1 106 ........#.......#...#.##..#........................#...#...##..........#...#......##..#.......##.....#..#.......................... -1 107 .....#...#.....#..#.........###..#..............#..#......#.##..........#..##.##.................#...#.##.............#.#.....#..#. -1 108 ..##..#............###...#..#....#..#.#.......#.......#.##....#.........#.#.#..................#.#...#.#......#.#.#................ -1 109 ...........#.#...............#.....##.................##.#...##.......#.##..#..................##....#.#....#....##.#.....#.....#.. -1 110 .........#........#...............................#.#..#..#.........##....#..#.#...........#..##.....#..###.......#..#.#.#..#...#.. -1 111 ...........#......#.#.#.......#...#.....##..........#.....#...........##.##...#...........##.#.....#.#..##.#.#......#.......#...#.. -1 112 ..#....##....#....#.........#...#......................#...............#.......#...........#....#........##..#.##.....#.....##..... -1 113 ....#........#......#....##......#.........#.......#.#......##.....#..##......#.........#...##....#..#..................#......#... -1 114 .........#...#..............................................###...........#............#..#......#....#..#...........#.#........... -1 115 ..#....#.#.#.#.#.............#.#.......#...................#..........#.......................##.#.#..#.#..#...#.......#........... -1 116 ..................#......#.#....####..###.....................#....#.#....#...........#.#.#....#.........#.##...............#...... -1 117 .........##.#.#.........#..........#.......###..................#....#.....#..........##..#.#....#.....#..#.......#...#.....#...... -1 118 .............####.........#...................#..........#.#.#....###....##........#.#..#....#..#..#............##........##....... -1 119 ........##.#.#..#...........##.#.....##......#.#............##..#..##...................#.#...#..##...####.#..#...........##.#..... -1 120 ..........#.............##...................#..#..........#.#......#...................#....#.....#..#...#...#.#.............#.#.. -1 121 ......##..#..#.#.#....#..#..#.....##.#..#....#.....#..........#....................#..............#......##.......#.......#..##.#.. -1 122 .......#.#...#.#..##.#........#.#.#.......#.....##.##...........#.............#...........#....##.#.#.....#.#..........#........#.. -1 123 ..#....#....#..........#...#..........#.#....##......#.......#.#...#.................##..........#.#..##..#..............#....#.... -1 124 .....................#............#......#..........##...............................#.#.#.#............#...#.....#.....#....#..... -1 125 ........#..#........#.......................#.....#....#...............................#...............#.#.##...#...#..#.....###... -1 126 ....#..#.#...#...........#.....#......#......#....#...##....................##........................#.##.....#......#.#......#... -1 127 .......#.#.....#......#....#.....#.....#............................................#....#...#...#.....#.#.#............###.#.#.... -1 128 ......#.#.......##...#...#...#.....###..####...#........#.#................#.................#............#.....#.................. -1 129 ...........##..............##...............##..........#..#..............##....#...#...#.##........#......#....#.##.#....#....###. -1 130 ....#..#.#......#..#.#.........#.....#......#..###.....#.#.......................#.....#......#....#..##....#....#....#.#.#........ -1 131 ...................................................................................................................................
diff --git a/2023/21/solution.rs b/2023/21/solution.rs
@@ -0,0 +1,102 @@
-1 1 use std::collections::VecDeque;
-1 2
-1 3 #[path = "../lib.rs"]
-1 4 mod lib;
-1 5
-1 6 fn parse_input() -> (Vec<Vec<bool>>, usize, usize) {
-1 7 let mut rocks = vec![];
-1 8 let mut x0 = 0;
-1 9 let mut y0 = 0;
-1 10
-1 11 for (y, line) in lib::iter_input().enumerate() {
-1 12 let mut row = vec![];
-1 13 for (x, b) in line.bytes().enumerate() {
-1 14 match b {
-1 15 b'.' => { row.push(false) }
-1 16 b'#' => { row.push(true) }
-1 17 b'S' => {
-1 18 row.push(false);
-1 19 x0 = x;
-1 20 y0 = y;
-1 21 }
-1 22 _ => unreachable!(),
-1 23 };
-1 24 }
-1 25 rocks.push(row);
-1 26 }
-1 27 return (rocks, x0, y0);
-1 28 }
-1 29
-1 30 fn flood(rocks: &Vec<Vec<bool>>, x0: usize, y0: usize, factor: usize) -> Vec<Vec<usize>> {
-1 31 let n = rocks.len();
-1 32 let mut distance = vec![vec![usize::MAX; n * factor]; n * factor];
-1 33 let mut queue = VecDeque::new();
-1 34
-1 35 let offset = n * (factor / 2);
-1 36 queue.push_back((x0 + offset, y0 + offset));
-1 37 distance[y0 + offset][x0 + offset] = 0;
-1 38
-1 39 while let Some((x, y)) = queue.pop_front() {
-1 40 let mut neighbors = vec![];
-1 41
-1 42 if x > 0 {
-1 43 neighbors.push((x - 1, y));
-1 44 }
-1 45 if x + 1 < n * 5 {
-1 46 neighbors.push((x + 1, y));
-1 47 }
-1 48 if y > 0 {
-1 49 neighbors.push((x, y - 1));
-1 50 }
-1 51 if y + 1 < n * 5 {
-1 52 neighbors.push((x, y + 1));
-1 53 }
-1 54
-1 55 let v = distance[y][x] + 1;
-1 56 for (xx, yy) in neighbors.iter() {
-1 57 if !rocks[*yy % n][*xx % n] && distance[*yy][*xx] > v {
-1 58 distance[*yy][*xx] = v;
-1 59 queue.push_back((*xx, *yy));
-1 60 }
-1 61 }
-1 62 }
-1 63
-1 64 return distance;
-1 65 }
-1 66
-1 67 fn count(distance: &Vec<Vec<usize>>, steps: usize) -> usize {
-1 68 let mut count = 0;
-1 69 for y in 0..distance.len() {
-1 70 for x in 0..distance[0].len() {
-1 71 if distance[y][x] <= steps && distance[y][x] % 2 == steps % 2 {
-1 72 count += 1;
-1 73 }
-1 74 }
-1 75 }
-1 76 return count;
-1 77 }
-1 78
-1 79 fn quad(c1: usize, c2: usize, c3: usize, k: usize) -> usize {
-1 80 let a = (c3 - 2 * c2 + c1) / 2;
-1 81 let c = c1;
-1 82 let b = c2 - a - c;
-1 83 return a * k * k + b * k + c;
-1 84 }
-1 85
-1 86 fn main() {
-1 87 let (rocks, x0, y0) = parse_input();
-1 88 assert!(rocks.len() == rocks[0].len());
-1 89 let distance = flood(&rocks, x0, y0, 5);
-1 90
-1 91 println!("part1: {}", count(&distance, 64));
-1 92
-1 93 // I originally thought that the prism just repeats.
-1 94 // Reddit told me to do quadratic interpolation instead and it worked.
-1 95 let steps = 26_501_365;
-1 96 let n = rocks.len();
-1 97 assert!(steps % n == n / 2);
-1 98 let c1 = count(&distance, n / 2);
-1 99 let c2 = count(&distance, n + n / 2);
-1 100 let c3 = count(&distance, 2 * n + n / 2);
-1 101 println!("part2: {}", quad(c1, c2, c3, steps / n));
-1 102 }
diff --git a/2023/21/test.txt b/2023/21/test.txt
@@ -0,0 +1,11 @@ -1 1 ........... -1 2 .....###.#. -1 3 .###.##..#. -1 4 ..#.#...#.. -1 5 ....#.#.... -1 6 .##..S####. -1 7 .##..#...#. -1 8 .......##.. -1 9 .##.#.####. -1 10 .##..##.##. -1 11 ...........