Infrastructure as Advent of Code

In the cold of December we have but one thing to keep us warm: our laptops, trying to solve Advent of Code puzzles with inefficient algorithms. This year, 2024, is the tenth edition, and the puzzles are filled with more Easter eggs than ever before. Unfortunately, I’m not interested in Easter eggs, or solving the puzzles. I am a DevOps engineer, and I’m going to apply Infrastructure as Code principles to Advent of Code.

After burning myself out halfway through the puzzles last year, I decided I was going to make it easy on myself this year, and use Python, as most problems are simply solved in the standard library and most other things are easily solved with Numpy or NetworkX. Then a friend told me I was being suspiciously normal, so I opted to honour my day job in DevOps and, as a challenge, implement as many puzzle solutions as possible in Terraform.

Terraform, as we will go into more detail about soon, is not exactly a programming language. Its intended use is to define a desired set of cloud infrastructure, which you can then feed to the terraform binary and tell it to “make it so.” As such, you might be surprised that it can do programming at all. After all, it’s a configuration tool, and you would like your configuration to be simple, static, and predictable¹. While that’s partially true, years of adding convenience to the language have definitely created some structures that could be used to solve puzzles.

If you’re not interested in learning Terraform, you can skip ahead to the discussion of the puzzles.

What is Terraform?

HashiCorp Terraform, to call it by its full, nominatively fair use name, is a tool used to codify infrastructure. In its most basic form, you use provider plugins to write resource definitions, which can then be apply‘d to make reality match your configuration. For example, the following configuration would set up a server in the Netherlands in Google Cloud Platform.

provider "google" {
  project = "my-gcp-project"
}

resource "google_compute_instance" "my_server" {
  name         = "my-server"
  machine_type = "n2-standard-2"
  zone         = "europe-west4-a"

  boot_disk {
    initialize_params {
      image = "debian-cloud/debian-12"
    }
  }
}

And this works pretty well. When your operation grows, you will however generally accumulate more and more servers, and you want to avoid repeating yourself for each one of them. Because of this, over time, several features have been added that allow you to not repeat yourself, do little calculations, and overall express yourself more concisely.

Our tools

As mentioned, Terraform is not intended for heavy computational use, but it has a few things that we might put to work as such any way. Let’s go over what we have to work with.

Data types

Terraform has a reasonably complete set of data types, though they rarely come up due to automatic coercion. We have basic primitives string, number², and boolean, as well as collection types list, set, and map. The map type only has string keys, but its value type can very. The collections can also be composed, so list(map(number)) is a valid type. null is also a type, but for our purposes it doesn’t really come up.

Even though the documentation insists that casts are rarely necessary because everything generally coerces to the right type, this stops being true as soon as you start to do any programming. The string "0" will indeed coerce to 0 when passed to a context that expects a number, but these values are not equal.

run "type_equality" {
  assert {
    condition     = "0" != 0
    error_message = "Integers aren't equal to strings!"
  }
}

For completeness, it should be noted that there are two more data types, tuple and object, that are simply list and map but with different types of values rather than all the same. I will not be using those for our solution programs.

Structure

Our Terraform project is structured in modules. A module is effectively some directory with .tf files³. Terraform doesn’t really have an ordering between files, they should all be viewed together at once as if they were one big file. In its simplest form, a module defines some input variables and some output variables that are derived from that. For example, the module below takes a number and doubles it.

variable "my_num" {
    type = number
}

output "my_result" {
    value = var.my_num * 2
}

It’s often useful to compute a repeated bit once, and then use it later. You can do so with local variables:

locals {
    double = var.my_num * 2
    quadruple = local.double * 2
}

In a way, modules are like functions: they take some input, do their transformations on it, and produce an observable output. Any local variables are implementation details and are hidden from the caller. Modules can also call each other to create more complex structures. Here, they either point to a module in some well-known registry, but you can also simply point to different directory of Terraform files. You can then refer to the outputs of that module to continue your computation.

module "doubler_as_a_service" {
    source = "./doubler"

    my_num = var.outer_input
}

output "is_42" {
    value = module.doubler_as_a_service.my_result == 42
}

