AoC 2024: Day 19

Challenge
1

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

1 Like
2

Today had a nice and compact solution. The key for part 2 was memoization.

https://zigbin.io/a80cee

3

Started yesterday, had a really good idea on how to do part 2 today. Part 2 is O(n), only a single allocation and no recursion. I just made part 1 be based on part 2, so its basically the same thing.

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

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

    const input = try std.fs.cwd().openFile("src/19/input", .{});
    defer input.close();
    var bufreader = std.io.bufferedReader(input.reader());
    const reader = bufreader.reader();

    const stdout = std.io.getStdOut();
    defer stdout.close();

    const p1, const p2 = try solve(allocator, reader);
    try stdout.writer().print("{d}\n", .{p1});
    try stdout.writer().print("{d}\n", .{p2});
}

fn solve(allocator: std.mem.Allocator, reader: anytype) !struct { usize, usize } {
    var towels_buf: [4 * 1024]u8 = undefined;
    const towels = b: {
        var list: std.ArrayList([]const u8) = .init(allocator);
        errdefer list.deinit();

        const line = try reader.readUntilDelimiter(&towels_buf, '\n');
        var iter = std.mem.splitSequence(u8, line, ", ");
        while (iter.next()) |towel|
            try list.append(towel);

        break :b try list.toOwnedSlice();
    };
    defer allocator.free(towels);

    var sum: usize = 0;
    var ways_to_solve: usize = 0;

    var buf: [1024]u8 = undefined;
    _ = try reader.readUntilDelimiter(&buf, '\n');
    while (try reader.readUntilDelimiterOrEof(&buf, '\n')) |pattern| {
        const ways = try waysToMake(allocator, towels, pattern);
        sum += @intFromBool(ways > 0);
        ways_to_solve += ways;
    }

    return .{ sum, ways_to_solve };
}

fn waysToMake(
    allocator: std.mem.Allocator,
    towels: []const []const u8,
    pattern: []const u8,
) !usize {
    const visits = try allocator.alloc(usize, pattern.len + 1);
    defer allocator.free(visits);
    visits[0] = 1;
    @memset(visits[1..], 0);

    for (0..pattern.len) |i| {
        for (towels) |towel| {
            if (std.mem.startsWith(u8, pattern[i..], towel))
                visits[i + towel.len] += visits[i];
        }
    }

    return visits[visits.len - 1];
}

test {
    const allocator = std.testing.allocator;
    var input = std.io.fixedBufferStream(
        \\r, wr, b, g, bwu, rb, gb, br
        \\
        \\brwrr
        \\bggr
        \\gbbr
        \\rrbgbr
        \\ubwu
        \\bwurrg
        \\brgr
        \\bbrgwb
    );

    const p1, const p2 = try solve(allocator, input.reader());
    try std.testing.expectEqual(6, p1);
    try std.testing.expectEqual(16, p2);
}
4

Fast memoization day. One pass solves both parts, so part2 just produces the other result.

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

        parse   part1   part2   total
day 19:  4.1 µs 66.6 µs 30.0 ns 70.7 µs (+-0%)
5

https://zigbin.io/2c716e