Advent of Code 2024: Day 10

$ zig version
0.13.0

This problem involves walking a grid from multiple possible starts towards multiple possible goals. For each part, I count a different measure for each path. As the longest path consists of 9 steps, from 0 to 1 to ... to 9, I decided to use recursion for the solution.

The first learning point was planned: to use a HashMap - indeed, I ended up using two. The second learning point was unplanned: anonymous structs to return multiple values from a function.

Representing the Grid

The grid is created within a readGrid function, which reads the input data from file. Each character in the file represents the height of a point in a 2D grid: so the grid is represented as a HashMap mapping points to heights.

fn readGrid(allocator: std.mem.Allocator, filename: []const u8) !std.AutoHashMap(Point, usize) {  // <1>
    const file = try std.fs.cwd().openFile(filename, .{});
    defer file.close();
    const stat = try file.stat();
    const data = try file.readToEndAlloc(allocator, stat.size);

    // setup grid
    var grid = std.AutoHashMap(Point, usize).init(allocator);                                     // <2>

    var lines = std.mem.tokenizeScalar(u8, data, '\n');
    var row: usize = 0;                                                                           // <3>
    while (lines.next()) |line| {                                                                 // <4>
        for (0..(line.len)) |col| {                                                               // <5>
            try grid.put(Point { .row = row, .col = col }, line[col]-'0');                        // <6>
        }
        row += 1;
    }

    return grid;
}

1. Notice the return type for the HashMap.
2. I use an AutoHashMap, as it is then set up to map points to numbers.
3. I keep a row counter, for the point coordinate.
4. Iterate over the lines in the file - each line will be a row in the grid.
5. Iterate over the characters in each line - each character is a column entry in the row.
6. Finally, create the point and height to put into the grid.

Finding All Trails

The heart of the program is the following function, which considers every start position in the grid and finds all possible trails to all possible goal states.

Notice that this function uses an anonymous struct to return the part_1 and part_2 solutions to the caller.

fn allTrails(allocator: std.mem.Allocator, grid: *std.AutoHashMap(Point, usize)) !struct {part_1: usize, part_2: usize} { // <1>
    var trail_score: usize = 0;
    var total_trails: usize = 0;

    var iter = grid.keyIterator();                                                                                       // <2>
    while (iter.next()) |point| {
        if (grid.get(point.*) == 0) { // for each starting point                                                         // <3>
            // buildPaths fills out this map, counting number of trails to end point:
            // results[end-point] -> count
            var result = std.AutoHashMap(Point, usize).init(allocator);                                                  // <4>
            defer result.deinit ();

            buildPaths(grid, point.*, &result);                                                                          // <5>

            // part_1: trail_score is number of keys
            trail_score += result.count ();

            // part_2: total_trails is sum of counts
            var result_iter = result.valueIterator();                                                                     // <6>
            while (result_iter.next()) |count| {
                total_trails += count.*;
            }
        }
    }

    return .{ .part_1 = trail_score, .part_2 = total_trails };                                                            // <7>
  }

1. The return type is a struct - it declares the fields, but is anonymous.
2. An iterator over the keys (the points) in the grid map.
3. Notice that the point must be dereferenced - I get references to values out of a HashMap.
4. This is the second HashMap - I use one to store a count of how often each goal state is reached by a trail.
5. Again the point must be dereferenced before passing to the buildPaths function - I also pass a pointer to the result HashMap, to store the computed values.
6. An iterator over the values is used to get a sum of counts.
7. Finally, the two calculated numbers are returned in named fields in an anonymous struct.

Finding Trails

To find the trails a matter of trying all possible paths from a given point. The problem definition meant two great simplifications could be applied: first, the fact that the height has to go up by 1 on each step means you cannot have cycles - no need to check if we are going somewhere we have been before; and second, there are a maximum of 9 steps from the origin to the goal, so recursion will not be too deep.

My buildPaths function recursively calls itself, moving to new points which are going up by one height step, until it reaches the goal. When it reaches the goal, I increase the count for that goal state by one in the result HashMap.

