Advent of Code 2024 Week 2: this time it's all grids, all the time

Solved p1 by graph search before looking a bit closer on the examples and going, oh...

In pt2 I had some floating point weirdness when solving for keypress count, I was checking if the key presses where integers (can't press button A five and half times after all) by checking if A = floor(A) and sometimes A would drop to the number below when floored, i.e. it was in reality (A-1).999999999999999999999999999999999999999999999. Whatever, I rounded it away but I did spend a stupid amount of time on it because it didn't happen in the example set.

Although saying "minimum" was a bit evil when all of the systems had exactly 1 solution (not necessarily in ℕ^2), I wonder if it's puzzle trickiness, anti-LLM (and unfortunate non comp-sci souls) trickiness or if the puzzle was maybe scaled down from a version where there are more solutions.

I made a pretty shitty animation to render the bots and paused it when the tree appeared. This took me way longer than if I had just looked at the 10000 entry text file that I had already made. If I have the energy I’ll make a screen recording.

I randomly got it by sorting for the most robots in the bottom left quadrant while looking for robot concentrations, it was number 13. Despite being in the centre of the grid it didn't show up when sorting for most robots in the middle 30% columns of the screen, which is kind of wicked, in the traditional sense.

The first things I tried was looking for horizontal symmetry (find a grid where all the lines have the same number of robots on the left and on the right of the middle axis, there is none, and the tree is about a third to a quarted of the matrix on each side) and looking for grids where the number of robots increased towards the bottom of the image (didn't work, because turns out tree is in the middle of the screen).

I thinks I was on the right track with looking for concentrations of robots, wish I'd thought about ranking the matrices according to the amount of robots lined up without gaps. Don't know about minimizing the safety score, sorting according to that didn't show the tree anywhere near the first tens.

Realizing that the patterns start recycling at ~10.000 iterations simplified things considerably.

(This is three matrices separated by rows of underscores)

Ok it probably works because it isn't bang center but a bit up of center, most other steps most be half half noise vertically, and the reason it doesn;t minimize on an earlier horizontal step (where every step is mostly half half), is because the middle points on the trunk, that don't contribute to the overall product therefore minimizing it even lower.

So memoisation is predictably needed for part 2 to run in time. It's an O(eⁿ), so it takes seconds by step 39 and minutes by step 47.

Well my pt1 solution would require something like at least 1.5 petabytes RAM to hold the fully expanded array, so it was back to the drawing board for pt2 😁

Luckily I noticed the numbers produced in every iteration were incredibly repetitive, so I assigned a separate accumulator to each one, and every iteration I only kept the unique numbers and updated the corresponding accumulators with how many times they had appeared, and finally I summed the accumulators.

The most unique numbers in one iteration were 3777, the 75 step execution was basically instant.

edit: other unhinged attempts included building a cache with how many pebbles resulted from a number after x steps that I would start using after reaching the halfway point, so every time I found a cached number I would replace that branch with the final count according to the remaining steps, but I couldn't think of a way to actually track how many pebbles result downstream from a specific pebble, but at least it got me thinking about tracking something along each pebble.

// F# as usual
// fst and snd are tuple deconstruction helpers

[<TailCall>]
let rec blink (idx:int) (maxIdx:int) (pebbles : (int64*int64) list) =
    if idx = maxIdx
    then pebbles |> List.sumBy snd
    else
        pebbles
        // Expand array
        |> List.collect (fun (pebbleId, pebbleCount) -> 
            let fpb = float pebbleId
            let digitCount = Math.Ceiling(Math.Log(fpb + 1.0,10))      
            match pebbleId with
            | 0L -> [ 1L, pebbleCount ]
            | x when digitCount % 2.0 = 0.0 -> 
                let factor = Math.Pow(10,digitCount/2.0)
                let right = fpb % factor
                let left = (fpb - right) / factor
                [int64 left, pebbleCount; int64 right,pebbleCount]   
            | x -> [ x * 2024L, pebbleCount ])
        // Compress array
        |> List.groupBy fst
        |> List.map (fun (pebbleId, pebbleGroup) -> pebbleId, pebbleGroup |> List.sumBy snd)
        |> blink (idx+1) maxIdx


"./input.example"
|> Common.parse
|> List.map (fun pebble -> pebble,1L)
|> blink 0 25 
|> Global.shouldBe 55312L

"./input.actual"
|> Common.parse
|> List.map (fun pebble -> pebble,1L)
|> blink 0 75 
|> printfn "Pebble count after 75 blinks is %d" 

Definitely a bit tedious, I had to "play" a whole session to spot bugs that I had. It took me far longer than average. I had buggy dissepearing boxes because of update order, I would reccomend a basic test case of pushing a line/pyramid of boxes in every direction.

The issue with my code was that I didn't make a push atomic, i.e. I would move boxes even if their ancestors couldn't be pushed. Making a list of candidate boxes to push solved this.

Here's the visualisation of the complete solution, though it doesn't show the last 100 frames or so. Please forgive me

https://imgur.com/a/RL50MaC