AoC 2024: Day 24

Happy Christmas Eve!

Main thread for Day 24 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 24 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
Day 10: AoC 2024: Day 10
Day 11: AoC 2024: Day 11
Day 12: AoC 2024: Day 12
Day 13: AoC 2024: Day 13
Day 14: AoC 2023: Day 14
Day 15: AoC 2024: Day 15
Day 16: AoC 2024: Day 16
Day 17: AoC 2024: Day 17
Day 18: AoC 2024: Day 18
Day 19: AoC 2024: Day 19
Day 20: AoC 2024: Day 20
Day 21: AoC 2024: Day 21
Day 22: AoC 2024: Day 22
Day 23: AoC 2024: Day 23

1 Like

Part 2 was a very visual & manual task - before coming up with heuristics, I wrote a simulator and solved it manually. (Video of the simulator in action below).
Automated solution is 100% heuristics, but super quick.

Source: aoc2024/src/day24.zig at main · p88h/aoc2024 · GitHub
Video: https://www.youtube.com/watch?v=nWNtNvxCjp0

Benchmark:

        parse   part1   part2   total
day 24:  9.0 µs  2.7 µs  0.8 µs 12.6 µs (+-4%) iter=98110

Hi all,

a little bit late, but Family and stuff. Also I challenged myself to solve this puzzle completely in comptime. During runtime only the result should be printed. I finally did it (for part 1):

Solution 1 (comptime only)
const std = @import("std");

//const input = @embedFile("./small.inp");
//const input = @embedFile("./small2.inp");
//const input = @embedFile("./medium.inp");
const input = @embedFile("./big.inp");

const maxBranch = 10_000_000;
// Wires
const emptyStr = "   ";
const maxWires = 1000;

fn getWires(comptime inp: []const u8) [maxWires][3:0]u8 {
    @setEvalBranchQuota(maxBranch);
    var list: [maxWires][3:0]u8 = undefined;
    for (&list) |*elem| {
        elem[0] = emptyStr[0];
        elem[1] = emptyStr[1];
        elem[2] = emptyStr[2];
    }
    var lines = std.mem.tokenizeScalar(u8, inp, '\n');
    var idx: usize = 0;
    while (lines.next()) |line| {
        var tmplist: [3][]const u8 = undefined;
        var app = false;
        if (line.len > 10 and //
            (std.mem.eql(u8, line[4..7], "XOR") or //
            std.mem.eql(u8, line[4..7], "AND")))
        {
            app = true;
            tmplist[0] = line[0..3];
            tmplist[1] = line[8..11];
            tmplist[2] = line[15..18];
        } else if (std.mem.eql(u8, line[4..6], "OR")) {
            app = true;
            tmplist[0] = line[0..3];
            tmplist[1] = line[7..10];
            tmplist[2] = line[14..17];
        }
        if (app) {
            for (tmplist) |str| {
                var inlist = false;
                for (list) |elem| {
                    if (std.mem.eql(u8, &elem, str)) {
                        inlist = true;
                        break;
                    }
                }
                if (!inlist) {
                    list[idx][0] = str[0];
                    list[idx][1] = str[1];
                    list[idx][2] = str[2];
                    idx += 1;
                }
            }
        }
    }
    return list;
}

pub fn createWiresType() type {
    @setEvalBranchQuota(maxBranch);
    const wires = comptime getWires(input);
    comptime var nfields = 0;
    for (wires) |wire| {
        if (!std.mem.eql(u8, &wire, emptyStr)) {
            nfields += 1;
        } else {
            break;
        }
    }

    var fields: [nfields]std.builtin.Type.StructField = undefined;
    for (wires[0..nfields], 0..) |wire, idx| {
        fields[idx] = .{ //
            .name = &wire,
            .type = i8,
            .default_value = null,
            .is_comptime = false,
            .alignment = 0,
        };
    }

    return @Type(.{
        .Struct = .{
            .layout = .auto,
            .fields = &fields,
            .decls = &.{},
            .is_tuple = false,
            .backing_integer = null,
        },
    });
}

