aoc/year2023/
day11.rs

1//! # Cosmic Expansion
2//!
3//! We simplify the problem by treating each axis independently. Consider 4 galaxies on the same
4//! axis at arbitrary non-decreasing values `a b c d`. The pairwise distances are:
5//!
6//! * `b - a`
7//! * `c - b + c - a` => `2c - (a + b)`
8//! * `d - c + d - b + d - a` => `3d - (a + b + c)`
9//!
10//! We can see that each pairwise distance can be expressed as the current coordinate multiplied by
11//! the previous number of galaxies minus the [prefix sum](https://en.wikipedia.org/wiki/Prefix_sum)
12//! of the coordinates of the previous galaxies.
13//!
14//! In the special case that two or more galaxies are at the same coordinate, for example `c == d`:
15//!
16//! * `c - b + c - a` => `2c - (a + b)`
17//! * `d - c + d - b + d - a` => `3d - (a + b + c)` => `2c - (a + b)`
18//! * Total: `2 * [2c - (a + b)]`
19//!
20//! This implies that we only need the *count* of the number of galaxies at each coordinate. A
21//! further simplification is looking at the incremental difference between galaxies.
22//!
23//! | Distance         | Delta (row minus previous row) |
24//! | ---------------- | ------------------------------ |
25//! | 1b - (a)         | 1(b - a)                       |
26//! | 2c - (a + b)     | 2(c - b)                       |
27//! | 3d - (a + b + c) | 3(d - c)                       |
28pub struct Input {
29    xs: [usize; 140],
30    ys: [usize; 140],
31}
32
33pub fn parse(input: &str) -> Input {
34    let mut xs = [0; 140];
35    let mut ys = [0; 140];
36
37    for (y, row) in input.lines().enumerate() {
38        for (x, b) in row.bytes().enumerate() {
39            if b == b'#' {
40                xs[x] += 1;
41                ys[y] += 1;
42            }
43        }
44    }
45
46    Input { xs, ys }
47}
48
49pub fn part1(input: &Input) -> usize {
50    axis(&input.xs, 2) + axis(&input.ys, 2)
51}
52
53pub fn part2(input: &Input) -> usize {
54    axis(&input.xs, 1_000_000) + axis(&input.ys, 1_000_000)
55}
56
57fn axis(counts: &[usize], empty_space: usize) -> usize {
58    let mut result = 0;
59    let mut galaxies = 0;
60    let mut sum = 0;
61
62    for &count in counts {
63        result += count * sum;
64        galaxies += count;
65        sum += galaxies * if count > 0 { 1 } else { empty_space };
66    }
67
68    result
69}
aoc/year2023/day11.rs

aoc/year2023/
day11.rs
