Sotolf's thoughts and oddities

Gettin Ziggy With It

I’m fascinated with programming languages, and I like playing around with them. The latest one that I have been really enjoying is zig, it’s a very low level language, but has some quite nice features that makes it feel a lot more high level than what it actually is.

Zig is a fun language to play around with, and I actually feel good about the code that I write in it, in comparison to go, rust and odin it’s very simple and nice to work with.

This time’s task is Advent of code 2022: day 9

Like always I start with creating a couple of types that I can use to store the input in a more convenient format:

1const Dir = enum { up, down, left, right };
2
3const Motion = struct {
4    dir: Dir,
5    len: usize,
6};

Just a simple enum and a structure to keep things together. With this we can then start working on parsing the file into a list of motions:

 1fn getLines(path: []const u8, alloc: mem.Allocator) !std.ArrayList(Motion) {
 2    const file = try fs.cwd().openFile(path, .{});
 3    defer file.close();
 4
 5    var buf_reader = std.io.bufferedReader(file.reader());
 6    const reader = buf_reader.reader();
 7
 8    var motions = std.ArrayList(Motion).init(alloc);
 9
10    var line = std.ArrayList(u8).init(alloc);
11    defer line.deinit();
12
13    var line_no: usize = 1;
14    const writer = line.writer();
15
16    while (reader.streamUntilDelimiter(writer, '\n', null)) : (line_no += 1) {
17        defer line.clearRetainingCapacity();
18        const dir = switch (line.items[0]) {
19            'D' => Dir.down,
20            'U' => Dir.up,
21            'L' => Dir.left,
22            'R' => Dir.right,
23            else => {
24                return error.UnknownDirection;
25            },
26        };
27        const steps = try std.fmt.parseInt(usize, line.items[2..line.items.len], 10);
28
29        try motions.append(Motion{ .dir = dir, .len = steps });
30    } else |err| switch (err) {
31        error.EndOfStream => {},
32        else => return err,
33    }
34
35    return motions;
36}

And that is quite a mouthful, thankfully I find the reading of files to be one of the more complex parts of this one, so if you get through that one you’re well set.

Strings in zig are []const u8 so basically a fat pointer to a character array, this gets a bit more complicted as the strings are utf-8, but as long as you know stuff is going to be ascii you can just treat it as that, thankfully.

Our return type is !std.ArrayList(Motion) the exclamation point means that this function can return an error or a value, and the function calling it will have to deal with it. We won’t see much of that in this one though, since this is basically a throw-away script all my error handling is basically bubble up to main, and quit if something is out of whack.

We also have to send an allocator along to this function, since we need to deal with arrayLists, and zig is very explicit about that, if your function allocates it needs an allocator, that way you will always be aware of where you allocate, which is nice. The only real exception to this I can see is that you can cheat if you have a function that accepts something like an arrayList, and you can then steal the allocator that it uses, but I’m quite sure that’s frowned upon.

We create some boilerplate stuff, a buffered reader and an arraylist to read the line into as a buffer. then we go through each line, parse the direction into an enum and parse the steps into an usize.

 1pub fn main() !void {
 2    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
 3    defer _ = gpa.deinit();
 4    const alloc = gpa.allocator();
 5
 6    const filename = "day09.txt";
 7    const lines = try getLines(filename, alloc);
 8    defer lines.deinit();
 9
10    try part1(lines, alloc);
11    try part2(lines, alloc);
12}

So then we can look at the main function, here we set up an allocator, parse the file into a list of motions that we then send over to the functions for part1 and part 2. We also make sure to deinit (free) the list of motions at the end of the function so that we don’t leak memory. When you use the general purpose allocator the compiler will yell at you about the memory that you forget to free, which is nice, kind of makes me feel more confident that I’m doing that correctly, and it’s good that it does, since I’ve seen from using zig a bit now, that I’m still not great at remembering to do that.

1fn part1(motions: std.ArrayList(Motion), alloc: mem.Allocator) !void {
2    var rope = Rope{};
3    const score = try rope.move(motions, alloc);
4    print("Part1: {d}\n", .{score});
5}

Part one looks very nice and high level, we construct a rope, and ask it to move through the motions, and print it’s score, this looks very nice. So let’s see what a rope is, and how it works:

 1const Rope = struct {
 2    head: Point = Point{},
 3    tail: Point = Point{},
 4
 5    fn move(self: *Rope, motions: std.ArrayList(Motion), alloc: mem.Allocator) !usize {
 6        var seen = std.AutoHashMap(Point, void).init(alloc);
 7        defer seen.deinit();
 8
 9        for (motions.items) |motion| {
10            for (0..motion.len) |_| {
11                self.head.move(motion.dir);
12                self.tail.follow(self.head);
13                try seen.put(self.tail, {});
14            }
15        }
16
17        return seen.count();
18    }
19};

