AoC 2025: Day 4

Challenge
1

Main thread for Day 4 of the 2025 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.

Notice that Advent of Code has changed it’s schedule and there will only be 12 days of puzzles this year.

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. If you use the new WYSIWYG editor, remember to close the details section, as it is opened by default. This is an issue (feature?) of the newest discourse updates. If you use markdown, then you can remove the “open" parameter (not in by default unless you use the WYSIWYG editor)
  2. Have Fun

Day 4 Challenge

Templates:

Resources:

3

Would have been nice to try combine the solutions. Nothing fancy here, still runs in under 1ms.

const std = @import("std");

pub fn main() void {
    const input = @embedFile("04.txt");

    var part1: usize = 0;
    var part2: usize = 0;

    const row_len = comptime std.mem.findScalar(u8, input, '\n').?;
    const border: [row_len + 1]u8 = @splat('.');
    const const_grid = border ++ input ++ border;

    var grid: [const_grid.len]u8 = undefined;
    @memcpy(grid[0..], const_grid[0..]);

    // 1.
    for (border.len..input.len + border.len) |i| {
        if (grid[i] != '@') continue;

        var c: usize = 0;
        inline for (.{
            i - border.len - 1,
            i - 1,
            i + border.len - 1,
        }) |offset| {
            for (grid[offset..][0..3]) |e| c += @intFromBool(e == '@');
        }
        if (c < 5) {
            part1 += 1;
        }
    }

    // 2.
    var removed: usize = 0;
    while (true) {
        for (border.len..input.len + border.len) |i| {
            if (grid[i] != '@') continue;

            var c: usize = 0;
            inline for (.{
                i - border.len - 1,
                i - 1,
                i + border.len - 1,
            }) |offset| {
                for (grid[offset..][0..3]) |e| c += @intFromBool(e == '@');
            }
            if (c < 5) {
                grid[i] = '.';
                removed += 1;
            }
        }

        part2 += removed;
        if (removed == 0) break;
        removed = 0;
    }

    std.debug.print("1: {}\n2: {}\n", .{ part1, part2 });
}
2 Likes
2

Bruteforce simple (with lots of allocations for part 2): The Zig Pastebin

Worked first try for both! (minus compiler errors due to my rustiness with zig).

Plenty of optimizations possible as this is a convolution problem.

4

I love using enums for the grid based puzzles!

example types:

const Cell = enum(u8) { OOB = ' ', EMPTY = '.', ROLL = '@' };
const Grid = ArrayList(Cell);

My algorithm for the second star could be more efficient by checking for duplicates but performance wasn’t an issue. I suspect it could have been brute-forced is reasonable time.

5

Ugly solution, but here it is And thousands of poor Cock Robin. ‘It just occurred to me.

Text description of the solution

Create a bitset from input grid, which then can be queried using .get(). There are several hiccups. BitSet expects a flat usize index, so I had to convert human x,y coordinates to single index number. Another issue is borders. Because all indices are probably usize type, you have to add special checks when calculating neighbors for the very first cell (and other) to not to overflow usize or go out of bounds. But this can be solved by adding empty cells on each side of the grid.

I wish there was a AutoGrowableBitSet. DynamicBitSet can only be resized to certain length :frowning:

6 
const std = @import("std");

const data = @embedFile("data.txt");
const col_max: usize = std.mem.indexOfScalar(u8, data, '\n').?;
const row_max: usize = @divFloor(std.mem.lastIndexOfScalar(u8, data, '\n').?, col_max);

pub fn main() !void {
    var rolls: std.StaticBitSet(col_max * row_max) = .initEmpty();
    var iter = std.mem.splitScalar(u8, data, '\n');
    var row: usize = 0;
    while (iter.next()) |line| : (row += 1) {
        for (line, 0..) |c, col| {
            if (c == '@') rolls.set(row * col_max + col);
        }
    }

    const offsets = [_]isize{ -1, 0, 1 };
    var totalRemoved: usize = 0;
    while (true) {
        var to_remove: std.StaticBitSet(col_max * row_max) = .initEmpty();
        // check accessible rolls
        var rolls_iter = rolls.iterator(.{});
        while (rolls_iter.next()) |pos| {
            var adjCount: usize = 0;
            const j = @rem(pos, col_max);
            const i = @divTrunc(pos, col_max);
            for (offsets) |di| {
                for (offsets) |dj| {
                    if (di == 0 and dj == 0) continue; // current position
                    if ((i == 0 and di == -1) or (i == row_max and di == 1)) continue; // top/bottom border
                    if ((j == 0 and dj == -1) or (j == col_max and dj == 1)) continue; // left/right border
                    const adjrow: usize = @intCast(@as(isize, @intCast(i)) + di);
                    const adjcol: usize = @intCast(@as(isize, @intCast(j)) + dj);
                    const adjpos = adjrow * col_max + adjcol;
                    if (adjpos >= rolls.capacity()) continue;
                    if (rolls.isSet(adjpos)) adjCount += 1;
                }
            }
            if (adjCount < 4) to_remove.set(i * col_max + j);
        }
        // remove accessible rolls
        if (to_remove.count() == 0) break;
        std.debug.print("{d}\n", .{to_remove.count()});
        totalRemoved += to_remove.count();
        var rem_iter = to_remove.iterator(.{});
        while (rem_iter.next()) |pos| {
            rolls.unset(pos);
        }
    }
    std.debug.print("{d}\n", .{totalRemoved});
}
7

