_ = @import("day19.zig");

    const day19 = @import("day19.zig");

const days = 18;

const days = 19;

const std = @import("std");
const PATH = "../input/day19.txt";
const Str = []const u8;
const test_input =
    \\0: 4 1 5
    \\1: 2 3 | 3 2
    \\2: 4 4 | 5 5
    \\3: 4 5 | 5 4
    \\4: "a"
    \\5: "b"
    \\
    \\ababbb
    \\bababa
    \\abbbab
    \\aaabbb
    \\aaaabbb
;
pub fn first(allocator: ?std.mem.Allocator) anyerror!usize {
    var arena = std.heap.ArenaAllocator.init(allocator.?);
    defer arena.deinit();
    var monster = try parseInput(arena.allocator(), @embedFile(PATH));
    defer monster.rules.deinit();
    const good = try monster.genRule(arena.allocator(), 0);
    var goodMap = std.StringHashMap(void).init(arena.allocator());
    for (good) |gm| {
        try goodMap.put(gm, {});
    }
    var count: usize = 0;
    for (monster.messages.items) |m| {
        if (goodMap.contains(m)) count += 1;
    }
    return count;
}
pub fn second(allocator: ?std.mem.Allocator) anyerror!usize {
    _ = allocator;
    return 0;
}
const RuleNums = u8;
const Rule = [][]RuleNums;
const Monster = struct {
    rules: std.AutoHashMap(RuleNums, Rule),
    cache: std.AutoHashMap(RuleNums, []Str),
    messages: std.ArrayList(Str),
    fn genRule(
        self: *@This(),
        allocator: std.mem.Allocator,
        ruleNum: RuleNums,
    ) anyerror![]Str {
        if (self.cache.get(ruleNum)) |ruleset| return ruleset;
        var ret = std.ArrayList(Str).init(allocator);
        const rule = self.rules.get(ruleNum).?;
        for (rule) |pipe| {
            // rule_items holds each rule Str a separate slice item, so it is easier to
            // generate the cumulated rule for the line.
            var rule_items = std.ArrayList([]Str).init(allocator);
            defer rule_items.deinit();
            for (pipe) |item| {
                const tmp = self.cache.get(item) orelse try self.genRule(allocator, item);
                try rule_items.append(tmp);
            }
            // pipe_rule holds the rule string for a pipe, so the cumulated rule is
            // the multiple of pipe_rule values.
            var pipe_rule = std.ArrayList(Str).init(allocator);
            defer pipe_rule.deinit();
            for (rule_items.items) |item_rule| {
                if (pipe_rule.items.len == 0) {
                    // if pieces are empty, fill it up with first strings
                    try pipe_rule.ensureTotalCapacity(item_rule.len);
                    pipe_rule.appendSliceAssumeCapacity(item_rule);
                } else {
                    // expand pieces, so we can append the new parts after them
                    for (pipe_rule.items) |prev_rules| {
                        try pipe_rule.appendNTimes(prev_rules, item_rule.len - 1);
                    }
                    for (pipe_rule.items) |_, idx| {
                        pipe_rule.items[idx] = try std.fmt.allocPrint(
                            allocator,
                            "{s}{s}",
                            .{ pipe_rule.items[idx], item_rule[(idx + idx / item_rule.len) % item_rule.len] },
                        );
                    }
                }
            }
            try ret.appendSlice(pipe_rule.items);
        }
        // add result to cache
        try self.cache.put(ruleNum, ret.items);
        return ret.items;
    }
};
fn parseInput(allocator: std.mem.Allocator, input: Str) !Monster {
    var m = Monster{
        .rules = std.AutoHashMap(RuleNums, Rule).init(allocator),
        .cache = std.AutoHashMap(RuleNums, []Str).init(allocator),
        .messages = std.ArrayList(Str).init(allocator),
    };
    var lines = std.mem.split(u8, input, "\n");
    lines: while (lines.next()) |line| {
        if (line.len == 0) break; // continue with message lines
        var rules = std.ArrayList([]RuleNums).init(allocator);
        var line_rules = std.mem.tokenize(u8, line, ":");
        const rule_no = try std.fmt.parseUnsigned(RuleNums, line_rules.next().?, 10);
        var pipes = std.mem.tokenize(u8, line_rules.next().?, "|");
        var pipe_num: usize = 0;
        while (pipes.next()) |pipe| : (pipe_num += 1) {
            var rule = std.ArrayList(RuleNums).init(allocator);
            var nums = std.mem.tokenize(u8, pipe, " ");
            var nums_count: usize = 0;
            while (nums.next()) |num| : (nums_count += 1) {
                if (std.fmt.parseUnsigned(RuleNums, num, 10)) |number| {
                    try rule.append(number);
                } else |err| switch (err) {
                    // handle "a" and "b" by presetting cache values for them
                    error.InvalidCharacter => {
                        const char = std.mem.trim(u8, num, " \"")[0];
                        const tmp = try allocator.alloc(Str, 1);
                        std.mem.set(Str, tmp, try std.fmt.allocPrint(allocator, "{c}", .{char}));
                        try m.cache.put(rule_no, tmp);
                        continue :lines;
                    },
                    else => return err,
                }
            }
            try rules.append(rule.toOwnedSlice());
        }
        try m.rules.put(rule_no, rules.toOwnedSlice());
    }
    // parse message lines
    while (lines.next()) |line| {
        try m.messages.append(line);
    }
    return m;
}
test "Test input" {
    var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
    defer arena.deinit();
    var monster = try parseInput(arena.allocator(), test_input);
    defer monster.rules.deinit();
    {
        const exp = &[_]Str{"a"};
        const ret = try monster.genRule(arena.allocator(), 4);
        for (ret) |_, idx| {
            try std.testing.expectEqualStrings(exp[idx], ret[idx]);
        }
    }
    {
        const exp = &[_]Str{"b"};
        const ret = try monster.genRule(arena.allocator(), 5);
        for (ret) |_, idx| {
            try std.testing.expectEqualStrings(exp[idx], ret[idx]);
        }
    }
    {
        const exp = &[_]Str{ "aa", "bb" };
        const ret = try monster.genRule(arena.allocator(), 2);
        for (ret) |_, idx| {
            try std.testing.expectEqualStrings(exp[idx], ret[idx]);
        }
    }
    {
        const exp = &[_]Str{ "ab", "ba" };
        const ret = try monster.genRule(arena.allocator(), 3);
        for (ret) |_, idx| {
            try std.testing.expectEqualStrings(exp[idx], ret[idx]);
        }
    }
    {
        const exp = &[_]Str{
            "aaab",
            "bbba",
            "aaba",
            "bbab",
            "abaa",
            "babb",
            "abbb",
            "baaa",
        };
        const ret = try monster.genRule(arena.allocator(), 1);
        for (ret) |_, idx| {
            try std.testing.expectEqualStrings(exp[idx], ret[idx]);
        }
    }
    {
        const exp = &[_]Str{
            "aaaabb",
            "abbbab",
            "aaabab",
            "abbabb",
            "aabaab",
            "ababbb",
            "aabbbb",
            "abaaab",
        };
        const ret = try monster.genRule(arena.allocator(), 0);
        for (ret) |_, idx| {
            try std.testing.expectEqualStrings(exp[idx], ret[idx]);
        }
    }
}
test "Real input" { // 16: "b", 26: "a"
    var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
    defer arena.deinit();
    var monster = try parseInput(arena.allocator(), @embedFile(PATH));
    defer monster.rules.deinit();
    {
        const exp = &[_]Str{ "ba", "aa" };
        const ret = try monster.genRule(arena.allocator(), 39);
        for (ret) |_, idx| {
            try std.testing.expectEqualStrings(exp[idx], ret[idx]);
        }
    }
    {
        const exp = &[_]Str{ "bba", "baa", "aba" };
        // 19: 16 39 | 26 132
        const ret = try monster.genRule(arena.allocator(), 19);
        for (ret) |_, idx| {
            try std.testing.expectEqualStrings(exp[idx], ret[idx]);
        }
    }
    {
        const exp = &[_]Str{ "abb", "baa" };
        // 30: 26 125 | 16 112
        const ret = try monster.genRule(arena.allocator(), 30);
        for (ret) |_, idx| {
            try std.testing.expectEqualStrings(exp[idx], ret[idx]);
        }
    }
    {
        const exp = &[_]Str{ "bbab", "baab", "abab", "abba", "baaa" };
        // 56: 19 16 | 30 26
        const ret = try monster.genRule(arena.allocator(), 56);
        for (ret) |_, idx| {
            try std.testing.expectEqualStrings(exp[idx], ret[idx]);
        }
    }
}
test "day19a" {
    try std.testing.expectEqual(@as(usize, 208), try first(std.testing.allocator));
}
test "day19b" {
    try std.testing.expectEqual(@as(usize, 0), try second(std.testing.allocator));
}