diff options
Diffstat (limited to 'src/21/main.zig')
| -rw-r--r-- | src/21/main.zig | 188 |
1 files changed, 188 insertions, 0 deletions
diff --git a/src/21/main.zig b/src/21/main.zig new file mode 100644 index 0000000..d64252a --- /dev/null +++ b/src/21/main.zig @@ -0,0 +1,188 @@ +const std = @import("std"); +const aoc = @import("aoc"); + +const hasher = std.hash.CityHash32; +const IngredientInfo = struct { + count: u32, +}; +const Pair = struct { ingredient: []const u8, allergen: []const u8 }; + +fn freeListmap(listmap: *std.AutoHashMap(u32, std.ArrayList(u32))) void { + var mapit = listmap.iterator(); + while (mapit.next()) |kv| { + kv.value_ptr.deinit(); + } + listmap.deinit(); +} + +fn getAllergen(allergens: *std.AutoHashMap(u32, std.ArrayList(u32)), ingredient: u32) ?u32 { + var allergenit = allergens.iterator(); + while (allergenit.next()) |alg| { + if (alg.value_ptr.items.len == 1 and alg.value_ptr.items[0] == ingredient) + return alg.key_ptr.*; + } + return null; +} + +fn updateAllergens(allocator: std.mem.Allocator, allergens: *std.AutoHashMap(u32, std.ArrayList(u32)), allergen: u32) !void { + var next = std.ArrayList(u32).init(allocator); + defer next.deinit(); + + try next.append(allergen); + + while (next.items.len > 0) { + const key = next.items[0]; + var ingredient = allergens.getEntry(key).?.value_ptr.items[0]; + var mapit = allergens.iterator(); + while (mapit.next()) |alg| { + if (alg.key_ptr.* == key) continue; + const ind = std.mem.indexOfScalar(u32, alg.value_ptr.items, ingredient); + if (ind != null) { + _ = alg.value_ptr.swapRemove(ind.?); + if (alg.value_ptr.items.len == 1) { + try next.append(alg.key_ptr.*); + } + } + } + _ = next.swapRemove(0); + } +} + +fn parseAllergens(allocator: std.mem.Allocator, allergens: *std.AutoHashMap(u32, std.ArrayList(u32)), unhash: *std.AutoHashMap(u32, []const u8), ingredient_counts: *std.AutoHashMap(u32, u32), input: []const u8) !void { + var ingredients = std.ArrayList(u32).init(allocator); + defer ingredients.deinit(); + + var lineit = std.mem.tokenize(u8, input, "\n"); + while (lineit.next()) |line| { + var allergen = false; + + try ingredients.resize(0); + + var spaceit = std.mem.tokenize(u8, line, " "); + while (spaceit.next()) |word| { + if (std.mem.eql(u8, word, "(contains")) { + allergen = true; + continue; + } + + if (allergen) { + const allergen_name = if (word[word.len - 1] == ')' or word[word.len - 1] == ',') word[0 .. word.len - 1] else word; + const allergen_hash = hasher.hash(allergen_name); + try unhash.put(allergen_hash, allergen_name); + var algentry = allergens.getEntry(allergen_hash); + if (algentry) |algent| { + var i: u32 = 0; + while (i < algent.value_ptr.items.len) { + if (std.mem.indexOfScalar(u32, ingredients.items, algent.value_ptr.items[i]) == null) { + _ = algent.value_ptr.swapRemove(i); + } else { + i += 1; + } + } + + if (algent.value_ptr.items.len == 1) { + try updateAllergens(allocator, allergens, algent.key_ptr.*); + } + } else { + var copy = std.ArrayList(u32).init(allocator); + errdefer copy.deinit(); + for (ingredients.items) |ing| { + if (getAllergen(allergens, ing) == null) { + try copy.append(ing); + } + } + try allergens.put(allergen_hash, copy); + } + } else { + const ingredient_hash = hasher.hash(word); + try unhash.put(ingredient_hash, word); + try ingredients.append(ingredient_hash); + const entry = ingredient_counts.getEntry(ingredient_hash); + if (entry == null) { + try ingredient_counts.put(ingredient_hash, 1); + } else { + entry.?.value_ptr.* += 1; + } + } + } + } +} + +fn ascendingAllergen(ctx: void, p1: Pair, p2: Pair) bool { + _ = ctx; + var i: u32 = 0; + while (i < std.math.min(p1.allergen.len, p2.allergen.len) and p1.allergen[i] == p2.allergen[i]) : (i += 1) {} + return p1.allergen[i] < p2.allergen[i]; +} + +fn part1(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 { + _ = args; + + var allergens = std.AutoHashMap(u32, std.ArrayList(u32)).init(allocator); + defer freeListmap(&allergens); + + var ingredient_counts = std.AutoHashMap(u32, u32).init(allocator); + defer ingredient_counts.deinit(); + + var unhash = std.AutoHashMap(u32, []const u8).init(allocator); + defer unhash.deinit(); + + try parseAllergens(allocator, &allergens, &unhash, &ingredient_counts, input); + + var answer: u32 = 0; + + var algit = allergens.iterator(); + while (algit.next()) |alg| { + aoc.debugfmt("{} - ", .{alg.key_ptr.*}); + for (alg.value_ptr.items) |v| { + aoc.debugfmt("{} ", .{v}); + } + aoc.debugfmt("\n", .{}); + } + + var mapit = ingredient_counts.iterator(); + while (mapit.next()) |kv| { + if (getAllergen(&allergens, kv.key_ptr.*) == null) answer += kv.value_ptr.*; + } + + return try std.fmt.allocPrint(allocator, "{}", .{answer}); +} + +fn part2(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 { + _ = args; + + var allergens = std.AutoHashMap(u32, std.ArrayList(u32)).init(allocator); + defer freeListmap(&allergens); + + var ingredient_counts = std.AutoHashMap(u32, u32).init(allocator); + defer ingredient_counts.deinit(); + + var unhash = std.AutoHashMap(u32, []const u8).init(allocator); + defer unhash.deinit(); + + try parseAllergens(allocator, &allergens, &unhash, &ingredient_counts, input); + + var pairs = std.ArrayList(Pair).init(allocator); + defer pairs.deinit(); + + var mapit = ingredient_counts.iterator(); + while (mapit.next()) |kv| { + const alg = getAllergen(&allergens, kv.key_ptr.*); + if (alg != null) { + try pairs.append(Pair{ .ingredient = unhash.get(kv.key_ptr.*).?, .allergen = unhash.get(alg.?).? }); + } + } + + std.sort.sort(Pair, pairs.items, {}, ascendingAllergen); + + var parts = std.ArrayList([]const u8).init(allocator); + defer parts.deinit(); + for (pairs.items) |p, i| { + if (i > 0) try parts.append(","); + try parts.append(p.ingredient); + } + return try std.mem.join(allocator, "", parts.items); +} + +const sol2 = "fqhpsl,zxncg,clzpsl,zbbnj,jkgbvlxh,dzqc,ppj,glzb"; +pub const main = aoc.main(part1, part2, .{ "2584", sol2 }); |