AoC 2025: Day 10

Challenge
1

Main thread for Day 10 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 10 Challenge

Templates:

Resources:

2

This round is tough. I only had time to do part 1 for now. If I’ll get some time tomorrow, I’ll finish it up.

The problem description is misleading. Pushing a button more than once reverses the lights back to the original state. Also xor can be done in any order; it’s commutative and associative.

misc_zig/aoc/aoc10.zig at main · williamw520/misc_zig · GitHub

1 Like
3

I’ve only done part 1. I fear part 2 will elude me :frowning: I can do the example for part 2 in a similar way but I think that’s a dead end.

1 Like
4

I found part 1 to be pretty easy (took me about an hour in total), but part 2 looks like black magic to me. I would be really really interested if someone can find a reasonable solution (meaning understandable for mortals and runtime < 10 minutes) that doesnt just involve using z3 like most people did on reddit.

5

I’ve solved part 2 by using gaussian elimination to reduce the number of free variables and then just doing brute force search. Runs in in less than a second on my laptop.

4 Likes
6

Part 1

Very funky code. My idea was to use depth first search (?) in order to find the smallest number of iterations that set the correct thing.

Also had an excuse to play around with Vectors and SIMD xD.

Part 2

No idea except for brute forcing.

const std = @import("std");
const data = @embedFile("data");

const V = @Vector(64, u1);

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

    var it = std.mem.tokenizeAny(u8, data, "\n");

    var result: usize = 0;

    while (it.next()) |line| {
        var it_line = std.mem.tokenizeAny(u8, line, " ");

        const pattern = blk: {
            const str = it_line.next().?;
            var binary: V = @splat(0);

            inline for (0..64) |i| {
                if (i == str.len - 2) break;

                const c = str[1 .. str.len - 1][i];

                if (c == '#')
                    binary[i] = 1
                else if (c != '.')
                    unreachable;
            }
            break :blk binary;
        };

        var buttons = try std.ArrayList(V).initCapacity(gpa, 0);
        defer buttons.deinit(gpa);

        while (it_line.next()) |bracket| {
            if (bracket[0] == '{') break;

            var it_bracket = std.mem.tokenizeAny(u8, bracket[1 .. bracket.len - 1], ",");
            const button = blk: {
                var binary: V = @splat(0);

                while (it_bracket.next()) |num| {
                    const n = try std.fmt.parseInt(usize, num, 10);

                    inline for (0..64) |i| {
                        if (i == n) {
                            binary[i] = 1;
                            break;
                        }
                    }
                }

                break :blk binary;
            };

            try buttons.append(gpa, button);
        }

        var starting_vec: V = @splat(0);
        var best: usize = std.math.maxInt(usize);

        dfs(buttons.items, &starting_vec, 0, pattern, 0, &best);

        result += best;
    }

    std.debug.print("Result is {}\n", .{result});
}

fn dfs(
    slice: []const V,
    xor: *V,
    i: usize,
    wanted: V,
    subset_len: usize,
    best_len: *usize,
) void {
    if (subset_len >= best_len.*) return;

    if (i == slice.len) {
        if (@reduce(.And, xor.* == wanted)) {
            // We found a solution smaller than current best
            best_len.* = subset_len;
        }
        return;
    }
    // Option 1: skip current element
    dfs(slice, xor, i + 1, wanted, subset_len, best_len);

    // Option 2: include current element
    xor.* ^= slice[i];
    dfs(slice, xor, i + 1, wanted, subset_len + 1, best_len);

    xor.* ^= slice[i]; // backtrack
}
1 Like
7

I spent two whole nights because I’m not familiar with matrices.
Part1, after using Gaussian elimination, search for all free variables. Part 2 uses bareiss to search all free variables after elimination. The upper bound of the free variable uses some techniques that I myself don’t quite understand to slightly reduce the search space, although I’m not sure myself whether this is optimization or negative optimization.
I’m not familiar with these matrix operations, but I have managed to implement them for the time being. At one point, optimization to avoid brute force search was considered, but all failed.

PS D:\advent-of-code-template> zig build solve -Dday=10 -Doptimize=ReleaseFast
[10/1] (0.116 ms)    411
[10/1] (10.541 ms)   16063
Total elapsed solution time: 10.657 ms

