In the first part of this series, I starting writing solutions for the 2024 Advent of Code (AoC) challenges, each in a different language. To recap, Advent of Code is a yearly programming event. On each day of the advent leading up Christmas, a new challenge is released. Each challenge consists of a problem description and an input file. Challenges generally involve processing the input file to come up with a particular output, which serves as the solution. Each challenge consists of two parts, with the second part being revealed upon completion of the first. Both parts use the same input, which is slightly different for each participant.

Apart from the obvious goals of trying out new and different programming languages and revisiting old favourites, I’m also using this as a way to gauge how good AI (mostly Claude 3.5 Sonnet, running in Cursor) is at writing, explaining and refactoring code in different languages.

My single constraint was to use each language only once. See below for how I broke it.

# Day 6: Python & Inform 7

Challenge: count the locations a guard will visit on a map if he turns right at every obstacle.

As soon as I read this challenge, I regretted using Inform 7 for Day 1. As I noted then, Inform was not hugely suited for number crunching. However, something it is suited to is navigating grids! The problem immediately put me in mind of a maze of twisty little passages, all alike. And Inform even automatically records the number of rooms you visit!

The one problem would be generating the grid itself. As far as I’m aware, Inform 7 provides no method for programmatically creating rooms and the connections between them – you must manually specify each room and its connections, like this:

The Chamber is a room. The Chamber is north of the Hallway.

My input file for this challenge was a 129*129 map, and there was no way I was going to manually specify that many rooms. Thus I would need to generate the Inform code itself programmatically.

This dovetailed nicely with the problem of having already used Inform 7 once this advent. If I generated the Inform 7 code using Python, that would be sort of like using Python for this challenge, and I haven’t used Python yet. And as an added bonus/punishment, it would ensure I didn’t fallback to using Python in later, more difficult challenges.

I started with the Inform 7 code, which is very simple:

"Guard Gallivant Solution" by "David Yates"

Chapter 1 - Game Logic

Forward is a direction that varies. Forward is north. [i.e. var forward = north]

Patrolling is an action applying to nothing.

Understand "patrol" as patrolling.

Carry out patrolling:
	while the player is not in Endgame:
		try going forward. [move in the direction stored in forward]

Instead of going nowhere:
	now forward is right of forward; [i.e. forward = right_of(forward)]
	say "Turning right...";
	say "You have visited [number of visited rooms] rooms so far.";
	try going forward.

To decide what direction is right of (D - direction): [i.e. def right_of(D)]
	if D is north:
		decide on east; [i.e. return east]
	if D is east:
		decide on south;
	if D is south:
		decide on west;
	if D is west:
		decide on north.

Report going to Endgame:
    say "You have visited [number of visited rooms] rooms in total.";
    end the story.

Inform 7 is a rules-based language for building turn-based games. The code defines a bunch of rules (Instead of..., Report... and so), and every turn the engine evaluates and applies a subset of these rules. Rules can be generally applicable (Every turn) or highly specific (Instead of going from the ballroom when the player is Mr Mustard and has the candlestick). These rules are executed in a particular order, according to their placement in different rulebooks. Because the rule in Report going to Endgame is executed before the rule that marks Endgame as a visited room¹, our room visited count will be accurate.

Instead of going nowhere is a rule that runs if the player tries to move in a direction that is not catered for. For example, if I’m in a room with other rooms to the south, east and west, and I try to go north, this rule will be triggered. Therefore, I just needed to create a game map in which rooms adjacent to obstacles did not have connections in that direction.

To solve the challenge, all the player would need to do is type patrol. Once I had the map generated, that is.

I generated the map by reading the file into a Numpy 2D array and then iterating over it. For the starting space and opening spaces on the map, I created rooms. Upon the creation of each room, I checked the cardinal directions from that room and created connections to surrounding open spaces. For rooms on edges of the map, I created connections to a special room, Endgame, which would signify the end of the patrol. For obstacles, I left a comment without creating a room or any connections.