pub fn initWires(comptime inp: []const u8, comptime wires: *Wires_t) void {
    @setEvalBranchQuota(maxBranch);
    comptime {
        for (@typeInfo(Wires_t).Struct.fields) |field| {
            @field(wires, field.name) = 0;
        }
    }
    var blocks = std.mem.tokenizeSequence(u8, inp, "\n\n");
    var lines = std.mem.tokenizeScalar(u8, blocks.next().?, '\n');

    while (lines.next()) |line| {
        const initval = if (line[5] == '1') 1 else 0;
        @field(wires, line[0..3]) = initval;
    }
}

const Wires_t = createWiresType();

pub fn wireOutput(comptime wires: Wires_t) usize {
    @setEvalBranchQuota(maxBranch);
    var output: usize = 0;
    comptime {
        for (@typeInfo(Wires_t).Struct.fields) |field| {
            if (field.name[0] == 'z') {
                const val: usize = @field(wires, field.name);
                const idx: u6 = 10 * (field.name[1] - '0') + field.name[2] - '0';
                output += val << idx;
            }
        }
    }
    return output;
}

pub fn printWires(wires: Wires_t) void {
    @setEvalBranchQuota(maxBranch);
    inline for (comptime @typeInfo(Wires_t).Struct.fields) |field| {
        std.debug.print("{s}: {b}\n", .{ field.name, @field(wires, field.name) });
    }
}

// Gates
const maxGates = maxWires;
const ops = enum { and_op, or_op, xor_op };

const Gate_t = struct {
    inp1: []const u8,
    inp2: []const u8,
    out: []const u8,
    op: ops,
};

const Gates_t = struct {
    ngates: usize,
    gates: [maxGates]Gate_t,
};

pub fn initGates(inp: []const u8, gates: *Gates_t) void {
    @setEvalBranchQuota(maxBranch);
    gates.ngates = 0;

    var blocks = std.mem.tokenizeSequence(u8, inp, "\n\n");
    _ = blocks.next();
    var lines = std.mem.tokenizeScalar(u8, blocks.next().?, '\n');

    while (lines.next()) |line| {
        var field = std.mem.tokenizeScalar(u8, line, ' ');
        const inp1 = field.next().?;
        const opstr = field.next().?;
        const inp2 = field.next().?;
        _ = field.next();
        const out = field.next().?;
        var op: ops = undefined;
        if (std.mem.eql(u8, opstr, "AND")) {
            op = .and_op;
        } else if (std.mem.eql(u8, opstr, "OR")) {
            op = .or_op;
        } else if (std.mem.eql(u8, opstr, "XOR")) {
            op = .xor_op;
        }

        gates.gates[gates.ngates] = Gate_t{
            .inp1 = inp1,
            .inp2 = inp2,
            .op = op,
            .out = out,
        };
        gates.ngates += 1;
    }
}

pub fn printGates(gates: Gates_t) void {
    @setEvalBranchQuota(maxBranch);
    for (0..gates.ngates) |i| {
        const gate = gates.gates[i];
        const opstr = switch (gate.op) {
            .and_op => "AND",
            .or_op => "OR ",
            .xor_op => "XOR",
        };
        std.debug.print("{s} {s} {s} -> {s}\n", //
            .{ gate.inp1, opstr, gate.inp2, gate.out });
    }
}

pub fn computeWire(comptime wires: *Wires_t, comptime gates: Gates_t, out: []const u8) void {
    @setEvalBranchQuota(maxBranch);
    if (out[0] == 'x') {
        return;
    }
    for (0..gates.ngates) |i| {
        const gate = gates.gates[i];
        if (std.mem.eql(u8, gate.out[0..3], out[0..3])) {
            computeWire(wires, gates, gate.inp1);
            computeWire(wires, gates, gate.inp2);
            switch (gate.op) {
                .and_op => { //
                    @field(wires, gate.out) |= //
                        @field(wires, gate.inp1) //
                        & //
                        @field(wires, gate.inp2);
                },
                .or_op => {
                    @field(wires, gate.out) |= //
                        @field(wires, gate.inp1) //
                        | //
                        @field(wires, gate.inp2);
                },
                .xor_op => {
                    @field(wires, gate.out) |= //
                        @field(wires, gate.inp1) //
                        ^ //
                        @field(wires, gate.inp2);
                },
            }
        }
    }
}

pub fn computeCircuit(comptime wires: *Wires_t, comptime gates: Gates_t) void {
    @setEvalBranchQuota(maxBranch);
    for (0..gates.ngates) |i| {
        const gate = gates.gates[i];
        if (gate.out[0] == 'z') {
            computeWire(wires, gates, gate.out);
        }
    }
}

