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" 

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.