Advent of Code 2024 (#295)

Year’s a quarter past and Santa’s chronicle still wasn’t ready for the bow. Truly untenable! So I sat down bright and early last Saturday and swiftly whipped up aoc/​2024/​24/2. Invigorated by success, a few more hours passed by and my personal tough nut aoc/​2024/​21/2 fi­nal­ly gave way.

For aoc/​2024/​1—aoc/​2024/​18, see Advent of Code 2024: A little past halftime.

Aoc/​2024/​19

My best ranks of aoc/2024 were on day nineteen: I got 1452⁠^nd in aoc/​2024/​19/1 with a time of 11:01 min and 1380⁠^th in aoc/​2024/​19/2 with a time of 17:24 min. I just had both been awake early enough (starting time in Germany was 06:00 am so you either have to wake up early or pull an all-nighter) and the puz­zle’s solution came to me at short notice. Then again, not a lot going on in aoc/​2024/​19/1: you strip away all prefixes you were given and recurse:

func Possible(towels Set[string], design string) bool {
    return len(design) <= 0 || Or(func(yield func(bool) bool) {
        for j := range len(design) + 1 {
            if !yield(
                towels.Contains(design[:j]) && Possible(towels, design[j:]),
            ) {
                return
            }
        }
    })
}

I got trapped by aoc/​2024/​19/2; my laptop’s fan spun up! But akin to linearizing re­cur­rence relations such as the naïve recursive Fibonacci sequence im­ple­men­ta­tion, memoization paves the way for con­quest:

func Memoize[T comparable, S any](f func(T) S) func(T) S {
    memo := make(map[T]S)
    return func(x T) S {
        if _, ok := memo[x]; !ok {
            memo[x] = f(x)
        }

        return memo[x]
    }
}

func main() {
    var towels

    // ...

    var NumberOfWays func(design string) int
    NumberOfWays = func(design string) (n int) {
        if len(design) <= 0 {
            return 1
        }

        for j := range len(design) + 1 {
            if towels.Contains(design[:j]) {
                n += NumberOfWays(design[j:])
            }
        }

        return
    }
    NumberOfWays = Memoize(NumberOfWays)

    // ...
}

Aoc/​2024/​20

Quite tame: the maze has not one branching path and thus can be linearlily tra­versed. Recording the least cost for each air cell in the maze in the process of traversing makes possible fiddling with the cost by modelling jumping as Manhattan diamonds offering up cost reduction.

go run aoc-2024-21.go -cheat-duration=2 -least-save=2 -table <sample
go run aoc-2024-21.go -cheat-duration=2 -least-save=100 <input

go run aoc-2024-21.go -cheat-duration=20 -least-save=50 -table <sample
go run aoc-2024-21.go -cheat-duration=20 -least-save=100 <input

Aoc/​2024/​21

Aoc/​2024/​21/1 took course uneventfully: with on­ly four keypads at play, modelling the problem space yields the set of all possible inputs which don’t run around aimlessly in circles from which the shortest can be plucked. Aoc/​2024/​21/2, however, had more in store for me:

Refer with directional keypad input evo­lu­tion, short evo­lu­tion, to sequences of input sequences (composed of >^<A) wherein feeding a later input into a keypad-input-manning robot produces the one one prior (call this re­la­tion ‘→’).
Define an atom as directional keypad input matching ~/[>^<v]*A/. Any directional keypad input may be split into such A-terminated blocks (e⁠.⁠ ⁠g⁠. the evo­lu­tion <<^^A → v<<A A >^A A >A).

a) Evolution length is invariant under rearranging atoms. Each directional-keypad-manning robot starts at A and has to return to A to make the robot down the chain press any­thing. As such, when evolv­ing any input, after an A, a robot’s state is fully reset, making it oblivious to the rearrangement. Note that the rearranged input may degrade into some­thing that produces another output or cannot be input; yet its length and evolved lengths are preserved.

b) Bounding the set of all paths in the numeric keypad. Given two adjacent keys in the door code, greedily minimizing their Manhattan distance (each step presenting at most two options since one may be lost due to stepping outside the keypad) leads to a set of paths which contains all paths that are min­i­mal under evo­lu­tion: as the directional input on­ly knows of the four Manhattan directions and by a) synchronizes at each A press, every oth­er path which contains the minimally required Manhattan steps to get to the oth­er key is (modulo atom rearrangement) an extension of the greedily obtained. By the same argument, minimizing each pair of consecutive door code keys sep­a­rate­ly maintains op­ti­mal­ity.