It should be noted that the order that expressions and definitions appear in the files do not matter; instead, Terraform attempts to build a directed acyclic graph between all definitions, and then computes everything starting from the leaves. It does so in parallel, which has the neat little side effect that it’s trivial to write highly multithreaded code in Terraform.

Basic arithmetic

It might seem minor given the above areas, but Terraform also has a reasonably complete set of arithmetic operators, which combine in all the ways you would expect. In addition, it also has boolean logic, though it doesn’t do short-circuiting for con- and disjunctions. This will come to bite us later, but we can make it work.

Loop structures

Terraform doesn’t have loops directly, but it does have two sets of primitives that we can use as loops in our programs. Both have roughly the same limitations:

Iterations cannot depend on the result of a previous iteration
The number of iterations is always bounded
We cannot exit early
We can skip individual iterations conditionally

This, it turns out, is good enough for many purposes.

Comprehensions

If you are familiar with Python, you will have seen list- and dictionary comprehensions, as a way of creating these collections from an iterator, without a for loop.

first_list = []
for n in range(10):
    first_list.append(n * 2)

second_list = [n * 2 for n in range(10)]

In Terraform, we don’t have the luxury of for loops, but we do have for expressions which are essentially list- and map comprehensions. We will be using those as our primary looping mechanism. Terraform has roughly the same functionality as Python here. We can loop over one thing, construct another, and optionally skip elements that don’t meet certain conditions.

locals {
    list_example = [for n in range(10) : 2 * n]
    map_example = {for n in range(10): n => n * 2}

    list_from_map = [
        for key, value in local.map_example :
        value
        # Skip keys that are divisible by three
        if key % 3 != 0
    ]
}

As previously, mentioned, keys in a map will always be strings. This is luckily mostly managed by automatic type conversion, so you can use integers as map keys just fine.

There is one more special comprehension. For maps, it is an error to have more than one value for the same key. For the cases where you actually do have more than one value per key, you can use the grouping map comprehension. This combines all values with the same key into a list, in order of appearance.

locals {
    grouped_map = {
      for n in range(10000):
      n % 7 => n...
    }
}

Repetition

Aside the earlier comprehensions, we can also repeat resources and modules using the meta arguments count and for_each. count takes a number and repeats a given resource or module that many times. for_each takes a map and instantiates a given resource or module once for each key in the map.

module "count_module" {
    source = "./source"
    count = 10
    # The 0-based index of the resource is available to customize the different modules
    input_var = count.index
}

module "foreach_module" {
    source = "./source"
    for_each = local.some_map
    # the key and value of the current map entry are available to use
    input_var = each.key + each.value
}

count can also be used in a conditional this way: by setting count to 0, you can conditionally turn of that particular module. This is, as of now, also the only way to have conditionally-created resources in Terraform, even when using it as intended. It feels like a hack every time you do.

Standard functions

Aside from code structures we might use, Terraform also offers a collection of functions that you can use to express complicated structures that you otherwise wouldn’t be able to. The main workhorses for the puzzles were split and the various regex operations, as they allowed me to parse the input in about the same way as I would in Python.

Unit testing

Any development experience will be infinitely more awful if you can’t rapidly iterate, and for that, you need a way to quickly test your code. Terraform offers both unit and integration tests for this, where it will run your code either in plan or in apply mode respectively, and allows you.

locals {
  two_times_two = 2 * 2
}

run "test_math" {
  assert {
    condition     = local.two_times_two == 4
    error_message = "Maths machine broke"
  }
}

I’ve used this to encode the sample inputs and their from the stories into test cases, so I could quickly check whether my code gave the right answer yet.

What we don’t have

With all the features outlined above, one might think Terraform is a pretty normal, albeit rather quirky programming language. This is wrong. It is an expressive declarative configuration language. As such, we don’t have any method to mutability. Variables are declared exactly once, with their initial value. Due to the lack of loops, there is no way to declare a variable again with a new value. Because of this, algorithms that walk through a grid following some arbitrary rules are impossible to implement. You can’t write Dijkstra’s algorithm without maintaining some to-do list. You might be able to with sufficient recursion, except you can’t.

