const std = @import("std");
const path = "../data/day14/input.txt";
const RetType = u12;
const Str = []const u8;
const Rules = std.StringHashMap(u8);
const Polymer = struct {
    template: Str,
    rules: Rules,
};
fn parseInput(a: std.mem.Allocator) anyerror!Polymer {
    const input = @embedFile(path);
    var lines = std.mem.split(u8, input, "\n");
    var ret = Polymer{
        .template = undefined,
        .rules = Rules.init(a),
    };
    ret.template = lines.next().?;
    _ = lines.next(); // skip empty line
    // parse rules
    while (lines.next()) |rule_line| {
        if (rule_line.len == 0) break;
        var rule = std.mem.tokenize(u8, rule_line, " -> ");
        try ret.rules.put(rule.next().?, rule.next().?[0]);
    }
    return ret;
}
pub fn first() anyerror!RetType {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    const allocator = gpa.allocator();
    var p = try parseInput(allocator);
    defer p.rules.deinit();
    var pairs = std.StringHashMap(RetType).init(allocator);
    defer pairs.deinit();
    // initialize pairs
    for (p.template) |_, idx| {
        if (idx == p.template.len - 1) break;
        const ps = p.template[idx .. idx + 2];
        var item = try pairs.getOrPut(ps);
        if (item.found_existing) item.value_ptr.* += 1 else item.value_ptr.* = 1;
    }
    // arena for allocPrint()
    var arena = std.heap.ArenaAllocator.init(allocator);
    defer arena.deinit();
    var step: usize = 0;
    while (step < 10) : (step += 1) {
        var next_pairs = std.StringHashMap(RetType).init(allocator);
        var it = pairs.iterator();
        while (it.next()) |item| {
            const next_left = try std.fmt.allocPrint(arena.allocator(), "{c}{c}", .{ item.key_ptr.*[0], p.rules.get(item.key_ptr.*).? });
            var next_item = try next_pairs.getOrPut(next_left);
            if (next_item.found_existing) next_item.value_ptr.* += item.value_ptr.* else next_item.value_ptr.* = item.value_ptr.*;
            const next_right = try std.fmt.allocPrint(arena.allocator(), "{c}{c}", .{ p.rules.get(item.key_ptr.*).?, item.key_ptr.*[1] });
            next_item = try next_pairs.getOrPut(next_right);
            if (next_item.found_existing) next_item.value_ptr.* += item.value_ptr.* else next_item.value_ptr.* = item.value_ptr.*;
        }
        pairs.deinit();
        pairs = next_pairs;
    }
    var chars = std.AutoHashMap(u8, RetType).init(allocator);
    defer chars.deinit();
    // put in the last char as the counter below skips it
    try chars.put(p.template[p.template.len - 1], 1);
    var pit = pairs.iterator();
    while (pit.next()) |pair| {
        const char = pair.key_ptr.*[0];
        const item = try chars.getOrPut(char);
        if (item.found_existing) item.value_ptr.* += pair.value_ptr.* else item.value_ptr.* = pair.value_ptr.*;
    }
    var min = ~@as(RetType, 0);
    var max: RetType = 0;
    var cit = chars.valueIterator();
    while (cit.next()) |c| {
        if (c.* < min) {
            min = c.*;
        }
        if (c.* > max) {
            max = c.*;
        }
    }
    return max - min;
}
pub fn main() anyerror!void {
    var timer = try std.time.Timer.start();
    const ret = try first();
    const t = timer.lap() / 1000;
    try std.testing.expectEqual(@as(RetType, 3411), ret);
    std.debug.print("Day 14a result: {d} \t\ttime: {d}µs\n", .{ ret, t });
}
test "day14a" {
    try std.testing.expectEqual(@as(RetType, 3411), try first());
}

SNPVPFCPPKSBNSPSPSOF
CF -> N
NK -> B
SF -> B
HV -> P
FN -> S
VV -> F
FO -> F
VN -> V
PV -> P
FF -> P
ON -> S
PB -> S
PK -> P
OO -> P
SP -> F
VF -> H
OV -> C
BN -> P
OH -> H
NC -> F
BH -> N
CS -> C
BC -> N
OF -> N
SN -> B
FP -> F
FV -> K
HP -> H
VB -> P
FH -> F
HF -> P
BB -> O
HH -> S
PC -> O
PP -> B
VS -> B
HC -> H
NS -> N
KF -> S
BO -> V
NP -> S
NF -> K
BS -> O
KK -> O
VC -> V
KP -> K
CK -> P
HN -> F
KN -> H
KH -> N
SB -> S
NO -> K
HK -> H
BF -> V
SV -> B
CV -> P
CO -> P
FC -> O
CP -> H
CC -> N
CN -> P
SK -> V
SS -> V
VH -> B
OS -> N
FB -> H
NB -> N
SC -> K
NV -> H
HO -> S
SO -> P
PH -> C
VO -> O
OB -> O
FK -> S
PN -> P
VK -> O
NH -> N
OC -> B
BP -> O
PF -> F
KB -> K
KV -> B
PO -> N
NN -> K
CH -> O
KC -> P
OP -> V
VP -> F
OK -> P
FS -> K
CB -> S
HB -> N
KS -> O
BK -> C
BV -> O
SH -> H
PS -> N
HS -> K
KO -> N