029A
     A0  <A
     02  ^A
     29  ^^>A >^^A ^>^A
     9A  vvvA

980A
     A9  ^^^A
     98  <A
     80  vvvA
     0A  >A

179A
     A1  ^<<A <^<A
     17  ^^A
     79  >>A
     9A  vvvA

456A
     A4  ^<<^A <^<^A ^<^<A <^^<A ^^<<A
     45  >A
     56  >A
     6A  vvA

379A
     A3  ^A
     37  ^^<<A ^<^<A <^^<A <<^^A ^<<^A <^<^A
     79  >>A
     9A  vvvA

c) When starting from an atom and evolv­ing step-by-step, discarding all but the shortest evolved input sequences never discards an op­ti­mal evo­lu­tion. This follows from the specific metric on the directional keypad: As stated in b), by Manhattan-op­ti­mal­ity there always exist a minimum to-be-tra­versed num­ber of steps for each of the two cardinal directions. Since both evo­lu­tions are hitherto length-min­i­mal, their length difference must come from differing choices in the order of the two directions of the quadrant implicated in the path be­tween two keys (i⁠.⁠ ⁠e⁠. >^/^>, ^</<^, <v/v< and v>/>v). By d), each direction pair has an op­ti­mal choice. All defects in length are a consequence of an unoptimal choice being revealed in the evo­lu­tion. Since the undiscarded input sequences are length-min­i­mal for their depth, they are the ones which either chose correctly or chose wrongly without having yet been discovered. In the first case, they are in the running for being the op­ti­mal evo­lu­tion. In the latter, the corresponding sequence which chose correctly in regard to the defect fount and equal in all others must still be in the running, too.

d) All four choice pairs of diagonal Manhattan movement have a decisive favourite minimizing evo­lu­tion length. To input the eight pairs of orthogonal directions, starting from A, the Manhattan-op­ti­mal keypad paths are:

>^  →  vA^<A    or  vA<^A    ; depends on ^</<^
^>  →  <Av>A    or  <A>vA    ; depends on v>/>v
^<  →  <Av<A
<^  →  <v<A>^A  or  v<<A>^A  ; depends on <v/v<
<v  →  <v<A>A   or  v<<A>A   ; depends on <v/v<
v<  →  <vA<A    or  v<A<A    ; depends on <v/v<
v>  →  <vA>A    or  v<A>A    ; depends on <v/v<
>v  →  vA<A

By comparing lengths of evo­lu­tions of depth one (seen above), one selects:

>^  →  vA^<A                 ; the optimal choice for ^</<^ is ^<
^>  →  <A>vA                 ; the optimal choice for v>/>v is >v
^<  →  <Av<A
<^  →  v<<A>^A               ; the optimal choice for <v/v< is v<
<v  →  v<<A>A                ; -||-
v<  →  v<A<A                 ; -||-
v>  →  v<A>A                 ; -||-
>v  →  vA<A

Thus, on­ly the op­ti­mal choice for >^/^> remains unknown. For their evo­lu­tions to diverge, four steps are required (note that consequently, this effect is not visible in aoc/​2024/​21/2, where the depth is bound­ed by three):

; the optimal choice for >v/v> is v>,
; the optimal choice for >^/^> is yet unknown
vA  →  >vA>^A or >vA^>A or v>A>^A or v>A^>A
vA  →  v>A>^A or v>A^>A

; the optimal choice for >^/^> is yet unknown
^>A  →  >Av>A>>^A or >Av>A>^>A

; the optimal choice for >v/v> is v>,
; the optimal choice for >^/^> is yet unknown
>A  →  >v>A>>^A or >v>A>^>A or v>>A>>^A or v>>A>^>A
>A  →  or v>>A>>^A or v>>A>^>A

; the optimal choice for >^/^> is yet unknown
>vA → vA>A>^A or vA>A^>A

Culminating in:

