Advent of Code 2024: Days 1–5

Advent of Code (AoC) 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.

To give a trivial example, the first part of a challenge could be to count the number of times the word “Christmas” appears in a text file and the second part could be to count the number of lines in the file which contain the word “Christmas”. In both instances, the count serves as the challenge solution.

Because all of the challenges are designed to provide a short answer string, you can solve them in whatever way you choose, pursuing other goals along the way. You might choose to do them all in your favourite language and see how concise and/or fast you can make the solution. Or maybe you want to use the challenges to help you learn a new language. You could do each challenge in a different language. It’s even conceivable that you could print the challenge input files and solve them with a notebook and pen.

For this year’s event, I decided it would be fun to try each one in a different language. Some of the languages I’ve chosen are ordinary, mainstream programming languages that I’ve used in the past or want to use more in the future. Others are domain-specific and/or idiosyncratic languages that may not be obvious (or good) choices for the challenges I’ve applied them to – though I’ve not gone so far as to torture myself with Brainfuck or Malbolge.

With the constraint of using each language only once, and a bias for languages I know, I’ve either gone for the language that best fits the problem, or one where the problem won’t be overly painful to solve. I’ve used AI here and there to assist with the languages I know less well, but not by prompting it with the puzzle text wholesale. Part of the aim of this exercise is for me to gauge how good common AI models are at different languages.

# Day 1: Inform 7

Challenge: find the sum of diffs between two lists.

Inform 7 is a programming language designed to closely resemble normal human prose and used for making text adventure games (interactive fiction if you’re feeling literary). I’ve written about it previously here. I chose it for the first day because it is highly unsuited to the sort of programming required for these challenges, so it seemed like a good idea to get it out of the way for an easy one.

The kind of thing you’re suppose to make with Inform.

The kind of thing you’re suppose to make with Inform.

I thought I might be the first person to attempt an AoC challenge in Inform, but as it turns out someone else beat me to it, encountering pain points such as having to implement arithmetic operations for strings because Inform only offers up to 32-bit signed integers.

This challenge was a lot simpler, though it still presented its share of snarls. The input data consisted of two columns of numbers, so I decided to represent it with a table. Initially, I wanted to populate the table by reading from the input file, but the input file was too large for this to work. I considered a few different ways to solve this, but ultimately went the easy route and copied the input into a manually defined table, replacing the three-space column separators with tabs.

"Historian Hysteria Solution" by "David Yates"

[Inform games need at least one room to compile.]
The Chief Historian's Office is a room. "Elves run amuck looking for location IDs."

Chapter - Inputs

[Really more of an appendix]

Table of Location IDs
First (a number)	Second (a number)
123 456
124 457
[etc... (not my real input values)]

With the input in place, it was time to begin solving the puzzle, which required me to sort the columns, get the distance between each row, and add that all together. As the columns had to sorted separately, it soon became apparent that a table was not the right data structure for this problem.1 So I extracted each column into a list and sorted both lists.

Chapter 1 - Definitions

List 1 is a list of numbers that varies.

List 2 is a list of numbers that varies.

When play begins:
	repeat with N running from 1 to the number of rows in the Table of Location IDs:
		add first in row N of the Table of Location IDs to List 1;
	repeat with M running from 1 to the number of rows in the Table of Location IDs:
		add second in row M of the Table of Location IDs to List 2;
	sort List 1;
	sort List 2.

Next, I would need to get the distance between each value in both lists by subtracting the smaller number from the larger number. I wrote a deciding phrase (basically a function with a return value) for this:

To decide what number is the distance between (N - number) and (M - number):
	if M is greater than N:
		decide on M minus N;
	decide on N minus M

i.e.

function distance(int n, int m) {
    if m > n {
        return m - n;
    }
    return n - m;
}

Inform allows you to use > instead of greater than and - instead of minus, but I felt like spelling everything out was more in the spirit of things.

To get the final answer, I will need to sum the contents of a list. This will require another deciding phrase, which we can use in a reduction later.