fn buildPaths(grid: *std.AutoHashMap(Point, usize), point: Point, result: *std.AutoHashMap(Point, usize)) void {
    if (grid.get(point)) |curr| {                                                             // <1>
        if (curr == 9) { // reached end of trail
            const counts = result.get(point) orelse 0;                                        // <2>
            result.put(point, counts + 1) catch unreachable;                                  // <3>
        } else {
            pathFrom(grid, Point{.row = point.row + 1, .col = point.col}, result, curr);      // <4>
            if (point.row > 0) {                                                              // <5>
                pathFrom(grid, Point{.row = point.row - 1, .col = point.col}, result, curr);
            }
            pathFrom(grid, Point{.row = point.row, .col = point.col + 1}, result, curr);
            if (point.col > 0) {
                pathFrom(grid, Point{.row = point.row, .col = point.col - 1}, result, curr);
            }
        }
    }
}

1. Using get to retrieve a value from a HashMap leaves open the option of getting a null value - this form of if statement guarantees that curr will be a point instance, and not null.
2. orelse is used here to ensure that counts is either the previous count for point, or 0.
3. This makes it easy to update or put the new count in the HashMap for the current point.
4. I now call the pathFrom function, which will recursively call buildPaths if the next point is valid.
5. I didn't want to use this check here, but taking it out means changing Point to use numbers which could be negative, which may require changes elsewhere in the code, etc.

The pathFrom function simply checks if the given point is valid: is it within the grid, and is it one step up in height? If so, call the buildPaths function again, recursively.

fn pathFrom(grid: *std.AutoHashMap(Point, usize), point: Point, result: *std.AutoHashMap(Point, usize), currHeight: usize) void {
    if (grid.get(point)) |nextHeight| {
        if (nextHeight == currHeight + 1) {
            buildPaths(grid, point, result);
        }
    }
}

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", .{});
    }
}

fn solveDay (allocator: std.mem.Allocator, filename: []const u8) !void {
    var grid = try readGrid(allocator, filename);
    defer grid.deinit();

    const result = try allTrails(allocator, &grid);
    std.debug.print("Part 1: {d}\n", .{result.part_1});
    std.debug.print("Part 2: {d}\n", .{result.part_2});
}

fn readGrid(allocator: std.mem.Allocator, filename: []const u8) !std.AutoHashMap(Point, 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);

    // setup grid
    var grid = std.AutoHashMap(Point, usize).init(allocator);

    var lines = std.mem.tokenizeScalar(u8, data, '\n');
    var row: usize = 0;
    while (lines.next()) |line| {
        for (0..(line.len)) |col| {
            try grid.put(Point { .row = row, .col = col }, line[col]-'0');
        }
        row += 1;
    }

    return grid;
}

fn allTrails(allocator: std.mem.Allocator, grid: *std.AutoHashMap(Point, usize)) !struct {part_1: usize, part_2: usize} {
    var trail_score: usize = 0;
    var total_trails: usize = 0;

    var iter = grid.keyIterator();
    while (iter.next()) |point| {
        if (grid.get(point.*) == 0) { // for each starting point
            // buildPaths fills out this map, counting number of trails to end point:
            // results[end-point] -> count
            var result = std.AutoHashMap(Point, usize).init(allocator);
            defer result.deinit ();

            buildPaths(grid, point.*, &result);

            // part_1: trail_score is number of keys
            trail_score += result.count ();

            // part_2: total_trails is sum of counts
            var result_iter = result.valueIterator();
            while (result_iter.next()) |count| {
                total_trails += count.*;
            }
        }
    }

    return .{ .part_1 = trail_score, .part_2 = total_trails };
}

fn buildPaths(grid: *std.AutoHashMap(Point, usize), point: Point, result: *std.AutoHashMap(Point, usize)) void {
    if (grid.get(point)) |curr| {
        if (curr == 9) { // reached end of trail
            const counts = result.get(point) orelse 0;
            result.put(point, counts + 1) catch unreachable;
        } else {
            pathFrom(grid, Point{.row = point.row + 1, .col = point.col}, result, curr);
            if (point.row > 0) {
                pathFrom(grid, Point{.row = point.row - 1, .col = point.col}, result, curr);
            }
            pathFrom(grid, Point{.row = point.row, .col = point.col + 1}, result, curr);
            if (point.col > 0) {
                pathFrom(grid, Point{.row = point.row, .col = point.col - 1}, result, curr);
            }
        }
    }
}

fn pathFrom(grid: *std.AutoHashMap(Point, usize), point: Point, result: *std.AutoHashMap(Point, usize), currHeight: usize) void {
    if (grid.get(point)) |nextHeight| {
        if (nextHeight == currHeight + 1) {
            buildPaths(grid, point, result);
        }
    }
}

const Point = struct {
    row: usize,
    col: usize,
};