Đọc trên blog của tác giả
Huy's Everyday Blog
Huy's Everyday Blog

12.11.2022 - Zig/Using Zig for Advent of Code

← All posts

Posted On 12.11.2022

This year, I decided to use Zig to solve Advent of Code. I started learning Zig sometime ago but took a break.

It was not something easy from the beginning, so in the first few days, I had to use either Go or TypeScript and reimplement the solution using Zig. Starting from Day 09, I became more comfortable writing Zig code.

To learn Zig, I think the best way is to refer to both of the language references◹ to learn the concepts and the source code◹ to learn about the stdlib. Reading the code is still better than reading the Standard Library Documentation◹.

Below are some notes about what I’ve learned during this session.

Read input file

There are a couple of ways to read an input file in Zig, the most common way is to use @embedFile◹:

const content = @embedFile("input.txt");

This function will take the file content and embed it into the source code as a string.

If you don’t like the idea of embedding a file into the source code, you can try reading it at runtime:

pub fn readInputFile(allocator: std.mem.Allocator) ![]const u8 {
    const file = try std.fs.cwd().openFile("input.txt", .{});
    defer file.close();
    const stat = try file.stat();
    const fileSize = stat.size;
    return try file.reader().readAllAlloc(allocator, fileSize);
}

Splitting a string

In both cases, we get a string of everything in a file, and in most problems, we should split them into lines. In Zig, to split a string, we can use std.mem.tokenize◹. This will return an iterator so you can iterate and do stuff with each of the lines.

For example, we can use an ArrayList◹ to store the lines:

var lines = std.ArrayList([]const u8).init(allocator);
defer lines.deinit();
var readIter = std.mem.tokenize(u8, content, "\n");
while (readIter.next()) |line| {
    try lines.append(line);
}

Working with strings

You can’t directly compare two []const u8 strings, and this must be done via the std.mem.eql◹ function:

const isMatch = std.mem.eql(u8, str1, str2);

To find out if a string is prefixed or postfixed with something, use std.mem.startsWith and std.mem.endsWith:

if (std.mem.startsWith(u8, <haystack>, <needle>)) {
    ...
}

There are many other helpful functions that you can use like indexOf, replace, join,… in the std.mem module. And they also work for any type of slice.

Converting between types

A string can be parsed to an integer number using the std.fmt.parseInt◹ method:

const sizeStr = "1000";
const fileSize: u64 = try std.fmt.parseInt(u64, sizeStr, 10);

Just like C or Go, you can convert a character into a number (for example, to use as array indexes) by subtracting it with the letter 'a' or convert an index back to a letter:

pub fn charCode(c: u8) usize {
    if (c >= 97 and c <= 122) {
        return c - 'a';
    } else {
        return c - 'A' + 26;
    }
}
 
pub fn codeToChar(code: usize) u8 {
    if (code < 26) {
        return 'a' + @intCast(u8, code);
    } else {
        return 'A' + @intCast(u8, code) - 26;
    }
}

Initializing arrays

If you have a list in which the length is known at comptime, you can use arrays, and the repeating pattern is very helpful in this case:

//1-dimensional array
var charFrequency: [CHAR_COUNT]usize = .{0} ** CHAR_COUNT;
//2-dimensional array
var freqs: [size][CHAR_COUNT]usize = .{.{0} ** CHAR_COUNT} ** size;

In the context of Advent of Code, most problems will have a known input size, which means we always have a comptime size:

pub fn solve(inputContent: []const u8, comptime ropeLen: usize) i32 {
    const knots: [ropeLen]Point = .{ Point.new() } ** ropeLen;
    ...
}

For an array in which length is only known at runtime, ArrayList should be the solution:

var list = std.ArrayList(Foo).init(allocator);
var listLen = list.items.len;
 
for (list.items) |item| {
    ...
}
 
const item = list.items[4];

If you really want to use an array in this case, you can allocate the array yourself:

const arr = try std.heap.c_allocator.alloc(<type>, <length>);

Or use a classical fixed-length array with a pointer to indicate the last element’s position.

// Poor man's Dynamic Array - Fixed capacity
var list: [1024]u32 = .{};
var listEnd: usize = 0;
// Insertion                                       
list[listEnd] = 1; listEnd += 1;
list[listEnd] = 2; listEnd += 1;
list[listEnd] = 3; listEnd += 1;
// Access                                       
print("{any}\n", .{list[0..listEnd]});

Poor man’s Queue

Zig has a built-in queue as part of the LinkedList module called TailQueue◹, but sometimes, if I’m in need of a handy queue and I know the set of data I’m working with is small, I’ll just roll out my own “queue”:

// Poor man's Queue
var queue: [1024]u32 = .{};
var head: usize = 0;
var tail: usize = 0;
// Enqueue / Push back
queue[tail] = 1; tail += 1;
queue[tail] = 2; tail += 1;
queue[tail] = 3; tail += 1;
// Peek the top
print("{}\n", .{queue[head]});
// Dequeue / Pop front
head += 1;
// Peek the whole queue
print("{}\n", .{queue[head..tail]});

Of course, this is neither something new nor Zig-specific and there are a lot of problems with this “queue”, but as I said, it works as long as the problem’s requirements are small.

Iterating over slices

By default, when you use the for loop to iterate over a slice, the captured value is an immutable reference of each element:

for (list.items) |item| {
    // modify item will not work
    item += 10;
}

In order to modify the elements, you’ll need to capture them as a mutable reference, and deref them with .* to modify:

for (list.items) |*item| {
    // modify item will not work
    item.* += 10;
}

Lookup table with HashMaps

Zig has many helpful built-in data structures, one of which is std.AutoHashMap◹.

var map = std.AutoHashMap(u32, bool).init(std.testing.allocator);
defer map.deinit();
 
try map.put(5, true);
 
var it = map.iterator();
while (it.next()) |entry| {
    // entry.key
    // entry.value
}
 
_ = map.remove(5);

std.AutoHashMap does not support string as a key type, and in this case, you should use std.StringHashMap◹ instead.

const DirectoryMap = std.StringHashMap(*FileEntry);
var dirMap = DirectoryMap.init(allocator);
try dirMap.put("/", &root);

You can also use std.ComptimeStringMap◹ to define a string-keyed hashmap at the compile time as well:

const MOVE_MAP = std.ComptimeStringMap(Point, .{
    .{ "U", .{ 0,  1} },
    .{ "D", .{ 0, -1} },
    .{ "R", .{ 1,  0} },
    .{ "L", .{-1,  0} },
});

std.ComptimeStringMap is limited to 2000 entries.

Working with numbers

You can cast between number types using @intCast◹:

self.display[@intCast(usize, self.cycle-1)] = '$';

In other languages, modulo can be calculated using the % operator. This is not the case in Zig. You have to use the @mod◹ function instead:

if (@mod(n, 2) == 0) {
    // even number!
}

Also, you can find the absolute value of a number using std.math.absCast◹, which will cast and return the value right away, or use std.math.absInt, which will return the error if the conversion fails.

Sorting and Searching

Zig has many interesting built-in methods to help you handle sorting and searching.

For searching, the most simple one is the std.mem.indexOf◹ function that let you find the index of an element in a slice:

const foundAt = std.mem.indexOf(u32, [_]u32{1, 2, 3, 5}, [_]u32{2});

Or you can use std.sort.binarySearch◹:

fn order_u32(context: void, lhs: u32, rhs: u32) math.Order {
    _ = context;
    return math.order(lhs, rhs);
}
 
const index = binarySearch(u32, 5, &[_]u32{ 1, 2, 3, 4, 5 }, {}, S.order_u32);

For sorting, most of the time, you can use std.sort.sort◹ method:

std.sort.sort(i32, haystack, {}, std.sort.desc(i32));

The last parameter is the comparator function, and Zig has many built-in comparators that you can use, like std.sort.asc◹, std.sort.desc◹,..

Overall, my experience using Zig for this AoC session involved a lot of fighting with the compiler due to my lack of comprehension about comptime. But once I get past that, it becomes just a pleasure to write Zig code (I know, weird).

Zig’s reference and std document are decent points to start searching for knowledge. But most of the time, they’re just lacking, and most knowledge is better found by reading the std’s source code. Which is also a good thing because it helps me know Zig’s codebase better. Heheh.

Anyway, AoC has yet to be concluded, and so does my journey with Zig. This post will be continued to grow as I learn more stuff throughout the session.

Thank you so much for reading. I hope you all have a great holiday!

After I published the article, @andrewrk commented with some suggestions about the points I made in the article:

  • (1) Use std.fs.Dir.readFileAlloc instead of your readInputFile function.
  • (2) No need to append lines into an array list. Just iterate over the memory directly.
  • (4) std.fmt.digitToChar
  • (6) std.fifo.LinearFifo
  • (9) Please be aware of what @intCast does which is asserting that the mathematical value is representable in the destination type. Also, the % operator is available but only when modulus division and remainder division would yield the same result, i.e., when the inputs are unsigned.