Advent of Code 2024: Day 7

> zig version
0.13.0

This problem involves trying combinations of operators within a list of numbers, attempting to reach a given total: e.g. to form 79 from 12 6 7 you would do 12 * 6 + 7. Order is always from left-to-right, and the part 2 task adds a third operator.

From a Zig perspective, the data is again in lines, so we need a parseLine function to extract the expected value and the list of numbers to work with. Today's solution sees me use these in a more convenient manner.

In previous days, I created an ArrayList in the calling class, passed a reference to the file reading code, and added items to that reference. I've been working through Tyler Calder's videos and have now learnt how to create the ArrayList within the parsing code and return it to the caller, and how slices can reuse the data within that ArrayList.

The line format is "79: 12 6 7", where the number before the colon is the expected value, and the numbers after are the numbers to work with.

fn parseLine (allocator: std.mem.Allocator, line: []const u8) !struct { usize, std.ArrayList(usize) } { // <1>
    var numbers_iter = std.mem.tokenizeAny(u8, line, ": ");                                             // <2>
    const expected = try std.fmt.parseInt(usize, numbers_iter.next().?, 10);                            // <3>
    var numbers = std.ArrayList(usize).init(allocator);                                                 // <4>

    while (numbers_iter.next()) |num_str| {                                                             // <5>
        const number = try std.fmt.parseInt(usize, num_str, 10);                                        // <6>
        try numbers.append(number);                                                                     // <7>
    }

    return .{expected, numbers};                                                                        // <8>
}

The return type is an anonymous struct - the first item will be the expected value, and the second is an ArrayList of numbers.
tokenizeAny splits the line on all colon and space characters, returning an iterator on the intervening numbers.
Take the first number off the iterator, and convert to an integer - this is the expected value.
Create an ArrayList for the numbers.
We can now simply iterate through the remaining numbers,
converting each one to an integer,
and appending to the number list.
Finally, we return an anonymous struct with the expected value and list of numbers.

The function that reads the file contains the following loop on the lines in the file:

    var lines = std.mem.tokenize(u8, data, "\n");
    while (lines.next()) |line| {
        const line_data = try parseLine(allocator, line);                             // <1>
        const expected = line_data[0];                                                // <2>
        const numbers = line_data[1];
        defer numbers.deinit();                                                       // <3>

        if (isSolvable(expected, numbers.items[0], numbers.items[1..], do_concat)) {  // <4>
            result += expected;
        }
    }

Parse the line into a tuple, using the above function,
then pick out the expected value from the tuple,
and the list of numbers - not forgetting to deinit the numbers, as we now own that allocated object.
We now pass a slice of the numbers from within the ArrayList to the isSolvable function, which will use recursion to move along that slice until all numbers are processed.

Testing

Zig supports testing by writing test functions within the source code. These can be checked using zig test day-07.zig.

test parseLine {
    const line_data = try parseLine(std.testing.allocator, "182: 11 51 27");  // <1>
    defer line_data[1].deinit();                                              // <2>
    try std.testing.expect(line_data[0] == 182);                              // <3>
    try std.testing.expect(line_data[1].items.len == 3);
    try std.testing.expect(line_data[1].items[0] == 11);
    try std.testing.expect(line_data[1].items[1] == 51);
}

We can use a test allocator where needed.
Not forgetting to free up memory - if you don't, the tests will complain about leaked memory.
expect checks for correct results.

Performance

ReleaseFast makes a significant difference in performance, about 6x here.

$ zig build-exe day-07.zig 
$ time ./day-07 day-07-input.dat 

real	0m0.482s
user	0m0.475s
sys	0m0.003s

$ zig build-exe -O ReleaseFast day-07.zig 
$ time ./day-07 day-07-input.dat 

real	0m0.082s
user	0m0.078s
sys	0m0.002s

Final Program

const std = @import("std");