So basically a rope is a head and a tail, which both are points (we will look into the point type later) and one function move, which does the main work.

Since we need to get the number of places that are visited at least once we need some way of deduping the points, and since zig has no set, we’re using a hashmap with only keys. Memory management here is very simple, since we’re just throwing everything away after the function goes through.

To do the motion we do the steps one by one, so that we can record the place of the tail after each step. Basically we inchworm our way foreward, we first move the head, and then let the tail follow. after that we record the place the tail is, and we repeat until we’re through everything.

In the end we count how many keys we have, and that’s our answer.

So the next step to look into is the Point type:

 1const Point = struct {
 2    row: i64 = 0,
 3    col: i64 = 0,
 4
 5    fn move(self: *Point, dir: Dir) void {
 6        switch (dir) {
 7            .up => self.row += 1,
 8            .down => self.row -= 1,
 9            .left => self.col -= 1,
10            .right => self.col += 1,
11        }
12    }
13
14    fn follow(self: *Point, other: Point) void {
15        const row_diff = other.row - self.row;
16        const col_diff = other.col - self.col;
17        if (@abs(row_diff) <= 1 and @abs(col_diff) <= 1) return;
18        if (col_diff > 0) {
19            self.col += 1;
20        }
21        if (col_diff < 0) {
22            self.col -= 1;
23        }
24        if (row_diff > 0) {
25            self.row += 1;
26        }
27        if (row_diff < 0) {
28            self.row -= 1;
29        }
30    }
31};

A point is pretty simple, it’s a row and column (I prefer them to x and y since they are less easy to confuse, which I often do)

The point also has two functions in it’s namespace. One that moves a point one step in a direction, and another one that lets one point follow another point, nothing really complex here, just the abs function that is a compiler builtin, probably since it works on many number types, I don’t really know why that has to be, but it is, so I’ll just have to deal with that, compiler built in functions are always prefixed with an @

And that’s it for Part 1, and Part 2 is not that much harder, first the function to part2 will look quite familiar:

1fn part2(motions: std.ArrayList(Motion), alloc: mem.Allocator) !void {
2    var rope = LongRope{};
3    const score = try rope.move(motions, alloc);
4    print("Part2: {d}\n", .{score});
5}

The only difference to part 1 is that we have a different type of rope, so let’s look at this long rope:

 1const LongRope = struct {
 2    knots: [10]Point = .{Point{}} ** 10,
 3
 4    fn move(self: *LongRope, motions: std.ArrayList(Motion), alloc: mem.Allocator) !usize {
 5        var seen = std.AutoHashMap(Point, void).init(alloc);
 6        defer seen.deinit();
 7
 8        for (motions.items) |motion| {
 9            for (0..motion.len) |_| {
10                self.knots[0].move(motion.dir);
11                for (1..self.knots.len) |idx| {
12                    self.knots[idx].follow(self.knots[idx - 1]);
13                }
14                try seen.put(self.knots[9], {});
15            }
16        }
17
18        return seen.count();
19    }
20};

The long rope has an identical interface to the normal rope, but internally it’s quite different, instead of having just a head and a tail we now have an array of 10 knots, for our move function we now iterate thorugh the array of knots, letting each of them follow the last, and we have our answer.

The whole listing will follow at the end of the post, but first, I just want to talk a little bit about things that I really enjoy with zig.

The language is very simple, it doesn’t have a lot of abstractions, basically just the normal set of basic types, and a couple of collections, and things are pretty easy to understand. Even reading the stdlib when some function has confused me wasn’t really that difficult. And I find that I could pretty quickly just write code, rather than reading and looking at the documentation all the time. There is something freeing about that. Now that being said, there are quite a lot of things I just haven’t done in it yet, like comptime, but I mean I’ve been using nim for a long time without having to deal with macros as well, but I think I will want to look into it, since it’s something people seem to really love about the language.

I like that you can put functions in the namespace of a structure or an enum, that way I feel like my code is a lot more organised than what my nim code is, I’m not sure if this is mostly an illusion, but if it is, it’s one that I really do enjoy.

I was very unsure about the fact that not using a variable, or not marking an unchanged variable is a compiler error, but I’ve had exactly that remind me of something that I hadn’t completely written through yet multiple times, so I’m leaning towards actually liking that. If I do have to run some half written code to see something I can always discard them with _ = variable so it’s not that bad.

