AoC 2024: Day 10

Brainstorming
1

Main thread for Day 10 of the 2024 advent of code. Feel free to discuss the challenge and ask questions. If particular discussions become large, we can break them off into new threads.

Some Rules:

  1. Please try to keep spoilers within spoiler tags. This is done by typing [spoiler]text to be blurred[\spoiler]. If you have longer sections you can also use the [details=“Title”] tags.
  2. Have Fun

Day 10 Challenge

Templates:

Resources:

Previous days discussions

Day 1: AoC 2024: Day 1
Day 2: AoC 2024: Day 2
Day 3: AoC 2024: Day 3
Day 4: AoC 2024: Day 4
Day 5: AoC 2024: Day 5
Day 6: AoC 2024: Day 6
Day 7: AoC 2024: Day 7
Day 8: AoC 2024: Day 8
Day 9: AoC 2024: Day 9

2

Wrote a little Matrix type to make it nicer. Overkill? Yes. Educational? As well.

Parts 1 & 2 
const std = @import("std");

pub fn Matrix(comptime T: type, comptime rows: usize, comptime cols: usize) type {
    return struct {
        const Self = @This();
        m: [rows * cols]T,
        pub fn init() Self {
            return Self{ .m = undefined };
        }
        pub fn at(self: Self, v: @Vector(2, usize)) T {
            return self.m[rows * v[0] + v[1]];
        }
        pub fn set(self: *Self, v: @Vector(2, usize), value: T) void {
            self.m[rows * v[0] + v[1]] = value;
        }
    };
}

const Vec2 = @Vector(2, usize);
pub fn part1(allocator: std.mem.Allocator, input: []const u8, comptime rows: usize, comptime cols: usize) !u32 {
    var m = Matrix(u8, rows, cols).init();
    var it = std.mem.tokenizeScalar(u8, input, '\n');
    var i: usize = 0;
    var starts = std.ArrayList(Vec2).init(allocator);
    defer starts.deinit();
    while (it.next()) |line| : (i += 1) {
        for (line, 0..) |c, ii| {
            m.setV(Vec2{ i, ii }, c - '0');
            if (c == '0') {
                try starts.append(Vec2{ i, ii });
            }
        }
    }
    var acc: u32 = 0;
    for (starts.items) |start| {
        var seen = std.AutoHashMap(Vec2, void).init(allocator);
        defer seen.deinit();
        var queue = std.ArrayList(Vec2).init(allocator);
        defer queue.deinit();
        try queue.append(start);
        while (queue.items.len > 0) {
            const curr = queue.pop();
            if (seen.contains(curr)) continue;
            try seen.put(curr, {});
            if (m.at(curr) == 9) {
                acc += 1;
            }
            // neighbors
            if (curr[0] > 0) {
                const next = curr - Vec2{ 1, 0 };
                if (m.at(next) == m.at(curr) + 1) {
                    try queue.insert(0, next);
                }
            }
            if (curr[0] < rows - 1) {
                const next = curr + Vec2{ 1, 0 };
                if (m.at(next) == m.at(curr) + 1) {
                    try queue.insert(0, next);
                }
            }
            if (curr[1] > 0) {
                const next = curr - Vec2{ 0, 1 };
                if (m.at(next) == m.at(curr) + 1) {
                    try queue.insert(0, next);
                }
            }
            if (curr[1] < cols - 1) {
                const next = curr + Vec2{ 0, 1 };
                if (m.at(next) == m.at(curr) + 1) {
                    try queue.insert(0, next);
                }
            }
        }
    }
    return acc;
}