pub fn main() !void {
    // get allocator
    var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
    const allocator = arena.allocator();
    defer _ = arena.deinit();

    // get command-line args
    const args = try std.process.argsAlloc(allocator);
    defer std.process.argsFree(allocator, args);

    // see if filename is on command-line
    if (args.len == 2) {
        const filename = args[1];
        solveDay(allocator, filename) catch |err| {
            switch (err) {
                error.FileNotFound => {
                    std.debug.print("Error: File {s} was not found.\n", .{filename});
                    std.process.exit(1);
                },
                else => {
                    std.debug.print("Error: in processing file.\n", .{});
                    std.process.exit(1);
                },
            }
        };
    } else {
        std.debug.print("Provide a filename of input data.\n", .{});
    }
}

// call the solvers and report results
fn solveDay (allocator: std.mem.Allocator, filename: []const u8) !void {
    std.debug.print("Part 1: {d}\n", .{try countSolveables(allocator, filename, false)});
    std.debug.print("Part 2: {d}\n", .{try countSolveables(allocator, filename, true)});
}

// line of form: "182: 11 51 27" - return (182, { 11, 51, 27} ) as anonymous struct
fn parseLine (allocator: std.mem.Allocator, line: []const u8) !struct { usize, std.ArrayList(usize) } {
    var numbers_iter = std.mem.tokenizeAny(u8, line, ": ");
    const expected = try std.fmt.parseInt(usize, numbers_iter.next().?, 10);
    var numbers = std.ArrayList(usize).init(allocator);

    while (numbers_iter.next()) |num_str| {
        const number = try std.fmt.parseInt(usize, num_str, 10);
        try numbers.append(number);
    }

    return .{expected, numbers}; 
}

test parseLine {
    const line_data = try parseLine(std.testing.allocator, "182: 11 51 27");
    defer line_data[1].deinit();
    try std.testing.expect(line_data[0] == 182);
    try std.testing.expect(line_data[1].items.len == 3);
    try std.testing.expect(line_data[1].items[0] == 11);
    try std.testing.expect(line_data[1].items[1] == 51);
}

fn combine (num1: usize, num2: usize) usize {
    const multiplier = std.math.powi(usize, 10, std.math.log10_int(num2) + 1) catch { return 1; };
    return num1 * multiplier + num2;
}

test combine {
    try std.testing.expect(combine(1, 2) == 12);
    try std.testing.expect(combine(48, 157) == 48157);
}

fn isSolvable (expected: usize, current: usize, numbers: []usize, do_concat: bool) bool {
    if (numbers.len == 0) {
        return expected == current;
    } else if (current > expected) {
        return false;
    } else {
        // try +
        if (isSolvable(expected, current+numbers[0], numbers[1..], do_concat)) {
            return true;
        }
        // try *
        if (isSolvable(expected, current*numbers[0], numbers[1..], do_concat)) {
            return true;
        }
        // try concat
        if (do_concat and
            isSolvable(expected, combine(current, numbers[0]), numbers[1..], do_concat)) {
            return true;
        }
    }

    return false;
}

test isSolvable {
    var ex1 = [_]usize{10, 19};
    try std.testing.expect(isSolvable(190, ex1[0], ex1[1..], false) == true);
    var ex2 = [_]usize{81, 40, 27};
    try std.testing.expect(isSolvable(3267, ex2[0], ex2[1..], false) == true);
    var ex3 = [_]usize{15, 6};
    try std.testing.expect(isSolvable(156, ex3[0], ex3[1..], false) == false);
    try std.testing.expect(isSolvable(156, ex3[0], ex3[1..], true) == true);
    var ex4 = [_]usize{6, 8, 6, 15};
    try std.testing.expect(isSolvable(7290, ex4[0], ex4[1..], false) == false);
    try std.testing.expect(isSolvable(7290, ex4[0], ex4[1..], true) == true);
}

fn countSolveables (allocator: std.mem.Allocator, filename: []const u8, do_concat: bool) !usize { 
    const file = try std.fs.cwd().openFile(filename, .{});
    defer file.close();
    const stat = try file.stat();
    const data = try file.readToEndAlloc(allocator, stat.size);

    var result: usize = 0;

    var lines = std.mem.tokenize(u8, data, "\n");
    while (lines.next()) |line| {
        const line_data = try parseLine(allocator, line);
        const expected = line_data[0];
        const numbers = line_data[1];
        defer numbers.deinit();

        if (isSolvable(expected, numbers.items[0], numbers.items[1..], do_concat)) {
            result += expected;
        }
    }

    return result;
}