pub fn main() !void {
    @setEvalBranchQuota(maxBranch);
    comptime var wires: Wires_t = undefined;
    comptime initWires(input, &wires);
    comptime var gates: Gates_t = undefined;
    comptime initGates(input, &gates);

    //printWires(wires);
    //printGates(gates);
    //std.debug.print("\n", .{});
    //printGates(gates);
    comptime computeCircuit(&wires, gates);
    //printWires(wires);
    const output = comptime wireOutput(wires);
    std.debug.print("Output wire signals are: {b} => {d}\n", .{ output, output });
}
Solution 2
const std = @import("std");
const stdout = std.io.getStdOut().writer();
const stderr = std.io.getStdErr().writer();

const Op = enum { XOR, OR, AND };

const Wire = struct {
    name: usize,
    gateidx: usize,
    val: bool,
    ok: bool,
    inp: bool,

    const Self = @This();

    pub fn fromLine(line: []const u8) Self {
        var fields = std.mem.tokenizeSequence(u8, line, ": ");
        const name = fields.next().?;
        const val = std.fmt.parseInt(u8, fields.next().?, 10) catch {
            unreachable;
        };
        return str2wire(name, val, true);
    }
};

test "readWire" {
    const line = "x37: 1";
    const wire = Wire.fromLine(line);
    const refwire = Wire{
        .name = 720307,
        .gateidx = 0,
        .val = true,
        .ok = true,
        .inp = false,
    };
    try std.testing.expect(wire.name == refwire.name);
    try std.testing.expect(wire.val == refwire.val);
}

pub fn str2wire(str: []const u8, val: u8, inp: bool) Wire {
    var num: usize = 0;
    for (str) |char| {
        num *= 100;
        num += char - '0';
    }
    return Wire{ .name = num, .gateidx = 0, .val = val == 1, .ok = true, .inp = inp };
}

test "str2wire" {
    try std.testing.expect(str2wire("abc", 0, false).name == 495051);
    try std.testing.expect(str2wire("x02", 1, false).name == 720002);
}

pub fn wire2str(wire: Wire) [3]u8 {
    var str: [3]u8 = undefined;
    for (0..3) |i| {
        const val = @mod(wire.name / std.math.pow(usize, 100, i), 100);
        str[2 - i] = @as(u8, @intCast(val)) + '0';
    }
    return str;
}

test "wire2str" {
    const str = wire2str(Wire{ .name = 495051, .gateidx = 0, .val = false, .ok = true, .inp = false });
    const ref = "abc";
    try std.testing.expect(std.mem.eql(u8, &str, ref));
    const str2 = wire2str(Wire{ .name = 720002, .gateidx = 0, .val = false, .ok = true, .inp = false });
    const ref2 = "x02";
    try std.testing.expect(std.mem.eql(u8, &str2, ref2));
}

pub fn wirename2str(wirename: usize) [3]u8 {
    var str: [3]u8 = undefined;
    for (0..3) |i| {
        const val = @mod(wirename / std.math.pow(usize, 100, i), 100);
        str[2 - i] = @as(u8, @intCast(val)) + '0';
    }
    return str;
}

const Gate = struct {
    in1: usize,
    in1idx: usize,
    in2: usize,
    in2idx: usize,
    out: usize,
    pout: usize,
    outidx: usize,
    active: bool,
    op: Op,

    const Self = @This();

    pub fn fromLine(line: []const u8) Self {
        var gate: Self = undefined;
        var fields = std.mem.tokenizeScalar(u8, line, ' ');
        gate.in1 = str2wire(fields.next().?, 0, false).name;
        const opstr = fields.next().?;
        if (std.mem.eql(u8, opstr, "AND")) {
            gate.op = .AND;
        } else if (std.mem.eql(u8, opstr, "XOR")) {
            gate.op = .XOR;
        } else if (std.mem.eql(u8, opstr, "OR")) {
            gate.op = .OR;
        } else {
            unreachable;
        }
        gate.in2 = str2wire(fields.next().?, 0, false).name;
        _ = fields.next().?;
        gate.out = str2wire(fields.next().?, 0, false).name;
        gate.pout = gate.out;
        gate.active = false;

        return gate;
    }
};