pub fn part2(allocator: std.mem.Allocator, input: []const u8, comptime rows: usize, comptime cols: usize) !u32 {
    var m = Matrix(u8, rows, cols).init();
    var it = std.mem.tokenizeScalar(u8, input, '\n');
    var i: usize = 0;
    var starts = std.ArrayList(Vec2).init(allocator);
    defer starts.deinit();
    while (it.next()) |line| : (i += 1) {
        for (line, 0..) |c, ii| {
            m.setV(Vec2{ i, ii }, c - '0');
            if (c == '0') {
                try starts.append(Vec2{ i, ii });
            }
        }
    }
    var acc: u32 = 0;
    for (starts.items) |start| {
        var queue = std.ArrayList(Vec2).init(allocator);
        defer queue.deinit();
        try queue.append(start);
        while (queue.items.len > 0) {
            const curr = queue.pop();
            if (m.at(curr) == 9) {
                acc += 1;
            }
            // neighbors
            if (curr[0] > 0) {
                const next = curr - Vec2{ 1, 0 };
                if (m.at(next) == m.at(curr) + 1) {
                    try queue.insert(0, next);
                }
            }
            if (curr[0] < rows - 1) {
                const next = curr + Vec2{ 1, 0 };
                if (m.at(next) == m.at(curr) + 1) {
                    try queue.insert(0, next);
                }
            }
            if (curr[1] > 0) {
                const next = curr - Vec2{ 0, 1 };
                if (m.at(next) == m.at(curr) + 1) {
                    try queue.insert(0, next);
                }
            }
            if (curr[1] < cols - 1) {
                const next = curr + Vec2{ 0, 1 };
                if (m.at(next) == m.at(curr) + 1) {
                    try queue.insert(0, next);
                }
            }
        }
    }
    return acc;
}
3

Initially my first solution was doing what was asked for in part two, because i misunderstood the task.

Solution-1

const std = @import(“std”);

//const input = @embedFile(“./small.inp”);
const input = @embedFile(“./big.inp”);

fn digit2number(digit: u8) i8 {
switch (digit) {
‘1’ => return 1,
‘2’ => return 2,
‘3’ => return 3,
‘4’ => return 4,
‘5’ => return 5,
‘6’ => return 6,
‘7’ => return 7,
‘8’ => return 8,
‘9’ => return 9,
‘0’ => return 0,
‘.’ => return -1,
else => unreachable,
}
}

const peak_t = struct { irow: usize, icol: usize, reached: bool };

const grid_t = struct {
nrows: usize,
ncols: usize,
vals: std.ArrayList(i8),

const Self = @This();

pub fn init(allocator: std.mem.Allocator) Self {
    const grid = Self{
        .nrows = 0,
        .ncols = 0,
        .vals = std.ArrayList(i8).init(allocator),
    };
    return grid;
}

pub fn deinit(self: *Self) void {
    self.nrows = 0;
    self.ncols = 0;
    _ = self.vals.deinit();
}

pub fn get_pos(self: Self, irow: usize, icol: usize) ?i8 {
    if (irow < self.nrows and icol < self.ncols) {
        return self.vals.items[irow * self.ncols + icol];
    }
    return null;
}

pub fn read(self: *Self, inputstr: []const u8) !void {
    var lines = std.mem.tokenizeScalar(u8, inputstr, '\n');

    while (lines.next()) |line| {
        self.nrows += 1;
        for (line) |char| {
            try self.vals.append(digit2number(char));
        }
    }
    self.ncols = self.vals.items.len / self.nrows;
}

pub fn print(self: Self) void {
    std.debug.print("\n", .{});
    std.debug.print("{d}x{d}\n", .{ self.nrows, self.ncols });
    for (0..self.nrows) |irow| {
        for (0..self.ncols) |icol| {
            const maybe_pos = self.get_pos(irow, icol);
            if (maybe_pos) |pos| {
                if (pos >= 0) {
                    std.debug.print("{d}", .{pos});
                } else {
                    std.debug.print(".", .{});
                }
            }
        }
        std.debug.print("\n", .{});
    }
}

pub fn find_reachable_peaks(self: Self, irow: usize, icol: usize, expect_height: i8, peaks: *std.ArrayList(peak_t)) void {
    const maybe_pos = self.get_pos(irow, icol);
    if (maybe_pos) |pos| {
        // tested position matches
        if (pos == expect_height) {
            // finished exploration
            if (pos == 9) {
                for (peaks.items) |*peak| {
                    if (peak.irow == irow and peak.icol == icol) {
                        peak.reached = true;
                    }
                }
            } else {
                if (irow < self.nrows - 1) {
                    self.find_reachable_peaks(irow + 1, icol, expect_height + 1, peaks);
                }
                if (irow > 0) {
                    self.find_reachable_peaks(irow - 1, icol, expect_height + 1, peaks);
                }
                if (icol < self.ncols - 1) {
                    self.find_reachable_peaks(irow, icol + 1, expect_height + 1, peaks);
                }
                if (icol > 0) {
                    self.find_reachable_peaks(irow, icol - 1, expect_height + 1, peaks);
                }
            }
        }
    }
}

pub fn get_score(self: Self, irow: usize, icol: usize, peaks: *std.ArrayList(peak_t)) i32 {
    self.find_reachable_peaks(irow, icol, 0, peaks);
    var score: i32 = 0;
    for (peaks.items) |*peak| {
        if (peak.reached) {
            score += 1;
            peak.reached = false;
        }
    }
    return score;
}

};

