https://www.huy.rocks/everyday/12-11-2022-zig-using-zig-for-advent-of-code

huy.rocks/everyday#

- All posts

Zig / Using Zig for Advent of Code

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^&urtri; 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^&urtri;, 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^&urtri;.

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^&urtri; instead.

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

You can also use std.ComptimeStringMap^&urtri; 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^&urtri;:

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^&urtri;
function instead:

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

Also, you can find the absolute value of a number using
std.math.absCast^&urtri;, 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^&urtri;
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^&urtri;:

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^&urtri;
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^&urtri;,
std.sort.desc^&urtri;,..

---------------------------------------------------------------------

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!

---------------------------------------------------------------------
Read more

  * 08.31.2022 - TypeScript/Test parameter passed into a function
    with Jest
  * 08.29.2022 - TypeScript/Optional Chaining and Code Coverage
  * 08.28.2022 - Typescript/Mocking File and FileList in Jest
  * 08.27.2022 - TypeScript/Testing localStorage in Jest
  * 06.06.2022 - Self-hosting/Migrating docker-compose application to
    M1 Mac

 @huy

 RSS