test "readGate" {
    const line = "x37 XOR y03 -> brm";
    const gate = Gate.fromLine(line);
    const refgate = Gate{
        .in1 = 720307,
        .in1idx = 0,
        .in2 = 730003,
        .in2idx = 0,
        .out = 506661,
        .pout = 506661,
        .outidx = 0,
        .active = false,
        .op = .XOR,
    };
    try std.testing.expect(gate.in1 == refgate.in1);
    try std.testing.expect(gate.in2 == refgate.in2);
    try std.testing.expect(gate.out == refgate.out);
    try std.testing.expect(gate.op == refgate.op);
}

const Circuit = struct {
    wires: std.ArrayList(Wire),
    gates: std.ArrayList(Gate),
    inX: usize,
    inY: usize,

    const Self = @This();

    fn wireLessThan(_: void, lhs: Wire, rhs: Wire) bool {
        return lhs.name < rhs.name;
    }

    pub fn sortWires(self: Self) void {
        std.mem.sort(Wire, self.wires.items, {}, wireLessThan);
    }

    pub fn fromLines(inp: []const u8, allocator: std.mem.Allocator) Self {
        var circuit = Self{
            .wires = std.ArrayList(Wire).init(allocator),
            .gates = std.ArrayList(Gate).init(allocator),
            .inX = undefined,
            .inY = undefined,
        };

        var blocks = std.mem.tokenizeSequence(u8, inp, "\n\n");
        const inval_block = blocks.next().?;
        const gate_block = blocks.next().?;

        // get the initial wires
        var lines = std.mem.tokenizeScalar(u8, inval_block, '\n');
        while (lines.next()) |line| {
            circuit.wires.append(Wire.fromLine(line)) catch {
                unreachable;
            };
        }

        // fill the gate array
        lines = std.mem.tokenizeScalar(u8, gate_block, '\n');
        while (lines.next()) |line| {
            circuit.gates.append(Gate.fromLine(line)) catch {
                unreachable;
            };
        }

        // loop over all gates and add the outputs to the wires array
        for (circuit.gates.items, 0..) |gate, idx| {
            circuit.wires.append(Wire{ .name = gate.out, .gateidx = idx, .val = false, .ok = true, .inp = false }) catch {
                unreachable;
            };
        }

        circuit.sortWires();

        // map the input and output wires to the wires in the list
        for (circuit.gates.items) |*gate| {
            gate.in1idx = circuit.getWireIdxViaName(gate.in1).?;
            gate.in2idx = circuit.getWireIdxViaName(gate.in2).?;
            gate.outidx = circuit.getWireIdxViaName(gate.out).?;
        }

        circuit.inX = circuit.getInputX();
        circuit.inY = circuit.getInputY();

        return circuit;
    }

    pub fn deinit(self: Self) void {
        self.wires.deinit();
        self.gates.deinit();
    }

    pub fn reset(self: *Self) void {
        for (self.gates.items) |*gate| {
            gate.active = false;
        }
        for (self.wires.items) |*wire| {
            wire.val = false;
        }
        self.setInputX(self.inX);
        self.setInputY(self.inY);
    }

    pub fn getWireIdxViaName(self: Self, name: usize) ?usize {
        var lidx: usize = 0;
        var hidx: usize = self.wires.items.len - 1;
        while (lidx <= hidx) {
            const midx: usize = lidx + @divFloor(hidx - lidx, 2);
            if (self.wires.items[midx].name == name) {
                return midx;
            }
            if (self.wires.items[midx].name < name) {
                lidx = midx + 1;
            } else {
                hidx = midx - 1;
            }
        }
        return null;
    }

    pub fn getWireViaIdx(self: Self, idx: usize) ?*Wire {
        if (idx < self.wires.items.len) {
            return &(self.wires.items[idx]);
        }
        return null;
    }

    pub fn print(self: Self) !void {
        for (self.wires.items) |wire| {
            try stdout.print("{s}: {?} ({?})\n", .{ wire2str(wire), wire.val, wire.inp });
        }
        try stdout.print("\n", .{});

        for (self.gates.items) |gate| {
            const in1 = self.getWireViaIdx(gate.in1idx).?;
            const in1val: u8 = if (in1.val) '1' else '0';
            try stdout.print("{s}({c})", .{ wire2str(in1.*), in1val });
            const opstr = switch (gate.op) {
                .OR => "OR ",
                .XOR => "XOR",
                .AND => "AND",
            };
            try stdout.print(" {s} ", .{opstr});
            const in2 = self.getWireViaIdx(gate.in2idx).?;
            const in2val: u8 = if (in2.val) '1' else '0';
            try stdout.print("{s}({c})", .{ wire2str(in2.*), in2val });
            try stdout.print(" -> ", .{});
            const out = self.getWireViaIdx(gate.outidx).?;
            const outval: u8 = if (out.val) '1' else '0';
            try stdout.print("{s}({c})", .{ wire2str(out.*), outval });
            try stdout.print("\n", .{});
        }
    }

    pub fn evalWire(self: *Self, wireidx: usize) void {
        var out = &self.wires.items[wireidx];
        var gate = &self.gates.items[out.gateidx];
        if (!gate.active) {
            gate.active = true;
            const in1 = self.getWireViaIdx(gate.in1idx).?;
            const in2 = self.getWireViaIdx(gate.in2idx).?;
            if (!in1.inp) {
                self.evalWire(gate.in1idx);
            }
            if (!in2.inp) {
                self.evalWire(gate.in2idx);
            }

            out.val = switch (gate.op) {
                .OR => in1.val or in2.val,
                .AND => in1.val and in2.val,
                .XOR => (in1.val or in2.val) and !(in1.val and in2.val),
            };
        }
    }

    pub fn evaluate(self: *Self) void {
        for (0..46) |j| {
            const i: usize = 45 - j;
            const name: usize =
                ('z' - '0') * 100 * 100 + @divFloor(i, 10) * 100 + @mod(i, 10);
            const idx = self.getWireIdxViaName(name).?;
            self.evalWire(idx);
        }
    }

    fn getWiresVal(self: Self, c: u8) usize {
        var outval: usize = 0;
        for (self.wires.items) |wire| {
            if (wire.name / 10000 + '0' == c) {
                const val: usize = if (wire.val) 1 else 0;
                var idx: u8 = 0;
                idx += @as(u8, @intCast(10 * @divFloor(@mod(wire.name, 10000), 100)));
                idx += @as(u8, @intCast(@mod(wire.name, 100)));
                outval += val << @as(u6, @intCast(idx));
            }
        }
        return outval;
    }

    pub fn getOutput(self: Self) usize {
        return self.getWiresVal('z');
    }

    pub fn getInputX(self: Self) usize {
        return self.getWiresVal('x');
    }

    pub fn getInputY(self: Self) usize {
        return self.getWiresVal('y');
    }

    pub fn setWiresVal(self: *Self, c: u8, val: usize) void {
        for (self.wires.items) |*wire| {
            if (wire.name / 10000 + '0' == c) {
                var idx: u8 = 0;
                idx += @as(u8, @intCast(10 * @divFloor(@mod(wire.name, 10000), 100)));
                idx += @as(u8, @intCast(@mod(wire.name, 100)));
                const k = @as(u6, @intCast(idx));
                const bit = (val & (@as(usize, 1) << k)) >> k;
                wire.val = @as(u8, @intCast(bit)) == 1;
            }
        }
    }

    pub fn setInputX(self: *Self, val: usize) void {
        self.setWiresVal('x', val);
    }

    pub fn setInputY(self: *Self, val: usize) void {
        self.setWiresVal('y', val);
    }

    pub fn markActiveGates(self: *Self) void {
        for (self.gates.items) |*gate| {
            //const in1 = self.getWireViaIdx(gate.in1idx).?;
            //const in2 = self.getWireViaIdx(gate.in2idx).?;
            const out = self.getWireViaIdx(gate.outidx).?;
            //if (in1.val or in2.val or out.val) {
            if (out.val) {
                gate.active = true;
            }
        }
    }

    pub fn getActiveGatesList(self: Self, list: *std.ArrayList(usize)) !void {
        for (self.gates.items) |gate| {
            const wire = self.wires.items[gate.outidx];
            if (wire.val) {
                var has_elem = false;
                for (list.items) |item| {
                    if (item == gate.outidx) {
                        has_elem = true;
                        break;
                    }
                }
                if (!has_elem) {
                    try list.append(gate.outidx);
                    //std.debug.print("{s}\n", .{wire2str(wire)});
                }
            }
        }
    }

    pub fn markAllWiresOk(self: *Self) void {
        for (self.wires.items) |*wire| {
            wire.ok = true;
        }
    }

    pub fn markAllOutputWiresBroken(self: *Self) void {
        self.markAllWiresOk();
        for (self.gates.items) |gate| {
            self.wires.items[gate.outidx].ok = false;
        }
    }

    pub fn swapWires(self: *Self, a: usize, b: usize) void {
        var wire_a = &self.wires.items[a];
        var gate_a = &self.gates.items[wire_a.gateidx];
        var wire_b = &self.wires.items[b];
        var gate_b = &self.gates.items[wire_b.gateidx];

        var tmp = wire_a.gateidx;
        wire_a.gateidx = wire_b.gateidx;
        wire_b.gateidx = tmp;

        tmp = gate_a.outidx;
        gate_a.outidx = gate_b.outidx;
        gate_b.outidx = tmp;

        tmp = gate_a.out;
        gate_a.out = gate_b.out;
        gate_b.out = tmp;
    }

    pub fn testBitAddition(self: *Self, bitidx: usize) bool {
        self.reset();
        const iu6 = @as(u6, @intCast(bitidx));
        self.inX = @as(usize, 1) << iu6;
        self.inY = 0;
        self.reset();
        self.evaluate();
        return self.getOutput() == self.inX + self.inY;
    }

    pub fn testBitCarry(self: *Self, bitidx: usize) bool {
        self.reset();
        const iu6 = @as(u6, @intCast(bitidx));
        self.inX = @as(usize, 1) << iu6;
        self.inY = @as(usize, 1) << iu6;
        self.reset();
        self.evaluate();
        return self.getOutput() == self.inX + self.inY;
    }

    pub fn testBitCarryAdd(self: *Self, bitidx: usize) bool {
        self.reset();
        if (bitidx > 0) {
            const iu6 = @as(u6, @intCast(bitidx));
            self.inX = @as(usize, 1) << iu6;
            self.inY = @as(usize, 1) << (iu6 - 1);
            self.inX += self.inY;
            self.reset();
            self.evaluate();
            return self.getOutput() == self.inX + self.inY;
        }
        return true;
    }

    pub fn testAll(self: *Self) usize {
        var nerrors: usize = 0;
        for (0..45) |i| {
            if (!self.testBitAddition(i)) {
                nerrors += 1;
            }
            if (!self.testBitCarry(i)) {
                nerrors += 1;
            }
            if (!self.testBitCarryAdd(i)) {
                nerrors += 1;
            }
        }
        return nerrors;
    }

    pub fn testUpToll(self: *Self, bitidx: usize) usize {
        var nerrors: usize = 0;
        for (0..bitidx) |i| {
            if (!self.testBitAddition(i)) {
                nerrors += 1;
            }
            if (!self.testBitCarry(i)) {
                nerrors += 1;
            }
            if (!self.testBitCarryAdd(i)) {
                nerrors += 1;
            }
        }
        return nerrors;
    }

    pub fn getAllActiveGatesList(self: *Self, bitidx: usize, list: *std.ArrayList(usize)) void {
        list.clearRetainingCapacity();
        if (!self.testBitAddition(bitidx)) {
            self.getActiveGatesList(list) catch {
                unreachable;
            };
        }
        if (!self.testBitCarry(bitidx)) {
            self.getActiveGatesList(list) catch {
                unreachable;
            };
        }
        if (!self.testBitCarryAdd(bitidx)) {
            self.getActiveGatesList(list) catch {
                unreachable;
            };
        }
    }
};

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

    const args = try std.process.argsAlloc(allocator);
    defer std.process.argsFree(allocator, args);
    if (args.len < 2) {
        try stderr.print("Usage: {s} <filename>\n", .{args[0]});
        return error.InvalidArguments;
    }
    const filename = args[1];
    const file = try std.fs.cwd().openFile(filename, .{});
    defer file.close();
    const file_size = try file.getEndPos();

    const input = try allocator.alloc(u8, file_size);
    defer allocator.free(input);

    const bytes_read = try file.readAll(input);
    if (bytes_read != file_size) {
        try stderr.print("Warning: Read {d} bytes but expected {d}\n", .{ bytes_read, file_size });
    }

    var circuit = Circuit.fromLines(input, allocator);
    defer circuit.deinit();

    //const inX = circuit.getInputX();
    //const inY = circuit.getInputX();

    var sus_outs_map = std.AutoHashMap(usize, usize).init(allocator);
    defer sus_outs_map.deinit();

    circuit.reset();
    circuit.evaluate();
    //std.debug.print("x:    {0b:0>45} {0d:>10}\n", .{circuit.getInputX()});
    //std.debug.print("y: +  {0b:0>45} {0d:>10}\n", .{circuit.getInputY()});
    //std.debug.print("z: = {0b:0>46} {0d:>10}\n", .{circuit.getOutput()});
    //std.debug.print("r:   {0b:0>46} {0d:>10}\n", .{circuit.getInputX() + circuit.getInputY()});

    // determine set of suspecious wires.
    circuit.markAllOutputWiresBroken();
    for (0..45) |i| {
        if (circuit.testBitAddition(i)) {
            for (circuit.wires.items) |*wire| {
                if (wire.val) {
                    wire.ok = true;
                }
            }
        }
        if (circuit.testBitCarry(i)) {
            for (circuit.wires.items) |*wire| {
                if (wire.val) {
                    wire.ok = true;
                }
            }
        }
        if (circuit.testBitCarryAdd(i)) {
            for (circuit.wires.items) |*wire| {
                if (wire.val) {
                    wire.ok = true;
                }
            }
        }
    }

    var sus_outs = std.ArrayList(usize).init(allocator);
    defer sus_outs.deinit();
    for (circuit.gates.items) |gate| {
        const wire = circuit.wires.items[gate.outidx];
        if (!wire.ok) {
            try sus_outs.append(gate.outidx);
            //std.debug.print("{s}\n", .{wire2str(wire)});
        }
    }

    var active_outs = std.ArrayList(usize).init(allocator);
    defer active_outs.deinit();
    for (0..45) |i| {
        if (circuit.testUpToll(i) > 0) {
            circuit.getAllActiveGatesList(i, &active_outs);

            var nerrors = circuit.testAll();
            var bestidxa: usize = 0;
            var bestidxb: usize = 0;
            for (active_outs.items) |aout| {
                for (sus_outs.items) |sout| {
                    if (aout == sout) {
                        continue;
                    }
                    circuit.swapWires(aout, sout);
                    const new_errors = circuit.testAll();
                    if (new_errors <= nerrors) {
                        bestidxa = aout;
                        bestidxb = sout;
                        //std.debug.print("swapped {s} - {s}\n", .{ wire2str(circuit.wires.items[aout]), wire2str(circuit.wires.items[sout]) });
                        nerrors = new_errors;
                    }
                    circuit.swapWires(aout, sout);
                }
            }
            circuit.swapWires(bestidxa, bestidxb);
            //std.debug.print("nerrors: {d}\n", .{nerrors});
        }
    }

    var wrong_wires = std.ArrayList([3]u8).init(allocator);
    defer wrong_wires.deinit();

    for (circuit.gates.items) |gate| {
        if (gate.out != gate.pout) {
            try wrong_wires.append(wirename2str(gate.pout));
        }
    }
    std.mem.sort([3]u8, wrong_wires.items, {}, stringLessThan);
    std.debug.print("Wrong wires: {s}", .{wrong_wires.items[0]});
    for (wrong_wires.items[1..]) |wire| {
        std.debug.print(",{s}", .{wire});
    }
    std.debug.print("\n", .{});
    //std.debug.print("Ref wires:   cqr,ncd,nfj,qnw,vkg,z15,z20,z37\n", .{});
}

fn stringLessThan(_: void, lhs: [3]u8, rhs: [3]u8) bool {
    return std.mem.order(u8, &lhs, &rhs) == .lt;
}

Edit: Timings

Benchmark 1: ./solution-1
  Time (mean ± σ):       0.0 µs ±   1.0 µs    [User: 104.4 µs, System: 2.1 µs]
  Range (min … max):     0.0 µs …  52.6 µs    2808 runs

Edit: Finally solved part 2

Benchmark 1: ./zig-out/bin/solution-2 ./src/big.inp
  Time (mean ± σ):     849.2 ms ±   7.0 ms    [User: 847.9 ms, System: 1.0 ms]
  Range (min … max):   839.5 ms … 860.0 ms    10 runs

2 Likes