This year I wanted to do a little write up on the Advent of Code solutions As I solved them using the Zig programming language. Obviously there are going to be spoilers, so stop reading now if you don’t want to see them.

Day 1:

As is customary with each year, we are presented with an overarching problem that will need to be solved over the next 25 days. This year the elves' chief historian has gone AWOL. The senior historians have asked for our help in finding him.

The first task is to find where he may have gone. The historians give us two lists they have compiled of ID’s of locations that he may have been. Unfortunately the lists don’t match.

Our first task is to see how far off each list is from each other, by comparing each number by it’s relative position in the list, the minimum of list 1 to the minimum of list 2.

Part 1 Solution:

Reading Data

The solution requires that we read the data in our file. For this I wrote a simple helper function loadData:

/// Load the Data from path
fn loadData(allocator: Allocator, path: []const u8) ![]u8 {
    const fd = try fs.cwd().openFile(path, .{});
    return try fd.readToEndAlloc(allocator, max_read);
}

Something I’ve had to get used to with languages like Zig or Rust, is the extensive API’s provided by the standard library. readToEndAlloc is an example of that. While zig provides a basic read function for it’s File structs, it also provides many other read like functions so that we can read our files in specific ways.

For something as simple as Advent of Code, I find readToEndAlloc with a generous max_read value to be sufficient for my needs.

Parsing the data

Now that we have the data loaded we need to split it into two lists. The goal will then be to sort both lists and doing a element-wise subtraction of each list to calculate our “Distance” score (the target value for this part of the challenge).

zig provides some basic tooling for parsing sequences of values. Here our data looks like this:

3   4
4   3
2   5
1   3
3   9
3   3

Generally we have a pattern like this “{number}{space}{number}\n”. The std.mem.tokenizeAny function comes in handy here. std.mem.tokenize* family of functions are useful for taking text and splitting it up on either a character (tokenizeScalar) or string (tokenizeSequence). tokenizeAny will work like tokenizeScalar, except that you can specify multiple characters to split on. In this case I used the newline and the space characters.

var iter = std.mem.tokenizeAny(u8, rawdata, "\n ");

The tokenize functions return an iterator, which means we can loop on it. Because I’ve split the data on both newlines and spaces, we will get a pattern like this {3, 4, 4, …, null}. Every odd element will go in our first list and every even element will go in our seconds list.

/// Initialize our lists
var list1 = std.ArrayList(usize).init(allocator);
var list2 = std.ArrayList(usize).init(allocator);

var i: usize = 0;
while (iter.next()) |id| : (i += 1) {
    if (i % 2 == 0) {
        try list1.append(try fmt.parseInt(usize, id, 10));
    } else {
        try list2.append(try fmt.parseInt(usize, id, 10));
    }
}

In zig you can loop over an optional value, where the loop terminates if it receives a null value. Each call to next will return the next value in the iterator until it is complete, where it sends a final null. It is a great pattern that allows for core language features (loops) to be used by custom types, but doesn’t depend on hidden control flow, as you would in a language like python.

Sorting

Once we are done parsing the data, we just need to sort each list and do our distance calculations. The Zig standard library provides a few sorting implementations in the std.sort namespace. In this case i chose pdq sort, which is an unstable inplace sorting function. Since we don’t care what order equal elements are in, this method of sorting should be perfect for our use case.

sort.pdq(usize, list1.items, .{}, lessThan);
sort.pdq(usize, list2.items, .{}, lessThan);

Now you may look at this and wonder why there is so much information needed to call sort. If we look at the function signature for pdq sort we will see:

pub fn pdq(
    comptime T: type,
    items: []T,
    context: anytype,
    comptime lessThanFn: fn (context: @TypeOf(context), lhs: T, rhs: T) bool,
) void

The first argument T is the Type of the values being sorted. The next one items is a slice of our objects that we want to sort. So far that seems fairly straightforward.

The third parameter is the context parameter. This is a common pattern in zig, where a functions behavior can be modified by passing in a context object. In our case we don’t really need any context, so we just pass in an empty struct.

Finally, we have the lessThanFn parameter. Because pdq sort can be used on any Type, we need to define a function that it can use to do comparisons of the Type in question. In our case we are comparing unsigned integers of type usize, so a simple function will do:

fn lessThan(_: @TypeOf(.{}), a: usize, b: usize) bool {
    return a < b;
}

Part 2

Unfortunately, after doing our analysis of the two lists, it seems like the lists are too different. But maybe we can find a different way to measure similarity. Rather than calculate the distance between elements, the historians urge us to count the number of times each location id in the first list appears in the second list.

Overview of solution

In order to achieve this, I decided to use a hashmap to keep track of all the different values in the second list, using it as a counter. Once we have that we can loop over the values in the first list and perform the required calculation.

AutoHashMap

To use our map, I decided to use the AutoHashMap. In this case the Auto in AutoHashMap refers to the fact that you are getting a default configuration of the HashMap that zig provides. Zig provides a highly configurable HashMap implementation, however often we just want the ‘out of the box’ version. This is what the AutoHashMap gives us.

Once we have that set up, it just requires a tweak to our current code to add in support for our ‘counter’.

var i: usize = 0;
while (iter.next()) |id| : (i += 1) {
    if (i % 2 == 0) {
        try list1.append(try fmt.parseInt(usize, id, 10));
    } else {
        try list2.append(try fmt.parseInt(usize, id, 10));
        const entry = try counter.getOrPut(try fmt.parseInt(usize, id, 10));
        if (entry.found_existing) {
            entry.value_ptr.* += 1;
        } else {
            entry.value_ptr.* = 1;
        }
    }
}

With the getOrPut function, we are able to get an Entry out of the map by key. If the value doesn’t exist yet, the entry is created in the map, with an undefined value, which we can then set. value_ptr gives us a pointer to the value, which allows us to update the map as we go.

Conclusion

Overall, as is expected for the first day of Advent Of Code, the Logical portion of the challenge was fairly straightforward. However it did provide opportunity to learn about some structs and modules I haven’t used before in zig. The full code for today’s answer is available on my github.

• zig
• AoC2024