// Transposed Matrix
//       Target | Btn0 Btn1 Btn2 Btn3
// Lgt0 [   1   |   1    0    1    0 ]  => b0 + b2 = 1
// Lgt1 [   0   |   0    1    1    0 ]  => b1 + b2 = 0
// Lgt2 [   1   |   1    1    0    1 ]  => b0 + b1 + b3 = 1
// Lgt3 [   0   |   0    0    0    1 ]  => b3 = 0
//
//                  Target
//                  v
// Row 0: 0...0001011  (Target:1, Buttons: 0, 2 active)
// Row 1: 0...0001100  (Target:0, Buttons: 1, 2 active)
// Row 2: 0...0010111  (Target:1, Buttons: 0, 1, 3 active)
//        ^     ^^^^^
//     Padding  Coeffs
const std = @import("std");
pub const LinearSystemBit64 = struct {
    rows: [64]u64,
    max_row_id: u6,
    max_col_id: u6,
    pub const InitCursor = struct {
        ref: *LinearSystemBit64,
        current_col_id: u6,
        pub inline fn setTargetBit(self: *@This(), row_id: usize) void {
            self.ref.rows[row_id] |= 1;
        }
        pub inline fn nextCol(self: *@This()) void {
            self.current_col_id += 1;
        }
        pub inline fn setColBit(self: *@This(), row_id: usize) void {
            self.ref.rows[row_id] |= (@as(u64, 1) << self.current_col_id);
        }
        pub inline fn finish(self: *@This()) void {
            self.ref.max_col_id = self.current_col_id;
            self.* = undefined;
        }
    };
    pub inline fn clearRows(self: *@This(), new_row_num: usize) InitCursor {
        @memset((&self.rows)[0..new_row_num], 0);
        self.max_row_id = @intCast(new_row_num - 1);
        return .{ .ref = self, .current_col_id = 0 };
    }
    pub fn eliminateInplace(self: *@This()) struct {
        rank: u6,
        pivot_mask: u64,
    } {
        var pivot_row_id: u6 = 0;
        var pivot_col_mask: u64 = 0;
        for (1..@as(usize, self.max_col_id) + 1) |col_id| {
            const col_mask: u64 = @as(u64, 1) << @as(u6, @intCast(col_id));
            const row_id_to_swap: usize = blk: for (pivot_row_id..@as(usize, self.max_row_id) + 1) |r| {
                if ((self.rows[r] & col_mask) != 0) {
                    break :blk r;
                }
            } else continue;
            std.mem.swap(u64, &self.rows[pivot_row_id], &self.rows[row_id_to_swap]);
            for (0..@as(usize, self.max_row_id) + 1) |r| {
                if (r != pivot_row_id) {
                    if ((self.rows[r] & col_mask) != 0) {
                        self.rows[r] ^= self.rows[pivot_row_id];
                    }
                }
            }
            pivot_col_mask |= col_mask;
            pivot_row_id += 1;
        }
        return .{ .rank = pivot_row_id, .pivot_mask = pivot_col_mask };
    }
    pub fn minSolutionPopInplace(self: *@This()) ?u6 {
        const eliminate_result = self.eliminateInplace();
        const rank = eliminate_result.rank;
        const pivot_mask = eliminate_result.pivot_mask;
        for (rank..@as(usize, self.max_row_id) + 1) |r| {
            if (self.rows[r] != 0) return null;
        }
        const full_var_mask = (@as(u64, std.math.maxInt(u64)) >> (63 - self.max_col_id)) - 1;
        var free_mask = full_var_mask & ~pivot_mask;
        var free_col_ids: [64]u6 = undefined;
        var free_count: u6 = 0;
        while (free_mask != 0) {
            free_col_ids[free_count] = @intCast(@ctz(free_mask));
            free_count += 1;
            free_mask &= free_mask - 1;
        }
        var min_solution_pop: u6 = 63;
        const combs = @as(u64, 1) << free_count;
        for (0..combs) |comb_mask| {
            var solution: u64 = 1;
            var pop: u6 = 0;
            for (0..free_count) |i| {
                if (((comb_mask >> @as(u6, @intCast(i))) & 1) == 1) { // 检查组合的第 i 位
                    solution |= @as(u64, 1) << free_col_ids[i];
                    pop += 1;
                }
            }
            for (0..rank) |r| {
                if (@popCount(self.rows[r] & solution) % 2 == 1) {
                    pop += 1;
                }
            }
            if (pop < min_solution_pop) min_solution_pop = pop;
        }
        return min_solution_pop;
    }
};

