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) ;