advent-of-code-2021/14/solve.zig

const std = @import("std");
const print = std.debug.print;

const PairMap = struct {
    map: std.AutoHashMap(u16, u64),
    alloc: *std.mem.Allocator,

    fn squash(pair: []const u8) u16 {
        return @intCast(u16, pair[0]) << 8 | pair[1];
    }

    fn init(alloc: *std.mem.Allocator) PairMap {
        return PairMap{
            .map = std.AutoHashMap(u16, u64).init(alloc),
            .alloc = alloc,
        };
    }

    fn deinit(self: *PairMap) void {
        self.map.deinit();
    }

    fn get(self: *PairMap, pair: []const u8) u64 {
        return self.map.get(squash(pair)) orelse 0;
    }

    fn add(self: *PairMap, pair: []const u8, value: u64) void {
        self.map.put(squash(pair), self.get(pair) + value) catch {};
    }

    fn result(self: *PairMap) u64 {
        var counts = std.AutoHashMap(u8, u64).init(self.alloc);
        defer counts.deinit();

        var keys = self.map.iterator();
        while (keys.next()) |entry| {
            var key = entry.key_ptr.*;
            var value = entry.value_ptr.*;

            var left = @intCast(u8, (key & 0xff00) >> 8);
            var right = @intCast(u8, key & 0xff);
            counts.put(left, (counts.get(left) orelse 0) + value) catch {};
            counts.put(right, (counts.get(right) orelse 0) + value) catch {};
        }

        var min: u64 = std.math.maxInt(u64);
        var max: u64 = 0;
        var it = counts.valueIterator();
        while (it.next()) |value| {
            var actual = @divFloor(value.* + 1, 2);
            min = std.math.min(min, actual);
            max = std.math.max(max, actual);
        }

        return max - min;
    }
};

pub fn main() !void {
    var alloc = std.heap.GeneralPurposeAllocator(.{}){};
    defer std.debug.assert(!alloc.deinit());
    var gpa = &alloc.allocator;

    const stdin = std.io.getStdIn().reader();

    var res: u32 = 0;

    var mapping = std.StringHashMap(u8).init(gpa);
    defer mapping.deinit();
    defer {
        var it = mapping.keyIterator();
        while (it.next()) |key| {
            gpa.free(key.*);
        }
    }

    var pairs = PairMap.init(gpa);
    defer pairs.deinit();

    var tmp: [256]u8 = undefined;
    var maybe_polymer = try stdin.readUntilDelimiterOrEof(&tmp, '\n');
    if (maybe_polymer) |polymer| {
        var i: u32 = 0;
        while (i < polymer.len - 1) : (i += 1) {
            var pair = polymer[i..i+2];
            pairs.add(pair, 1);
        }
    }
    try stdin.skipBytes(1, .{});
    while (try stdin.readUntilDelimiterOrEof(&tmp, '\n')) |line| {
        var key = try gpa.alloc(u8, 2);
        std.mem.copy(u8, key, line[0..2]);
        try mapping.put(key, line[6]);
    }

    var step: u32 = 0;
    while (step < 40) : (step += 1) {
        var newPairs = PairMap.init(gpa);
        defer {
            pairs.deinit();
            pairs = newPairs;
        }

        var it = mapping.iterator();
        while (it.next()) |entry| {
            var key = entry.key_ptr.*;
            var insert = entry.value_ptr.*;
            var current = pairs.get(key);

            tmp[0] = key[0];
            tmp[1] = insert;
            tmp[2] = key[1];

            var left = tmp[0..2];
            var right = tmp[1..3];

            newPairs.add(left, current);
            newPairs.add(right, current);
        }

        if (step == 10) print("{}\n", .{pairs.result()});
    }

    print("{}\n", .{pairs.result()});
}