const std = @import("std");

const PATH = "input/day21.txt";
const Str = []const u8;

pub fn first(allocator: ?std.mem.Allocator) anyerror!usize {
    var arena = std.heap.ArenaAllocator.init(allocator.?);
    defer arena.deinit();

    var food = try parseInput(arena.allocator(), @embedFile(PATH));
    try food.reduce();

    var count: usize = 0;
    for (food.ingrediens) |item| {
        if (food.allergens.get(item) == null) count += 1;
    }

    return count;
}

fn stringCompare(context: void, a: Str, b: Str) bool {
    _ = context;
    return std.ascii.lessThanIgnoreCase(a, b);
}

pub fn second(allocator: ?std.mem.Allocator) anyerror!Str {
    var arena = std.heap.ArenaAllocator.init(allocator.?);
    defer arena.deinit();

    var ret = std.ArrayList(u8).init(allocator.?);

    var food = try parseInput(arena.allocator(), @embedFile(PATH));
    try food.reduce();

    var order = std.ArrayList(Str).init(arena.allocator());

    var ait = food.allergens.iterator();
    while (ait.next()) |ntry| {
        try order.append(ntry.value_ptr.*);
    }

    std.sort.sort(Str, order.items, {}, comptime stringCompare);

    for (order.items) |o| {
        var it = food.allergens.iterator();
        while (it.next()) |entry| {
            if (std.mem.eql(u8, o, entry.value_ptr.*)) {
                try ret.appendSlice(entry.key_ptr.*);
                try ret.append(',');
            }
        }
    }

    ret.items = ret.items[0 .. ret.items.len - 1];

    return ret.toOwnedSlice();
}

const Foods = struct {
    ingrediens: []Str,
    reduced: std.StringHashMap(std.BufSet),
    allergens: std.BufMap,

    fn reduce(self: *@This()) !void {
        while (self.reduced.count() != self.allergens.count()) {
            var it = self.reduced.iterator();
            while (it.next()) |entry| {
                // if only one item left, that is the allergen
                if (entry.value_ptr.*.count() == 1) {
                    var eit = entry.value_ptr.*.iterator();
                    const value = eit.next().?;
                    try self.allergens.put(value.*, entry.key_ptr.*);
                } else {
                    // remove all known allergens from the ingrediens list
                    var ait = self.allergens.iterator();
                    while (ait.next()) |elem| {
                        entry.value_ptr.*.remove(elem.key_ptr.*);
                    }
                }
            }
        }
    }
};

fn parseInput(allocator: std.mem.Allocator, in: Str) !Foods {
    var f = Foods{
        .ingrediens = undefined,
        .reduced = std.StringHashMap(std.BufSet).init(allocator),
        .allergens = std.BufMap.init(allocator),
    };

    var ings = std.ArrayList(Str).init(allocator);
    var lines = std.mem.split(u8, in, "\n");

    while (lines.next()) |line| {
        // std.debug.print("{s}\n", .{line});
        var ing_allerg = std.mem.tokenize(u8, line, "()");

        const ingredients = ing_allerg.next().?;
        const allergens = ing_allerg.next().?;

        // collect ingredients
        var ing_list = std.ArrayList(Str).init(allocator);
        defer ing_list.deinit();

        var ing_it = std.mem.tokenize(u8, ingredients, " ");
        while (ing_it.next()) |ing| {
            try ing_list.append(ing);
        }

        try ings.appendSlice(ing_list.items);

        // collect allergens
        var all_it = std.mem.tokenize(u8, allergens, ", ");
        _ = all_it.next(); // drop "contains"
        while (all_it.next()) |a| {
            const res = try f.reduced.getOrPut(a);

            if (res.found_existing == true) {
                var new = std.BufSet.init(allocator);
                for (ing_list.items) |item| {
                    if (res.value_ptr.contains(item)) {
                        try new.insert(item);
                    }
                }
                res.value_ptr.* = new;
            } else {
                res.value_ptr.* = std.BufSet.init(allocator);
                for (ing_list.items) |item| {
                    try res.value_ptr.*.insert(item);
                }
            }
        }
    }

    f.ingrediens = try ings.toOwnedSlice();

    return f;
}

test "day20a" {
    try std.testing.expectEqual(@as(usize, 2162), try first(std.testing.allocator));
}

test "day20b" {
    const actual = try second(std.testing.allocator);
    defer std.testing.allocator.free(actual);
    try std.testing.expectEqualStrings("lmzg,cxk,bsqh,bdvmx,cpbzbx,drbm,cfnt,kqprv", actual);
}

const test_input =
    \\mxmxvkd kfcds sqjhc nhms (contains dairy, fish)
    \\trh fvjkl sbzzf mxmxvkd (contains dairy)
    \\sqjhc fvjkl (contains soy)
    \\sqjhc mxmxvkd sbzzf (contains fish)
;