1 files changed, 126 insertions, 0 deletions

diff --git a/day04/solution.zig b/day04/solution.zig
new file mode 100644
index 0000000..081277a
--- /dev/null
+++ b/day04/solution.zig
@@ -0,0 +1,126 @@
+const std = @import("std");
+const print = std.debug.print;
+const assert = std.debug.assert;
+const ArrayList = std.ArrayList;
+const mem = std.mem;
+
+const fin = mem.trim(u8, @embedFile("./input.txt"), &std.ascii.whitespace);
+var gpa = std.heap.GeneralPurposeAllocator(.{}){};
+const allocator = gpa.allocator();
+const u32HashSet = std.ArrayHashMap(u32, void, u32HashSetCtx, false);
+
+const u32HashSetCtx = struct {
+    pub fn hash(self: @This(), K: u32) u32 {
+        _ = self;
+        return K;
+    }
+
+    pub fn eql(self: @This(), K1: u32, K2: u32, s: usize) bool {
+        _ = s;
+        _ = self;
+        return K1 == K2;
+    }
+};
+
+const Card = struct {
+    var cardId: u32 = 1;
+    id: u32,
+    winning: u32HashSet,
+    owned: u32HashSet,
+};
+
+fn parseCard(text: []const u8) !Card {
+    var result = Card{
+        .id = Card.cardId,
+        .winning = u32HashSet.init(allocator),
+        .owned = u32HashSet.init(allocator),
+    };
+    Card.cardId += 1;
+
+    var prefix = mem.splitScalar(u8, text, ':');
+    _ = prefix.next(); // ignore 'Card ##' prefix
+    const postfix = prefix.next() orelse unreachable;
+
+    var allNumbers = mem.splitScalar(u8, postfix, '|');
+
+    var winningText = mem.splitScalar(u8, allNumbers.next() orelse unreachable, ' ');
+    var ownedText = mem.splitScalar(u8, allNumbers.next() orelse unreachable, ' ');
+    // split produces some empty strings that must be ignored later
+
+    while (winningText.next()) |numText| {
+        const num = std.fmt.parseInt(u32, numText, 10) catch continue;
+        try result.winning.put(num, undefined);
+    }
+    while (ownedText.next()) |numText| {
+        const num = std.fmt.parseInt(u32, numText, 10) catch continue;
+        try result.owned.put(num, undefined);
+    }
+
+    return result;
+}
+
+fn matchesPerCard(cards: ArrayList(Card)) ArrayList(u64) {
+    var res = ArrayList(u64).init(allocator);
+
+    for (cards.items) |card| {
+        var n: u64 = 0;
+
+        for (card.winning.keys()) |win| {
+            if (card.owned.contains(win)) {
+                n += 1;
+            }
+        }
+        res.append(n) catch unreachable;
+    }
+
+    return res;
+}
+
+pub fn part1(cards: ArrayList(Card)) void {
+    var ans: u64 = 0;
+    const matches = matchesPerCard(cards);
+    defer matches.deinit();
+
+    for (matches.items) |nMatches| {
+        if (nMatches > 0) {
+            ans += std.math.pow(u64, 2, nMatches - 1);
+        }
+    }
+
+    print("{d}\n", .{ans});
+}
+
+pub fn part2(cards: ArrayList(Card)) void {
+    var ans: u64 = 0;
+    var matches = matchesPerCard(cards);
+    var copies = ArrayList(u64).init(allocator);
+    defer {
+        matches.deinit();
+        copies.deinit();
+    }
+    copies.resize(matches.items.len) catch unreachable;
+    @memset(copies.items, 1);
+
+    for (matches.items, copies.items, 0..) |m, c, i| {
+        for (i + 1..i + 1 + m) |j| {
+            copies.items[j] += c;
+        }
+        ans += c;
+    }
+
+    print("{d}\n", .{ans});
+}
+
+pub fn main() !void {
+    var splitLines = mem.splitScalar(u8, fin, '\n');
+    var cards = ArrayList(Card).init(allocator);
+    defer cards.deinit();
+
+    while (splitLines.next()) |line| {
+        const c = try parseCard(line);
+        try cards.append(c);
+    }
+
+    part1(cards);
+    part2(cards);
+}