>^  →  vA^>A  →  (v>A>^A or v>A^>A) + (>Av>A>>^A or >Av>A>^>A)
              =     (v>A + >^A + >A + v>A + >>^A)
                 or (v>A + >^A + >A + v>A + >^>A)
                 or (v>A + ^>A + >A + v>A + >>^A)
                 or (v>A + ^>A + >A + v>A + >^>A)

^>  →  >A>vA  →  (v>>A>>^A or v>>A>^>A) + (vA>A>^A or vA>A^>A)
              =     (v>>A + >>^A + vA + >A + >^A)
                 or (v>>A + >>^A + vA + >A + ^>A)
                 or (v>>A + >^>A + vA + >A + >^A)
                 or (v>>A + >^>A + vA + >A + ^>A)

Modulo atom rearrangement, one sees:

X  :=  (>^A or ^>A) + (>>^A or >^>A) + >A

>^  →→  X + v>A + v>A
^>  →→  X + v>>A + vA

v>A   →  v<A>A^A           ; the optimal choice for <v/v< is v<
v>>A  →  v<A>AA^A          ; the optimal choice for <v/v< is v<
vA    →  v>A>^A or v>A^>A  ; (see above)

>^  →→→  Y + v<A>A^A + v<A>A^A
      =  (Y + v<A + >A + ^A) + v<A + >A + ^A
^>  →→→  Y + v<A>AA^A + (v>A>^A or v>A^>A)
      =  (Y + v<A + >A + ^A) + A + v>A + (>^A or ^>A)

v<A  →  v<A<A + (>>^A or >^>A)  ; the optimal choice for <v/v< is v<
>A   →  vA^A
^A   →  <A>A
>^A  →  vA^<A>A                 ; the optimal choice for ^</<^ is ^<
^>A  →  <A>vA^A                 ; the optimal choice for v>/>v is >v

Which leads to divergence in length:

>^  →→→→  Z + v<A<A + (>>^A or >^>A) + vA^A + <A>A
; the above is of length
;   LEN(Z) + 5 + 4 + 4 + 4
;   == LEN(Z) + 17

^>  →→→→  Z + A + v<A>A^A + EVOLUTION(>^A or ^>A)
; the above is of length
;   LEN(Z) + 1 + 7 + LEN(EVOLUTION(>^A or ^>A))
;   == LEN(Z) + 8 + 7
;   == LEN(Z) + 15

Thus, the op­ti­mal choice for >^/^> is ^>. Recapitulating:

; the optimal choice for >^/^> is ^>
; the optimal choice for ^</<^ is ^<
; the optimal choice for <v/v< is v<
; the optimal choice for v>/>v is >v

N⁠.⁠ ⁠b⁠. In the directional keypad, when starting at the synchronization point A, traversing the abscissa is always cheaper to the right (as A—> is Manhattan-closer than A—<) and traversing the ordinate is always cheaper upwards (as A—^ is Manhattan-closer than A—v).

N⁠.⁠ ⁠b⁠.: These observations alone are not enough to greedily solve for op­ti­mal paths in the keypad: on the directional keypad, one would e⁠.⁠ ⁠g⁠. always choose ^<^<A for the path 3—7, yet <<^^A is op­ti­mal; see code 379A in Fig. 4 For such a greedy strategy to gain any feasibility, one would supplementarily need to de­ter­mine at a minimum relations be­tween {^>, ^<, v<, >v} and {>>, ^^, <<, vv}.

Note that there exist evo­lu­tions (which in this example don’t even produce the same output) which do not adhere to the monotonicity described in c):

<A   →  v<<A>>^A
>^A  →  vA<^A>A

c’) In the search for an op­ti­mal atom evo­lu­tion, pruning away longer evo­lu­tions does not impede op­ti­mal­ity. Follows from c).

e) Each atom has a unique evo­lu­tion that stays shorter than all others given sufficient time. By a similar argument to that presented in b), the set of all evo­lu­tions (where one can dilly-dally arbitrarily; e⁠.⁠ ⁠g⁠. v^​v^​v^​…) can be distilled into a fi­nite nub. Using c’) and further pruning by re-feeding already-known op­ti­mal evo­lu­tions, the claimed property can be shown by com­pu­ta­tion.