To decide what number is the sum of (N - number) and (M - number)
	(this is summing):
	decide on M plus N.

With all the components of the solution now in place, I implemented it in the next section of the code:

Chapter 2 - The Answer

The Chief Historian's Office is a room. "Elves run amuck looking for location IDs."

[Type Z in game to trigger this.]
Instead of waiting:
	say "The elves diff the lists...[line break]";
	let diffs be a list of numbers;
        [construct diffs list]
	repeat with X running from 1 to the number of entries in List 1:
		add the distance between entry X of List 1 and entry X of List 2 to diffs;
	say "The elves add it all together...[line break]";
        [reduce diffs list to its sum]
	let answer be the summing reduction of diffs;
	say "The elves tell you that the answer is [answer]."

To get the solution, I compiled and ran the game and entered z into the parser. As if to further confirm Inform’s unsuitability for such a task (and perhaps the inefficiency of my code), getting to the answer took quite some time even on my reasonably powerful PC.

The second part of the challenge required counting the times each value in the first list appeared in the second list. After spending some time with filters and reductions, and then some more time with manual list traversal in the name of efficiency, I threw up my hands and nested a couple of repeat loops.

[Type YES in game to trigger this.]
Instead of saying yes:
	let similarity be 0;
	repeat with N running through List 1:
		let count be 0;
		repeat with M running through List 2:
			if N is M:
				now count is count plus 1;
			if M is greater than N: 
				break; [we know the list is sorted; a sop to efficiency]
		now similarity is similarity plus N times count;
	say "The elves tell you the answer is [similarity]."

It wasn’t quick, but it got the right answer.

Here’s the full code of my solution:

Full solution code

Closing thoughts: A more complete solution would read the input file and use custom parsing and casting to construct the two lists. I decided not to do this because I didn’t want to spend more time writing code for reading files than writing code for solving the actual challenge. In retrospect, this wasn’t the most interesting challenge to do with Inform – my code ended up being pretty boring imperative loops and conditionals, just spelled out.

While Inform 7 may look like English prose, it has quite strict syntax. Especially in the age of AI prompting, it’s very easy to get loose and start writing words Inform doesn’t expect or understand – for example, it took me a bit of time to remember that the syntax for setting a variable is now the VAR is VALUE rather than set VAR to VALUE. When prompted for Inform code, AI is liable to make the same mistake and mix in regular English prose, making it fairly useless for this language in particular.

# Day 2: Haskell

Challenge: find which lists increase or decrease smoothly.

I first encountered Haskell in a third-year Computer Science functional programming course and really enjoyed using it. The sheer amount of functionality you could pack into a line or two of code amazed me. Since then, I haven’t found much occasion to return to it, apart from when I went through Bruce Tate’s Seven Programming Languages in Seven Weeks a few years ago.

This puzzle involved a bunch of lists, so I chose Haskell because I remembered it being good at working with lists. Skimming through the Seven Languages book helped me get back up to speed, as did pair-programming with my good buddy Claude 3.5. The main thing that makes Haskell counterintuitive is that you have to write functions right to left most of the time.

The core of the problem was checking whether lists were ascending or descending, and checking that the differences between subsequent entries were within a given range. For the first part, we can do this:

-- check each pair of values is in asc order
-- produce a list of bool results
-- then AND that list
-- read right to left
isAscending :: [Int] -> Bool
isAscending xs = and $ zipWith (<=) xs (tail xs)

-- check each pair of values is in desc order
-- produce a list of bool results
-- then AND that list
-- read right to left
isDescending :: [Int] -> Bool
isDescending xs = and $ zipWith (>=) xs (tail xs)

For the second, we can do this:

validDistance :: [Int] -> Bool
validDistance xs = and $ map isValidDist $ zip xs (tail xs) -- check each pair in list
  where isValidDist (a, b) = dist a b >= 1 && dist a b <= 3 -- require dist between 1 & 3
        dist x y = abs (x - y) -- check dist by getting the absolute value of x-y