pub fn part1(input: []const u8) !usize {
    var line_it = std.mem.splitScalar(u8, input, '\n');
    var sum: usize = 0;
    var ls: LinearSystemBit64 = undefined;
    while (line_it.next()) |line| {
        if (line.len == 0) break;
        var line_reader: std.Io.Reader = .fixed(line);
        line_reader.toss(1);
        const target = (try line_reader.takeDelimiter(']')).?;
        var cursor = ls.clearRows(target.len);
        for (target, 0..) |state, light_id| {
            if (state == '#') cursor.setTargetBit(light_id);
        }
        while (line_reader.discardDelimiterInclusive('(')) |_| {
            const button = (try line_reader.takeDelimiter(')')).?;
            var light_id_it = std.mem.splitScalar(u8, button, ',');
            cursor.nextCol();
            while (light_id_it.next()) |light_id_str| {
                cursor.setColBit(try std.fmt.parseUnsigned(u6, light_id_str, 10));
            }
        } else |err| switch (err) {
            error.ReadFailed => return err,
            error.EndOfStream => {},
        }
        cursor.finish();
        sum += ls.minSolutionPopInplace() orelse std.debug.panic("{s}", .{line});
    }
    return sum;
}

pub const MiniNaturalLinearSystem = struct {
    rows: [64][64]i64,
    max_row_id: u6,
    max_col_id: u6,
    pub const InitCursor = struct {
        ref: *MiniNaturalLinearSystem,
        current_col_id: u6,
        pub inline fn setTargetInRow(self: *@This(), row_id: usize, value: i64) void {
            self.ref.rows[row_id][0] = value;
        }
        pub inline fn nextCol(self: *@This()) void {
            self.current_col_id += 1;
        }
        pub inline fn setColInRow(self: *@This(), row_id: usize, value: i64) void {
            self.ref.rows[row_id][self.current_col_id] = value;
        }
        pub inline fn finish(self: *@This()) void {
            self.ref.max_col_id = self.current_col_id;
            self.* = undefined;
        }
    };
    pub inline fn clearRows(self: *@This(), new_row_num: usize) InitCursor {
        @memset((&self.rows)[0..new_row_num], @as([64]i64, @splat(0)));
        self.max_row_id = @intCast(new_row_num - 1);
        return .{ .ref = self, .current_col_id = 0 };
    }
    pub fn eliminateInplace(self: *@This(), pivot_col_ids: *[64]u6) u6 {
        var pivot_row_id: u6 = 0;
        var prev_pivot: i64 = 1;
        for (1..@as(usize, self.max_col_id) + 1) |col_id| {
            const row_id_to_swap: usize = blk: for (pivot_row_id..@as(usize, self.max_row_id) + 1) |r| {
                if ((self.rows[r][col_id]) != 0) {
                    break :blk r;
                }
            } else continue;
            std.mem.swap([64]i64, &self.rows[pivot_row_id], &self.rows[row_id_to_swap]);
            const pivot = self.rows[pivot_row_id][col_id];
            pivot_col_ids[pivot_row_id] = @intCast(col_id);
            for (pivot_row_id + 1..@as(usize, self.max_row_id) + 1) |r| {
                const factor = self.rows[r][col_id];
                const bareiss = struct {
                    inline fn apply(current: i64, current_pivot: i64, row_factor: i64, col_factor: i64, previous_pivot: i64) i64 {
                        return @divExact(current * current_pivot - row_factor * col_factor, previous_pivot);
                    }
                };
                self.rows[r][0] = bareiss.apply(self.rows[r][0], pivot, factor, self.rows[pivot_row_id][0], prev_pivot);
                var c = col_id + 1;
                while (c <= self.max_col_id) : (c += 1) {
                    self.rows[r][c] = bareiss.apply(self.rows[r][c], pivot, factor, self.rows[pivot_row_id][c], prev_pivot);
                }
            }
            pivot_row_id += 1;
            prev_pivot = pivot;
        }
        return pivot_row_id;
    }
    /// The free column in the solution is required to be pre-filled, while the pivot columns are required to be 0.
    /// pivot_col_ids.len is rank.
    /// Index: [0]      [1]      [2]      [3]      [4]      [5]
    /// Type:  Target   Pivot    Free     Pivot    Free     Pivot
    ///                  Out      In       Out      In       Out
    fn backSubstituteSolveCost(self: *const @This(), solution: *[64]i64, pivot_col_ids: []const u6) ?usize {
        var r = pivot_col_ids.len;
        while (r > 0) {
            r -= 1;
            const pivot_col_id: usize = pivot_col_ids[r];
            var sum = self.rows[r][0]; // Target
            for (pivot_col_id + 1..@as(usize, self.max_col_id) + 1) |c| {
                sum -= self.rows[r][c] * solution[c];
            }
            const pivot_val = self.rows[r][pivot_col_id];
            if (pivot_val == 0) @panic("Singular Matrix!");
            if (@rem(sum, pivot_val) != 0) return null;

            const res = @divExact(sum, pivot_val);
            if (res < 0) return null;

            solution[pivot_col_id] = res;
        }
        var total: usize = 0;
        for (solution[1..@as(usize, self.max_col_id + 1)]) |val| {
            total += @intCast(val);
        }
        return total;
    }
    fn minCostRecursive(
        self: *const @This(),
        pivot_col_ids: []const u6,
        free_col_ids: []const u6,
        depth: u6,
        cols_physical_bounds: *const [64]?i64,
        solution: *[64]i64,
    ) ?usize {
        if (depth == free_col_ids.len) {
            return self.backSubstituteSolveCost(solution, pivot_col_ids);
        }
        const current_free_col_id = free_col_ids[depth];
        const free_min, const free_max = calc_bounds: {
            var free_min: i64 = 0;
            var free_max: i64 = cols_physical_bounds[current_free_col_id] orelse return minCostRecursive(
                self,
                pivot_col_ids,
                free_col_ids,
                depth + 1,
                cols_physical_bounds,
                solution,
            );
            if (depth == free_col_ids.len - 1) {
                const r = pivot_col_ids.len - 1;
                const pivot_col_id = pivot_col_ids[r];
                const pivot = self.rows[r][pivot_col_id];
                const coeff = self.rows[r][current_free_col_id];
                const raw_target = self.rows[r][0];
                var residue = raw_target;
                for (0..depth) |prev_depth| {
                    const prev_free_col_id = free_col_ids[prev_depth];
                    const prev_val = solution[prev_free_col_id];
                    residue -= self.rows[r][prev_free_col_id] * prev_val;
                }
                const negator: i64 = if (pivot < 0) -1 else 0;
                const aligned_residue = (residue ^ negator) - negator;
                const aligned_coeff = (coeff ^ negator) - negator;
                if (aligned_coeff > 0) {
                    const upper = @divTrunc(aligned_residue, aligned_coeff);
                    if (upper < free_max) free_max = upper;
                } else if (aligned_coeff < 0) {
                    const lower = @divTrunc(-aligned_residue + -aligned_coeff - 1, -aligned_coeff);
                    if (lower > free_min) free_min = lower;
                } else if (aligned_residue < 0) return null;
            }
            if (free_min > free_max) return null;
            break :calc_bounds .{ free_min, free_max };
        };
        var f = free_min;
        var min_local_cost: ?usize = null;
        while (f <= free_max) : (f += 1) {
            solution[current_free_col_id] = f;
            if (minCostRecursive(
                self,
                pivot_col_ids,
                free_col_ids,
                depth + 1,
                cols_physical_bounds,
                solution,
            )) |cost| {
                if (blk: {
                    break :blk cost < min_local_cost orelse break :blk true;
                }) min_local_cost = cost;
            }
        }
        return min_local_cost;
    }
    pub fn minSolutionCostInplace(self: *@This()) ?usize {
        var cols_physical_bounds: [64]?i64 = @splat(null);
        for (0..@as(usize, self.max_row_id) + 1) |r| {
            const target = self.rows[r][0];
            if (target > 0) {
                for (1..@as(usize, self.max_col_id) + 1) |c| {
                    const coeff = self.rows[r][c];
                    if (coeff > 0) {
                        const bound = @divTrunc(target, coeff);
                        if (blk: {
                            break :blk bound < cols_physical_bounds[c] orelse break :blk true;
                        }) {
                            cols_physical_bounds[c] = bound;
                        }
                    }
                }
            } else if (target == 0) {
                for (1..@as(usize, self.max_col_id) + 1) |c| {
                    if (self.rows[r][c] > 0) cols_physical_bounds[c] = 0;
                }
            }
        }
        var pivot_col_ids: [64]u6 = undefined;
        const rank = self.eliminateInplace(&pivot_col_ids);
        for (rank..@as(usize, self.max_row_id) + 1) |r| {
            if (self.rows[r][0] != 0) return null;
        }
        var solution: [64]i64 = @splat(0);
        if (rank == self.max_col_id) {
            return self.backSubstituteSolveCost(&solution, (&pivot_col_ids)[0..rank]);
        }
        var free_col_ids: [64]u6 = undefined;
        var free_count: u6 = 0;
        var p_id: u6 = 0;
        for (1..@as(usize, self.max_col_id) + 1) |c| {
            if (p_id < rank and pivot_col_ids[p_id] == c) {
                p_id += 1;
                continue;
            }
            free_col_ids[free_count] = @intCast(c);
            free_count += 1;
        }
        return minCostRecursive(
            self,
            pivot_col_ids[0..rank],
            free_col_ids[0..free_count],
            0,
            &cols_physical_bounds,
            &solution,
        );
    }
};

