Advent of Code 2024 in Zig - Day 2

Onwards to day 2, we're looking at reports!

If you want to check the previous day, linkie below 👇

Advent of Code 2024 in Zig - Day 1

Inspired by my brother’s post about his efforts solving AOC with Rust, I thought I’d share my adventure with Zig. I decided to choose Zig because I wanted to get into manual-memory-managed-land. I have solved some days in the previous years using Go, Clojure, and Rust, so I thought I’d

Dan's thoughtsDaniel

Given a list of numbers on each line, determine if they are "safe", where safe is:

1. strictly descending OR ascending
2. each subsequent number is only 1, 2, or 3 higher/lower than the previous one

So let's get crack'alackin. Boilerplate is same as previously, so just high level:

1. initialize an arena allocator, defer its deinit()
2. split input into lines

Then, for each line, create an list of the numbers on the line

var chars = mem.tokenizeScalar(u8, line, ' ');

// create list
var nums = std.ArrayList(i16).init(allocator);

while (chars.next()) |char| {
    try nums.append(try std.fmt.parseInt(i16, char, 10));
}

How do we determine whether it's safe? We could do what we did for day 1, get the diff between two numbers and see if it's between 1 and 3, but there's the thing of strictly increasing vs decreasing.. how do we handle that?

With an enum, thank you for asking:

const Dir = enum { increasing, decreasing };

fn is_safe(nums: []i16, dir: Dir) bool {
    return for (nums[0 .. nums.len - 1], nums[1..]) |n1, n2| {
        const diff = switch (dir) {
            .decreasing => n1 - n2,
            .increasing => n2 - n1,
        };
        if (diff < 1 or 3 < diff) {
            return false;
        }
    } else return true;
}

Lots happening here, so let's unpack:

1. Zig's for loops are expressions. We can return a value from them, but we need to make sure to return something if our loop did not produce one (see else return true; )
2. We once again take advantage of looping over two slices at the same time, or rather, one slice but an index apart (also sometimes called a "window"):
   1. nums[0 .. nums.len - 1] returns 0, 1, ... length - 1 elements
   2. nums[1..] returns 1, 2, ... length elements.
3. We then switch on the enum to produce the difference between the two numbers we have in the window.
4. Then comes the check - if the diff is less than 1, or more than 3, we can return false, because it violates the requirements.
5. If none of our numbers produce a false result, we know that the whole report is good, so at the end we return true

I don't know where I saw this, but if you look at diff check, it's a bit weird:

if (diff < 1 or 3 < diff) {
    return false;
}

Slight tangent, but you might be wondering why did I put diff in different locations for the two checks?

Because this way it helps to understand visually what the check is. diff is less than one, or more than three. It's as if it's on a number line. Compare the two versions below.

if (diff  <  1  or  3   <  diff)   

----diff-----1------3------diff---->

if (diff  <  1  or  diff  >  3  )

Tangent aside, here's how we check if a report is safe:

if (is_safe(nums.items, .increasing) or is_safe(nums.items, .decreasing)) {
    safe_reports += 1;
}

At the end, we return safe_reports (which starts as 0), which is the solution.

Same as for task 1, but this time we have to check whether each line is safe, allowing for one number that violates the requirements. So a line could be unsafe per first task's requirements, but if we were to remove one of the numbers (any one of them), then it could become safe.

The boilerplate for the task is the same - tokenize, parse, put into a list, then check if the report is safe.

How do we do this? One way could be recursion - remove one element from the list, and check whether the new list is safe.

I did not do it recursively though - instead:

fn is_safe_dampened(nums: []i16, dir: Dir) !bool {
    return for (0..nums.len) |idx_to_skip| {
        var count: u8 = 0;
        for (0..nums.len - 1) |idx| {
            if (idx == idx_to_skip) {
                continue;
            }
            const next_idx = if (idx + 1 == idx_to_skip) idx + 2 else idx + 1;
            if (next_idx >= nums.len) {
                continue;
            }

            const diff = switch (dir) {
                .decreasing => nums[idx] - nums[next_idx],
                .increasing => nums[next_idx] - nums[idx],
            };
            if (1 <= diff and diff <= 3) {
                count += 1;
            }
        }
        if (count == nums.len - 2) {
            return true;
        }
    } else return false;
}

Again, lots happening here, so:

1. outer loop produces indexes (idx_to_skip). We use this to decide which entry in the list to ignore
2. inner loop also produces indexes (idx). We use this to get the element at idx and idx+1 , except:
   1. if idx_to_skip == idx => we skip the check
   2. if idx_to_skip == idx + 1, then the next element will be idx + 2
3. We do this to ensure we check the list as if the element at idx_to_skip did not even exist in the list

We then do the same check as before, see if it's safe. This time though we keep track of number pairs that are safe, with a count. At the end of the outer loop (remember: where we have the idx_to_skip), if the number of times we saw correct numbers is equal to the size of the list sans the entry we skipped, we know that the report is safe.

This passes both the example and my input, but it's weird - surely there should exist entries that are safe but once we remove an item, it becomes unsafe. This does not happen in my input, as my solution passes (I don't do a separate check for the whole report, without ignoring numbers).

Oh well, as long as AOC is happy 🤷