It might seem tempting to have modules call themselves conditionally to achieve some sense of looping or smart recursion, but this doesn’t work. At the early stages of evaluation, Terraform builds a tree of your module structure to figure out in what order it should do its work. At this point, no other values have been evaluated, so it assumes that any use of a module actually happens. You can kind of achieve recursion by hard-coding your maximum depth into your folder structure, and you even can kind of avoid repeating yourself by using symlinks

outer_module/
└── recursive_module/
    └── main.tf
        └── recursive_module/
            └── main.tf (symlink to ../main.tf)
                └── recursive_module/
                    └── recursion_end.tf

This is of course not very fun to create, and since all recursion happens unconditionally, you will always suffer the overhead of having this entire structure, even if you don’t need it. In other words, it’s slow. This is even worse if you have some conditional branching, as the modules for both branches will be instantiated.

The puzzles

Now that we’ve established that programming in Terraform is a bad idea, let’s try to do it anyway. I will go over the various puzzles that worked out, and the workarounds that were needed to get there. With these odds, I’m happy with 18, perhaps 20 stars.

Day 1: Linked lists

Code - Puzzle

We start the puzzles easy, but we also encounter the limitations of automatic type coercion for the first time. It is simple enough to parse the lines of numbers into two lists of numbers. After that, we do have to explicitly cast the values to numbers before using the sort function.

The sort function will only sort numbers by value; any other value will be sorted lexicographically instead. That is reasonable behaviour, but can be unexpected when sorting numeric strings. This behaviour is also not documented; the documentation suggests that any form of sorting happens lexicographically regardless of type. Two stars.

Day 2: Report redaction

Code - Puzzle

On the second day, we get the first use of modules as reusable functions. We are asked to check whether a list is either ascending or descending, and whether the difference for each step is between one and three, inclusive. We can write a module that computes that for a given list.

For the second part, we are asked whether we can make the lists that do not yet match our requirements, pass the check after removing a single element from them. There exists a nice Dynamic Programming solution that can check whether a list of numbers can be fixed like that in a single pass, but since this is only the second puzzle, the lists are nice and short (up to eight elements) and simply checking whether the deletion of any one of those elements results in a valid list is good enough. Two stars.

Day 3: To multiply or not to multiply

Code - Puzzle

The third puzzle gives us garbled string like sub(2b,3)r7do()mul(3,4)don't()mul(3,10) and asked what the total for all the included multiplications mul(a,b) is. There are many ways to do this, but the easiest to me is to use a simple regular expression to find all the multiplications. Terraform’s regular expression engine proved capable of this just fine.

After solving that, the twist for the second puzzle is that there are additional do() and don't() instructions included in the string. Any mul after a don't() should be ignored until the next do().

At first, I thought this would be very hard to do in Terraform as my Python solution keeps a boolean indicating whether the last thing I’ve seen is a do() or a don't(), which is mutation. I did manage to implement this by tokenizing the string into a sequence of mul(), do(), and don't(), then for every mul(), check whether the most recent do() has a higher index than the most recent don't(). This implementation was made slightly harder by lack of a good “last matching element before position” function, though you can construct one using slice(), reverse(), and index() functions.

I was then informed by a colleague, who was attempting to complete the puzzles in an even less suitable programming tool⁴, that this is clearly the hard way to do this. You can simply use regular expression text replacements to filter out the parts you should ignore. You can first replace all don't()s until the next do() with the empty string, and finally delete any remaining don't() until the end of the string. Just be sure that you have enabled multiline matching in your regex engine, as the input spans multiple lines. After that, I updated my implementation which performed significantly better.

Originally I had thought that this approach would be impossible, as I had interpreted the problem as a matching-brackets kind of problem, where every don't() should be matched up to a do(). This is famously impossible with regular expressions due to the pumping lemma. The regular expression solution however does work, because you don’t have to match these tokens; the most recent gets to decide, so this fits perfectly into a regular language. Regardless, another two stars.

Day 4: Crazy crossword

Code - Puzzle

The fourth puzzle is a giant crossword puzzle. The puzzle is very simple, as it only contains the word “XMAS”. We have to find how often it contains this word. The way to solve this in Terraform is not that different from how it would be in any other language: look at every individual point in the crossword, look in all directions, and see if you hit anything you want to see.