pub fn main() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();

var grid = grid_t.init(allocator);
defer _ = grid.deinit();

try grid.read(input);
grid.print();

// create list of peaks
var peaks = std.ArrayList(peak_t).init(allocator);
defer _ = peaks.deinit();

for (0..grid.nrows) |irow| {
    for (0..grid.ncols) |icol| {
        const maybe_pos = grid.get_pos(irow, icol);
        if (maybe_pos) |pos| {
            if (pos == 9) {
                try peaks.append(peak_t{ .irow = irow, .icol = icol, .reached = false });
            }
        }
    }
}

var sum: i32 = 0;
for (0..grid.nrows) |irow| {
    for (0..grid.ncols) |icol| {
        const maybe_pos = grid.get_pos(irow, icol);
        if (maybe_pos) |pos| {
            // check if trail head
            if (pos == 0) {
                const score: i32 = grid.get_score(irow, icol, &peaks);
                //std.debug.print("Score({d},{d}) = {d}\n", .{ irow, icol, score });
                sum += score;
            }
        }
    }
}

std.debug.print("Sum of scores: {d}\n", .{sum});

}

Solution-2

const std = @import(“std”);

//const input = @embedFile(“./small.inp”);
const input = @embedFile(“./big.inp”);

fn digit2number(digit: u8) i8 {
switch (digit) {
‘1’ => return 1,
‘2’ => return 2,
‘3’ => return 3,
‘4’ => return 4,
‘5’ => return 5,
‘6’ => return 6,
‘7’ => return 7,
‘8’ => return 8,
‘9’ => return 9,
‘0’ => return 0,
‘.’ => return -1,
else => unreachable,
}
}