You can think of where as a way to define inner functions, similar to nesting defs in Python. With this core logic in place, we can do a bunch of file input and parsing and then get our solution.

The second part of the puzzle asks you to recompute the number of valid lists with an added tolerance for a single mistake in each. So we can just loop through each list, removing one value at a time and checking if that makes it valid.

isValidAfterRemoval :: [Int] -> Bool
isValidAfterRemoval xs = any isValid (possibleRemovals xs)
  where
    -- make a list of lists with one element removed
    -- loop through indices in the list and make new
    -- lists by concatting (++) the sublist before i
    -- with the sublist after i
    possibleRemovals lst = [take i lst ++ drop (i+1) lst | i <- [0..length lst - 1]]
    isValid lst = isAscendingOrDescending lst && hasValidDifferences lst
Full solution code

Closing thoughts: Haskell remains the language where I feel most like I’m writing horizontally rather than vertically. The syntax is quite funky and it’s a bit brain-bending to get back into after not looking at for a few years. I leaned on the AI a fair bit for bug-fixing and code explanations.

# Day 3: Ruby

Challenge: parse valid instructions out of corrupted text.

This seemed like a regex problem, so I grabbed Ruby, the language I know with the best regex. I’ve used Ruby quite a lot, so this problem was very quick and easy compared to the last couple of days.

input = File.read('input.txt')
matches = input.scan(/mul\((\d{1,3}),(\d{1,3})\)/)
puts matches.sum { |first, second| first.to_i * second.to_i }

The second part required some simple context-aware parsing, which for the sake of my sanity I did not attempt to do with look-behinds.