An X-MAS crossword — Can you find all the X-MAS I hid in here? Crossword generated with Crosswyrd, which isn’t really relevant within the scope of this article, but I found it a nice website.

The way I ended up implementing this, is with a module that is called once for every cell of the grid, then from there, call a second module that walks in a specified direction, and see what the grid spells in each of those directions. Here we hit a tiny wall.

Terraform modules turn out to have significant overhead, and evaluating these roughly $140 \times 140 \times (1 + 8) = 176400$ modules requires about 10GiB of RAM. I noticed this problem in the previous days’ puzzles, but here it became too much for my poor laptop. If we want this to run at all, we have to reduce the number of modules we expand. Luckily we can simplify the problem a little.

Horizontal instances of words are easy: we can simply do a string search for XMAS and SAMX in our input text, which we can do once for the entire input. This has immediately reduces the work we have to do by 22%, because we no longer have to search in those two directions.

The other six directions don’t have simplifications that are this nice, but we can at least reduce the amount of work by half by only searching of three of them, and searching for both XMAS and SAMX at the same time.

Together, these optimizations reduce the amount of RAM required enough so that I can run this on my laptop again.

For the second part, it turns out we weren’t looking for the word XMAS, but rather for pairs of the word MAS intersecting each other to make an X. A+ joke. This turns out to be much simpler than searching for XMAS, as the orientation is largely fixed. We simply look at all As, and see whether both diagonals running through the A spell MAS. I wrote a separate module for this, though thinking back, it could’ve been inlined as well.

This adds two more stars, though I have the code commented out in my Terraform project as the time to solve it hampers my iteration speed considerably. If you really want to, you can uncomment it to see it run.

Day 5: Directing cyclic graphs

Code - Puzzle

Today we are print lists of numbers, and we have a set of rules where one page must be printed in front of the other. For the first part, we must find how many of our lists are valid to be printed. To check this, you could try to find a topological order for the rules, and see whether the print lists follow this order. As various people on Reddit figured out, the rules are cyclic, so this topological order doesn’t exist. There is however a different way.

For every rule that says A must come before B, we can use this knowledge to see that if we ever see a B in a list, the rest of that list must not contain A. We can use the grouping map comprehension to build a blacklist for every number, then walk iteratively through our lists and for every position, check if tail starting after that position contains any numbers on the blacklist for the number at that position. This is kind of $O(n^3)$ per list, but the lists are still relatively short and it works out.

For the second part, we are required to figure out the correct order for the lists that aren’t in the correct order. I have not managed to design a sorting algorithm that works in Terraform, so I’m going to consider this one impossible. First incomplete puzzle, one star.

Day 8: Radio stars

Code - Puzzle

Our arch nemesis, the Easter Bunny, is using an array of radio antennae to convince the masses to buy cheap imitation chocolate. This is of course a completely unrealistic scenario and no real life bunny would ever do this. Nevertheless, we have to stop him.

Each of the antennae emits a certain frequency, and when two antennae with the same frequency interact, it causes antinodes, where the amplitude of the waves is maximized. That is unfortunately where the real-life accuracy ends, as the puzzle definition for antinodes works differently.

In part one, antinodes for each pair of antennae are located on all places that are twice as far from one antenna as they are from the other. The puzzle is nice, having no pairs at a distance of an integer multiple of three from each other, so every pair $a, b$ has two antinodes:

\begin{align*} v_1 & = a - (b - a) \\ v_2 & = b + (b - a) \end{align*}

The rest of the algorithm is then fairly straightforward in Terraform: loop over all grid coordinates to locate the antennae, group by frequency, compute all pairs, compute the resulting antinodes from those pairs, check whether they land inside the grid, and finally build a set out of all of these resulting nodes.

The second part adds slightly more nodes to the puzzle by having any grid point that is collinear with the pair of nodes be an antinode. That simplifies the list of grid points to

v_k = a + k \cdot (b - a)

for all integers $k$ . For simplicity, I had $k$ go from -max(width, height) to max(width, height) which should cover any grid point that may be an antinode. In theory, you should compute divide the $b - a$ vector by the greatest common denominator of its components, but at least in my puzzle it appears not to matter. It is however possible so let me show you. Euclid’s algorithm for greatest common denominator is usually written recursively as:

def gcd(a: int, b: int) -> int:
    if b < a:
        return gcd(b, a)
    elif a == 0:
        return b
    return gcd(b % a, a)

Euclid’s algorithm is very efficient, and runs (worst case) in $O(\log_{\phi}(n))$ recursive calls, where $\phi$ is the golden ratio, and $n$ is the smaller of our two numbers. Since our width is bounded to our input, we can linearly write out the algorithm for enough steps to cover that. So I did.

locals {
  dx = var.second[0] - var.first[0]
  dy = var.second[1] - var.first[1]

  # sort() doesn't work as it turns the numbers into strings
  gcd0 = abs(local.dx) < abs(local.dy) ? [abs(local.dx), abs(local.dy)] : [abs(local.dy), abs(local.dx)]

  # Do as many iterations as necessary. 
  gcd1  = local.gcd0[0] == 0 ? local.gcd0 : [local.gcd0[1] % local.gcd0[0], local.gcd0[0]]
  gcd2  = local.gcd1[0] == 0 ? local.gcd1 : [local.gcd1[1] % local.gcd1[0], local.gcd1[0]]
  gcd3  = local.gcd2[0] == 0 ? local.gcd2 : [local.gcd2[1] % local.gcd2[0], local.gcd2[0]]
  gcd4  = local.gcd3[0] == 0 ? local.gcd3 : [local.gcd3[1] % local.gcd3[0], local.gcd3[0]]
  gcd5  = local.gcd4[0] == 0 ? local.gcd4 : [local.gcd4[1] % local.gcd4[0], local.gcd4[0]]
  gcd6  = local.gcd5[0] == 0 ? local.gcd5 : [local.gcd5[1] % local.gcd5[0], local.gcd5[0]]
  gcd7  = local.gcd6[0] == 0 ? local.gcd6 : [local.gcd6[1] % local.gcd6[0], local.gcd6[0]]
  gcd8  = local.gcd7[0] == 0 ? local.gcd7 : [local.gcd7[1] % local.gcd7[0], local.gcd7[0]]
  gcd9  = local.gcd8[0] == 0 ? local.gcd8 : [local.gcd8[1] % local.gcd8[0], local.gcd8[0]]
  gcd10 = local.gcd9[0] == 0 ? local.gcd9 : [local.gcd9[1] % local.gcd9[0], local.gcd9[0]]

  # 10 iterations should cover numbers up to 55, which is more than the width/height
  gcd = local.gcd10[1]
}

One final thing to mention is that I while writing the section explaining how the eighth puzzle was impossible, I realized it was indeed very much possible to do so. Another two stars.

Day 11: Collatz’ Angels

Code - Puzzle

It was going so well, but suddenly the puzzles start requiring real programming and I couldn’t get Terraform to do any of it. Luckily, this day works surprisingly okay. We are asked to simulate a set of strange stones.

The stones have numbers written on them, and every time we blink, the stones change and split up according to the following rules:

if the stone is labelled $0$ , it is replaced by a stone labelled $1$ ,
else, if the number has an odd number of digits, it is multiplied by $2024$ ,
else, the stone is split into two separate stones: one labelled with the first half of the digits, and one labelled with the second half. A stone labelled 2005 would split into on two labelled 20 and 5 respectively.

We are to simulate this process for 25 blinks, and then for 75 blinks. The step that’s splitting the stones in two is suspicious, as exponential growth would make our pool of stones really big really fast. There has to be a trick to this.

Let’s take a quick detour around the Collatz conjecture, also known as the $3n + 1$ conjecture. It describes a similar iterative process, where we start with a number $n$ , and modify it as follows:

f(n) = \begin{cases} n/2 &\text{if } n \equiv 0 \pmod{2},\\[4px] 3n+1 & \text{if } n\equiv 1 \pmod{2} .\end{cases}

That is, if it is even, we divide it by two, if it is odd, we multiply it by three and add one. Let’s start with $12$ . This is even, so we divide by two and get to $6$ . $6$ is still even, so we divide again and get to $3$ . This is odd, so we multiply and add to reach $10$ . Then, to simplify

10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1 \to 4