const grid_t = struct {
nrows: usize,
ncols: usize,
vals: std.ArrayList(i8),

const Self = @This();

pub fn init(allocator: std.mem.Allocator) Self {
    const grid = Self{
        .nrows = 0,
        .ncols = 0,
        .vals = std.ArrayList(i8).init(allocator),
    };
    return grid;
}

pub fn deinit(self: *Self) void {
    self.nrows = 0;
    self.ncols = 0;
    _ = self.vals.deinit();
}

pub fn get_pos(self: Self, irow: usize, icol: usize) ?i8 {
    if (irow < self.nrows and icol < self.ncols) {
        return self.vals.items[irow * self.ncols + icol];
    }
    return null;
}

pub fn read(self: *Self, inputstr: []const u8) !void {
    var lines = std.mem.tokenizeScalar(u8, inputstr, '\n');

    while (lines.next()) |line| {
        self.nrows += 1;
        for (line) |char| {
            try self.vals.append(digit2number(char));
        }
    }
    self.ncols = self.vals.items.len / self.nrows;
}

pub fn print(self: Self) void {
    std.debug.print("\n", .{});
    std.debug.print("{d}x{d}\n", .{ self.nrows, self.ncols });
    for (0..self.nrows) |irow| {
        for (0..self.ncols) |icol| {
            const maybe_pos = self.get_pos(irow, icol);
            if (maybe_pos) |pos| {
                if (pos >= 0) {
                    std.debug.print("{d}", .{pos});
                } else {
                    std.debug.print(".", .{});
                }
            }
        }
        std.debug.print("\n", .{});
    }
}

pub fn score_path(self: Self, irow: usize, icol: usize, expect_height: i8) i32 {
    var score: i32 = 0;
    const maybe_pos = self.get_pos(irow, icol);
    if (maybe_pos) |pos| {
        // tested position matches
        if (pos == expect_height) {
            // finished exploration
            if (pos == 9) {
                score += 1;
            } else {
                if (irow < self.nrows - 1) {
                    score += self.score_path(irow + 1, icol, expect_height + 1);
                }
                if (irow > 0) {
                    score += self.score_path(irow - 1, icol, expect_height + 1);
                }
                if (icol < self.ncols - 1) {
                    score += self.score_path(irow, icol + 1, expect_height + 1);
                }
                if (icol > 0) {
                    score += self.score_path(irow, icol - 1, expect_height + 1);
                }
            }
        }
    }
    return score;
}

pub fn get_score(self: Self, irow: usize, icol: usize) i32 {
    return self.score_path(irow, icol, 0);
}

};

pub fn main() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();

var grid = grid_t.init(allocator);
defer _ = grid.deinit();

try grid.read(input);
grid.print();

var sum: i32 = 0;
for (0..grid.nrows) |irow| {
    for (0..grid.ncols) |icol| {
        const maybe_pos = grid.get_pos(irow, icol);
        if (maybe_pos) |pos| {
            // check if trail head
            if (pos == 0) {
                const score: i32 = grid.get_score(irow, icol);
                //std.debug.print("Score({d},{d}) = {d}\n", .{ irow, icol, score });
                sum += score;
            }
        }
    }
}

std.debug.print("Sum of scores: {d}\n", .{sum});

}

4

I also accidentally implemented p2 first :smiley:

Part 1 & 2 
const std = @import("std");

const util = @import("util.zig");
const gpa = util.gpa;

const data = @embedFile("data/day10.txt");

const Point = struct { x: usize, y: usize };

const lim = 54;
var grid = [_][lim]u8{[_]u8{0} ** lim} ** lim;
var visited_peaks: [lim]std.bit_set.IntegerBitSet(lim) = undefined;

pub fn main() !void {
    var p1: u32 = 0;
    var p2: u32 = 0;

    var lines = std.mem.tokenizeScalar(u8, data, '\n');
    var i: usize = 0;
    var zero_positions = std.ArrayList(Point).init(gpa);

    while (lines.next()) |line| : (i += 1) {
        for (line, 0..) |c, j| {
            const val = c - '0';
            grid[i][j] = val;

            if (val == 0) {
                try zero_positions.append(Point{ .x = i, .y = j });
            }
        }
    }

    for (zero_positions.items) |pos| {
        for (0..lim) |idx| {
            visited_peaks[idx] = std.bit_set.IntegerBitSet(lim).initEmpty();
        }

        p1 += trails(0, pos.x, pos.y);
        p2 += trailsScore(0, pos.x, pos.y);
    }

    std.debug.print("part1: {}\n", .{p1});
    std.debug.print("part2: {}\n", .{p2});
}