pub fn part2(input: []const u8) !usize {
    var line_it = std.mem.splitScalar(u8, input, '\n');
    var sum: usize = 0;
    var ls: MiniNaturalLinearSystem = undefined;
    while (line_it.next()) |line| {
        if (line.len == 0) break;
        var line_reader: std.Io.Reader = .fixed(line);
        line_reader.toss(1);
        var cursor = ls.clearRows(try line_reader.discardDelimiterExclusive(']'));
        while (std.mem.indexOfScalar(u8, try line_reader.peekGreedy(1), '(')) |delimiter_index| {
            line_reader.toss(delimiter_index + 1);
            const button = (try line_reader.takeDelimiter(')')).?;
            var light_id_it = std.mem.splitScalar(u8, button, ',');
            cursor.nextCol();
            while (light_id_it.next()) |light_id_str| {
                cursor.setColInRow(try std.fmt.parseUnsigned(u6, light_id_str, 10), 1);
            }
        }
        _ = try line_reader.discardDelimiterInclusive('{');
        const target = (try line_reader.takeDelimiter('}')).?;
        var target_it = std.mem.splitScalar(u8, target, ',');
        var row_id: u6 = 0;
        while (target_it.next()) |target_val_str| {
            cursor.setTargetInRow(row_id, try std.fmt.parseInt(i64, target_val_str, 10));
            row_id += 1;
        }
        cursor.finish();
        sum += ls.minSolutionCostInplace() orelse std.debug.panic("{s}\n", .{line});
    }
    return sum;
}
8

I never liked my answer to Day 10 part 2 (which was heavily inspired on @marcin-serwin ‘s answer above). I checked the relevant Reddit discussions, and indeed found a “simpler” solution that uses pure recursion / memoization and is very fast – and very clever indeed. All credit goes to the user who posted it.

I reimplemented my solution – it is now more readable and can be followed in a logical manner, without needing any knowledge of Gaussian elimination (or other maths).

Cheers!

3 Likes
9

Thanks you for the link. This seems to be a very elegant solution. I had my zig code set up and query some prolog to solve the systems of equations. but this would only work correctly for 127 of 153 lines. I just implemented a bruteforce for the rest, but this is unbearably slow. Thus, the link comes at the right time. I will implement it.