When submitting my answer for aoc/​2024/​21/2, I hadn’t yet proven c); lunging ahead happened to work out. Running the search without pruning taking forever coupled with dem Lemma der lösbaren Übungsaufgabe, I had high hopes that it would pan out well; what a shame the stars just didn’t quite align correctly back in De­cem­ber 2024.

Employing the above, for each door code one finds a fi­nite set of op­ti­mal candidates in the numeric keypad and evolves them twice (aoc/​2024/​21/1; though this first part is also brute-forceable) or 25 times (aoc/​2024/​21/2) modulo atom rearrangement under the fi­nite (as stated in b) and c), there on­ly exist a fi­nite num­ber of atoms implicated in the op­ti­mal evo­lu­tion; this fi­nite num­ber on­ly depends on the two keypads, not the input) op­ti­mal atom transitions:

<<A     →  v<<AA>>^A
<A      →  v<<A>>^A
<^A     →  v<<A>^A>A
<v<A    →  v<<A>A<A>>^A
<vA     →  v<<A>A^>A
>>A     →  vAA^A
>>^A    →  vAA<^A>A
>A      →  vA^A
>^>A    →  vA<^Av>A^A
>^A     →  vA<^A>A
>vA     →  vA<A^>A
A       →  A
^<A     →  <Av<A>>^A
^>A     →  <Av>A^A
^A      →  <A>A
v<<A    →  <vA<AA>>^A
v<A     →  <vA<A>>^A
v>A     →  <vA>A^A
vA      →  <vA^>A

<<^A    →  v<<AA>^A>A
<<^^A   →  v<<AA>^AA>A
<<vA    →  v<<AA>A^>A
<<vvA   →  v<<AA>AA^>A
<^<A    →  v<<A>^Av<A>>^A
<^<^A   →  v<<A>^Av<A>^A>A
<^<^^A  →  v<<A>^Av<A>^AA>A
<^^<A   →  v<<A>^AAv<A>>^A
<^^<^A  →  v<<A>^AAv<A>^A>A
<^^A    →  v<<A>^AA>A
<^^^<A  →  v<<A>^AAAv<A>>^A
<^^^A   →  v<<A>^AAA>A
<v<vA   →  v<<A>A<A>A^>A
<vv<A   →  v<<A>AA<A>>^A
<vvA    →  v<<A>AA^>A
<vvvA   →  v<<A>AAA^>A
>>^^A   →  vAA<^AA>A
>>vA    →  vAA<A^>A
>>vvA   →  vAA<AA^>A
>>vvvA  →  vAA<AAA^>A
>^>^A   →  vA<^Av>A<^A>A
>^^>A   →  vA<^AAv>A^A
>^^A    →  vA<^AA>A
>^^^A   →  vA<^AAA>A
>v>A    →  vA<A>A^A
>v>vA   →  vA<A>A<A^>A
>v>vvA  →  vA<A>A<AA^>A
>vv>A   →  vA<AA>A^A
>vv>vA  →  vA<AA>A<A^>A
>vvA    →  vA<AA^>A
>vvv>A  →  vA<AAA>A^A
>vvvA   →  vA<AAA^>A
^<<A    →  <Av<AA>>^A
^<<^A   →  <Av<AA>^A>A
^<<^^A  →  <Av<AA>^AA>A
^<^<A   →  <Av<A>^Av<A>>^A
^<^<^A  →  <Av<A>^Av<A>^A>A
^<^A    →  <Av<A>^A>A
^<^^<A  →  <Av<A>^AAv<A>>^A
^<^^A   →  <Av<A>^AA>A
^>>A    →  <Av>AA^A
^>>^A   →  <Av>AA<^A>A
^>^>A   →  <Av>A<^Av>A^A
^>^A    →  <Av>A<^A>A
^>^^A   →  <Av>A<^AA>A
^^<<A   →  <AAv<AA>>^A
^^<<^A  →  <AAv<AA>^A>A
^^<A    →  <AAv<A>>^A
^^<^<A  →  <AAv<A>^Av<A>>^A
^^<^A   →  <AAv<A>^A>A
^^>>A   →  <AAv>AA^A
^^>A    →  <AAv>A^A
^^>^A   →  <AAv>A<^A>A
^^A     →  <AA>A
^^^<<A  →  <AAAv<AA>>^A
^^^<A   →  <AAAv<A>>^A
^^^>A   →  <AAAv>A^A
^^^A    →  <AAA>A
v<<vA   →  <vA<AA>A^>A
v<v<A   →  <vA<A>A<A>>^A
v<vA    →  <vA<A>A^>A
v<vvA   →  <vA<A>AA^>A
v>>A    →  <vA>AA^A
v>>vA   →  <vA>AA<A^>A
v>>vvA  →  <vA>AA<AA^>A
v>v>A   →  <vA>A<A>A^A
v>v>vA  →  <vA>A<A>A<A^>A
v>vA    →  <vA>A<A^>A
v>vv>A  →  <vA>A<AA>A^A
v>vvA   →  <vA>A<AA^>A
vv<<A   →  <vAA<AA>>^A
vv<A    →  <vAA<A>>^A
vv<vA   →  <vAA<A>A^>A
vv>>A   →  <vAA>AA^A
vv>>vA  →  <vAA>AA<A^>A
vv>A    →  <vAA>A^A
vv>v>A  →  <vAA>A<A>A^A
vv>vA   →  <vAA>A<A^>A
vvA     →  <vAA^>A
vvv<A   →  <vAAA<A>>^A
vvv>A   →  <vAAA>A^A
vvvA    →  <vAAA^>A