pub fn trails(current: u8, x: usize, y: usize) u32 {
    if (current == 9) {
        if (visited_peaks[x].isSet(y)) return 0;

        visited_peaks[x].toggle(y);
        return 1;
    }

    const next = current + 1;
    var trails_found: u32 = 0;

    if (x > 0 and grid[x - 1][y] == next) trails_found += trails(next, x - 1, y);
    if (x < lim - 1 and grid[x + 1][y] == next) trails_found += trails(next, x + 1, y);
    if (y > 0 and grid[x][y - 1] == next) trails_found += trails(next, x, y - 1);
    if (y < lim - 1 and grid[x][y + 1] == next) trails_found += trails(next, x, y + 1);

    return trails_found;
}

pub fn trailsScore(current: u8, x: usize, y: usize) u32 {
    if (current == 9) return 1;

    const next = current + 1;
    var trails_found: u32 = 0;

    if (x > 0 and grid[x - 1][y] == next) trails_found += trailsScore(next, x - 1, y);
    if (x < lim - 1 and grid[x + 1][y] == next) trails_found += trailsScore(next, x + 1, y);
    if (y > 0 and grid[x][y - 1] == next) trails_found += trailsScore(next, x, y - 1);
    if (y < lim - 1 and grid[x][y + 1] == next) trails_found += trailsScore(next, x, y + 1);

    return trails_found;
}
5

I think part one and part two came in the wrong order :smile:.

Part 1 
const std = @import("std");

const input = @embedFile("input.txt");
const map_width = 45;
const map_height = 45;

const Map = [map_height][map_width]u8;

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

    const map = parseInput();

    var routes: u32 = 0;
    var ends = std.AutoHashMap(struct { usize, usize }, void).init(arena.allocator());
    for (map, 0..) |line, row| {
        for (line, 0..) |height, col| {
            if (height == 0) {
                try findRoutes(&map, row, col, &ends);
                routes += ends.count();
                ends.clearRetainingCapacity();
            }
        }
    }
    std.debug.print("{d}\n", .{routes});
}

fn findRoutes(map: *const Map, row: usize, col: usize, ends: *std.AutoHashMap(struct { usize, usize }, void)) !void {
    const current_height = map[row][col];
    if (current_height == 9 and !ends.contains(.{ row, col })) {
        try ends.put(.{ row, col }, {});
    }

    if (col > 0 and map[row][col - 1] == current_height + 1) {
        try findRoutes(map, row, col - 1, ends);
    }
    if (col < map_width - 1 and map[row][col + 1] == current_height + 1) {
        try findRoutes(map, row, col + 1, ends);
    }
    if (row > 0 and map[row - 1][col] == current_height + 1) {
        try findRoutes(map, row - 1, col, ends);
    }
    if (row < map_height - 1 and map[row + 1][col] == current_height + 1) {
        try findRoutes(map, row + 1, col, ends);
    }
}

fn parseInput() Map {
    var map: Map = undefined;
    var lines = std.mem.tokenizeScalar(u8, input, '\n');
    var row: usize = 0;
    while (lines.next()) |line| {
        for (line, 0..) |height, col| {
            map[row][col] = height - '0';
        }
        row += 1;
    }
    return map;
}
Part 2 
const std = @import("std");

const input = @embedFile("input.txt");
const map_width = 45;
const map_height = 45;

const Map = [map_height][map_width]u8;

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

    const map = parseInput();

    var routes: u32 = 0;
    for (map, 0..) |line, row| {
        for (line, 0..) |height, col| {
            if (height == 0) {
                routes += findRoutes(&map, row, col);
            }
        }
    }
    std.debug.print("{d}\n", .{routes});
}

fn findRoutes(map: *const Map, row: usize, col: usize) u32 {
    const current_height = map[row][col];
    if (current_height == 9) {
        return 1;
    }

    var routes: u32 = 0;

    if (col > 0 and map[row][col - 1] == current_height + 1) {
        routes += findRoutes(map, row, col - 1);
    }
    if (col < map_width - 1 and map[row][col + 1] == current_height + 1) {
        routes += findRoutes(map, row, col + 1);
    }
    if (row > 0 and map[row - 1][col] == current_height + 1) {
        routes += findRoutes(map, row - 1, col);
    }
    if (row < map_height - 1 and map[row + 1][col] == current_height + 1) {
        routes += findRoutes(map, row + 1, col);
    }

    return routes;
}