input = File.read('input.txt')
lines = input.split(/(do\(\))|(don't\(\))/)

valid_lines = []
deleting = false
lines.each do |line|
    deleting = line.match(/^don't\(\)$/) or (deleting and !line.match(/^do\(\)$/))
    valid_lines << line unless deleting
end

matches = valid_lines.join.scan(/mul\((\d{1,3}),(\d{1,3})\)/)
puts matches.sum { |first, second| first.to_i * second.to_i }

Closing thoughts: if I was going for time or code succinctness, I would do every challenge in Ruby.

# Day 4: GML

Challenge: find all instances of XMAS in a wordsearch.

For this challenge, I returned to my roots. The Game Maker Language (GML), a C-like language designed for use in the 2D game development tool GameMaker, was the first programming language I ever wrote significant code in, and so it holds a special place in my heart. I wrote about it previously here.

The kind of thing you’re suppose to make with GameMaker.

The kind of thing you’re suppose to make with GameMaker.

I chose GML for this challenge specifically because it involves a grid of letters, and GML has a grid data structure. This data structure was introduced somewhere around Game Maker 6.1 or 7,2 and I remember thinking it seemed really cool and useful but never actually having a practical use for it.

GML has changed somewhat since I last wrote about it – it now has functions with named parameters. Previously, all functions (or scripts) took up to 16 arguments and you’d have to reference them as argument0–argument15. Other than that, it seems mostly backwards compatible with the code I wrote almost twenty years ago.

To solve the puzzle, I created a new game with one room and one script. I invoked the script in the room’s creation code, and disabled GM’s sandbox so I could access arbitrary files.3 My script starts by prompting the user for the input file and then reads it into an array line-by-line:

function aoc4(){
	// prompt for input file
	var filename; // semicolons are only strictly necessary after var declarations
	var file;
	filename = get_open_filename("text file|*.txt", "")
	if (filename != "")
	{ // in my GML days I always put open braces on their own lines
	    file = file_text_open_read(filename)
	}

	// read lines
	var n = 0;
	while (!file_text_eof(file))
	{
		lines[n++] = file_text_readln(file)
	}
}

Next, we assemble a grid data structure from our array of lines:

	// assemble grid
	wordsearch = ds_grid_create(string_length(lines[0]), array_length(lines))
	for (var i = 0; i < ds_grid_height(wordsearch); i++)
	{
		for (var j = 0; j < ds_grid_width(wordsearch); j++)
		{
			wordsearch[# i, j] = string_char_at(lines[i], j+1)
		}
	}

A few notes:

  • I forgot to declare wordsearch with var here, which, due to GM’s lax approach to scoping, would turn it into an instance variable of whatever calls the script. Not quite sure what happens here, as it’s called in the room creation code.
  • In older versions of GM, data structures did not have accessor syntax, so the line in the innermost for loop here would have to have been ds_grid_set(wordsearch, i, j, string_char_at(lines[i], j+1). Retrieval would have been done with ds_grid_get.
  • Some languages do 1-indexing and other languages do 0-indexing. GML does 0-indexing… except for strings, which are 1-indexed. Hence j+1 in string_char_at.

Next, we have to find occurrences of the word XMAS in the grid. The solution must account for horizontal, vertical and diagonal words, both forwards and backwards. For this, I used a nested for loop and a whole lot of if statements.

	// find xmases
	var	xmas_count = 0;
	for (var v = 0; v < ds_grid_height(wordsearch); v++)
	{
		for (var h = 0; h < ds_grid_width(wordsearch); h++)
		{
			if (wordsearch[# h, v] = "X") // = and == are equivalent in GML
			{
				// east
				if (h < ds_grid_width(wordsearch) - 3)
				and (wordsearch[# h + 1, v] = "M")
				and (wordsearch[# h + 2, v] = "A")
				and (wordsearch[# h + 3, v] = "S")
					xmas_count++
				// west
				if (h >= 3)
				and (wordsearch[# h - 1, v] = "M")
				and (wordsearch[# h - 2, v] = "A")
				and (wordsearch[# h - 3, v] = "S")
					xmas_count++
				// south
				if (v < ds_grid_height(wordsearch) - 3)
				and (wordsearch[# h, v + 1] = "M")
				and (wordsearch[# h, v + 2] = "A")
				and (wordsearch[# h, v + 3] = "S")
					xmas_count++
				// north
				if (v >= 3)
				and (wordsearch[# h, v - 1] = "M")
				and (wordsearch[# h, v - 2] = "A")
				and (wordsearch[# h, v - 3] = "S")
					xmas_count++

				// southeast
				if (h < ds_grid_width(wordsearch) - 3)
                                and (v < ds_grid_height(wordsearch) - 3)
				and (wordsearch[# h + 1, v + 1] = "M")
				and (wordsearch[# h + 2, v + 2] = "A")
				and (wordsearch[# h + 3, v + 3] = "S")
					xmas_count++

				// southwest
				if (h >= 3) and (v < ds_grid_height(wordsearch) - 3)
				and (wordsearch[# h - 1, v + 1] = "M")
				and (wordsearch[# h - 2, v + 2] = "A")
				and (wordsearch[# h - 3, v + 3] = "S")
					xmas_count++

				// northeast
				if (h < ds_grid_width(wordsearch) - 3) and (v >= 3)
				and (wordsearch[# h + 1, v - 1] = "M")
				and (wordsearch[# h + 2, v - 2] = "A")
				and (wordsearch[# h + 3, v - 3] = "S")
					xmas_count++

				// northwest
				if (h >= 3) and (v >= 3)
				and (wordsearch[# h - 1, v - 1] = "M")
				and (wordsearch[# h - 2, v - 2] = "A")
				and (wordsearch[# h - 3, v - 3] = "S")
					xmas_count++
			}
		}
	}

	// show result
	show_message_async("XMASs: " + string(xmas_count))

As noted, GML is one of the few languages that allows you to make comparisons with a single =, the same as assignment. This is discouraged, but it’s how I wrote code when I was 16, along with the nasty ifs and nested fors.

The second part of the challenge involved finding Xs of the word MAS, e.g.

M-S M-M
-A- -A-
M-S S-S ...

I did this with some more ugly ifs:

	// find x-mases
	var x_mas_count = 0;
	for (v = 0; v < ds_grid_height(wordsearch); v++)
	{
		for (h = 0; h < ds_grid_width(wordsearch); h++)
		{
			if (wordsearch[# h, v] = "M")
			{
				if (h < ds_grid_width(wordsearch) - 2)
                                and (v < ds_grid_height(wordsearch) - 2)
				and (wordsearch[# h + 2, v] = "M")
				and (wordsearch[# h + 1, v + 1] = "A")
				and (wordsearch[# h, v + 2] = "S")
				and (wordsearch[# h + 2, v + 2] = "S")
					x_mas_count++
				else if (h < ds_grid_width(wordsearch) - 2)
                                and (v < ds_grid_height(wordsearch) - 2)
				and (wordsearch[# h + 2, v] = "S")
				and (wordsearch[# h + 1, v + 1] = "A")
				and (wordsearch[# h, v + 2] = "M")
				and (wordsearch[# h + 2, v + 2] = "S")
					x_mas_count++
			}
			else if (wordsearch[# h, v] = "S")
			{
				if (h < ds_grid_width(wordsearch) - 2)
                                and (v < ds_grid_height(wordsearch) - 2)
				and (wordsearch[# h + 2, v] = "M")
				and (wordsearch[# h + 1, v + 1] = "A")
				and (wordsearch[# h, v + 2] = "S")
				and (wordsearch[# h + 2, v + 2] = "M")
					x_mas_count++
				else if (h < ds_grid_width(wordsearch) - 2)
                                and (v < ds_grid_height(wordsearch) - 2)
				and (wordsearch[# h + 2, v] = "S")
				and (wordsearch[# h + 1, v + 1] = "A")
				and (wordsearch[# h, v + 2] = "M")
				and (wordsearch[# h + 2, v + 2] = "M")
					x_mas_count++
			}
		}
	}

	// show result
	show_message_async("X-MASs: " + string(x_mas_count))
}
Full solution code

Closing thoughts: not too painful. While a more expressive language would have made the solutions shorter and more elegant, this code has the virtue of at least being pretty obvious. When I was first writing GML, I did it without access to the Internet, using just the helpfile. I have enough of GML etched into the deep recesses of my skull that I didn’t feel the need to ask the AI anything, or even look at StackOverflow.

# Day 5: GNU Prolog

Challenge: find which lists adhere to all of the ordering rules.

This was clearly a constraints problem, so Prolog seemed like the right choice. I’ve only used Prolog once before, when going through Bruce Tate’s Seven Programming Languages in Seven Weeks book mentioned above. It is not an imperative or functional language, but a logic language – its closest sibling in wide use is probably SQL. Apart from that, its list handling and function definition syntax have some similarities with Haskell – you deal with lists through patterns, and can define multiple versions of the same function with different pattern inputs.

The core of the puzzle is about determining whether one element precedes another in a list. Lists containing the two elements in the correct order are valid, and so are lists containing only one of the two elements. So I started by encoding this rule into Prolog (thanks to this answer on StackOverflow):

precedes(X, Y, L):-
    \+ member(X, L); % either X must not (\+) be in L
    \+ member(Y, L). % or Y must not be in L
    (append(_, [X|Tail], L), % or find X and everything after it (Tail)
    append(_, [Y|_], Tail)); % then find Y in Tail, ergo X precedes Y

From there, I had the AI help me do the input file reading and text processing to get all the rules and lists I would need. This was annoying enough that at one stage I considered just writing a program in a different language that would output a Prolog file with the input hard-coded in. But as I often find with AI, I get much better results by prompting for each part of the code individually than by trying to prompt everything at once. Once I broke the problem down enough, Claude gave me the processing code I wanted.

I then ran every rule against every list. My code was highly inefficient, checking unnecessary rules and continuously reparsing the same data, and so it failed to complete in a reasonable amount of time. With the help of the AI, I optimised out some of its most obvious deficiencies and got it working. To start with, precedes was rewritten like this:

precedes(X, Y, L):-
    (   memberchk(X, L), % find only the first X in L (member tries to find all Xs)
        memberchk(Y, L) -> % find only the first Y in L
        once((append(_, [X|Tail], L), memberchk(Y, Tail))) % find only the first Y in Tail
    ;   true  % succeed if either X or Y is not in L
    ).

The second part of the puzzle required fixing the invalid lists. Again, my first stab at a solution – testing all rules against all list permutations – was too inefficient to complete in a reasonable amount of time (obviously). A more deliberate approach of finding individual rule violations and then swapping the elements involved worked much better.

fix_invalid_lists(Rules, InvalidLists, FixedLists) :-
    findall(FixedList,
            (member(List, InvalidLists),
             fix_list(Rules, List, FixedList)),
            FixedLists).

fix_list(Rules, List, FixedList) :-
    find_violation(Rules, List, X, Y),
    !,  % Cut to make sure we stop after finding one violation
    swap_elements(List, X, Y, NewList),
    fix_list(Rules, NewList, FixedList).
fix_list(_, List, List).  % No violations found, list is fixed

find_violation(Rules, List, X, Y) :-
    member(Rule, Rules),
    parse_rule(Rule, X, Y),
    \+ precedes(X, Y, List).

swap_elements(List, X, Y, NewList) :-
    append(Before, [A|Rest1], List), % split list at 1st element
    append(Middle, [B|After], Rest1), % split rest of list at 2nd element
    ((A = X, B = Y) ; (A = Y, B = X)), % match 1st and 2nd elements
    !,  % Cut to prevent multiple solutions
    append(Before, [B|Middle], Temp), % construct new list
    append(Temp, [A|After], NewList).

! here is the cut operator, which we use to force Prolog to commit to fixing the first violation it finds in fix_list and swapping the first instances of X and Y it finds in List in swap_elements. This forces our code to fix violations one at a time with a single swap rather than looking for multiple violations and multiple solutions to each one.

Full solution code

Closing thoughts: the AI had to help me quite a lot with this one, which wasn’t totally smooth sailing, because it very quickly gets confused between different versions of Prolog, and I had to keep reminding it I was using GNU Prolog rather than SWI-Prolog. Next time I’ll probably just bite the bullet and use SWI-Prolog instead.

This was quite a difficult language to use for a single challenge. I’d previously used Prolog mostly on the level of toy demos like this:

likes(alice, bob).
likes(bob, carol).

friend(X, Y) :- \+(X = Y), likes(X, Z), likes(Y,Z).

Needless to say, the differences between this sort of thing and a program that has to operate on large amounts of data are legion. One reason is that Prolog will usually try to find every solution that fits a set of constraints, and must be explicitly told to settle for just the first solution (hence once and !).

This seems to be the general approach to Prolog programming: first write a program that finds every solution for every problem, then prune the ones you don’t care about. For very small toy problems, you may never arrive at this second step, but AoC challenges, which I get the sense are designed to thwart brute-forcing, really reward efficiency.

I’ll cover Days 6–10 in the next part. Highlights include breaking my main rule for this exercise on day 6.

  1. I would still say it was better to start with a table than try to read in and parse a text file of numbers in a language with no obvious way to cast strings to numbers. ↩︎

  2. Having been around since 1999, GameMaker has gone through numerous rewrites, rebrands and version numbering resets. Originally it was Animo, then Game Maker, through versions 1 to 8.1. It was then rewritten and rebranded to GameMaker: Studio, which had versions 1 through 1.4. A second massive rewrite came in form of GameMaker Studio 2, which later adopted a rolling release cycle and rebranded as just GameMaker. ↩︎

  3. The sandbox was introduced in Studio. Previous versions of GM included functionality for accessing disk drives. That said, I might not have needed to do this because I ask the user to specify a file. ↩︎


Archive of posts
Image upload with render hooks
similar posts
Programming in Inform 7
Using an external text editor in GameMaker Studio 2
Programming in GameMaker
Syntax highlighting with render hooks
webmentions(?)