Every year since 2018, I’ve been taking part in Advent of Code. For those unfamiliar, it's an advent calendar where every day from December 1 to Christmas, instead of a tiny gift, you get to solve a little 2 part programming puzzle. It’s essentially a bunch of Leetcode style interview puzzles, except they’re actually fun to do (usually) and with a competitive element too, as there’s a global leaderboard and you can create your own private ones too.

As with every year before, I used Swift, and this post goes through some of the trickier puzzles this year. If you’d just like to look at the code, you can find all my solutions on my GitHub repo for Advent of Code.

Day 18

This was the first genuinely tricky problem this year, and the first that took me over an hour to solve. I encourage you to read the description of the problem before going ahead (part 1 is open to everyone even without an account, you need to complete it to unlock part 2).

A quick summary of the task at hand, minus the puzzle specific language: We need to construct a binary tree from the input and repeatedly traverse it in order until no nodes have a depth greater than 4 (we achieve this by splitting the combined value of such nodes across the in order predecessor and successor) and no nodes have a value greater than 10 (we achieve this by splitting the value into two nodes). There are some more specifics here but this is the core of the problem.

This seems fairly straightforward, except there’s just one tiny issue: Swift doesn’t come equipped with any tree types. The Swift standard library includes a lot of types and protocols for data structures, with even more potentially coming soon via the first-party Swift Collections package, which exists as a sort of staging area to refine new types until can be considered solid enough to move them to the standard library, but even there, trees, graphs, linked lists, etc. (basically anything that might use a reference type) aren’t included.

I purposely limit myself to using just the standard library when solving Advent of Code puzzles and also try to avoid referencing any other material, which meant I had to implement the tree type myself. Doing that and traversing it in order was straightforward enough, but finding the in order successor and processor was a bit tricker. But given the challenge at hand necessitated a small enough tree (The maximum depth allowed was 5 nodes, which meant an upper bound of 63 nodes; practically it rarely crossed half that) I ended up just storing the results of in order traversal in an array and navigating through that, which ended up being performant enough.

Part 2 was fairly trivial thereafter, you can read my full solution here.

Day 19

This was probably my favourite puzzle of the year. I’d encourage you to read the original text, but here’s a summary: We’re given a list of point clouds, with each point’s position being defined with respect to the cloud’s centre. Each cloud overlaps with at least one other, and at least 12 points make up the overlap. Our job is to work out the overlaps, and figure out the total number of unique points across all clouds. Adding to the complexity, another issue is we don’t know the orientation of the clouds; one cloud’s x-axis could be another cloud’s negative y-axis, for example.

Ignoring the issue of rotations for a second, a naive approach here is to shift each point cloud along each axis until we manage to overlap 12 points. This might work but given the size of the problem (we’re told the clouds are up to 2000 points wide in each direction), it seems horribly inefficient. We can avoid this however by removing the absolute centre of each cloud out of the equation entirely, by instead considering the relative positions of the points with respect to each other.

For a cloud of n points, we have a total of n * (n - 1) connections between the points. Since the overlapping subcloud has at least 12 points, this amounts to at least 12 * 11 = 132 overlapping connections, which we can check for while ignoring the absolute positions entirely. We can then find the actual overlapping points by seeing which ones contribute at least 11 connections to the overlap, and then find the positions of the centres by comparing the average magnitude of these sets of points.

As for the rotations, I couldn’t really find a straightforward way to compare these. I haven’t done much work in 3D yet, and couldn’t find anything about them in the standard library either, so I had to resort to manually constructing all possible orientations of the clouds by rotating every single point within them.

let rotations: [(Point) -> Point] = [
	{ Point(x: $0.x, y: $0.y, z: $0.z) },
	{ Point(x: $0.x, y: -$0.z, z: $0.y) },
	{ Point(x: $0.x, y: -$0.y, z: -$0.z) },
	{ Point(x: $0.x, y: $0.z, z: -$0.y) },
	
	{ Point(x: -$0.x, y: $0.y, z: -$0.z) },
	{ Point(x: -$0.x, y: -$0.z, z: -$0.y) },
	{ Point(x: -$0.x, y: -$0.y, z: $0.z) },
	{ Point(x: -$0.x, y: $0.z, z: $0.y) },
	
	{ Point(x: $0.y, y: $0.x, z: -$0.z) },
	{ Point(x: $0.y, y: -$0.z, z: -$0.x) },
	{ Point(x: $0.y, y: -$0.x, z: $0.z) },
	{ Point(x: $0.y, y: $0.z, z: $0.x) },
	
	{ Point(x: -$0.y, y: $0.x, z: $0.z) },
	{ Point(x: -$0.y, y: -$0.z, z: $0.x) },
	{ Point(x: -$0.y, y: -$0.x, z: -$0.z) },
	{ Point(x: -$0.y, y: $0.z, z: -$0.x) },
	
	{ Point(x: $0.z, y: $0.y, z: -$0.x) },
	{ Point(x: $0.z, y: $0.x, z: $0.y) },
	{ Point(x: $0.z, y: -$0.y, z: $0.x) },
	{ Point(x: $0.z, y: -$0.x, z: -$0.y) },
	
	{ Point(x: -$0.z, y: $0.y, z: $0.x) },
	{ Point(x: -$0.z, y: -$0.x, z: $0.y) },
	{ Point(x: -$0.z, y: -$0.y, z: -$0.x) },
	{ Point(x: -$0.z, y: $0.x, z: -$0.y) },
]