fn parseInput() Map {
    var map: Map = undefined;
    var lines = std.mem.tokenizeScalar(u8, input, '\n');
    var row: usize = 0;
    while (lines.next()) |line| {
        for (line, 0..) |height, col| {
            map[row][col] = height - '0';
        }
        row += 1;
    }
    return map;
}
6

I liked this puzzle. No fiddly details to keep tripping over.

My solution 
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,
};
7

it took me awhile to settle for a tree data structure to represent the possible trails from a starting point. After that it became easy.

const std = @import("std");
const u = @import("util.zig");

var alloc: std.mem.Allocator = undefined;

const shape = 45;
const data = @embedFile("data/day10.txt");

// const shape = 8;
// const data =
//     \\89010123
//     \\78121874
//     \\87430965
//     \\96549874
//     \\45678903
//     \\32019012
//     \\01329801
//     \\10456732
// ;

var map: [shape * shape]u8 = undefined;

fn initMap() [shape * shape]u8 {
    var m: [shape * shape]u8 = undefined;
    var lines = std.mem.tokenizeScalar(u8, data, '\n');
    var row: usize = 0;
    while (lines.next()) |line| {
        for (line, 0..) |char, col| {
            m[row * shape + col] = u.parseInt(u8, &[_]u8{char}, 0) catch unreachable;
        }
        row += 1;
    }
    return m;
}

fn near(index: usize) [4]?usize {
    return [4]?usize{
        if (index < shape) null else index - shape,
        if (index + shape >= shape * shape) null else index + shape,
        if (index % shape == 0) null else index - 1,
        if (index % shape == shape - 1) null else index + 1,
    };
}

const Path = struct {
    index: usize,
    height: usize,
    up: [4]?*Path,

    const Self = @This();

    fn init(index: usize) !*Path {
        var p = try alloc.create(Path);
        p.index = index;
        p.height = map[index];
        p.up = undefined;
        for (near(index), 0..) |n, i| {
            if (p.height == 9 or n == null or map[n.?] != p.height + 1) {
                p.up[i] = null;
            } else {
                p.up[i] = try Path.init(n.?);
            }
        }
        return p;
    }

    fn score(self: *Self) !usize {
        // combien de sommets distincts peux-t-on atteindre depuis ce point ?
        var heights = u.Map(usize, bool).init(alloc);
        var stack = u.List(*Path).init(alloc);
        try stack.append(self);
        while (stack.items.len > 0) {
            const last = stack.pop();
            if (last.height == 9) {
                try heights.put(last.index, true);
            } else {
                for (last.up) |path| {
                    if (path != null) {
                        try stack.append(path.?);
                    }
                }
            }
        }
        return heights.count();
    }

    fn rating(self: *Self) !usize {
        // par combien de chemins peux-t-on atteindre les sommets ?
        var count: usize = 0;
        var stack = u.List(*Path).init(alloc);
        try stack.append(self);
        while (stack.items.len > 0) {
            const last = stack.pop();
            if (last.height == 9) {
                count += 1;
            } else {
                for (last.up) |path| {
                    if (path != null) {
                        try stack.append(path.?);
                    }
                }
            }
        }
        return count;
    }
};

fn part1() !void {
    var total: usize = 0;
    for (map, 0..) |place, index| {
        if (place == 0) {
            const p = try Path.init(index);
            total += try p.score();
        }
    }
    u.print("part1: {}\n", .{total});
}

fn part2() !void {
    var total: usize = 0;
    for (map, 0..) |place, index| {
        if (place == 0) {
            const p = try Path.init(index);
            total += try p.rating();
        }
    }
    u.print("part2: {}\n", .{total});
}