When we reach $1$ , we will loop back to $4$ , and this pattern repeats forever. It turns out, every integer that anyone has ever tried will reach this loop eventually, though it has not been proven. Veritasium has recently done an episode on the history of the problem.

The rules for the problem are rather similar in their reduction to the rules from the Collatz conjecture, so it makes sense that there is some loop involved. Of course, we have to deal with an exponential number of stones, but this loop will provide the solution to that.

It turns out, that despite the number of stones expanding rather quickly, we will only every have three thousand something unique labels on those stones. We can use this fact to group stones with the same number on them, as they will evolve in the same way. We simply have to multiply the result with the number of like-labelled stones we have. In other words, our algorithm works as follows:

Convert the input into a map of {stone_label: number_of_stones_with_that_label}
Then, for every step of the simulation:
1. For each label and count, convert them to a list of new labels and counts
2. Group these new counts by label
3. Sum the counts grouped by label to create a new map
After all steps are done, sum all the map values to arrive at the final number

This is essentially the same algorithm I used in Python too, though with some issues due to Terraform. First, how do we write out 75 steps? My original idea was to do something like the following:

module "step" {
  source = "./step"
  count = 75

  input_map = count.index == 0 ? local.input_map : step[count.index - 1].output_map
}

Unfortunately, this doesn’t work: Terraform considers all instances of repeated resources and modules to be the same thing. Despite this hypothetical step module never actually referring to itself, Terraform does consider it a cycle, and will error when you try to evaluate this. The solution of course is to copy-and-paste this step module 75 times.

The second issue encountered here happened only when I moved to optimize my code a little. Originally, the step module called a separate transform module on every label individually and transformed it into a list of different labels. This involves a fairly large number of modules, so I wanted to inline the computation, because that way the overhead would be significantly reduced. After copying the code out of the module and into the parent, the code stopped working.

I managed to track this down to the fact that the input arguments for the module had a fixed type coerced the arguments to integers. The stone labels were stored as the key in a dictionary, but this coercion ensured that by the time they encountered my logic, they were in fact numbers. After inlining, this was no longer the case, and I got to discover that 0 != "0", even though everything else still works.

Despite all that, another two stars for the collection.

Day 13: Unfair fun fair

Code - Puzzle

After another day that was clearly impossible due to the 2D maze solving required, we end up with one that is just as easy in Terraform as it is in any other language. We are in control of a series of claw machines, each with two buttons. For each machine, those buttons move the claw a different number along the X and Y axes. The question is then how many times we have to press each button to get the claw to reach some specific position, and whether it is even possible.

The problem text explicitly asks for the minimal number of presses, but this is a red herring: there is exactly one unique combination of button press numbers that will bring us to the goal. This is because the underlying problem we are solving is the solution to the following linear equation:

\begin{bmatrix} a_x & b_x \\ a_y & b_y \end{bmatrix} \begin{bmatrix} a_{press} \\ b_{press} \end{bmatrix} = \begin{bmatrix} t_x\\ t_y \end{bmatrix}

This results in a system of two linear equations with two unknowns, $a_{press}$ and $b_{press}$ , which you can then solve for as you’ve learned in high school. To filter out the instances where the claw cannot reach the destination, simply verify that the solution you found still works after rounding to integers. Part two simply ensures that you weren’t brute-forcing button combinations by adding a huge offset to the number. Another two stars.

Day 14: Bathroom break

Code - Puzzle

Suddenly, there are a bunch of robots racing around the restroom, all with a known initial position and speed, teleporting when they hit a wall. We are asked to simulate where they end up after 100 seconds. This is simple modular multiplication, which Terraform can do easily.

The second half of the puzzle requires us to find the moment in time where all robots line up to form a picture of a Christmas tree. Unfortunately, I have not been able to come up with a heuristic for this that works in Terraform. Alas, another lone star.

Day 19: Magical towels

Code - Puzzle

My favourite joke from last year returns as we arrive at the Hot Springs of Advent of Code lore. Here, we are to see whether we can make a given pattern of five colours by sequencing together some towels with specific patterns that we have at our disposal. Both our towels’ pattern and the target are sequences of w, u, b, r, and g. We can actually build a regular expression of our towel patterns, of ^(every|single|towel|pattern)*$ and see whether the target patterns match this. This makes part 1 solvable in Terraform.