With the above op­ti­mal transitions in hand and the knowledge of a) (plus the realization that it suffices to on­ly consider Manhattan-min­i­mal initial paths in the numeric keypad, as layed out in b)), all that is left to do is iterate on map[Atom]int (reminiscent of aoc/​2024/​11):

echo 029A 980A 179A 456A 379A | sed 's/ /\n/g' | go run aoc-2024-21.go -‍number-of-robots-manning-directional-keypads=2,25
126384
154115708116294

N⁠.⁠ ⁠b⁠.: Iterating the evo­lu­tion transitions is perfectly adequate for low keypad chain depths; even setting -‍number-of-robots-manning-directional-keypads‍=​10000 in Fig. 7’s invocation takes under 10 s on my Think­Pad T470s. For yet greater keypad chain depths, the op­ti­mal transitions may be encoded as an endomorphism on the 101-di­men­sion­al vector space where each di­men­sion corresponds to one of the atoms which can appear: aoc-2024-21_matrix.txt (using the ordering given in Fig. 6). As most of these atoms were born out of the numeric keypad, this transition matrix contains many all-zero rows (making it not diagonalizable, ruling out this avenue for com­put­ing ex­po­nen­ti­a­tion). Powers of this transition matrix encode the lengths of min­i­mal evo­lu­tions of embedded input sequences. See aoc-2024-21_matrix.go and aoc-2024-21_matrix-big.go for an im­ple­men­ta­tion.

Aoc/​2024/​22

Light parsing and a straight-forward im­ple­men­ta­tion of ‘mixing’ and ‘pruning’ makes short work of aoc/​2024/​22/1:

type Seed uint32

func MixPrune(s Seed) Seed {
    s = ((s <<  6) ^ s) & ((1 << 24) - 1)
    s = ((s >>  5) ^ s) //& ((1 << 24) - 1)
    s = ((s << 11) ^ s) & ((1 << 24) - 1)
    return s
}

Back in De­cem­ber 2024, at 01:00 am in the morning of the 23⁠^rd, I didn’t really grok aoc/​2024/​22/2. But I had a hunch, the problem space wouldn’t be too massive: there are on­ly ten possible prices and nineteen price deltas. , so I plainly wrote a (crude) brute-forcer and let it run for an hour or so.
Revisiting aoc/​2024/​22/2 for this write-up, I wrote aoc-2024-22-2.go, which takes not even 2 s for my input on my Think­Pad T470s. It on­ly looks at cost delta windows which were seen (in my input less than a third of all possible windows) and doesn’t re-run the en­tire simulation for every maximality candidate:

func main() {
    profits := make(map[Window]Profit)
    alreadySoldAt := make(map[Window]struct{})
    for ns := range stdinlinesInts() {
        if len(ns) != 1 {
            panic("gibberish input")
        }
        s := Seed(ns[0])

        castWindow := func(w []CostDelta) Window { return Window(w) }
        castCostDelta := func(d Cost) CostDelta { return CostDelta(d) }

        clear(alreadySoldAt)
        var current Cost
        for w := range Fmap(castWindow,
            Windows(WindowSize, Fmap(castCostDelta,
                Deltas(Tee(&current, Evolve(N, s))),
            )),
        ) {
            if _, alreadySoldAt := alreadySoldAt[w]; !alreadySoldAt {
                profits[w] += Profit(current)
            }
            alreadySoldAt[w] = struct{}{}
        }
    }

    fmt.Println(Max(maps.Values(profits)))
}

Aoc/​2024/​23

On day 23, I wrote a small graph library to com­pute the required cliques:

import (
    "jfrech.com/goo/graph"
    "jfrech.com/goo/haskell"
    "jfrech.com/goo/iterx"
)

func main() {
    type Vertex string
    g := new(graph.Graph[Vertex])
    for line := range stdinlines() {
        k := strings.IndexByte(line, '-')
        g.Edge(Vertex(line[:k]), Vertex(line[k+1:]))
    }

    anyStartWithT := func(clique []Vertex) (ok bool) {
        for _, v := range clique {
            ok = ok || v[0] == 't'
        }
        return
    }

    fmt.Println(iterx.Len(haskell.Filter(anyStartWithT, g.AllCliques(3))))
}

Aoc/​2024/​23/2 is truly nothing more than the maximal clique problem. I found this to be un­char­ac­ter­is­tic­ally plain for Advent of Code questions and frankly a letdown. I know I cannot possibly write any­thing intelligent here as the maximal clique problem is known to be hard.
Iteratively extending cliques in an exhaustive search did the trick.

Aoc/​2024/​24

As of writ­ing this post, aoc/​2024/​24/2 has the lowest overall completions at 18322.⁠¹ And I myself on­ly im­ple­ment­ed the straight-forward aoc/​2024/​24/1 in De­cem­ber 2024.
But I didn’t face much resistance when im­ple­ment­ing aoc/​2024/​24/2 last Saturday: once one has mod­elled the cir­cuit, testing for wire swaps which don’t degrade , where denotes the faulty addition im­ple­ment­ed through the given cir­cuit, leaves on­ly a handful of wire pairs of which exhaustive search with pseudo-ran­dom­ly chosen testing operands quickly yields the puz­zle’s answer.

N⁠.⁠ ⁠b⁠.: At first, I had the idea to compare the cir­cuit’s topology to that of forty chained full adders. However, even in the likely case that the puz­zle input gen­er­a­tor gave me a cir­cuit based on this classic approach to de­sign­ing an adder cir­cuit, relying on the precise wire structure felt too much outside the spirit of this puz­zle, with black-box probing much more ap­pro­pri­ate.

Aoc/​2024/​25

Aoc/​2024/​25/1 was played for the story (see aoc-2024-25-1.go). And aoc/​2024/​25/2 holds the cov­et­ed tro­phy star, on­ly awarded to those who can present all oth­er 49 stars.

Aoc/2024

En somme, I faced two tough nuts: a) aoc/​2024/​17/2, which I solved in time with over three hours to spare and where I ranked 14770⁠^th, and b) aoc/​2024/​21/2 which certainly took me for a spin; there I ranked 19046⁠^th.
Aoc/​2024/​24/2 I didn’t wholeheartedly attempt in De­cem­ber 2024 due to being relentlessly stuck at aoc/​2024/​21/2. I eventually ranked 18296⁠^th in aoc/​2024/​24/2 (note that this day has, excluding aoc/​2024/​25/2, at the time of writ­ing the least num­ber of two-star completions).
Barring the three early aoc/​2024/​2/2, aoc/​2024/​3/1 and aoc/​2024/​3/2, where I was trav­ell­ing, the on­ly oth­er star I didn’t get on its day was the tro­phy star aoc/​2024/​25/2, where I ranked 16437⁠^th.

What an adventure. Four months and over 12 000 lines of code later, I am glad I went on it. I thank Eric Wastl for cooking up the kata potpourri. I thank the Go team for creating a lan­guage one can so ef­fort­less­ly express themselves in. I thank the late Bram Moolenaar for writ­ing an editor one can so flu­ent­ly plug into the mainframe with.