[aoc/2021] Finish day 14 without heap

2 files changed, 150 insertions, 0 deletions

diff --git a/aoc/2021/14/part-one.zig b/aoc/2021/14/part-one.zig
new file mode 100644
index 0000000..0f50c10
--- /dev/null
+++ b/aoc/2021/14/part-one.zig
@@ -0,0 +1,75 @@
+const AutoHashMap = std.AutoHashMap;
+const FixedBufferAllocator = std.heap.FixedBufferAllocator;
+const math = std.math;
+const print = std.debug.print;
+const split = std.mem.split;
+const std = @import("std");
+const tokenize = std.mem.tokenize;
+
+const Children = packed struct { left: Pair, right: Pair };
+const Pair = packed struct { left: u8, right: u8 };
+const Rule = packed struct { adj: Pair, _: u32, ins: u8 };
+
+fn KV(comptime M: type, comptime index: usize) type {
+    const type_info = @typeInfo(@typeInfo(M).Pointer.child.KV);
+    return type_info.Struct.fields[index].field_type;
+}
+
+fn addOrPut(map: anytype, key: KV(@TypeOf(map), 0),
+            value: KV(@TypeOf(map), 1)) !void {
+    const result = try map.getOrPut(key);
+    if (result.found_existing)
+        result.value_ptr.* += value
+    else
+        result.value_ptr.* = value;
+}
+
+pub fn main() !void {
+    var buffer: [0xdecaf]u8 = undefined;
+    var fba = FixedBufferAllocator.init(buffer[0..]);
+    var input = split(@embedFile("input"), "\n\n");
+    var count = AutoHashMap(Pair, usize).init(&fba.allocator);
+    defer count.deinit();
+    const template = input.next().?;
+    for (template[0..template.len-1]) |*c|
+        try addOrPut(&count, @ptrCast(*const Pair, c).*, 1);
+
+    var rules = tokenize(input.next().?, "\n");
+    var insertions = AutoHashMap(Pair, Children).init(&fba.allocator);
+    defer insertions.deinit();
+    while (rules.next()) |rule| {
+        const unmasked = @ptrCast(*const Rule, rule.ptr);
+        try insertions.put(unmasked.adj, .{
+            .left = .{ .left = unmasked.adj.left, .right = unmasked.ins },
+            .right = .{ .left = unmasked.ins, .right = unmasked.adj.right },
+        });
+    }
+
+    var result = AutoHashMap(u8, usize).init(&fba.allocator);
+    for (template) |c|
+        try addOrPut(&result, c, 1);
+
+    var step: u8 = 0;
+    while (step < 10) : (step += 1) {
+        var tmp = AutoHashMap(Pair, usize).init(&fba.allocator);
+        var items = count.iterator();
+        while (items.next()) |entry| {
+            const k = insertions.get(entry.key_ptr.*) orelse continue;
+            const v = entry.value_ptr.*;
+            try addOrPut(&tmp, k.left, v);
+            try addOrPut(&tmp, k.right, v);
+            try addOrPut(&result, k.left.right, v);
+        }
+        count.deinit();
+        count = tmp;
+    }
+
+    var values = result.valueIterator();
+    var max = values.next().?.*;
+    var min = max;
+    while (values.next()) |value| {
+        max = math.max(value.*, max);
+        min = math.min(value.*, min);
+    }
+    print("{}\n", .{ max - min });
+}
diff --git a/aoc/2021/14/part-two.zig b/aoc/2021/14/part-two.zig
new file mode 100644
index 0000000..3f8bf1f
--- /dev/null
+++ b/aoc/2021/14/part-two.zig
@@ -0,0 +1,75 @@
+const AutoHashMap = std.AutoHashMap;
+const FixedBufferAllocator = std.heap.FixedBufferAllocator;
+const math = std.math;
+const print = std.debug.print;
+const split = std.mem.split;
+const std = @import("std");
+const tokenize = std.mem.tokenize;
+
+const Children = packed struct { left: Pair, right: Pair };
+const Pair = packed struct { left: u8, right: u8 };
+const Rule = packed struct { adj: Pair, _: u32, ins: u8 };
+
+fn KV(comptime M: type, comptime index: usize) type {
+    const type_info = @typeInfo(@typeInfo(M).Pointer.child.KV);
+    return type_info.Struct.fields[index].field_type;
+}
+
+fn addOrPut(map: anytype, key: KV(@TypeOf(map), 0),
+            value: KV(@TypeOf(map), 1)) !void {
+    const result = try map.getOrPut(key);
+    if (result.found_existing)
+        result.value_ptr.* += value
+    else
+        result.value_ptr.* = value;
+}
+
+pub fn main() !void {
+    var buffer: [0xdecaf]u8 = undefined;
+    var fba = FixedBufferAllocator.init(buffer[0..]);
+    var input = split(@embedFile("input"), "\n\n");
+    var count = AutoHashMap(Pair, usize).init(&fba.allocator);
+    defer count.deinit();
+    const template = input.next().?;
+    for (template[0..template.len-1]) |*c|
+        try addOrPut(&count, @ptrCast(*const Pair, c).*, 1);
+
+    var rules = tokenize(input.next().?, "\n");
+    var insertions = AutoHashMap(Pair, Children).init(&fba.allocator);
+    defer insertions.deinit();
+    while (rules.next()) |rule| {
+        const unmasked = @ptrCast(*const Rule, rule.ptr);
+        try insertions.put(unmasked.adj, .{
+            .left = .{ .left = unmasked.adj.left, .right = unmasked.ins },
+            .right = .{ .left = unmasked.ins, .right = unmasked.adj.right },
+        });
+    }
+
+    var result = AutoHashMap(u8, usize).init(&fba.allocator);
+    for (template) |c|
+        try addOrPut(&result, c, 1);
+
+    var step: u8 = 0;
+    while (step < 40) : (step += 1) {
+        var tmp = AutoHashMap(Pair, usize).init(&fba.allocator);
+        var items = count.iterator();
+        while (items.next()) |entry| {
+            const k = insertions.get(entry.key_ptr.*) orelse continue;
+            const v = entry.value_ptr.*;
+            try addOrPut(&tmp, k.left, v);
+            try addOrPut(&tmp, k.right, v);
+            try addOrPut(&result, k.left.right, v);
+        }
+        count.deinit();
+        count = tmp;
+    }
+
+    var values = result.valueIterator();
+    var max = values.next().?.*;
+    var min = max;
+    while (values.next()) |value| {
+        max = math.max(value.*, max);
+        min = math.min(value.*, min);
+    }
+    print("{}\n", .{ max - min });
+}