pub fn main() !void {
    var arena = std.heap.ArenaAllocator.init(u.gpa);
    arena.deinit();
    alloc = arena.allocator();
    map = initMap();
    try part1();
    try part2();
}
8

This was significantly easier than yesterday. No point to optimize it more, it runs in 150us. My strategy for these maze puzzles is always to keep a list of scheduled positions that need to be further visited, and loop on directions and do the obvious things: stay in the grid, etc. And then for deduplicating the end points a quick hashmap. No backtracking needed to build the actual paths, but we are just at day 10…. This is a fun AOC, I am having a blast. Zig is great. Working in c++ at work all day, I am thinking about the fun I am going to have at night, staring at colored symbols while drinking scotch.

https://zigbin.io/881d07

1 Like
9

Yeah, this was pretty straightforward. Posting a little tip that has applied to several entries this year.

Smooth sailing with Zig on these except that I’m not a fan not allowing signed ints in indexing. Also still would like to have a way of for looping backwards, a while-loop is just not as readable.

Instead of using a HashMap for deduplicating, I’ve used a StaticBitSet/DynamicBitSet instead:

var visited9 = std.DynamicBitSet.initEmpty(arena.allocator(), W * H) catch unreachable;
...
// in the path solver
visited9.set(x + y * W);
...
// calculating # of reachable 9's is just:
visited9.count()

Below is the above in context:

pub fn int(v: anytype) isize { return @intCast(v); }
pub fn unsigned(v: anytype) usize { return @intCast(v); }

fn append(arena: std.mem.Allocator, arr: []const [2]i32, e: [2]i32) []const [2]i32 {
    const new = arena.alloc([2]i32, arr.len + 1) catch unreachable;
    @memcpy(new[0..arr.len], arr);
    new[arr.len] = e;
    return new;
}

fn solve(arena: std.mem.Allocator, cur_path: []const [2]i32, map: []const []const u8, visited9: *std.DynamicBitSet, num_paths: *usize) void {
    const W = int(map[0].len);
    const H = int(map.len);

    const pos = cur_path[cur_path.len - 1];

    const dirs: [4][2]i32 = .{
        .{ 0, -1 },
        .{ 1, 0 },
        .{ 0, 1 },
        .{ -1, 0 },
    };

    for (dirs) |dir| {
        const xx = pos[0] + dir[0];
        const yy = pos[1] + dir[1];
        if (xx >= 0 and xx < W and yy >= 0 and yy < H) {
            const h = int(map[uint(pos[1])][uint(pos[0])]);
            const hh = int(map[uint(yy)][uint(xx)]);
            if (hh == '.') {
                continue; // impassable debug block
            }
            const dh = hh - h;
            if (dh == 1) {
                if (hh == '9') {
                    // Legally hit end of trail.
                    visited9.set(uint(xx) + uint(yy) * uint(W));
                    num_paths.* += 1;
                } else {
                    solve(arena, append(arena, cur_path, .{ xx, yy }), map, visited9, num_paths);
                }
            }
        }
    }
}

fn solveMap(map: []const []const u8) void {
    var arena = std.heap.ArenaAllocator.init(std.heap.c_allocator);

    const W = map[0].len;
    const H = map.len;
    var visited9 = std.DynamicBitSet.initEmpty(arena.allocator(), W * H) catch unreachable;
    var score_sum: usize = 0;
    var paths_sum: usize = 0;
    for (map, 0..) |row, y| {
        for (row, 0..) |chr, x| {
            if (chr == '0') {
                var num_paths: usize = 0;
                const root_path = [_][2]i32{.{ @intCast(x), @intCast(y) }};
                visited9.unmanaged.unsetAll();
                solve(arena.allocator(), &root_path, map, &visited9, &num_paths);
                // part 1
                score_sum += visited9.count();
                // part 2
                paths_sum += num_paths;
            }
        }
    }
    std.debug.print("trailheads score:  {d}\n", .{score_sum});
    std.debug.print("trailheads rating: {d}\n", .{paths_sum});
}