AoC 2025: Day 11

Challenge
1

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

Templates:

Resources:

2

Classic AoC today, not sure I’d have solved it without all the practice of previous years.

For part two, the note “dac and fft (in any order)” was a red herring! I decided to memoize path counts between each device as an intermediary step. But when I looked out the counts and compared it against the example, I realised all I needed was a simple multiplication.

3

After day 10, which was as heavy handed as you can possibly get, day 11 was a breeze. Just remember to memoize your computations because the numbers are quite big.

4

Today was much more doable than yesterday :slight_smile: repo

Just did some simple recursion with memoization like most people did. Also I looked at all the relevant paths and also found that relevant steps are [svr => fft], [fft => dac], [dac => out].

part 2:

fn bytesToU24(bytes: [3]u8) u24 {
    return @bitCast(bytes);
}
fn u24ToBytes(val: u24) [3]u8 {
    return @bitCast(val);
}

const svr = bytesToU24("svr".*);
const fft = bytesToU24("fft".*);
const dac = bytesToU24("dac".*);
const you = bytesToU24("you".*);
const out = bytesToU24("out".*);

const NodeData = struct {
    parents: ArrayList(u24),

    pub const empty: NodeData = .{
        .parents = .empty,
    };
};

fn solution(r: *Reader, _: Io, gpa: Allocator) !u64 {
    var node_data: NodeDataSet = .empty;
    defer {
        var it = node_data.valueIterator();
        while (it.next()) |value| {
            value.parents.deinit(gpa);
        }
        node_data.deinit(gpa);
    }

    while (try r.takeDelimiter('\n')) |line| {
        var it = mem.tokenizeAny(u8, line, ": ");

        const node = bytesToU24(it.next().?[0..3].*);
        {
            const gop = try node_data.getOrPut(gpa, node);

            switch (gop.found_existing) {
                true => {},
                false => gop.value_ptr.* = .empty,
            }
        }
        while (it.next()) |bytes| {
            const outflow = bytesToU24(bytes[0..3].*);
            const gop = try node_data.getOrPut(gpa, outflow);

            switch (gop.found_existing) {
                true => {
                    if (mem.findScalar(u24, gop.value_ptr.parents.items, outflow) == null) {
                        try gop.value_ptr.parents.append(gpa, node);
                    }
                },
                false => {
                    gop.value_ptr.* = .empty;
                    try gop.value_ptr.parents.append(gpa, node);
                },
            }
        }
    }

    var seen_set: SeenSet = .empty;
    defer seen_set.deinit(gpa);

    const svr_fft = try pathToWrapped(gpa, &seen_set, &node_data, svr, fft);
    const fft_dac = try pathToWrapped(gpa, &seen_set, &node_data, fft, dac);
    const dac_out = try pathToWrapped(gpa, &seen_set, &node_data, dac, out);

    std.log.info("Cached {d} lookups", .{cache});
    cache = 0;
    return svr_fft * fft_dac * dac_out;
}

const NodeDataSet = std.AutoHashMapUnmanaged(u24, NodeData);
const SeenSet = std.AutoArrayHashMapUnmanaged(u24, u64);

fn pathToWrapped(gpa: Allocator, seen_set: *SeenSet, data_set: *NodeDataSet, src: u24, dest: u24) !u64 {
    seen_set.clearRetainingCapacity();
    return pathTo(gpa, seen_set, data_set, src, dest);
}

var cache: u64 = 0;
fn pathTo(gpa: Allocator, seen_set: *SeenSet, data_set: *NodeDataSet, src: u24, dest: u24) !u64 {
    assert(dest != src);

    {
        const seen_gop = try seen_set.getOrPut(gpa, dest);

        if (seen_gop.found_existing) {
            cache += 1;
            return seen_gop.value_ptr.*;
        }

        seen_gop.value_ptr.* = 0;
    }

    const data = data_set.get(dest) orelse fatal("Invalid node {x}", .{dest});

    var seen: u64 = 0; // Only update seen _after_ we recurse to ignore cycles
    for (data.parents.items) |parent| {
        if (parent == src) {
            seen += 1;
            continue;
        }

        seen += try pathTo(gpa, seen_set, data_set, src, parent);
    }
    const seen_gop = try seen_set.getOrPut(gpa, dest);
    assert(seen_gop.found_existing);
    seen_gop.value_ptr.* = seen;
    return seen;
}
1 Like