https://zigbin.io/846c2a. this was the most straightforward solve for me so far. i’m just operating on a the input slice in this one, no data structures. learned to do that in years past when i would have maybe used a hash map or something. also using wrapping math] i think is a nice way to avoid lots of casts to isize and simplify bounds checking a little.

2 Likes
8

Here’s mine: The Zig Pastebin

Using bitset for the removal was nice. It gave a good iterator so I could remove things quickly after the fact. Ran pretty quickly too.

Also leveraged the fact that there were new lines on the end to not have to make a check if the column was at the end. It won’t ever be, because there is always a newline at the end of each column.

2 Likes
9

Just finished both parts :partying_face:

This year I tried to not create a 2D nested array-like data structure for these kind of puzzles but try accessing an x, y coordinate by finding the row and column size upfront and then use a single number index to access the buffer.

The whole for loop game with usize and isize conversions feels a bit cumbersome though.

fn findAccessibleRolls(map: []u8, rows: usize, cols: usize) !usize {
    var result: usize = 0;

    for (0..cols) |i| {
        for (0..rows) |j| {
            const x: isize = @intCast(j);
            const y: isize = @intCast(i);
            var rolls_count: usize = 0;

            for (0..3) |yy| {
                inner: for (0..3) |xx| {
                    const xo = x + @as(isize, @intCast(xx)) - 1;
                    const yo = y + @as(isize, @intCast(yy)) - 1;
                    if (xo < 0 or
                        yo < 0 or
                        xo > rows - 1 or
                        yo > cols - 1 or
                        (xo == x and yo == y)) continue :inner;
                    const map_value = map[@intCast((xo * @as(isize, @intCast(rows))) + yo)];
                    if (map_value == '@' or map_value == 'x') {
                        rolls_count += 1;
                    }
                }
            }

            if (map[@intCast((x * @as(isize, @intCast(rows))) + y)] != '.' and rolls_count < 4) {
                map[@intCast((x * @as(isize, @intCast(rows))) + y)] = '.';
                result += 1;
            }
        }
    }

    // --- Print the map to visualise what's going on
    // for (0..cols) |_x| {
    //     for (0..rows) |_y| {
    //         std.debug.print("{c} ", .{map[(_x * rows) + _y]});
    //     }
    //     std.debug.print("\n", .{});
    // }

    return result;
}

fn part1(allocator: Allocator) anyerror!void {
    const input_embed = std.mem.trimEnd(u8, @embedFile("puzzle-04"), "\n");

    var it = std.mem.tokenizeSequence(u8, input_embed, "\n");
    const cols = it.peek().?.len;
    const rows = input_embed.len / cols;
    std.debug.print("Map size: {d} x {d}\n", .{ cols, rows });

    const map = try std.mem.replaceOwned(u8, allocator, input_embed, "\n", "");
    defer allocator.free(map);

    const result = try findAccessibleRolls(map, rows, cols);
    std.debug.print("Result: {d}\n", .{result});
}

fn part2(allocator: Allocator) anyerror!void {
    const input_embed = std.mem.trimEnd(u8, @embedFile("puzzle-04"), "\n");

    var it = std.mem.tokenizeSequence(u8, input_embed, "\n");
    const cols = it.peek().?.len;
    const rows = input_embed.len / cols;
    std.debug.print("Map size: {d} x {d}\n", .{ cols, rows });

    const map = try std.mem.replaceOwned(u8, allocator, input_embed, "\n", "");
    defer allocator.free(map);

    var step_result = try findAccessibleRolls(map, rows, cols);
    var summed_result: usize = step_result;
    while (step_result > 0) {
        step_result = try findAccessibleRolls(map, rows, cols);
        summed_result += step_result;
    }
    std.debug.print("Result: {d}\n", .{summed_result});
}
1 Like
10

This one took longer to run than days one and two: part 2 took an average of 1.9ms over 1000 reruns.

const Erosion = struct {
    mask: []u8,
    rows: usize,
    cols: usize,

    fn erode(self: *Erosion, allocator: std.mem.Allocator, threshold: usize) !usize {
        var neighbors: []u8 = try allocator.alloc(u8, self.rows * self.cols);
        defer allocator.free(neighbors);
        var cleaned: usize = 0;
        for (0..self.rows) |row| {
            var sum = self.mask[self.index(row, 0)];
            for (0..self.cols) |col| {
                if (col > 1) sum -= self.mask[self.index(row, col - 2)];
                if (col < self.cols - 1) sum += self.mask[self.index(row, col + 1)];
                neighbors[self.index(row, col)] = sum;
            }
        }

        for (0..self.cols) |col| {
            var sum = neighbors[self.index(0, col)];
            for (0..self.rows) |row| {
                if (row > 1) sum -= neighbors[self.index(row - 2, col)];
                if (row < self.rows - 1) sum += neighbors[self.index(row + 1, col)];
                const mask = self.mask[self.index(row, col)];
                if (mask == 1 and sum < (threshold + 1)) {
                    cleaned += 1;
                    self.mask[self.index(row, col)] = 0;
                }
            }
        }
        return cleaned;
    }

    inline fn index(self: Erosion, row: usize, col: usize) usize {
        return row * self.cols + col;
    }
};