All in all I’m really happy with the language, and I’m having fun with it, so I think I will play around with it some more.

  1const std = @import("std");
  2const mem = std.mem;
  3const fs = std.fs;
  4const print = std.debug.print;
  5
  6const ParseError = error{UnknownDirection};
  7
  8fn getLines(path: []const u8, alloc: mem.Allocator) !std.ArrayList(Motion) {
  9    const file = try fs.cwd().openFile(path, .{});
 10    defer file.close();
 11
 12    var buf_reader = std.io.bufferedReader(file.reader());
 13    const reader = buf_reader.reader();
 14
 15    var motions = std.ArrayList(Motion).init(alloc);
 16
 17    var line = std.ArrayList(u8).init(alloc);
 18    defer line.deinit();
 19
 20    var line_no: usize = 1;
 21    const writer = line.writer();
 22
 23    while (reader.streamUntilDelimiter(writer, '\n', null)) : (line_no += 1) {
 24        defer line.clearRetainingCapacity();
 25        const dir = switch (line.items[0]) {
 26            'D' => Dir.down,
 27            'U' => Dir.up,
 28            'L' => Dir.left,
 29            'R' => Dir.right,
 30            else => {
 31                return error.UnknownDirection;
 32            },
 33        };
 34        const steps = try std.fmt.parseInt(usize, line.items[2..line.items.len], 10);
 35
 36        try motions.append(Motion{ .dir = dir, .len = steps });
 37    } else |err| switch (err) {
 38        error.EndOfStream => {},
 39        else => return err,
 40    }
 41
 42    return motions;
 43}
 44
 45const Dir = enum { up, down, left, right };
 46
 47const Motion = struct {
 48    dir: Dir,
 49    len: usize,
 50};
 51
 52const Point = struct {
 53    row: i64 = 0,
 54    col: i64 = 0,
 55
 56    fn move(self: *Point, dir: Dir) void {
 57        switch (dir) {
 58            .up => self.row += 1,
 59            .down => self.row -= 1,
 60            .left => self.col -= 1,
 61            .right => self.col += 1,
 62        }
 63    }
 64
 65    fn follow(self: *Point, other: Point) void {
 66        const row_diff = other.row - self.row;
 67        const col_diff = other.col - self.col;
 68        if (@abs(row_diff) <= 1 and @abs(col_diff) <= 1) return;
 69        if (col_diff > 0) {
 70            self.col += 1;
 71        }
 72        if (col_diff < 0) {
 73            self.col -= 1;
 74        }
 75        if (row_diff > 0) {
 76            self.row += 1;
 77        }
 78        if (row_diff < 0) {
 79            self.row -= 1;
 80        }
 81    }
 82};
 83
 84const Rope = struct {
 85    head: Point = Point{},
 86    tail: Point = Point{},
 87
 88    fn move(self: *Rope, motions: std.ArrayList(Motion), alloc: mem.Allocator) !usize {
 89        var seen = std.AutoHashMap(Point, void).init(alloc);
 90        defer seen.deinit();
 91
 92        for (motions.items) |motion| {
 93            for (0..motion.len) |_| {
 94                self.head.move(motion.dir);
 95                self.tail.follow(self.head);
 96                try seen.put(self.tail, {});
 97            }
 98        }
 99
100        return seen.count();
101    }
102};
103
104const LongRope = struct {
105    knots: [10]Point = .{Point{}} ** 10,
106
107    fn move(self: *LongRope, motions: std.ArrayList(Motion), alloc: mem.Allocator) !usize {
108        var seen = std.AutoHashMap(Point, void).init(alloc);
109        defer seen.deinit();
110
111        for (motions.items) |motion| {
112            for (0..motion.len) |_| {
113                self.knots[0].move(motion.dir);
114                for (1..self.knots.len) |idx| {
115                    self.knots[idx].follow(self.knots[idx - 1]);
116                }
117                try seen.put(self.knots[9], {});
118            }
119        }
120
121        return seen.count();
122    }
123};
124
125fn part1(motions: std.ArrayList(Motion), alloc: mem.Allocator) !void {
126    var rope = Rope{};
127    const score = try rope.move(motions, alloc);
128    print("Part1: {d}\n", .{score});
129}
130
131fn part2(motions: std.ArrayList(Motion), alloc: mem.Allocator) !void {
132    var rope = LongRope{};
133    const score = try rope.move(motions, alloc);
134    print("Part2: {d}\n", .{score});
135}
136
137pub fn main() !void {
138    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
139    defer _ = gpa.deinit();
140    const alloc = gpa.allocator();
141
142    const filename = "day09.txt";
143    const lines = try getLines(filename, alloc);
144    defer lines.deinit();
145
146    try part1(lines, alloc);
147    try part2(lines, alloc);
148}