From fea372792d047c76ecefb4ee7c32d3398ef0bdea Mon Sep 17 00:00:00 2001 From: Brendan Hansen Date: Sat, 19 Dec 2020 14:11:55 -0600 Subject: [PATCH] added day 19 --- day19.onyx | 175 +++++++++++++++ input/day19.txt | 585 ++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 760 insertions(+) create mode 100644 day19.onyx create mode 100644 input/day19.txt diff --git a/day19.onyx b/day19.onyx new file mode 100644 index 0000000..321842a --- /dev/null +++ b/day19.onyx @@ -0,0 +1,175 @@ +#include_file "core/std/wasi" + +use package core +use package core.string.reader as reader + +// nt -> t +Unit :: struct { + nt : u32; + + t : u8; // character +} + +// nt0 -> nt1 +Solo :: struct { + nt0 : u32; + + nt1 : u32; +} + +// nt0 -> nt1 nt2 +Prod :: struct { + nt0 : u32; + + nt1 : u32; + nt2 : u32; +} + +Grammar :: struct { + unitary_rules : [..] Unit; + solo_rules : [..] Solo; + production_rules : [..] Prod; + + max_terminal : u32; +} + +grammar_init :: proc (use g: ^Grammar) { + array.init(^unitary_rules); + array.init(^solo_rules); + array.init(^production_rules); + + max_terminal = 0; +} + +grammar_prepare :: proc (use g: ^Grammar) { + // Not full-proof, but good enough for AOC. + for ^solo: solo_rules { + for ^prod: production_rules { + if prod.nt0 == solo.nt1 { + array.push(^production_rules, Prod.{ solo.nt0, prod.nt1, prod.nt2 }); + } + } + + for ^unit: unitary_rules { + if unit.nt == solo.nt1 { + array.push(^unitary_rules, Unit.{ solo.nt0, unit.t }); + } + } + } + + array.sort(^unitary_rules, proc (a: Unit, b: Unit) -> i32 { + return (cast(i32) a.nt) - (cast(i32) b.nt); + }); + + array.sort(^production_rules, proc (a: Prod, b: Prod) -> i32 { + return (cast(i32) a.nt0) - (cast(i32) b.nt0); + }); + + max_terminal = math.max( + production_rules[production_rules.count - 1].nt0, + unitary_rules[unitary_rules.count - 1].nt) + 1; +} + +cyk_algorithm :: proc (use grammar: ^Grammar, input: str) -> bool #export "CYK" { + dim_0 := input.count * max_terminal; + dim_1 := max_terminal; + dim_2 := 1; + + mem_size := sizeof bool * input.count * input.count * max_terminal; + T := cast(^bool) calloc(mem_size); + defer cfree(T); + memory.set(T, mem_size, ~~false); + + for s: 0 .. input.count { + for ^unit: unitary_rules { + if unit.t == input[s] { + T[0 * dim_0 + s * dim_1 + unit.nt * dim_2] = true; + } + } + } + + for l: 1 .. input.count { + for s: 0 .. input.count - l { + for p: 1 .. l + 1 { + for ^prod: production_rules { + if T[(p - 1) * dim_0 + s * dim_1 + prod.nt1 * dim_2] + && T[(l - p) * dim_0 + (s + p) * dim_1 + prod.nt2 * dim_2] { + T[l * dim_0 + s * dim_1 + prod.nt0 * dim_2] = true; + } + } + } + } + } + + return T[(input.count - 1) * dim_0]; +} + +main :: proc (args: [] cstr) { + contents := file.get_contents("input/day19.txt"); + defer string.free(contents); + + file := reader.make(contents); + + grammar : Grammar; + grammar_init(^grammar); + + while *file.data != #char "\n" { + nt0 := reader.read_u32(^file); + + reader.skip_bytes(^file, 2); // ': ' + + if *file.data == #char "\"" { + reader.skip_bytes(^file, 1); // '"' + t := reader.read_byte(^file); + + array.push(^grammar.unitary_rules, Unit.{ ~~nt0, t }); + + } else { + while true { + nt1 := reader.read_u32(^file); + + if *file.data == #char "\n" { + array.push(^grammar.solo_rules, Solo.{ ~~nt0, ~~nt1 }); + break; + + } else { + reader.skip_bytes(^file, 1); // ' ' + + if next_ch := *file.data; next_ch >= #char "0" && next_ch <= #char "9" { + nt2 := reader.read_u32(^file); + array.push(^grammar.production_rules, Prod.{ ~~nt0, ~~nt1, ~~nt2 }); + + if *file.data == #char " " do reader.skip_bytes(^file, 1); + } else { + array.push(^grammar.solo_rules, Solo.{ ~~nt0, ~~nt1 }); + } + + if *file.data == #char "|" { + reader.skip_bytes(^file, 1); // ' |' + } else { + break; + } + } + } + } + + reader.advance_line(^file); + } + + grammar_prepare(^grammar); + + for ^p: grammar.production_rules do printf("%i -> %i %i\n", p.nt0, p.nt1, p.nt2); + for ^p: grammar.unitary_rules do printf("%i -> %c\n", p.nt, p.t); + + valid_count := 0; + + reader.advance_line(^file); + while !reader.empty(^file) { + line := reader.read_line(^file); + + is_valid := cyk_algorithm(^grammar, line); + if is_valid do valid_count += 1; + } + + printf("Valid count: %i\n", valid_count); +} diff --git a/input/day19.txt b/input/day19.txt new file mode 100644 index 0000000..4bba7fa --- /dev/null +++ b/input/day19.txt @@ -0,0 +1,585 @@ +50: 15 65 | 60 74 +102: 33 65 | 68 74 +69: 65 74 | 74 65 +110: 45 74 | 102 65 +71: 65 23 | 74 68 +67: 74 55 | 65 23 +55: 95 95 +10: 104 74 | 30 65 +100: 65 77 | 74 109 +4: 82 74 | 43 65 +120: 115 65 | 32 74 +124: 74 13 | 65 22 +105: 74 81 | 65 57 +46: 94 65 | 73 74 +24: 18 65 | 73 74 +28: 53 65 | 94 74 +41: 65 107 | 74 67 +66: 65 23 | 74 23 +0: 8 11 +57: 102 65 | 22 74 +15: 74 112 | 65 71 +47: 84 65 | 105 74 +1: 74 50 | 65 121 +88: 65 73 | 74 55 +81: 74 91 | 65 7 +82: 74 69 | 65 55 +42: 74 123 | 65 79 +89: 128 74 | 40 65 +18: 65 74 | 95 65 +51: 56 65 | 86 74 +65: "b" +94: 65 74 +2: 65 94 | 74 55 +5: 68 65 | 33 74 +93: 65 20 | 74 78 +77: 18 74 | 68 65 +16: 65 12 | 74 55 +79: 47 65 | 3 74 +9: 65 100 | 74 49 +78: 53 74 | 23 65 +21: 74 12 | 65 23 +6: 65 68 | 74 33 +70: 112 74 | 77 65 +115: 73 65 | 53 74 +86: 20 74 | 67 65 +60: 62 74 | 34 65 +44: 103 65 | 120 74 +76: 65 68 | 74 18 +14: 117 74 | 98 65 +119: 69 65 | 73 74 +83: 17 74 | 73 65 +52: 125 74 | 48 65 +8: 42 | 42 8 +73: 74 74 | 65 95 +117: 74 110 | 65 54 +49: 37 65 | 115 74 +92: 75 74 | 4 65 +87: 65 94 | 74 53 +64: 74 73 | 65 69 +118: 65 14 | 74 126 +91: 19 65 | 23 74 +75: 65 102 | 74 85 +108: 65 76 | 74 115 +122: 74 88 | 65 66 +33: 65 74 | 65 65 +45: 23 65 | 94 74 +3: 26 74 | 90 65 +97: 73 74 | 12 65 +31: 74 118 | 65 29 +127: 74 28 | 65 106 +104: 59 74 | 94 65 +37: 23 65 | 111 74 +53: 74 74 | 65 74 +106: 65 94 | 74 33 +62: 65 59 +38: 16 74 | 64 65 +61: 122 74 | 116 65 +99: 115 74 | 24 65 +11: 42 31 | 42 129 +129: 11 31 +112: 95 12 +72: 65 107 | 74 5 +22: 53 74 | 68 65 +84: 65 108 | 74 70 +59: 74 65 | 65 65 +12: 65 65 | 74 95 +20: 74 18 | 65 69 +74: "a" +7: 95 55 +98: 99 65 | 38 74 +58: 27 74 | 51 65 +121: 65 36 | 74 72 +128: 41 65 | 101 74 +103: 71 65 +26: 74 39 | 65 10 +43: 65 17 | 74 59 +63: 74 92 | 65 44 +32: 33 65 | 94 74 +111: 74 65 | 74 74 +56: 65 46 | 74 106 +27: 113 74 | 124 65 +34: 33 65 | 18 74 +126: 65 9 | 74 61 +113: 74 25 | 65 83 +19: 74 65 +125: 68 74 +80: 74 18 | 65 53 +85: 65 12 | 74 69 +13: 65 18 | 74 33 +107: 65 12 | 74 59 +96: 55 74 | 53 65 +54: 6 74 | 87 65 +23: 74 74 +95: 65 | 74 +29: 74 63 | 65 58 +109: 68 65 | 94 74 +116: 5 65 | 107 74 +39: 74 119 | 65 2 +40: 52 74 | 114 65 +30: 74 59 | 65 19 +25: 53 65 | 12 74 +123: 65 89 | 74 1 +90: 65 93 | 74 127 +35: 19 74 | 23 65 +101: 97 74 | 80 65 +114: 35 65 | 106 74 +36: 21 74 | 96 65 +68: 65 65 +48: 94 74 | 17 65 +17: 65 65 | 74 74 + +bbaaabbbabaaaababaababbaaabbababbaabaababbbbaabb +baaaababaaaaabaaabbababbbbabbababbbbaabaaaaabaaa +abbbabbabaabaaaabababbabaabbbbaaabbabaab +bbbaabaaabaabbbbbbaabaaabbbabaabaaabbbab +abbbabbabbbabbbaaaaaabab +bbbbbbbbababbaaaaaabbbbabbababaa +abbbabaabaaaaabbaaaababbabbabbbb +babaabbbaabbabbaabababbbbaababaabaaabaabbbabbbba +babaabbaabbabbaabbbabbabbaabbbbbbababaabaaaabbbbbaaaabaaaabaaaaa +bbaaaabbbabbababaaaaaaababbabababbbaabbaabaabbaabbaaaabbbababaaa +abbaaaaaaababbaaaababbabababbabaabaabaab +aaaaaaabaaababbbabaababb +bbbabbbaaababbbbaabaabbababbbbababbbabbaaaaabaaabbababaaabbbbabaaaaabaaa +baababbbaababbaabbaabbbb +baaaabbaaaabbababaaaabaaabbbaabbabaaaaaaabbbbbabaaaabbbb +abbbabaabbbbbbabbbbabbaaaaabbbab +abaaabbaabaabbabbabbbbaa +babaaaaaaaabbbbabbaabbabbabbaaba +abbaabaabaaabbaaabaaabaa +aaabbbbababbbbabbaabbbba +abbaababbabbaaabbaaaaaabbbbabbbbabbabbaa +bababbbaabaaabbabbbaabab +aaabbbaabababaabbaabbaaabbbaabbaabbbabab +babbbbabaabbbaabababaabaabbbabab +bbbbbbabaaaaaabbbabbbaabaaaababaabbbabaabaaabbbbbaaabbbaaaaabbab +babaaaaabbbababbababaabbaaabaaaaaabbbbaa +aaababbbbababababaaabaab +aaabbbaaabaababaaababbbbababbaaaaaaaabbb +abaabababababaabaaabbbbabbbbaabaaaabaaab +abaabbbabaaaaabbaaaababababaaaabaaaaabaaabaaababbbaabaab +bbbbbaabaabbbaababababba +bbaaaabbabaabbbaabbbaaaaaabbbabaabbaaaabaabaaaaa +abbabbbaabaaaababbababab +baaaaaaaaabbbbaaabaaaabbbbaaabaaaaaabbbbaaaabaabababbbbbbabbbabbabbbbbba +aababaabbbabaaaaaababbbbabbbbaab +aaababbbbabaabbbababbbbb +bbaaabbbaabababbbbabbaaa +aabbabbabbbabbbbaaabbbbb +bbaabbaabbbbbbabaabaaaba +bababababbbaaaabbbabbbbbbbabbabb +abaababaabaabbbbbaaabaaa +bbbbbbbbbababbaaababbaaaaaababbbaabbbbbbbbababbaaaaaaaaa +abbaababbaababbabaabbbaa +ababaaabaaabbaabaabaababaaaaaaaa +babaabbbbaabaaaaababaabaabbbbbbb +baaababbabaaaaaaabbbabab +aabbaabbbaababbbbababbbaabbbbbaabbbbbabb +baaababbabbbbbabbbbbbbba +babababbabbbbaaabaaaabaa +bbbbbababbbbabbaababaababbbaabbaaabbbbaa +abaabababaabbaaabbaababb +bbabaabbaaabbbaaaabaaaba +aababbbbbabaabaabaaabbabbbbabaabbababbbb +babaabaaabbbaaaaabaaaabaaabbabaa +abbaabbaababaabbbbbaaaaa +baababbaaaababaaaabbbbaa +abababaabbbbbbbbababbbba +abbaabaababaabbbabaabbbabbbaababbaaabbbb +bbaaaabbbbbaaaabaaaaaaababbbbbbababaabbbbaababbbabbabaab +aabbabababbbbaaabaaabbaabaaabbaa +bbbabaaabaaabbabbababbabaaaaaabbaaaabbbaabbabbab +bbbabaaabbaaabbabbbaaabb +aabbbabbaababaababaababb +abbabbbaaababaabaaababbababbbbba +abbaabbbbaaaaabbbbbaababbbbabbbabbabbbaabaaaabaaaaabbbabbbbbbabbbababbab +bbababbbbbaaabbaabbbabbb +aaabaabaaababbabbbbbaaab +aabbabaabbabbaababaaababbbababaa +aaaaaaabbaababbbaababbbbbabbaababbaabaaa +aabbaaabaaaaaabbbbaaaabaababaaab +aabbaabababaabababbbbaab +abaaabbbaabbabbabaabbaabbaabbabaababbbaaabbbbaab +babbbaabaabbbabbabbaaaab +baabbaaabaabaababbaaaabaaababaaabbbbabaabaaabbbaaabbbbba +aaaaaaaabbabaaabbabbaaabaaaaabbbbaaaabbaabaaabbb +abbaabaabbbbaaaaaabaabbbaabbaaabbabababbbaaaabab +bbbbaaaabaabbbbabaababaabbbabbbabaaaabaaaababbbaaaaabbab +baabbaaaabaabaaaaaabbaaaabbbbbaabbaababaaabbbbbaababababbbbaaaba +bbbbabbabbaaabbbaabbaabaaabbabaa +aaaaaaabbbbbbababbababab +bababaaaabbbbbbaabbbabbabababaaaababbabaabbabaaa +bbabaaaabbbbbaabbbabaaab +ababbbaababbbabaabbbbaba +aaaabbbbbababbbabaababab +abbbaababaabaababbbaabaa +bababbaabaaaaaaaaaaaaabbaabaaaba +aabbaabaaaabbbbaaaababbbbababbbbaaaabbbabbbaaaaabaaaaababbabbbababbaaaab +aaaaaabbaabbabbababababbbaaaaabbababbabababbabba +aabbababbbaaabbaaaaabbaa +aabbaaaaaaaaaabbaabaaaaa +aababbaababbbbbbabbabbbababaabbabbaabbba +bbabaabbaaababaabbbabaaaaaaabbaaaaaaabaa +babaabbbaaaabaabbbababaa +bbabbbaabbbbabbaabbbabbabbaaabab +bbbbbbababababaaabababaabbbbabbabbaabbaabaaababaabbbbaababbbbababaaabbbb +aaabbbbaaaababbbbbababba +aaabbaabbabbabababaababaaaabaaaa +aaabbbaaababbabbaabbababbaabbabaaababaaa +ababaababaaabbabaabbaaaaababaabbaababaabbbbbabbaabbaaaba +ababaabababbbbabbbaaabab +aabbabaabbabaaabbaabaaaaabababbabbbaaabbaaababaaabbaabbaabbabaabbabaabaa +abbabaaaabbbaababaabaaabaaaabaabbbaabaaaababbaabbbabbbaabbbbaaaabbbababaababaaab +abbbaaababbbbaaaabbbbbbb +abbabbaaabbaaabbbbbbbbba +aaaababaaaabbaabbbbbababbbbbabbaabababba +aaabaabaabaaabbaabaaaaab +ababbbaabaaababbabbaabbaaabbabbb +bbbabaaaabaabaaabaabbbab +abaabbaabaaaaaabbababbababaababaaaaaabab +aababbabbaaaaaaaabaabaab +aababbbbbabbabbbabaababaaaaababbbbaaaabbbbabbaab +abbaabaaaaaaaaabaabbbabbaabbaabbaababaabbbaaaababbbabaab +bbaaaabbbbbabbbababaabbbbaababaaabbaaaba +baaabbabbabaababbaabaaba +abbaababababbabbbabbbbbbaabaaabbaaaaaaba +bbbbbbbbaaabbbaabaaababa +aaaaaaaabbbbbbaababbbbabaababbbbbbaaabbbbabbaabbbbabaaababaabaaa +aabbaabbbbbaabbbbabaabaaabaabaaabbabbbbabaababab +baabaaaaababbaaaaaaababbabaaabbb +aaaababbabaabbbbbabbbaba +bbbbbabaabbbabaaabaaabab +abababbbabbbabaaabbabaab +aaaaaaabaaabbababbbaabbbabbbbbbaababbbbb +bbabbbbabbaaaaaabbaabbabababaaabbbbaaaabbbaabbaabbabbaaa +aaaaabbbbbaaabbaaaabbbaaababaabbbaaaabaa +aababaabaabaabbaabbabbaa +aabbbababaaababbabbaaabaaaaaabababbbaabbaaabaaaaabaaabaabbaabbaabaababab +baaaaaaabbbabaaaaaabaaaa +baabababbbbbaababaababababbabaab +bbbbbababaaabbaaaabaabab +bbbabbaaabaabaaaabbaaaba +abaabbbabaaaaaaabaabbbbb +aabbbbabbaabaababaabbabbbbabaaaaaabbbbba +bbbaaaabaabbaabbabaabbbaaabbaabbaabbbbbb +babababbbaaababbbbbaaaabaabbbaba +aabbbaabbabababbbbababbbabbaaaba +aaaaabbbaabbaabababbbabbbaaaabbb +abbbbaaaabbbabbabbaababbbbbbaaaaaaabbaaa +abaabbbaaabbbaaaaabbababbaaaaaabbbbaaababbbabaabaaaabbaa +aabbbaaabababbabbabbababbaaababbabbaaaba +aabbabbabbaaabbbabbbaabbaabbaabaaaababbabbbabaabbbaabbbb +abbbaabbbabbbabaababbaab +babaaabbbbbabababbababbbbaabaaababbaabbabbaaabaaaaaabaab +babaabbbbbbbaaaabaaabaab +baaabbabbbabbbaaaaabbbbaaaabbbbabaaaabbbbabbaaaa +bababbbabababbbabababaabaabbabbaabaaabbb +aabbbaaaaaaabbbbbbabaaab +aababaabaabbbaaaabbbbabb +bbbaabbbbabaaabbbabababaababbaab +bbbabbaaabaabbbaaaaaaaba +bbbabbaabbbabaaabaababbabaaabaabbbbbaaba +aaababaaaaabbabaabbabbabbabbabbbbbbaaaabbaababbaabbabbaaabaaabaaababaaabbbbbabab +baabaababaaaabbbaaaabaabbabbababbabbaaabbbbbbabbbbaabbbb +babbbaabbaaaaabbaaabbababaabbbbaabbaaaba +bababbbaabaaaabaaaabbbbb +aaaabaabbaaababbbaababab +bbaaaababaaaaabbaababbabbaaabaaa +aabbbbabaabbaaabaabaaaba +aabaabbabbbbbaabbaaabbabbabaabababbbaaabbaaabbbb +bababbaabbbbbaabaaabaaaa +baababbbabbbabaaaabbaaaabababaabbbbaaaba +abbaabaaabbbbbbabaaabbaaaabbabababaabaabbbaababb +babaaaabbabbbaabbaabaabb +abbbaabbaaabbbaaababbaab +abbababababbaabbabbabbabbaabbabaaaaabaaa +aabaabbbbabbbbbbbbbbbaabababbbbbabbababb +bbbaaaabaabbbbabaabaaaaa +ababaabbbbbabbbbbabbabbbbbaabaaa +abaabbbaabaabbbbbbbbaabb +aabbabbaaaababaabaaabbaababaaaaabaaababa +abaaaaabaaabbbbbabbaabaabbbaaababaaaaaaaabaabbbbbbbbabbbabbabbba +bbaaaaababaabaaaaabbaabbbabbabaaabaabaab +abaaaaaabbabaabaaabbbbbabbbbbbaa +aaabbabaabbaaaaaabbbabbaaabbbbaa +aabbabbabbaaaababbbabaaabbaaaabbabbaabaababbbbbabbabbbba +baababbbabbbbbbaababbabaaabaabbabbbaabbbbabbaabbbbbbbbabaabbabab +abbaaaaaababbbaaabababba +bbaaaaabaabaabaaabbabaab +baaabbaaaabaabbaababbaaaaabbbaabababaabaabbbbbbabbaababbaaabababababaaababababababbabaab +bababbabbabababaaaabaaabbabaaabbbbbaaababababaaaabbbbabb +baababaaaababbbbbaababab +babaaaaabababaaabbbbbbaa +baaaaaaababbbbabaaaaabba +babaabbbbbbaabbaaabbaabababaaaaabaaaabbabababbbabaabbbaa +abaabaaaaabbaaaabaaabbbb +abaaaaaaaaaabaabbabbabba +ababaabababbabbbabbabbab +babbaabaaaabbaaababbbabbbbbbbabbbababbaaaaaabbab +aabbbbabbabbabbbbabaaaabbbabaaaaaaabbbaabbababaaabbbbabbaaaaaaba +aaaaaabbbabbbabbaabbabbbbaaaaaba +aaaabababaaabbaabbaaabbaaaabbabbbbbbaaba +abbaabaaaababbabbaabaabb +bbbbaaaabaababbbbabbaabb +aaaabaabbbabaaaaabaabbabaaaabaaaaaabbbab +aaaaaaabbbbbaaaabaaaaabbaababaabaababbaababbbabaaaaabbba +aaababbbabbbaabaababaabbaabbaabbaabbbbbabbabbaaaaaabbbab +babaababbbbbbbbbabbbbaab +bababaabaabbababaabbababaabaabbabbbbbaabaabbabbaabbaaabaaaabbbab +baababbababbaaabbbbbbbba +aaaabababbbbababbaaaabab +abaabbabbabbaaabbaabaaaaaaaaaabbbababaabaabbbbbbbbbbbbaaaaaaabaa +bbabaaaababaabababababba +babaabbbabaaabbabaaaaaabaaaaaabbaabbabbabbabbababbabbaaa +babababbbaabbabbabbbbaaabbbbbbaaaaabbbbb +abbbabbaaabababbaabaaabb +abaabbbbaababaabbaabbabbbaaababbabababab +aababbabbabbaaabbaaaaaba +bbbbbbabbbbbababbaaaaaabbaabababbbbaababaaabbbbbabbbbabb +bbaaaabbabbaaaaabbaaabab +aababbabaabaabbaabaabbaabaaababbbbaaaaaabaabbbaa +bbaabbaaaabbaaaaabaabbbbabbaabbabaaabbbb +babbbaaabbbabbaaaaaaaaba +aababaaabaabaabaaaaabaaa +baabaaaaaaaaaaababbbbabbaabbbaabbaaaaaabbaaabbabbbbabbaabbaaabbabbaabaaa +bbabaabaabbbaaaaabbaaaba +bbbaabbbbaabaaaaabaaabaa +aabbbbabbbbbbabaabbbaabaaaaaababababbbab +babbbabaaaaaaaabaaababab +aaaabaabbaaaabbababbabbabababaabbaababaaabbabbaabbaababb +bbaaaaabbbabaababbaaabbaabaaaabaaaaababbaaabbbaaabbabaaabbaaabaaabaaabbbbabaaababaabaabb +babababaabbabbbabbbbbaabbbaabababaabbabaaababbbaaaaabbbabaaaabbb +baaaaaabbbbaabbaababbaba +abbabaaababbaaababbbaabaaaaabbaabaaaaaaaabbbbaab +aabaabbabbaaabbaabbaaaba +aaaabaabbbaaabbaaabbaaaaaabbaaabbaababaaabaaabaabbaabababbbbaaab +abaabaaaababaabaabbbbaab +baaabbabbababaaaaabbabaa +abbbaabababababaabbabaab +aaaababaabaabbaaaabaabab +bbaaaababaabbaaabbaaabbaabaababb +aaaaaaaababbaaababaabbbbbabababbbaabbbabbbbaababbbbbaaaa +abaaaaaaaaaaaaabaababbaababababaaaabbaaa +bbabbbbbababaabbbabbabbb +bbababbbbaaaaaaaabbaabaa +abababaaabaabbbbabbaababaaaabbbb +aababbaabbababbbbbbabbbbaababbbbbbbababbbbaabaababbbabbb +baabaababbbabaaabbbbaaaabaaaaababbaababa +aaaaabbbbabaaabbabbabbaa +bbbaabbababaabaaababbaab +babbbaababbbbaaabaaaabab +abbaabaababaaabbbaaababbabbabaaa +aaabaabaabbababbabbbbbbbbabbbbab +aabbbabbaabbaaabbbabababaaaabbba +babaaaaabbaaabbaabbbbbbababbaaba +abbbaabbbaababbbbbabbbba +aabbababbabbbabaabbabbbb +aaaaabbbabababaabaabaaab +bbbabbaaaabbaababbabbaab +ababbaaabaaababbababbbab +bbbabbbbbababaababbbabbb +abaaaaaabaaabbabbbabbbba +aaabababbbaabababaaaababaababbabbabbaababbbbabbbaabbbbabbaabaaaa +babbbbbabababbbbaababbabbbaabbaaabaaabbbbabaabbabbbabbbbbbbaababbbbabbaaabaaabbbabbbaabbabbabbab +babaabaaabbbaabaabababaaabaaaabbababbbbb +babaaaaabbbabbbbbbbbbabababaabaababbaabbaabaaaba +baababaaabababaabbaaaabbbaabaaab +abaaabbababaabaabbbbababbababbabababbbab +abababbbabbbaabbbbbbaaaaaabbbababbabbabb +aaaabbbbaabbbaabbaaababbaababbabbbbbaaab +babaababbbbbbbabaaaabbbbbbbaaaabbbababab +aaaabbbbabaaaaaabbaaabab +bbbaabbaaaaababbbabbbabb +bbabbbaababbbaaabbbbaabb +bbabaabbbababbbabababbbabababbbabbbaabbabbabbaaabbbbbabb +bababbabbbbabababbbbaaaaabaabbaababbaaaa +aaababbaababaabbbabaaaaababbabaa +aaabbababaabbabbbbbabaab +bbbabbbaaaaaaabbaaabbaabbaabaabaabaaaabb +bbbababbabbbbbabbabbbbbbbababbaaaaaabbba +babaabaabbbaabbbabbaabababbbbaab +abaaaababbbbbbbbbbbaaaba +bbabaaaabaabbbaabaaaababbabaaaba +abaabbabbbaabbaaabbaaabb +baababbabaababaaabbaaabb +bbbbbaabbabbabbbbababaaaaaaabbabbaabbbab +aabbbbbbaaaabbbaaabaaaaaabaaaabb +abbaabbabaaaaaababbaabaababaaaabbaabaaaababaaabaaaaabbaaaabaaabb +ababbaaaaabbaaabbbabaaab +bbaaabbabbabaaaaababbbaaabbbaababbbabbaaaaaabbaaaaabbabbbaaabaab +bbaaaabbbabbbabbaabbbbbb +ababbabbaabababbaaabbbbabbbbabbaababbbab +abbbbbbaaabaabbbaababaabbaabbabbaaaaaaaaaaaabbbaabbaaaab +aaaaaabbbaabbaaaabbbaaaabaabbbab +babaabababababbbabaabbaaabaabbbbbaaaaaaababbabaa +babaaaaababaabbbababbbaaabaabaaababaaabbabaaabbbbbbaaabbbaabbbab +bbbaaaabbbbbababbababbaababbbbbb +aabbbaaababbaaababaabbbbababbbabbbababab +abbbbbbabbbabbbbbaaababa +baabbaaaaaaababbbabbabba +aabaabbabababaabbbaabbab +bbbbabbaabaabbbbbbaabaaa +bbababaabbabbabaaaaaabaaaabaaabbbbaaaabaaabbabab +aaaaabaaaabaabbbabbbbaaaabaaababaaabbbabbaaabaaababbbabbbbaababbbbbbbaabbaabbbabaababaaa +babababbabaaababaaaaaaaaaaababaabbbaabbbbbbaaaaaaaabbabaababababaaabbbabbbbaaaaa +bbbabbaabababbbabaaabbabbaabaabb +babbbabbbabbbbabbbaabaab +aaababbbabbbaaaabaabbaababaaabaa +bbbbababaabbaaaabbbbbaababbbaababbaabbab +abaabbbbbabbbababbaababb +baababbbababaababbbaabaa +abbbbbabababbbaaaabababa +bbbabbaaaababbabbabaaaaaaaaabaaabbabbaba +aaabbbaaabaabababbbabbbaaaabbbbabaababaabbaababb +aaaabaababbbababbabbabaa +babaaaababbaababbaaaabab +abababbbabaaabbabbaabbba +aabaabbababababaabaabbabbababbabbbbbaaab +aaabbababbbbbaabbbbabbbabbaabbbaaabaaabb +babbbbbbaaaabaabbbaaaabaaabbbbabbabaabbbbabbabbbaaabbabb +babbabbbabababbbbaabbbbb +bbaabbaabbbbababbbbbbbba +baabaabaaaababbbbbbbaaaaaaaaaaabbbababba +aabbaabaaaabaabaabaaaaaababbbaaabaaaaabbabbbbaba +baaaabbaababbaababbababa +babaaabbabbaabbaaaaabaabbbaabbaaabbaabaabababbbbbabbaabb +bbaaaabbaaabbaabbaabaabbababaaaaabbababbababbbbabaaabbba +abaabababbbaabbabbbbaaba +bbbbabababbaababbbabbbab +bbbbababaabbbabbaabbbabbbbbaaaabbababbbbaaaaaabaabbababb +aabbbbabbbbabbbbbabaaabbbabaaaabababbbab +babaaabbbbbbbbababbabbbb +baaaaaaabbbababaaabbbabbbbaabbabaaabbabb +aabbabbabbbbbbbbbaaabbabbaabaaabbbbabaab +bababbabbaababbabaaaaaabbaaaabbaaaabaabaaaaaaaababbabaaabbaaaaaaaabbbabbbbbabbbaaabbbbaa +aababbaabaaaaabbbbbbbbba +bbabbbaaabaabababbabbbbbaabaabaabaabbabbaaaabaababbababbbaaaabbb +bbbbbabaabaabbbbabababab +baaaaaaabbbbbaabaabbaaaaaaaabbbbaabaabaabbbbaaba +aabaabaaabaabababbbbbaaa +bbbbbababaabbaaaabbabaaa +abaababaababbbaababbaaba +babbbaaabbaaaabbababbaaaaabababbaaabaababbabababbaaabaaa +bbbbbbabbbaaaababaaaaabbababaabbbbababbbaabaaaba +bbabaaaaabaabbababababbbbabbaaabaaaabaaabaabbbaabbabaaab +abaabaaaabbbaaabbabbabbbaabaabaaabaabaab +aababbabaabaabaaabababba +aaaaaabbbababababbaabbaabbaabaaaaaababab +bababaabbabbbbaaaaaaabbaaababaaaabaababb +babbabbbbaaabbabbbbabbabaaaaaaba +bbaaaabababbbabbbabaaaba +abababaababaaaabaababbabaaabaabb +abaaaababaaaabbaaabbabbb +bbaaaaabaabaabbbbababaaababbbaabbabaaaabbbbabbbaabbbabab +baaaabbabbbabbaabbabbabb +bbbabaaaabababaaaaaaaaabaaabbbaabbaaabbbababbaaababbaabaabbbbbbb +abbaaaaaaabbbaababbabbbb +aababaabbabaababbbbabbbabbbababaabbbabaabaaabbbaabbbbaab +bbaaabbaaaabaabaaabbababaaaaaaba +aaaabbbbaabbaabbbabababbbbaababbabbbabab +babaaaaabababaabbbababab +aabbaaaaaaaaaabbbbaabaaa +abbbbbbabbaaaaabbaaaaabbaabababaaabbbbaa +bbbababbabbaababbbaabbab +babaababbbaaabbabbabbbaaabbbaabaaaaaaaaaaabaaaaa +abababbbbabbbaababbaababbaaaaaba +abbbabbabaababbaabaaaabb +aababbaaaaabbabaaababbabaaabbaaaabbabbaa +bbbabaaaaabaabbababbbbbbbbbabaab +abbbbbabbbbbbbababbbbbabbaabaaab +bbbaabbbaaaabaababbbaaaaababaaba +baaaaaaabbbbababbaaaabbabaabbabbbaabbbaabbaabbab +bbbbbaabaabbbabbbaababab +aababbabaaaabbbbbbbbabababaabbbaaaababbaabbaabbb +babaaabbbabbbabaabbbaaaaaaaabbab +abbbaabaabbaababbbbababbbbbbbaaa +aaaaaabbaaabaababbbababaaaababbbabbbbbbaaaabbbab +bbabbbabaababbaabababbbaabbaababbbabaabababaabab +babaabbbbbaaabbbbbaababa +aaababaabbbaaaabbaaabbba +abbaaaaaababbaaabbaabaaa +abbbbbbaaaababbbaaaabbbbabaababb +bbbbbababababbabbbababbbabaabbaa +bbaaabbbabbbaaabaaaabbaa +bbabaabbbaaabbabbbbabbabbbbabaaabaabaaaaabaababbbbabbbab +aabbaababaaabbabbabbbaabababbabbbaababaaabababbbabaaabbbabbabbaa +bababaababbbabbaaaababab +abaabbabbbabbbabbaaababa +abbbaabaabbbaabbaabbbaba +aababbbabaabaaabbbbabbbbbbbaaabbabaabaaaaaaabaababaaaabaabababbbabaaaaba +abaabbbabbbbabbaaabbbbba +abbbbaaaabbbbbababbbaabaabbbaabbabbabbaa +aababaabbabbbabbbaababab +bababbaaabaabbbaabaabbbabaabbaba +bbbabbaabaababaabaaaabababababaabbaaabbaaaaababbbbababab +baaaabbaaaaabababbaaabaa +abbaaaaaaababbaababbababbbabbbabaabaaaba +aabbbbabbabbbababaabaabaaababbba +baababaababaaaaaabbaaaba +babaaaabaabaabbababaabaabbbaaaaa +babbbbbbbbbabababbbaaaabaabaabbbbbbaaabb +aabaabbaabaabbaaabaabaab +aabbaaaaabbbbbbabbaaabbababbabbabbaabbbb +babbbabbaaabbababbaabbba +abababaaabbbaaabaaaababbbbbaabaaaaaaabab +bababbababaabaabbabaaabaaaaabbba +bbaabbaaaabbabbabaaabbbb +abaabaaabbababaaaaaaabaabaabaabb +bbababbbbaababaaaabaabaaababbaaababbaabbababaaaaaabbabaa +bbbababbaaabbbaababbbbabbababbbabbababab +abababaabbabaaaabaabbbab +abababbabbaabaaaabbabaaabaaaabbb +bbbaabbbbabbabababbbaaaabaabbbba +babaabbbabbbaaabababaaababbabbbabaaaabbaababaaab +bbbbbababaabbaaabbbaaaaa +aabbaabaabbbaababaaabaaababbabaaabbabbbbbababaabbabaaabbbbabaaabaabaaaaa +babaababbabaabababbaabbaaaaababbbbaaabaaabbbababaabbabaa +aabbbaaaaaababaaabbabaaa +babbbabbababbaaabaabbaaabbbabababbbabbbabbababba +abbaabbabababaaababbbbbbabbababaabaababb +ababbbaaabaabbbbabaaaaab +abaabaaaaabaabaabbaababb +abababbbbbaaabbaaababbbbabaababb +abbbabbaabaaabbaabbbaabaaabaaaaabbbaabab +ababbabbbbbabbbbaaaaaaabbbbabaab +abaabbbaabbaababbbbbbaabbabababaaabbbbbb +baaabbabbababaaaaaabaabaabaabaaabbbabbabababbbabbabaaaba +baababbbaaabbbaaaaaaaabbabbaaaaaaaaabaabbbabbbba +aabaabababbbabbbabbababbabbbbababbbaaabaabaabbbabaabbaabbaaabaab +bbbaabbbbabaaaabbaabaaab +abbaabababaaaababaaabbaaaaabaaabababbbbb +aabbabbaaabbababbbaababb +bbaaaaaabbbabbaabbabbabbbaaaababbbbaaaab +abaabaaaababbbaaaaabbbab +babaaababaaabbaabbbbabaababaabbabaaabaaaaabbbaaa +baabaababbabbbaaababaabaabbaaaba +aaaaaabbabababbbabbababb +babbaaabbabbbbbbbbaaaaabbbaaaaabbbbbaaaaabaabbaabaabbbaa +abbaabaaabaaaababaaababa +aaaabbbbabbabbbaabbbaaaaaabaaabb +bbbabbbbbaababbababbbbba +aababbbbbabaabaaaaaabaabbaaaabbb +aaabbaabaababaabbbabaabbbabaababbababaabaababaababbbbaba +aaaababaabaabbbababbbbba +babaaaaaabaabbabbbbabbaabaaaaaabbaaabaab +abbbaabaaababbbbbbbbaaab +baaabbaaabaabbbbaaaaaaabbbbababaabbbbababbbaaababbabbbab +babbabbbaabbabbaaaabbabaaabaaaaaaaaabbba +bbbabaaabbbbaaaaaabbaaabaaabbbbbbbbaaabb +aabbbbababaabbbaabbaabababaabbabbaaabbaaabbabbab +bbaaaabbbbbbbaabbababbaabaaabbbb +bbabbbabaabaabababaabbbaabbabbaaabbbabaababbaababbaabbaabaababaababaabaaaaabaaabaaaaabbbbaaaabbb +baaabbaabbabaaaaabababbabbbbabbb +aabbabbabbbbbbbabaabbabbababbaabbbbaaaaabaaabbaaabbbbaba +bbaaabbbbbabaabbaaababaabbbabbaabbabaaaabaabbaab +aabbabbbbaaaaaabbabaaaababaaaabaaabaaaabbabaaaab +bbabaaaabaabaababbababba +babbbaabbaaabbababbabbaa +aababaabbbaaaabbabbbaaabbbababbbbabbbabbbbbaaabb +babbbabbbbbababbbbbaaaababababbbabababaababbbbabbbabbabb +aaabbbaabbaabbaabaabbbba +abbbbbabbabaabaaaaaabbaa +bbbabababbbaaababbbabbbabaabaaabbbbbbabbaabbbbbbaabababaaabbabba +abababaaaabbababbabaabbbaabbaaabababaababbbaabaabbbaabaa +abbbaabbababaababbbaaabb \ No newline at end of file -- 2.25.1