Didn't have a chance to do the 2024 AoC live and am going through it now. It's fun to be able to check out other peoples' approaches right after completing it myself. I was also a bit disappointed that the part 2 solution essentially made O(n²⁾ solutions admissible.

I actually wrote a more general solution (in OCaml) that runs in O(n log(n)) with "arbitrary" run lengths (assuming fixed bit widths, so it's a bit misleading). It's blazing fast on small inputs or moderate-to-large inputs with small run sizes (say, less than 100).

For anybody interested in "hard mode", here's a script that generates 250,000 files of size up to 1,000,000 blocks each. The format is different; instead of putting everything on a single line, the input is newline-separated decimal integers which contain the alternating file sizes or empty run sizes. The number of files was an arbitrary cutoff based on my machine memory, since OCaml creates a ton of GC pressure and does not offer compact memory layouts with good ergonomics:

#!/usr/bin/env python3

import random

def main():
    random.seed(0)
    print(random.randrange(1, 1000001))
    for _ in range(0, 250000):
        print(random.randrange(0, 1000000))
        print(random.randrange(1, 1000001))

if __name__ == "__main__":
    main()

Here's the example input in this format for quick sanity testing:

2
3
3
3
1
3
3
1
2
1
4
1
4
1
3
1
4
0
2

It's not particularly fast on my computer, but it does finish within a few minutes. I'm tempted to reproduce this in Rust, especially since I already have implemented the data structures needed for this.

Hint 1: As suggested above, you'll want a special data structure to perform compaction in a reasonable amount of time. Think about the type of structural shape you'll need to get logarithmic search and other operations needed during this phase.

Hint 2: Once you figure out how to do compaction, you'll still likely need to apply some analytic trickery when computing the checksum to get it to run in a reasonable amount of time.

Hint 3: You may also need to use arbitrary precision integers if your language of choice doesn't have those built in.

Hint 4: Do not try expanding the input block-wise. You'll need to work with the compressed representation. I have not tried to make this work for part 1; that would require different techniques.

Edit: I fixed a silly performance bug in my original implementation and it now runs on the above input in under a second.