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().?;

    var allNumbers = mem.splitScalar(u8, postfix, '|');

    var winningText = mem.splitScalar(u8, allNumbers.next().?, ' ');
    var ownedText = mem.splitScalar(u8, allNumbers.next().?, ' ');
    // 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);
}