print("INFORM CODE ABOVE")
print("""
Chapter 2 - The Map

Endgame is a room.
"""

import numpy as np

# create grid
grid = np.array([list(line.strip()) for line in open("small.txt")])

# generate I7 code
room_name = lambda y, x: f"P{y}-{x}"
for y, row in enumerate(grid):
    for x, cell in enumerate(row):
        # skip obstacle
        if cell not in '.^':
            continue

        # create room
        this_room = room_name(y, x)
        print(f"{this_room} is a room.")

        # create room connections
        for d, ay, ax in [("west", y, x-1), ("east", y, x+1), ("north", y-1, x), ("south", y+1, x)]:
            if not (0 <= ay < grid.shape[0] and 0 <= ax < grid.shape[1]): # out of bounds
                print(f"Endgame is {d} of {this_room}.")
            elif grid[ay, ax] in '.^': # in bounds and not an obstacle
                print(f"{room_name(ay, ax)} is {d} of {this_room}.")

        # create starting room
        if cell == '^':
            print(f"""
When play begins:
\tnow the player is in {this_room}.""")

The most annoying thing about printing the Inform code from Python, is that both languages have meaningful indentation, but Inform 7 insists that you use tabs and Python prefers spaces. I also might have simplified the code with more strategic room creation – Inform 7 doesn’t strictly require rooms to be declared with X is a room if there’s already a line that says X is [direction] of [existing room].

With my input file, this script produced ~78k lines of Inform code. Unfortunately, when I pasted it into a new project in the Inform 7 IDE, it refused to compile.

Some experimentation and a couple of questions on forums later, I figured out that I could get the code to compile from the command line by passing -no-index to the compiler, which prevented it from trying to generate such things as a world map for the IDE’s internal Index pane.

The Inform 7 compiler produces a source file in Inform 6, which must then be run through the Inform 6 compiler to produce a playable game file for the chosen virtual machine. I wrote a script to go from Python to Inform 7 to Inform 6 to the Glulx format.² From there, I started up the packaged game file in glulxe-term and typed patrol to get my answer. The code for this ran much faster than the code for my Day 1 solution.

Full code for part 1 on GitHub.

The second part of the challenge was to figure out how many different positions a single extra obstacle could be placed in to make the guard move in a loop. The approach to this that seemed obvious to me was this:

1. Run through the map once to build a set of the rooms visited.
2. Restart, run through again with the first room in the set blocked off.
3. Continue until we reach the edge of the map or encounter a loop.
4. Restart and run through again with the next room blocked off.
5. Repeat until we’ve tested blocking every room.

I think this is possible to do in Inform, but I’m not sure how. It would almost certainly be possible to do in Inform 6, a more standard language, though I rather feel that would defeat the point of the challenge. After experiencing repeated freeze-ups and crashes with my attempt at a solution for the sample input, I decided to shelve this one. I’ve uploaded my attempt here.

A pure Python solution is technically in line with the constraint I’ve set for myself, though not quite in the spirit of it (worse than using Inform 6? I’m not sure). With a heavy heart, I wrote the code to solving the second part in Python.

import numpy as np

def patrol(grid, loops=False):
    directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]  # up, right, down, left
    in_bounds = lambda y, x: 0 <= y < len(grid) and 0 <= x < len(grid[0])

    y, x = np.where(grid == '^')[0][0], np.where(grid == '^')[1][0]
    visited = set()
    visited.add((y, x))
    direction = 0
    loop = False

    while in_bounds(y, x):
        my, mx = y + directions[direction][0], x + directions[direction][1]

        if not in_bounds(my, mx):
            break # we've left the map
        if grid[my, mx] == '#':
            direction = (direction + 1) % 4 # hit an obstacle, turn right
            continue

        y, x = my, mx # move

        # Record visited
        current = (y, x, direction) if loops else (y, x)
        if loops and current in visited:
            return (visited, True)

        visited.add(current)

    return (visited, loop) if loops else visited

grid = np.array([list(line.strip()) for line in open("input.txt")])

# Part 1
visited = patrol(grid)
print(len(visited))

# Part 2
loops = 0
for y, x in visited:
    if grid[y, x] == '^':
        continue # can't put an obstacle where the guard is
    grid[y, x] = '#' # new obstacle
    _, loop = patrol(grid, True)
    grid[y, x] = '.' # reset
    loops += 1 if loop else 0

print(loops)

Full code for part 2 on GitHub.

Closing thoughts: I remain very happy with the elegance of my Inform solution for part 1. The main difficulties it presented were in getting it to compile with the full input, not writing the code itself. Attempting and ultimately failing to complete part 2 in Inform was, out of all challenges so far, the one that took me the most time. I still think it’s possible, at least for very small maps, but I don’t quite understand the language or its environment well enough to make it work.

Claude 3.5 Sonnet surprised me with its competence at writing Inform for this challenge, though its contributions ultimately came to nothing. It still made some mistakes, but probably the same ones a human would. Inform might look like natural language, but entry number in my list is valid code and the number entry in my list is a syntax error.

# Day 7: Racket

Challenge: find valid operators for incomplete equations.

I’ve wanted to learn and use Lisp ever since I first read Paul Graham’s famous essay on the language. Over the years, I’ve occasionally toyed with Scheme, Clojure, Racket and Elisp, but I still have yet to do substantial original programming in any of them. So of course this exercise seemed like a good excuse to return to my favourite of the Lisps I’ve tried, Racket.

We begin, as always, by reading and parsing the input file:

#lang racket