Unfortunately, for part two, the question changes to how many different ways we can construct to create each pattern. To the best of my knowledge this requires actual recursion, which we can’t do with our limited tools. One more star.

Day 25: Keys to success

Code - Puzzle

Our last day is coincidentally also the last puzzle I managed to solve. We are given a list of schematics for keys and locks, and we must find out how many combinations of keys and locks could theoretically fit each other. A key does not fit if the height of one of its teeth pin stacks overlaps with one of the matching pin stacks⁵ in the lock. This is simple enough; the challenge is in parsing these heights from the input. Our diagrams look as follows:

#####
##.##
##.##
.#.##
.#...
.....
.....

.....
.....
#....
#....
#.##.
#.###
#####

We can tell whether an entry is a lock or a key by seeing whether the first row is full. The first item here is a lock with heights [3, 5, 1, 4, 4] and the second is a key with heights [5, 1, 3, 3, 2]. These almost fit each other, except the first pin overlaps.

The diagrams would be significantly easier to parse if they were horizontal, but with a slightly inefficient for loop, we can parse the heights, check every lock against every key, and determine the potential matches.

This is our final star. I didn’t manage to get anywhere close to getting all other stars, so the part 2 bonus star for today remains locked. That brings us to a nice and round 18 (out of 50) stars achievable in pure Terraform.

What didn’t work

So despite getting about one third of the stars available, there are a lot of things that I could not get Terraform to do. For completeness, I’d like to go through a few reasons why I deemed puzzles impossible and what might yet be possible.

Any algorithm that requires mutating state is immediately out, as we don’t have mutable variables. Sometimes I could work around this by adding another factor $n$ to the algorithmic complexity, but this only works in specific cases.
Any walking through a maze generally requires mutation to do efficiently, which means that any puzzle that involved walking through a maze was immediately impossible.
Some puzzles can theoretically be phrased in terms that Terraform may compute, but anything that requires a bunch of modules is likely to be prohibitively slow. The overhead of expanding a module appears on the order of several kilobytes, even for otherwise empty modules.

This all said, I have a hunch that both parts of day 7 might be possible, by using the fake-bounded recursion that I discussed previously. It would require $O(n \cdot 2^l)$ modules for the first part and $O(n \cdot 3^l)$ for part two, with $n$ the number of samples and $l$ the length of the lists. I don’t believe my computer can do that.

Final thoughts

There exists a literary technique called constrained writing, where the writer binds themselves to an unnecessary restriction and tries to make their story work anyway. The book “Initial Instructions” by Joseph Prouser for example is a translation of the Book of Genesis that does not use the letter “E”. Instead of creating the heavens and the earth, it starts:

God’s initial act in His constantly unfolding work of cosmogony was formation of our world and its sky.

I am not a religious person, but playing with language in this way tickles me pink. The point of the exercise is to make you see your work differently. The restrictions force you to be creative to work around them, which in turn leads you to new ideas.

Attempting to problem-solve with Terraform made me think differently. Last year I wrote about being burned out on Advent of Code, but this year I had the most fun I’ve had since doing the polyglot challenge. Terraform is very much not made for programming, but finding new ways to use the primitives it does offer together has been a great way to keep me thinking.

I encourage anyone to try a similarly restrictive challenge for Advent of Code, or any other programming puzzle. If you instead send me a pull request in this style, I do reserve the right to request changes. Happy New Year.

As long as you aren’t part of the Javascript ecosystem, in which case it is perfectly fine for a config file to be arbitrary code. I think. ↩︎
What exactly that number is, is unspecified, but it appears to be a 64 bit floating point number. ↩︎
This is not entirely true, Terraform files may also be plain JSON, and you can have some variable definition files, and a bunch of other things, but let’s ignore that for the time being. ↩︎
They were attempting to complete the puzzles using the Channable tool. This is not even close to a programming language; it’s an e-commerce automation tool, but it has a rules engine, and if you try really hard you can indeed solve some of the puzzles with it. ↩︎
If any lock picking aficionados read this, and I turn out to completely wrong in my terminology, please don’t correct me. ↩︎