Leaving something to run for 20-30 minutes expecting nothing and actually getting a valid and correct result: new positive feeling unlocked.

Now to find out how I was ideally supposed to solve it.

I got a different solution than the one given on the site for the example data, the sequence starting with 2 did not yield the expected solution pattern at all, and the one I actually got gave more bananas anyway.

The algorithm gave the correct result for the actual puzzle data though, so I’m leaving it well alone.

Also the problem had a strong map/reduce vibe so I started out with the sequence generation and subsequent transformations parallelized already from pt1, but ultimately it wasn’t that intensive a problem.

Toddler’s sick (but getting better!) so I’ve been falling behind, oh well. Doubt I’ll be doing 24 & 25 on their release days either as the off-days and festivities start kicking in.

DFS (it’s all dfs all the time now, this is my life now, thanks AOC) pruned by unless-I-ever-passed-through-here-with-a-smaller-score-before worked well enough for Pt1. In Pt2 in order to get all the paths I only had to loosen the filter by a) not pruning for equal scores and b) only prune if the direction also matched.

Pt2 was easier for me because while at first it took me a bit to land on lifting stuff from Djikstra’s algo to solve the challenge maze before the sun turns supernova, as I tend to store the paths for debugging anyway it was trivial to group them by score and count by distinct tiles.

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)

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.

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" 

Yeah basically if you were doing DFS and forgot to check if you’d already visited the next node you were solving for pt2, since the rule about the next node always having a value of +1 compared to the current one was already preventing cyclic paths.

Hardly a groundbreaking implementation but I hadn’t posted actual code in a while so

(* F# - file reading code and other boilerplate omited *)

let mapAllTrails (matrix : int array2d) =
    let rowCount = matrix |> Array2D.length1
    let colCount = matrix |> Array2D.length2

    let rec search (current:int*int) (visited: HashSet<int*int>) (path: (int*int) list) : (int*int) list list= 
        let (row,col) = current
        let currentValue = matrix.[row,col]

        // Remove to solve for 10-2
        visited.Add (row,col) |> ignore

        // If on a 9 return the complete path
        if currentValue = 9 then [List.append path [row,col] ]
        // Otherwise filter for eligible neihboring cells and continue search
        else                    
            [ row-1, col;row, col-1; row, col+1; row+1,col]
            |> List.filter (fun (r,c) -> 
                not (visited.Contains(r,c))
                && r >= 0 && c>=0 && r < rowCount && c < colCount
                && matrix.[r,c]-currentValue = 1 )
            |> List.collect (fun next ->
                [row,col] 
                |> List.append path  
                |> search next visited)

    // Find starting cells, i.e. contain 0
    matrix
    |> Global.matrixIndices
    |> Seq.filter (fun (row,col) -> matrix.[row,col] = 0)
    // Find all trails starting from those cells and flatten the result
    |> Seq.collect (fun trailhead -> search trailhead (HashSet<int*int>()) [])
    

"./input.example"
|> Common.parse 
|> mapAllTrails
|> Seq.length
|> Global.shouldBe 81

"./input.actual"
|> Common.parse 
|> mapAllTrails
|> Seq.length
|> printfn "The sum total of trail rankings is %d"

Used the coordinates of every two same type frequences to create the ilnear equation (y = ax + b) and then fed it all the matrix coordinates to see which belonged to the line. To get the correct number of antinodes I had to check for |y - ax - b| < 0.0001, otherwise I got around 20 too few.

// F#
let isLegit ((total: int64), (calibration : int64 array)) = 

    let rec search (index : int) (acc: int64) =
        let currentValue = calibration.[index]
        
        [Add; Times; Concat] // operators - remove 'Concat' to solve for 7-1
        |> List.exists (fun op -> // List.exists returns true the first time the lambda returns true, so search stops at first true
                match op with // update accumulator
                | Add -> acc + currentValue
                | Times -> acc * currentValue
                | Concat -> int64 (sprintf "%d%d" acc currentValue)
                |> function // stop search on current accumulator value (state) exceeding total, or being just right
                | state when state > total -> false
                | state when state = total && index < (calibration.Length-1) -> false // this was the problem
                | state when state = total && index = (calibration.Length-1) -> true
                | state -> // stop if index exceeds input length, or continue search
                    if index+1 = calibration.Length
                    then false
                    else search (index+1) state
        )
     
    // start search from second element using the first as current sum
    search 1 calibration.[0]

EDIT: total && index < (calibration.Length-1) -> false – i.e. stop if you reach the total before using all numbers, well, also stops you from checking the next operator, So, removing it worked.

Rubber ducking innocent people on the internets works, who knew.