; Load the input file
(define filename "input.txt")
(define file (open-input-file filename))
(define input-str (read-string (file-size filename) file))
(close-input-port file)

; Parsing function
(define (parse-input input-str)
  (let ([parse-line (lambda (line) ; Racket lets you use (), [] and {} interchangeably
          (map string->number (string-split (string-replace line ":" ""))))])
    (map parse-line
         (string-split input-str "\n"))))

; Parse the file contents
(define equations (parse-input input-str))

The lines of the file are in the form 190: 10 19, where the first number is the answer you need to find by inserting + or * operators between the rest. Like most functional languages, Racket has the concept of the head and tail of a list, i.e. the first element and the rest of the list.³ As the answer will always be the first element, I’m just stripping out the : and parsing every line into a simple list. So equations will be a list of lists.

To solve this, we’ll invoke a function that takes this list of lists and a list of valid operators. This function will find and apply all possible combinations of the operators to each list. The answers belonging to lists with at least one valid combination will then be summed.

(sum-calibration-equations equations '(+ *))
; the ' makes the operators an inert list rather than an instruction to be executed

But before we actually define sum-calibration-equations, we’re going to need some helper functions. First, apply-op, which we’ll use to apply an operator from our list to two numbers.

(define (apply-op op a b)
  (case op
    ['+ (+ a b)]
    ['* (* a b)]))

Next, a function to generate all possible combinations of length n:

; Recursively generate all possible operator combinations for n numbers
(define (generate-operator-combinations n operators)
  (if (= n 1)
      '(())  ; base case: no operators needed for 1 number
      (for*/list ([ops (generate-operator-combinations (- n 1) operators)] ; outer loop
                  [new-op operators]) ; inner loop
        (append ops (list new-op)))))

for*/list is a way to create a nested for-loop with a single function. The one above is equivalent to the following:

(for/list ([ops (generate-operator-combinations (- n 1) operators)])
    (for/list [new-op operators]
        (append ops (list new-op)))
)

Nested for loops are the hammer I use to solve all of these challenges, so I thought this was really cool.

The last helper function we need is try-combination, which will return the result from trying a list of operators on a list of numbers. Per the instructions, equations must be evaluated left to right.

(define (try-combination ns ops)
  (let loop ([result (first ns)] ; Start with first number
             [rest-nums (rest ns)] ; Rest of the numbers
             [rest-ops ops]) ; All operators
    (if (null? rest-nums)
        ; If there are no more numbers, return the result
        result 
        ; Otherwise apply operator to result & next number
        (loop (apply-op (first rest-ops) 
                       result
                       (first rest-nums))
              (rest rest-nums) ; Continue with remaining numbers
              (rest rest-ops))))) ; Continue with remaining operators

The let here defines a function named loop and immediately calls it with some initial values (so [ result (first ns)] means [parameter-name initial-argument]). It then recursively works down the numbers and operators, accumulating the final result.

Now we can define sum-calibration-equations:

(define (sum-calibration-equations input operators)
  (for*/sum ([calibration-equation input])
    (for/fold ([result 0]) ; assume result is 0, i.e. no valid combo
              ([combo (generate-operator-combinations
                     (- (length calibration-equation) 1) ; 1 fewer op than we have numbers
                     operators)])
    #:break (not (zero? result)) ; break when we find a non-zero result
    (if (= (first calibration-equation)
           (try-combination (rest calibration-equation) combo))
        ; ^ first and rest used to get answer and equation
        (first calibration-equation) ; found a valid answer, return it
        result))))

With Racket, I find myself writing code from the inside out. The core of this function is the if statement, which checks if a particular operator combo produces a valid result for a particular equation. I initially wrapped that in a for*/list, but that gave me every valid result when I only needed one per equation. So the AI suggested I replace it with a for/fold that uses this funky syntax to break. for/fold works a bit like let above.

Finally, I wrapped the for/fold that produced the answers for valid equations in a for/sum to add them all together and get the challenge solution.

I had an inkling that the second part of the challenge would involve additional operators and wrote my code with that assumption. I was correct – part 2 requires you to add the || or concatenation operator, which works like this:

123 || 456
=> 123456

To support this, we just have to add a third option to apply-op:

(define (apply-op op a b)
  (case op
    ['+ (+ a b)]
    ['* (* a b)]
    ['|| (string->number ; Convert numbers to strings, concat, convert back 
          (string-append 
            (number->string a)
            (number->string b)))]))

Then we can call sum-calibration-equations again with our new operator:

(sum-calibration-equations equations '(+ * ||))

Full code on GitHub.

Closing thoughts: I feel like I’m starting to see the much-vaunted power of Lisp through things like for*/list and let – these feel like programming idioms at such a high level that I hadn’t even considered them idioms before. At a few points, I was tempted to mush more of my code together with local function definitions, but that quickly becomes the kind of mess of brackets that makes people complain about Lisp.

This problem was not complex enough to require any of Lisp’s storied meta-programming, but I do feel as though a bit of the spirit of that came through in apply-op. It was immensely satisfying to complete part 2 with such a small change.

I had a bit of help from AI here, but not as much as I thought I’d need. Mostly I had Claude explain different functions to me – he it is pretty good at Racket.

# Day 8: Io

Challenge: map out the antinodes for pairs of antennas.

Io is another language I discovered through Seven Programming Languages in Seven Weeks. It’s a prototype-based language, like JavaScript. Unlike JavaScript, it commits to the prototype thing, implements it well, and doesn’t have any Java-style class syntax to hide it from you. As with Ruby, everything in Io, even numbers. Method invocation (technically message-passing) is so central to the language that it’s automatically invoked when two items are placed side-by-side. For example:

"Hello world" println
==> Hello world

Chaining calls is simple:

"Hello world" exSlice(6)
==> world
"Hello world" exSlice(6) size
==> 5
"Hello world" exSlice(6) size sqrt
==> 2.2360679774997898

Io has very minimal syntax and implements everything with this kind of message passing. For example, if-else control flow can look like this:

(x == 3) ifTrue("Yes" println) ifFalse("No" println)

On the surface, working with operators (a := 1, 1 + 2, 5 - 4, 10 > 1, etc) appears to be an exception, but the operators themselves are only a thin layer of syntactic sugar over message passing (1 + 2 sends the + message to 1 with 2 as an argument i.e. 1 +(2), and := wraps a setter method). Io even lets you define your own operators by adding them to the OperatorTable (which is used to determine precedence). Hmm…

This is another 2D grid challenge, so a bounds-checking operator could be quite useful. Let’s create one:

// Bounds-checking operator
OperatorTable addOperator("<>", 5)
// ^ put it in position 5 in the table so it will be
// evaluated with other comparison operators

Number <> := method(bound, (self >= 0 and self < bound))

Now we can use a <> b to check if a is less than b and non-negative. Because of how Io compiles code, this needs to go in a separate file from the implementation.

doFile("operators.io")
doFile("antinodes.io")

In antinodes.io, we’ll start by reading in the input file:

inputFile := File with("input.txt")
inputFile open
inputText := inputFile readToEnd
inputFile close

We then need to find all the antennas.

findAntennas := method(input,
    antennas := List clone
    input split("\n") foreach(y, line, # foreach provides an index and item
        line foreach(x, cell, // Python- and C-style comments are both valid
            if(cell asCharacter != ".", // without asCharacter we'd get 46
                antennas append(List clone append (x, y, cell))
            )
        )
    )
    antennas
)

As Io is a prototype language, we create new objects by cloning an existing one, usually a base object. List clone creates a new empty list, and List clone append(1, 2, 3) creates a new list containing (1, 2, 3).

Now we can calculate the positions of the antinodes. I found the challenge description a bit confusing, but the diagrams showed that each antinode should be as far from its antenna as it is from the other antenna, but in the other direction. Maybe there’s no way to explain that nicely in words.

calculateAntinodes := method(antennas, mapWidth, mapHeight,
    antinodes := List clone

    isValidPosition := method(x, y, width, height,
        x <> width and y <> height
    )

    addAntinodeIfValid := method(x, y, width, height,
        if(isValidPosition(x, y, width, height),
            antinode := List clone append(x, y)
            if(antinodes detect(n, n == antinode) == nil,
                antinodes append(antinode)
            )
        )
    )

    processAntinodePairs := method(a, b, width, height,
        x1 := a at(0); y1 := a at(1)
        x2 := b at(0); y2 := b at(1)
        dx := x2 - x1; dy := y2 - y1

        addAntinodeIfValid(x1 - dx, y1 - dy, width, height)
        addAntinodeIfValid(x2 + dx, y2 + dy, width, height)
    )

    antennas foreach(i, a,
        antennas foreach(j, b,
            if(a != b and a at(2) == b at(2),
                processAntinodePairs(a, b, mapWidth, mapHeight)
            )
        )
    )

    antinodes
)

Finally, we put it all together with this:

inputFile := File with("input.txt")
inputFile open
inputText := inputFile readToEnd
inputFile close

antennas := findAntennas(inputText)
mapWidth := inputText split("\n") at(0) size
mapHeight := inputText split("\n") size

calculateAntinodes(antennas, mapWidth, mapHeight) size println

For the second part of the challenge, we need to get antinodes at any (map-bound) distance from their antennas, as well as antinodes on the antennas themselves. This can be integrated into calculateAntinodes with an extra parameter:

calculateAntinodes := method(antennas, mapWidth, mapHeight, partTwo,
    antinodes := List clone

    isValidPosition := method(x, y, width, height,
        x <> width and y <> height
    )

    addAntinodeIfValid := method(x, y, width, height,
        if(isValidPosition(x, y, width, height),
            antinode := List clone append(x, y)
            if(antinodes detect(n, n == antinode) == nil,
                antinodes append(antinode)
            )
        )
    )

    processAntinodePairs := method(a, b, width, height,
        x1 := a at(0); y1 := a at(1)
        x2 := b at(0); y2 := b at(1)
        dx := x2 - x1; dy := y2 - y1

        if(partTwo,
            # Part 2: Add antennas as antinodes and calculate full path
            addAntinodeIfValid(x1, y1, width, height)
            addAntinodeIfValid(x2, y2, width, height)

            # Find antinodes in both directions
            pos := list(x1, y1)
            while(isValidPosition(pos at(0) - dx, pos at(1) - dy, width, height),
                pos = list(pos at(0) - dx, pos at(1) - dy)
                addAntinodeIfValid(pos at(0), pos at(1), width, height)
            )

            pos = list(x2, y2)
            while(isValidPosition(pos at(0) + dx, pos at(1) + dy, width, height),
                pos = list(pos at(0) + dx, pos at(1) + dy)
                addAntinodeIfValid(pos at(0), pos at(1), width, height)
            )
            ,
            # Part 1: Only check one point in each direction
            addAntinodeIfValid(x1 - dx, y1 - dy, width, height)
            addAntinodeIfValid(x2 + dx, y2 + dy, width, height)
        )
    )

    antennas foreach(i, a,
        antennas foreach(j, b,
            if(a != b and a at(2) == b at(2),
                processAntinodePairs(a, b, mapWidth, mapHeight)
            )
        )
    )

    antinodes
)

Full code on GitHub.

Closing thoughts: Io code looks a little strange at first, but once you get into it it doesn’t feel too different from any other high-level imperative language. I’m glad I used it right after Racket, because the languages have some interesting similarities and contrasts. Io is about as syntactically minimal as Lisp, but it’s much easier to read for two reasons:

1. Logic flows left to right.
2. Function execution is signalled by white space rather than brackets ("Hello world" println vs (display "Hello world")).

Fittingly, Io has similarly powerful reflection and metaprogramming abilities, which I didn’t really need for this simple challenge. I also made no use of its concurrency features or even custom objects, but I’m glad I found a use for OperatorTable.

Claude surprised me with its familiarity with this relatively obscure language, though I didn’t use it much besides having it do some refactoring. The official Io tutorial, which is more a of cheatsheet, was also very helpful.

# Day 9: J

Challenge: pack items from the right side of a list into empty spaces on the left.

For this challenge, I chose J, a language I’ve been intrigued by since reading about it on James Hague’s Programming in the 21st Century blog. It’s a very terse language capable of producing programs that look like a jumbled mess of characters, and so fairly intimidating at first glance.

J is an array programming language, in the lineage of APL. Unlike APL, it does not require a special keyboard to program in, as it only uses ASCII characters. An array programming language felt like a good choice for this challenge, as the input is a single very long list.

As the J Primer will tell you, users of J prefer to use natural language terminology when talking about elements of J. Sentences (statements) are made up of words, some of which are verbs (functions), others of which are nouns (variables/literals) and still others of which are adverbs or even copulas.

Despite all this talk of words, most of J’s syntax consists of symbols. There are single symbols, such as {, +, # and %, all of which do slightly different things than you might expect from other languages. Then there are words made out of groups of symbols, like |. <" and ~:. Occasionally you get single letters followed by dots: I. and E.. The things that look most like words, for. and if. and break., are not nouns or verbs, but control structures.

Each verbs can each have two forms: monadic and dyadic. The first takes one argument and the second takes two. These forms tend to do related but different things. For example, the monadic # a will count the values in a, and the dyadic 3 # a will create three copies of a.

This may start to make more sense as we get to some actual code. So let’s read the input file:

input =: fread 'input.txt' NB. read file
ints =: ". each input NB. convert each character to a number

The first line is simple enough, but what does ". mean? For the answer to this and many more questions we’ll have throughout this section, I direct you to NuVoc, a syntax cheat-sheet on the J wiki that I found invaluable for completing this challenge. This is the verb Do, which executes a sentence. If the sentence to be executed is a string containing numeric character(s), executing it will turn it into number.

   ". '1'
1

Now let’s write a function to expand the compressed representation of our disk map, as done in the challenge instructions.

NB. Expand to disk map
expand =: 3 : 0
    fileID =. 0
    disk =. 0 $ a: NB. empty array
    for_size. y do.
        if. 2 | size_index do. NB. free space
            NB. append a boxed . to disk SIZE times
            disk =. disk , (; size) # <'.'
        else. NB. file
            NB. append the boxed fileID to disk SIZE times
            disk =. disk , (; size) # <": fileID
            fileID =. fileID + 1
        end.
    end.
    disk
)

What does any of this mean? Like many functional languages, code here must be read right to left. Beyond that, writing J is an exercise in memorising symbols.

• 3 : 0 is used to define a monadic function verb. We could use 4 : 0 to define a dyadic verb. Monadic verbs take the argument y and dyadic verbs take the arguments x and y.
• =. is used to define a local variable. =: is for globals.
• Dyadic | is modulo.
• Dyadic , is append (used for both arrays and strings).
• Monadic < is used to box some input. Boxing allows us to make arrays containing different types. So we can make an array of numbers for the file IDs and strings (’.’) for the empty spaces. Without boxing, we’d need to make a string, which makes shifting things around problematic for file IDs greater than 9.
• Monadic ; is used to unbox, or raze values. We have to unbox numbers before we can do numeric operations on them.
• Dyadic # makes copies. For example, 3 # '.' would produce ....
• ) signals the end of the verb definition. It is intentionally unmatched.

Next, we’ll shift the file IDs on the right side of our disk map to free spaces on the left. We’ll do this by making lists of all the indices of spaces and files, reversing the list of file indices, and then using them to make substitutions.

NB. Move file segments into free spaces
fragment =: 3 : 0
    spaces =. I. y = <'.' NB. indices of free spaces
    files =. |. I. y ~: <'.' NB. indices of files in reverse order
    index =. 0
    for_space. spaces do.
        if. space > index { files do.
            break. NB. this space is to the right of this file, so we're done
        end.
        NB. replace current space with  current file segment
        y =. ((index { files) { y) space } y
        NB. replace current file segment with space
        y =. (<'.') (index { files) } y
        index =. index + 1
    end.
    y
)

Again:

• Dyadic ~: is not equals.
• Mondadic I. gets the indices of a list matching some condition. This was probably the second most useful word in this challenge.
• Monadic |. reverses its input.
• Dyadic { is array indexing (1 } y means y[1]).
• Dyadic } is an adverb that makes a copy of y, using x to replace the contents of location(s) m – x m} y. For example, 'z' 0 } 'abc' would make 'zbc'. And 'yz' 0 2 } 'abc' would make 'ybz'.

Making lists of indices was a little confusing at first, but it worked out well.

To get the answer for the first part of the challenge, we need a checksum function, which discards the spaces, multiplies the file IDs by their new indices and adds everything together.

checksum =: 3 : 0
    ints =. (<0) (I. y = (<'.')) } y
    +/ (i. # ints) * ; ints
)

In the first line, I used } to replace all .s with 0s. In the second, I did the checksum calculation. / is an adverb that inserts the verb on its left between the items of y. So +/ allows us to sum a list.

Appropriately for a challenge themed around disk defragmentation, the second part requires us to move files into free space contiguously, rather than chopping them up like we did in the first part.

At first, I considered trying to complete this challenge using the original input rather than the disk map. I made a bit of progress before realising that I would need to fit files into spaces larger than their sizes, thus creating new spaces and messing up the indices. Nevertheless, the defragment function I wrote to solve this part of the challenge does use the original input before expanding it into a disk map.

NB. Move files into free spaces, contiguously
defragment =: 3 : 0
    NB. make a backwards list of even integers half the length of y
    file_ids =. |. i.(>. -: (#y))
    disk =. expand y

    for_fid. file_ids do.
        positions =. (< fid) I.@:E. disk NB. indices of file ID in disk map
        file =. (# positions) # (< fid) NB. full size file
        space =. (# positions) # <'.' NB. same sized space
        space_enough =. {. space I.@:E. disk NB. find earliest big enough free space
        NB. only move if we have enough space and aren't moving right
        if. space_enough *. space_enough < {. positions do.
            disk =. (file) (space_enough +i.#file) } disk NB. replace free space with file
            disk =. (space) (positions) } disk NB. replace file with free space
        end.
    end.
    disk
)

This function loops backwards through file IDs, finds their positions in the disk map, finds the earliest free space large enough to fit the file, and then swaps the file for the free space, continuing until the next space is the right of the next file.

New symbols here:

• -: is the idiomatic J way to halve something, rather than dividing it by 2 (% 2).
• E. finds matches. @, a conjunction, composes two verbs. Composing I. with E. gives us the indices of each match.
• {. gets the head, or first element, of y.
• *. is boolean AND.
• i.#file creates a new list the same size as file, starting at 0 (0 1 2...).⁴ Then space_enough + adds space_enough to each value therein. This gives us all the indices we need from the start of the space to insert our file with }.

Echoing the disk map at each step gave me the following output for the challenge’s sample data:

Full code on GitHub.

Closing thoughts: J is not a beginner-friendly language. Beyond just knowing what each symbol does, you need to make sure you’re using it in the right position relative to everything else on a given line. The error messages are singularly terse and unhelpful: the J console spits out the offending line and some text like domain error (problem with types), length error (array access issues), syntax error or even rank error. Because each line packs in so much functionality, knowing only the error type and line can still leave you scratching your head.

I found Claude Sonnet 3.5 markedly better than ChatGPT 4o at writing J, though neither could write very much correct J code at a time. To make matters worse, trying to Google anything about programming in J mostly gave me answers for Java (and sometimes Julia). Fortunately, the J Wiki is a pretty good resource, particularly the NuVoc page.

# Day 10: Solidity

Challenge: find all the possible hiking trails on a map.

Solidity is a C-like language for writing smart contracts for the Ethereum blockchain (and other EVM-based chains). Smart contracts are basically classes with (usually) a bunch of publicly callable functions. These functions can be called by other contracts and Ethereum end-users to do things like transfer and swap different cryptocurrency tokens, invest funds in lending pools, and much else besides. Code that makes changes to the chain state (e.g. sending tokens from one wallet to another) must be executed across the network, and therefore each opcode has an associated cost (called gas). For this reason and others, I’ll be running the code in a local dev environment, provided by Foundry.

Solidity is not particularly well suited to solving Advent of Code challenges, particularly ones involving strings. So it helps that the input for this challenge is a grid of numbers.

To start off with, a HikingTrail smart contract:

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

contract HikingTrail {
    // the map
    uint8[50][50] public map;
    uint8 public rows = 50;
    uint8 public cols = 50;

    // navigation helpers
    struct Position {
        uint8 row;
        uint8 col;
        uint8 height;
    }
    int8[4] rowDirections = [int8(0), 0, -1, 1];
    int8[4] colDirections = [int8(-1), 1, 0, 0];

    // pass map in on deployment
    constructor(uint8[50][50] memory inputMap) {
        map = inputMap;
    }

    // call this function to get the answer
    function calculateTrailheadScores() external view returns (uint256 score) {
        for (uint256 i = 0; i < rows; i++) {
            for (uint256 j = 0; j < cols; j++) {
                // calculate the score for each trailhead (0) on the map
                if (map[i][j] == 0) {
                    score = calculateScoreForTrailhead(uint8(i), uint8(j));
                }
            }
        }
    }
}

A few notes:

• constructor is a special function that gets called when a contract is deployed on the blockchain. It can take arguments, allowing us to make this contract a general Advent of Code solution.
• I used the smallest signed and unsigned integer types, int8 and uint8, because the numbers in map go from 0 to 9. Everywhere else, I used uint256, as that’s the default.⁵

The real work gets done in calculateScoreForTrailhead, which uses a stack to exhaustively check each position on the trail for viable next steps.

    function calculateScoreForTrailhead(
        uint8 startRow,
        uint8 startCol
    ) internal view returns (uint256 score) {
        // init some vars
        bool[50][50] memory visited;
        Position[] memory stack = new Position[](uint256(rows) * uint256(cols));
        // uint8s in the above would overflow, causing a revert
        uint256 stackSize = 0;
        int8 x;
        int8 y;

        // push the start position onto the stack
        stack[stackSize++] = Position(startRow, startCol, 0);
        visited[startRow][startCol] = true;


        while (stackSize > 0) {
            // pop the top position off the stack
            Position memory current = stack[--stackSize];

            if (current.height == 9) {
                // we've reached the end of the trail
                score++;
                continue;
            }

            // check all 4 directions
            for (uint256 d = 0; d < 4; d++) {
                y = int8(current.row) + int8(rowDirections[d]);
                x = int8(current.col) + int8(colDirections[d]);

                // skip if out of bounds
                if (!(y >= 0 && newRow < int8(rows)
                      && x >= 0 && newCol < int8(cols))) continue;

                // if it's a new position at a reachable height, push it onto the stack
                if (!visited[uint8(y)][uint8(x)] &&
                    map[uint8(y)][uint8(x)] == current.height + 1
                ) {
                    visited[uint8(y)][uint8(x)] = true;
                    stack[stackSize++] = Position(
                        uint8(y),
                        uint8(x),
                        current.height + 1);
                }
            }
        }
    }

To fulfill my goal of reading the input file natively wherever possible, I wrote the following Forge test to execute the solution:

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.13;

import {Test, console} from "forge-std/Test.sol";
import {HikingTrail} from "../src/HikingTrail.sol";

contract HikingTrailTest is Test {
    HikingTrail public trail;

    function parseInput(string memory input) public pure returns (uint8[50][50] memory) {
        bytes memory inputBytes = bytes(input);
        uint8[50][50] memory map;

        uint8 x = 0;
        uint8 y = 0;

        for (uint256 i = 0; i < inputBytes.length; i++) {
            uint8 c = uint8(inputBytes[i]);
            if (c >= 48 && c <= 57) { // digit
                c -= 48;
                map[x][y] = c;
                x++;
            }
            else if (c == 10) { // newline
                x = 0;
                y++;
            }
        }

        return map;
    }

    function setUp() public {
        string memory input = vm.readFile("input.txt");
        uint8[50][50] memory map = parseInput(input);

        trail = new HikingTrail(map);
    }

    function test_calculateTrailheadScores() public {
        uint256 score = trail.calculateTrailheadScores();
        console.log("Score:", score);
    }
}

This required adding below line to the project’s foundry.toml, as Solidity code isn’t usually expected to access random files:

fs_permissions = [{ access = "read", path = "input.txt" }]

I could then execute the solution with forge test -vv. This spins up a local EVM blockchain, deploys HikingTrail and HikingTrailTest, and runs all the functions in the latter starting with test (also the setUp function).

The amount of processing needed quickly ran into EVM memory limits. To get around that, I rewrote calculateTrailheadScores as a batch function, which stores the last processed row and column. As calculating scores now involved writing to contract storage, it would no longer be a gas-free action for end users. If I were optimising for that, I would have made the batching take a start position. Or not written this code in Solidity.

    function calculateTrailheadScoresBatch(uint8 batchSize) public {
        for (uint256 i = lastProcessedRow; i < rows; i++) {
            for (uint256 j = (i == lastProcessedRow ? lastProcessedCol : 0); 
                j < cols; j++) {
                if (map[i][j] == 0) {
                    totalScore += calculateScoreForTrailhead(uint8(i), uint8(j));
                }
                if (--batchSize == 0) {
                    lastProcessedRow = uint8(i);
                    lastProcessedCol = uint8(j) + 1;
                    if (lastProcessedCol == cols) {
                        lastProcessedRow++;
                        lastProcessedCol = 0;
                    }
                    return;
                }
            }
        }
        lastProcessedRow = 0;
        lastProcessedCol = 0;
    }

The new test function looked like this:

    function test_calculateTrailheadScores() public {
        while (trail.lastProcessedRow() < 50) {
            trail.calculateTrailheadScoresBatch(100); // don't change this
        }
        console.log("Score:", trail.totalScore());
    }

Most other batch sizes still led to a MemoryOOG error, but 100 managed to get the right answer.

The second part of the challenge involved finding the trailhead rating, which was the number of unique trails it branched into. This was actually simpler than the first part. I used essentially the same code, minus the previously visited check.

    function calculateRatingForTrailhead(
        uint8 startRow,
        uint8 startCol
    ) public view returns (uint256 rating) {
        // init some vars
        Position[] memory stack = new Position[](uint256(rows) * uint256(cols));
        uint256 stackSize = 0;
        int8 x;
        int8 y;

        // push the start position onto the stack
        stack[stackSize++] = Position(startRow, startCol, 0);

        while (stackSize > 0) {
            // pop the top position off the stack
            Position memory current = stack[--stackSize];

            if (current.height == 9) {
                // we've reached the end of the trail
                rating++;
                continue;
            }

            // check all 4 directions
            for (uint256 d = 0; d < 4; d++) {
                y = int8(current.row) + int8(rowDirections[d]);
                x = int8(current.col) + int8(colDirections[d]);

                // skip if out of bounds
                if (!(y >= 0 && y < int8(rows)
                    && x >= 0 && x < int8(cols))) continue;

                // if it's at a reachable height, push it onto the stack
                if (map[uint8(y)][uint8(x)] == current.height + 1) {
                    stack[stackSize++] = Position(
                        uint8(y),
                        uint8(x),
                        current.height + 1
                    );
                }
            }
        }
    }

The same batching approach used with the score was required to calculate the rating.

As I briefly mentioned earlier, gas is the unit of cost for running code on the Ethereum blockchain. Each instruction, such as a variable read, a loop, or an assignment, has an associated gas cost. The price of gas fluctuates depending on how congested the network is. Right now, it would cost around $120 (US) to deploy HikingTrail to Ethereum mainnet. To actually calculate the answers would cost this much:

Full code on GitHub.

Closing thoughts: As much as Solidity is not designed for this sort of thing, it was pretty simple to get this solution working. Solidity developers prize readability and efficiency,⁶ so you won’t see a lot of weird functional programming-style trickery. Its syntax is mercifully free of weird sigils (a relief after J). In many other languages, the memory and storage keywords would probably be % and $ or something equally obscure.

Next up, Days 11–15. I make no promises about having it up before Christmas of this or any other year.