You can find my full solution here.

Day 22

A thing you learn quickly when you start doing mobile development is that the O(n) complexity of certain algorithms matters significantly less at the tiny values of n youʼre usually dealing with. This problem, though, was one where n was large enough to matter.

We’re given a list of cuboids and whether they should turn on or off all the points within them. Parts 1 and 2 are identical, except part 1 limits the size of the active area to 100 points along each axis, and part 2 is unbounded. Part 1 thus could be solved with a naive implementation looking at all the points in a cuboid with a maximum area of about a million points¹, but part 2 goes well beyond a quadrillion points, so the approach needs to be a bit more considered.

The way I went about this was subdividing each cuboid. Each new cuboid would be compared with the already processed ones to check for any overlaps. Two cubes overlap if their x, y, and z values all overlap. Next, the split. This is the core logic of the puzzle, and works out like so:

extension ClosedRange where Bound == Int {
	func split(over other: Self) -> Set<Self> {
		if other.isSuperset(of: self) {
			return [self]
		} else if lowerBound < other.lowerBound, upperBound > other.upperBound {
			return [
				(lowerBound ... other.lowerBound - 1),
				other,
				(other.upperBound + 1 ... upperBound)
			]
		} else if other.lowerBound <= lowerBound {
			return [(lowerBound ... other.upperBound), (other.upperBound + 1 ... upperBound)]
		} else {
			return [(lowerBound ... other.lowerBound - 1), (other.lowerBound ... upperBound)]
		}
	}
}

Essentially we want to split each axis of the existing cuboid (self) into sub-axes that are either entirely within or entirely outside the new cuboid’s axis (other). This ensures that when we glue back the new axes, we can ignore the ones that are entirely contained within the new cuboid, thus only counting those overlapping points once or not at all, by either including or removing the new cuboid, respectively.

You can read my full solution here.

Day 24

This was, by a margin, the toughest problem this year.

We’re given a program for an ALU with 4 integer registers (w, x, y, and z) and 6 operations (assignment, addition, multiplication, division, modulus, and an equality check). The program requires an input of 14 single-digit integers between 1 and 9 to execute, and our task is to find the maximum (part 1) and minimum (part 2) input values that result in the value of z to be 0.

A brute force solution is fairly easy to construct, except it’s also horribly inefficient, as the total search space is 9^14, or about 2.2 trillion values. The program is a pure function over the input, so there’s no obvious optimisation for a search here. We need to dig into the actual instructions.

Compiling out the program, turns out that the calculations are fairly simple, and partially repetitive. The program has 14 parts. Each begins with receiving the value of w to the next input, and using it to build the value of z. The values of w, x, and y are entirely transitive and reset in each part. I was thus able to reduce the program to 14 operations where the value of z is calculated using just it’s own current value and the next input.

Another insight from the compiled program is that 6 steps involve both multiplying z by 26 and adding the input and some constant value to it. The others always divide z by 26, but depending on the input they either do nothing else, or perform the same multiplication and addition as the rest². We never multiply z by 0 and the program doesn’t allow for subtraction, so it’s clear that the input allowing for this division is the only way to make z reach 0.

Moreover, since division only happens by 26 at most, we can also make other assumptions going off of that. Here’s the last step, for example:

let m13 = (z12 % 26) - 14 == input[13] ? 1 : 26
let c13 = (z12 % 26) - 14 == input[13] ? 0 : input[13] + 13
let z13 = m13 * (z12/26) + c13

z13 is the value of z after the 14th step (I’ve indexed by zero here), z12 is the value of z after the 13th step, input[13] is the 14th input, and m13 and c13 are the multiplier and constant.

We know that z12 is divided by 26 at most. We need the multiplier to be 1 and the constant to be 0 too, sure, but we also need z12 to be 26 or lower for the division to succeed. If z12 is greater than 26, we can avoid this calculation entirely. Going further, we can assert that it’s the value of z12 that’s the issue here; no possible value of input[13] can make z resolve to zero, so the values of the input before it need to be adjusted.

We can make similar assertions for the 8 instructions that don’t guarantee to perform a multiplication. This vastly reduces our search space as we can go straight from evaluating say 99999999999999 to 99999989999999 (that’s an 8 in the 7th position), ignoring 10 million intermediary calculations that were guaranteed to fail.

With this optimisation in place, it takes 0.3 seconds to calculate both parts of our answer.

You can read my full solution here.

---

All in all, I quite enjoyed this year’s Advent of Code. I thought the second week was a bit easier than it has been in past years, but the last few days more than made up for it in terms of difficulty. I’m already looking forward to next year.

As for my tooling, I’m not sure I’ll want to use a language other than Swift as it is the language I feel most confident with, but I do hope to update my setup to use the Swift Package Manager next year. While I can mostly build or fake them in a good enough way in a pinch, I look forward to having access to solid implementations of common data structures like priority queues, graphs, and so on, both for Advent of Code and just in general.

After trickier days I like to browse the r/adventofcode solutions mega thread for the day to see what solutions and techniques others used, and while there are rarely any Swift solutions in there anyways, I don’t recall seeing a single one this year. I realise the language is somewhat esoteric and largely used by people developing native apps for Apple platforms, but I hold out hope that that changes with time.