Architeuthis
It’s not always easy to distinguish between existentialism and a bad mood.
13 commentary
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.
thinkers like computer scientist Eliezer Yudkowsky
That’s gotta sting a bit.
11 discussion with spoliers
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.
11 code
// 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"
10 commentary
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.
10 Code
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"
Day 9 seemed pretty straightforward, don’t really have anything to add.