Advent of Code 2024: A little past halftime. (#293)
Twenty twenty-four is the first year I actively participate in Advent of Code: Each day, I open my digital advent calendar’s door and brood over how best to help the Christmas Elves find their Chief Historian. Although I had heard of Advent of Code and a fellow student had once bothered me two years past with aoc/2022/16/1, where I couldn’t come up with anything smarter than applying brute force and he later mentioned in passing to not have seen anything smarter on forums he lightly perused, this year is the first time I go to bed each day in joyous anticipation of waking up, rushing to code some discrete solver.
Aoc/2024/1
Day one expectedly was but a warm-up; a kata in the classical sense. Solvable in a Haskell one-liner (the second part I didn’t elegantly get transformed into point-free notation):
{- aoc/2024/1/1 -}
main = sum . fmap abs . uncurry (zipWith (-)) . swap . fmap (snd <$>) . swap
. fmap (snd <$>) . break fst . sort . zipWith ($) (cycle [(False,), (True,)])
. fmap (read :: String -> Integer) . words <$> getContents >>= print
Aoc/2024/2
For the second day, I really wanted to use Ivy as Russ Cox had done so effortlessly in 2021 (though I unfortunately drive Ivy not with Acme but with Shell). Yet my APL understanding was too lacklustre to get it to work, making me give up and whip up a straight-forward Go solution (not shown herein). Already on day two, I had taken longer than a day to submit a solution. But I also wasn’t too interested in the early days.
# aoc/2024/2/1
{ cat <<EOI
op incordec rep = and/ ((up rep) == iota rho rep) | (down rep) == iota rho rep
op inrange rep =
srt = rep[down rep]
δ = 1 drop (-1 rot srt) - srt
and/ (δ >= 1), (δ <= 3)
op safe rep = (incordec rep) & inrange rep
EOI
sed 's!^!safe !'
} | ivy | grep 1 | wc -l
Aoc/2024/3
On the third day, I realized everything in Shell. To sum everything up (Legacy sum computes a deprecated file checksum and does not sum up lists of decimal numbers!), I modified my nascent, unit-aware arbitrary-precision calculator dreisatz to read from stdin and not space-join its arguments (the ad-hoc, hacky solution chosen for any new command implementation).
# aoc/2024/3/2
grep -Po "(mul\((0|[1-9][0-9]{0,2}),(0|[1-9][0-9]{0,2})\)|do\(\)|don't\(\))" \
| awk '/^do/{DISABLED=0}; /^don/{DISABLED=1}; /^m/{if(!DISABLED)print}' \
| sed 's![mul()]!!g; s!,!*!g; a+' | xargs | sed 's! !!g; s!\+$!!' \
| sed 's!$!=x!' | xargs dreisatz | grep -o '[0-9]*'
From day four onwards, I primarily wrote Go (aoc/2024/17/2 sees a little C).
Aoc/2024/4
Day four wasn’t too interesting⸺fiddling with two-dimensional char arrays.
Days three and four were coded in swift succession on the ICE from Hamburg to Tübingen. On-board WiFi worked flawlessly, if of a tad high latency.
Aoc/2024/5
Day five, on the other hand, lead me to pass a receiver-bound method to Go’s slices.SortFunc for an elegant core:
// aoc/2024/5/2
type PageOrdering struct { before, after map[int][]int }
func main() {
var tot int
po := NewPageOrdering()
scanner := bufio.NewScanner(os.Stdin)
for scanner.Scan() {
// ...
po.Leq(atoi(nm[:k]), atoi(nm[k+1:]))
}
for scanner.Scan() {
ns := Fmap(strings.Split(scanner.Text(), ","), atoi)
if slices.IsSortedFunc(ns, po.Cmp()) {
continue
}
slices.SortFunc(ns, po.Cmp())
tot += middle(ns)
}
must(scanner.Err())
fmt.Println(tot)
}
Aoc/2024/6
Problems where you don’t need to optimize but only execute hide all of their complexity in parsing. Day six was nothing more. Yet me crudely implementing a (buggy!) representation of one infinite Cartesian plane quadrant *Quadrant[T] would cause confusion the coming days.
Aoc/2024/7
For day seven’s first part, I encoded all possible expressions inside an integer’s bits (since there were only ‘+’ and ‘*’ to choose from). When ‘||’ got added, I made good use of Go’s fresh-out-of-the-oven coroutines:
// aoc/2024/7/2
func Cartesian[S ~[]T, T interface{~int8 | ~int}](x T, n int) iter.Seq[S] {
return func(yield func(S) bool) {
if x <= 0 || n < 0 {
return
}
xs := make(S, n)
for {
if !yield(xs) {
return
}
j := len(xs)-1
xs[j]++
for xs[j] >= x {
if j == 0 {
return
}
xs[j] = 0
j--
xs[j]++
}
}
}
}
Aoc/2024/8
Day eight was fun: type Pt = image.Point is a versatile two-dimensional vector representation and stepping to the end of the board to then step back in gcd-divided steps for aoc/2024/8/2 made for a neat little algorithm. I was, however, surprised to realize Go is missing integer-valued abs and gcd. Not that I had any reason to expect their existence after my many sleepless hours poring over Go’s stdlib.
// aoc/2024/8/1
func Choose2[T any](xs []T) iter.Seq[[2]T] {
return func(yield func([2]T) bool) {
for i := 0; i < len(xs); i++ {
for j := i+1; j < len(xs); j++ {
if !yield([2]T{xs[i], xs[j]}) {
return
}
}
}
}
}
func abs(x int) int {
return x * sgn(x)
}
func sgn(x int) int {
switch {
case x < 0:
return -1
default:
return 0
case x > 0:
return +1
}
}
// aoc/2024/8/2
// Cf. https://en.cppreference.com/w/cpp/numeric/gcd [2024-12-08]
func gcd(x, y int) int {
switch {
case x < 0 && y < 0:
return gcd(-x, -y)
case x < 0:
return -gcd(-x, y)
case y < 0:
return -gcd(x, -y)
case x == 0:
return y
case y == 0:
return x
case x < y:
return gcd(y, x)
default:
return gcd(y, x % y)
}
}
Aoc/2024/9
Brains off, code! was the theme for day nine. I missed a possible “slices.LastIndex” symbol.
// aoc/2024/9/2
func slicesLastIndex[S ~[]E, E comparable](s S, v E) int {
for j := len(s)-1; j >= 0; j-- {
if s[j] == v {
return j
}
}
return -1
}
Aoc/2024/10
Restricted graph hiking lead me to implement an iterator on day ten which proved versatile the coming days.
// aoc/2024/10/1
func CardinalSteps() iter.Seq[Pt] {
return func(yield func(Pt) bool) {
_ = yield(Pt{+1, 0}) && yield(Pt{0, -1}) &&
yield(Pt{-1, 0}) && yield(Pt{0, 1})
}
}
Aoc/2024/11
Day eleven had the affronting moment of implementing aoc/2024/11/1 as build in-memory, then count only to suffer a snub at aoc/2024/11/2 with me owning only non-exponentially-growing memory sticks.
// aoc/2024/11/2
type (
Pebble int
Pebbles map[Pebble]int
)
func blink(pebbles Pebbles) Pebbles {
evolved := make(Pebbles)
for pebble, count := range pebbles {
if pebble == 0 {
evolved[1] += count
} else if s := strconv.Itoa(int(pebble)); len(s) % 2 == 0 {
// strconv.Atoi assumes base 10,
// so the possible leading zeroes don't trigger an octal sniff
evolved[Pebble(atoi(s[:len(s)/2]))] += count
evolved[Pebble(atoi(s[len(s)/2:]))] += count
} else {
evolved[pebble * 2024] += count
}
}
return evolved
}
func main() {
cast := func(x int) Pebble { return Pebble(x) }
pebbles := Count(Fmap(cast, Fmap(atoi, stdinwords())))
for range 75 {
pebbles = blink(pebbles)
}
fmt.Println(Sum(maps.Values(pebbles)))
}
Aoc/2024/12
Finally, a tougher nut to crack: I fiddled with day twelve’s edge finding so long that I had to interrupt my coding to go to the doctor’s office. Fortunately, they offered an open WiFi and I could submit aoc/2024/12/2’s answer from inside the waiting room (the following is a refactored version a few hours after submission).
// aoc/2024/12/2
func main() {
var price int
garden := stdinbyteplane()
step := func(Pt) iter.Seq[Pt] { return CardinalSteps() }
for pt0 := range garden.Components(step) {
area := iterLen(garden.FloodFill(step, pt0))
perim := garden.CountEdges(step, pt0)
price += area * perim
}
fmt.Println(price)
}
// Edge detection via four separate region expansions.
//
// pt0 is the representative of a component.
func (p *Plane[T]) CountEdges(step func(Pt) iter.Seq[Pt], pt0 Pt) int {
var sides [4]Plane[bool]
for pt := range p.FloodFill(step, pt0) {
side := -1
for enws := range CardinalSteps() {
side++
if p.Peek(pt.Add(enws)) != p.Peek(pt) {
sides[side].Poke(pt.Add(enws), true)
}
}
}
var n int
for _, side := range sides {
n += iterLen(side.Components(step))
}
return n
}
Aoc/2024/13
That Friday was my birthday. I planned to wake up early at 5:50am to get going quickly but after falling back asleep for ten minutes, I was in such a daze that I couldn’t invert the 2x2 integer matrix this day’s problem ways about. It took me a whopping 52:32 minutes to submit aoc/2024/13/1 and, as I didn’t brute-force it, 53:13 minutes to submit aoc/2024/13/2.
We suffered a power outageˣwhich brought down my cellar-dwelling Raspberry Pi 2’s by-then-glorious uptimeˣaand I felt too frail to attend a talk I badly wanted to witness.
Birthday dinner with my family later that day was a vile experience, too. Bad puzzle, bad day.
Aoc/2024/14
Aoc/2024/14/2 was utter garbage: Looking at white noise until one finds some picture isn’t solving puzzles. And the resulting christmas tree for day fourteen is framed and tucked arbitrarily somewhere on the bathroom floor. By far the worst Advent of Code question I have seen in my journey (which currently is 107 stars long).
Aoc/2024/15
I love Sokoban. Just not playing it (cf. #258). So on day fifteen I wrote a generic block-pushing-puzzle library for aoc/2024/15/1. When the boxes grew in aoc/2024/15/2, I wrote a companion library for arbitrarily-shaped boxes.
// aoc/2024/15/1
import "jfrech.com/goo/puzzle/boxpush"
func main() {
warehouse := new(boxpush.World)
var robot Pt
var instrs []boxpush.Dir
// parse ...
for _, instr := range instrs {
multipush := true
warehouse.Push(robot, instr, multipush)
if warehouse.Peek(robot.Add(instr.Vec())) == boxpush.Air {
robot = robot.Add(instr.Vec())
}
}
var tot int
bounds := warehouse.Bounds()
for pt, _ := range warehouse.All() {
if warehouse.Peek(pt) == boxpush.Box {
tot += 100 * (pt.Y - bounds.Min.Y) + (pt.X - bounds.Min.X)
}
}
fmt.Println(tot)
}
// aoc/2024/15/2
import "jfrech.com/goo/puzzle/boxpush/glued"
func main() {
warehouse := new(boxpush.World)
// ...
for {
// ...
trafo := func(pt Pt) Pt { return Pt{pt.X*2, pt.Y} }
switch c {
case '@':
robot = trafo(pt)
warehouse.PokeAir(trafo(pt))
warehouse.PokeAir(trafo(pt).Add(Pt{1, 0}))
case '.':
warehouse.PokeAir(trafo(pt))
warehouse.PokeAir(trafo(pt).Add(Pt{1, 0}))
case 'O':
warehouse.PokeAir(trafo(pt))
warehouse.PokeAir(trafo(pt).Add(Pt{1, 0}))
warehouse.PokeBox(boxpush.Box{trafo(pt), trafo(pt).Add(Pt{1, 0})})
}
}
// ...
}
Aoc/2024/16
Day sixteen had be stumped for a bit. I had seen Russ Cox solve aoc/2021/23’s amphipod shuffling using a priority queue based on container/heap and parametric polymorphism. But when I had set up my priority queue, my solver choked on the combinatorial explosion which comes about due to the many equi-costing labyrinth cycle turn options. Figuring out in aoc/2024/16/1 to prune the cost-guided search using a global already-visited-map was insightful. Amending said global history with a record of alternate subsolutions to then reconstruct the union of all optimal paths in aoc/2024/16/2 was eye-opening.
The solver I had christened that day would later be modified to solve aoc/2024/18 and from there grow into a generic library.
Aoc/2024/17
Day seventeen. What a doozy! Aoc/2024/17/1 is as lame as unsalted broccoli. But aoc/2024/17/2, when read wrong, touches on undecidability. After all, defining some imperative DSL, writing a program in it and asking for the inverted program’s output can’t be solved in all generality.
So I tried brute-forcing in Go. That went nowhere, even after hastily parallelizing it to four cores.
I then bypassed my Go-written aoc/2024/17-DSL-interpreter by hand-transpiling the DSL-described program into C, but it never output anything:
/* aoc/2024/17/2 */
#include <stdbool.h>
#include <stdio.h>
bool prog(long long a) {
int force[] = {2, 4, 1, 1, 7, 5, 4, 6, 0, 3, 1, 4, 5, 5, 3, 0, -1};
a = a > 0 ? a : 1;
long long b = 0, c = 0;
int printed = 0;
while (a) {
b = a % 8;
b = b ^ 1;
c = a >> b;
b = b ^ c;
a >>= 3;
b = b ^ 4;
int out = b % 8;
if (force[printed] != out)
return false;
printed++;
}
return printed == (sizeof force / sizeof (int) - 1);
}
int main() {
for (long long a = 1;; a++)
prog(a) && (printf("%lld\n", a), fflush(stdout));
}
I had no angle of approach. From looking at the DSL-written program in question, I knew the flow diagram was a single loop without prelude or epilogue:
; aoc/2024/17/2 2 4 ; bst: b <- a MOD 8 1 1 ; bxl: b <- b XOR 1 7 5 ; cdv: c <- a RSHIFT b 4 6 ; bxc: b <- b XOR c 0 3 ; adv: a <- a RSHIFT 3 1 4 ; bxl: b <- b XOR 4 5 5 ; out: PRINT (b MOD 8) 3 0 ; jzz: IF (a == 0) THEN HALT ELSE LOOP
I tried known compiler techniques: rewrite into SSA form (I knew I wanted to hit exactly 16 loops which I could then unroll) and force values backward:
; aoc/2024/17/2 a := UNKNOWN b := 0 c := 0 a1_0 := a b1_0 := b c1_0 := c b1_1 := a1_0 MOD 8 b1_2 := b1_1 XOR 1 c1_1 := a1_0 RSHIFT b1_2 b1_3 := b1_2 XOR c1_1 a1_1 := a1_0 RSHIFT 3 b1_4 := b1_3 XOR 4 d1 := b1_4 MOD 8 force d1 to 2 force a1_1 to positive ; fourteen more times ; ... force d16 to 0 force a16_1 to 0
But how do you force the bitwise exlusive disjunction of two non-constants? How do you force a rightwards bit shift of two non-constants? Both would imply branching in the analysis which may then again accumulate enough search space that one would be better off brute-forcing.
Think of bit vectors! I thought and calculated an RSHIFT encoding on the level of individual bits:
zabcd >> efg = zabcd >> e00 | zabcd >> 0f0 | zabcd >> 00g = 0000z & 0000e | 00zab & 00fff | 0zabc & 0gggg
Thus I thought of representing each integer as 64 boolean variables, using the above SSA form to construct a non-linear boolean system of equations in thousands of variables, setting all of a’s bits to zero and, starting at the least-significant end, removing these equations until a solution was found (as I needed a solution which minimizes a’s numeric value). I hoped for the somewhat linear nature of SSA as a source to the system of equations to aid in solving it (as SAT, famously, is NP-complete and if I had a nondeterministic Turing machine, I wouldn’t be sitting in front of a forever-toiling C fragment).
By hand I had already proved a’s least significant bits couldn’t as a pack be 001.
But then again: a lot of bookkeeping effort with a high likelihood of producing a hard-to-solve non-linear system of boolean equations. I didn’t follow through on this approach.
What I did is stare at the program in question. I needed to find an a. What effect does changing it have on the program’s behaviour?
Asking the right question is oh so often in itself the answer!
Line three, c1_1 := a1_0 RSHFIT b1_2, is hard to reason about. But b1_1 := a1_0 MOD 8 is known. So the shift can be at most of size seven. The only other place where a is mentioned is in a1_1 := a1_0 RSHIFT 3. And the program only outputs d1 := b1_4 MOD 8. Thus, in each iteration, only seven consecutive bits of a contribute to the output and in each iteration, said contributing bit pack shifts by three leftwards.
Trying out 1024 values for a to produce the first wanted value, locking in all possibilities for the first pack of three bits and repeating fifteen times takes only a tenth of a second on my ThinkPad.
// aoc/2024/17/2
func main() {
var prog *Prog
// parse ...
var force []int = prog.Text()
b0, c0 := prog.B, prog.C
run := func(a int) iter.Seq[int] {
prog.A, prog.B, prog.C = a, b0, c0
prog.Pc = 0
return prog.Run()
}
as := make(map[int]struct{})
for j := range (1 << 7) {
as[j] = struct{}{}
}
for k := range len(force) {
as2 := make(map[int]struct{})
for left := range 8 {
for right := range as {
a := left << (7+3*k) | right
if out, ok := Get(run(a), k); ok && out == prog[k] {
as2[a] = struct{}{}
}
}
}
as = as2
}
a := slices.Min(slices.Collect(maps.Keys(as)))
if !slices.Equal(slices.Collect(run(a)), force) {
panic("unreachable")
}
fmt.Println(a)
}
After submission, I stopped my freshly then-yesterday unboxed ThinkPad T470s (boasting an i7!) whose tight C-written brute-forcing loop had toiled all day, only covering ~0.5% of the search space (assuming 1<<45 <= a < 1<<48, for which I had a slight hunch due to the a <- a RSHIFT 3 line).
Aoc/2024/18
Today, the eighteenth of December 2024, was strikingly similar to aoc/2024/16. And aoc/2024/18/2’s maze un-solving was brute-forceable, not even requiring a primitive optimization such as re-computing a solution only when the known one has been blocked.
Watching optimality’s jittery quiddity is a treat each time around (cf. #230, #161).
- pingback from #295