From df42c79b04080a25a22710e898782e912d7b37ab Mon Sep 17 00:00:00 2001 From: Nguyễn Gia Phong Date: Tue, 14 Dec 2021 16:19:10 +0700 Subject: [aoc/2021] Finish day 14 without heap --- aoc/2021/14/part-one.zig | 75 ++++++++++++++++++++++++++++++++++++++++++++++++ aoc/2021/14/part-two.zig | 75 ++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 150 insertions(+) create mode 100644 aoc/2021/14/part-one.zig create mode 100644 aoc/2021/14/part-two.zig 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 }); +} -- cgit 1.4.1