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
;

const RuleNums = u8;
const Rule = [][]RuleNums;

    const good = try monster.genRule(arena.allocator(), 0);

    var good = std.ArrayList([]Str).init(arena.allocator());
    defer good.deinit();

    var goodMap = std.StringHashMap(void).init(arena.allocator());
    for (good) |gm| {
        try goodMap.put(gm, {});
    }

    try good.append(try monster.genRule(arena.allocator(), 42));
    try good.append(try monster.genRule(arena.allocator(), 31));
    const chunk_size = 8;

    for (monster.messages.items) |m| {
        if (goodMap.contains(m)) count += 1;

    messages: for (monster.messages.items) |message| {
        // The only good version is [42][42][31]
        if (message.len != chunk_size * 3) continue;
        var active_chunk: usize = 0;
        var pos: usize = 0;
        chunks: while (pos < message.len - chunk_size + 1) {
            if (pos == chunk_size * 2) active_chunk = 1;
            var chunk = message[pos .. pos + chunk_size];
            for (good.items[active_chunk]) |gm| {
                if (std.mem.eql(u8, chunk, gm)) {
                    pos += chunk_size;
                    continue :chunks;
                }
            }
            if (pos != message.len) {
                continue :messages;
            }
        }
        count += 1;

// Rule zero is this: 0: 8 11
// We rewrite 8 and 11 to this:
// 8: 42 | 42 8
// 11: 42 31 | 42 11 31
// So the good messages has to start with 1 or more [42] and
// continue with at least one [42][31], but between them 0 or more [42][31] allowed.
//
// Good:
// [42][42][31] (this is the shortest good one)
// [42][42][42][31][31] (embedded one extra [11])
// [42][42][42][42][42][31][31] (embedded one extra [11] and two extra [8] after the first one)
//
// Bad:
// [42][42][31][31] ([42] is missing from [8], or [11] is not symmetric)

    _ = allocator;
    return 0;
}

    var arena = std.heap.ArenaAllocator.init(allocator.?);
    defer arena.deinit();
    var monster = try parseInput(arena.allocator(), @embedFile(PATH));
    defer monster.rules.deinit();
    var good = std.ArrayList([]Str).init(arena.allocator());
    defer good.deinit();
    try good.append(try monster.genRule(arena.allocator(), 42));
    try good.append(try monster.genRule(arena.allocator(), 31));
    const chunk_size = 8;
    var count: usize = 0;
    messages: for (monster.messages.items) |message| {
        // shortest message must be [42][42][31] long
        if (message.len < chunk_size * 3) continue;
        var chunk_counter: [2]usize = .{ 0, 0 };

const RuleNums = u8;
const Rule = [][]RuleNums;

        var active_chunk: usize = 0;
        var pos: usize = 0;
        chunks: while (pos < message.len - chunk_size + 1) {
            // the last chunk has to be a 31, can not be 42
            if (pos == message.len - chunk_size) active_chunk = 1;
            var chunk = message[pos .. pos + chunk_size];
            for (good.items[active_chunk]) |gm| {
                if (std.mem.eql(u8, chunk, gm)) {
                    pos += chunk_size;
                    chunk_counter[active_chunk] += 1;
                    continue :chunks;
                }
            }
            if (active_chunk == 0) {
                active_chunk = 1;
                continue :chunks;
            }
            if (pos != message.len) {
                continue :messages;
            }
        }
        // Number of [42] items has to be more than [31] ones
        // so accidental early [31] matches will not count.
        if (chunk_counter[0] > chunk_counter[1]) count += 1;
    }

    return count;
}

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
;
const test_input_part2 =
    \\42: 9 14 | 10 1
    \\9: 14 27 | 1 26
    \\10: 23 14 | 28 1
    \\1: "a"
    \\11: 42 31
    \\5: 1 14 | 15 1
    \\19: 14 1 | 14 14
    \\12: 24 14 | 19 1
    \\16: 15 1 | 14 14
    \\31: 14 17 | 1 13
    \\6: 14 14 | 1 14
    \\2: 1 24 | 14 4
    \\0: 8 11
    \\13: 14 3 | 1 12
    \\15: 1 | 14
    \\17: 14 2 | 1 7
    \\23: 25 1 | 22 14
    \\28: 16 1
    \\4: 1 1
    \\20: 14 14 | 1 15
    \\3: 5 14 | 16 1
    \\27: 1 6 | 14 18
    \\14: "b"
    \\21: 14 1 | 1 14
    \\25: 1 1 | 1 14
    \\22: 14 14
    \\8: 42
    \\26: 14 22 | 1 20
    \\18: 15 15
    \\7: 14 5 | 1 21
    \\24: 14 1
    \\
    \\abbbbbabbbaaaababbaabbbbabababbbabbbbbbabaaaa
    \\bbabbbbaabaabba
    \\babbbbaabbbbbabbbbbbaabaaabaaa
    \\aaabbbbbbaaaabaababaabababbabaaabbababababaaa
    \\bbbbbbbaaaabbbbaaabbabaaa
    \\bbbababbbbaaaaaaaabbababaaababaabab
    \\ababaaaaaabaaab
    \\ababaaaaabbbaba
    \\baabbaaaabbaaaababbaababb
    \\abbbbabbbbaaaababbbbbbaaaababb
    \\aaaaabbaabaaaaababaa
    \\aaaabbaaaabbaaa
    \\aaaabbaabbaaaaaaabbbabbbaaabbaabaaa
    \\babaaabbbaaabaababbaabababaaab
    \\aabbbbbaabbbaaaaaabbbbbababaaaaabbaaabba
;

    try std.testing.expectEqual(@as(usize, 0), try second(std.testing.allocator));

    try std.testing.expectEqual(@as(usize, 316), try second(std.testing.allocator));