day19

2 files changed, 786 insertions, 1 deletions

diff --git a/input19 b/input19
new file mode 100644
index 0000000..70581c6
--- /dev/null
+++ b/input19
@@ -0,0 +1,605 @@
+25: 6 54 | 28 122
+52: 27 54 | 25 122
+44: 118 122 | 30 54
+37: 122 97 | 54 98
+38: 122 22 | 54 3
+77: 54 34 | 122 7
+17: 122 124 | 54 47
+1: 54 79 | 122 119
+13: 122 121 | 54 15
+29: 122 3 | 54 97
+24: 54 97 | 122 62
+80: 122 1 | 54 21
+62: 54 54 | 122 54
+5: 54 61 | 122 119
+28: 54 57 | 122 36
+101: 122 48 | 54 44
+81: 120 54 | 14 122
+14: 54 96 | 122 38
+18: 40 122 | 76 54
+27: 122 93 | 54 103
+4: 123 122 | 90 54
+65: 122 87 | 54 22
+113: 54 | 122
+23: 122 127 | 54 62
+117: 71 54 | 119 122
+53: 35 54 | 126 122
+26: 122 52 | 54 108
+125: 54 33 | 122 4
+10: 74 122 | 53 54
+84: 54 19 | 122 109
+123: 122 114 | 54 115
+42: 70 122 | 26 54
+16: 122 39 | 54 98
+63: 98 54 | 51 122
+39: 54 122
+76: 122 83 | 54 101
+61: 122 3 | 54 39
+50: 122 85 | 54 95
+78: 22 122 | 3 54
+114: 122 122
+64: 122 122 | 122 54
+40: 122 81 | 54 55
+92: 127 122 | 97 54
+119: 122 51
+57: 98 54 | 114 122
+3: 113 122 | 54 54
+97: 122 113 | 54 122
+7: 122 37 | 54 59
+74: 54 46 | 122 56
+2: 122 67 | 54 50
+48: 43 122 | 65 54
+124: 54 94 | 122 36
+82: 54 98 | 122 64
+93: 59 122 | 116 54
+96: 115 122 | 97 54
+98: 54 54
+60: 51 54 | 22 122
+72: 122 98 | 54 3
+106: 39 54 | 39 122
+41: 51 54 | 97 122
+31: 18 54 | 69 122
+91: 122 62 | 54 127
+120: 105 122 | 19 54
+56: 60 122 | 78 54
+47: 16 122 | 91 54
+88: 97 113
+30: 22 122 | 115 54
+71: 51 54 | 39 122
+87: 122 122 | 54 122
+21: 122 102 | 54 73
+43: 122 22 | 54 127
+35: 54 23 | 122 90
+51: 113 113
+90: 122 62 | 54 87
+32: 54 127 | 122 97
+115: 122 54 | 54 113
+55: 54 84 | 122 89
+73: 122 51 | 54 39
+36: 22 54 | 114 122
+68: 122 87 | 54 98
+34: 118 54 | 32 122
+95: 54 87
+83: 122 117 | 54 20
+33: 99 54 | 29 122
+19: 122 127 | 54 98
+46: 54 112 | 122 79
+89: 54 72 | 122 66
+110: 54 51 | 122 98
+109: 64 54 | 22 122
+9: 54 107 | 122 5
+12: 54 80 | 122 45
+104: 54 100 | 122 32
+15: 75 122 | 63 54
+69: 122 49 | 54 12
+8: 42
+75: 97 54 | 3 122
+108: 122 77 | 54 125
+103: 122 88 | 54 24
+111: 3 54 | 39 122
+70: 122 58 | 54 10
+20: 122 105 | 54 68
+0: 8 11
+122: "a"
+79: 62 54 | 22 122
+102: 87 122 | 97 54
+105: 98 54 | 98 122
+49: 13 54 | 2 122
+112: 54 39 | 122 62
+58: 9 122 | 17 54
+11: 42 31
+107: 66 122 | 110 54
+86: 54 106 | 122 82
+99: 127 122 | 39 54
+22: 54 122 | 122 54
+118: 54 3 | 122 64
+67: 122 59 | 54 111
+126: 78 54 | 92 122
+121: 54 41 | 122 38
+66: 22 113
+94: 54 39
+6: 88 122 | 29 54
+127: 122 54
+116: 54 39 | 122 87
+59: 54 51
+85: 64 122 | 97 54
+100: 98 122 | 62 54
+54: "b"
+45: 86 122 | 104 54
+
+baaabbaabababaaababaaaaababbbabaabbbabba
+baabbbbbaababbabaaabbabb
+abbabbaabbabbbaabbabaaaaaabaabbbabbabbaa
+bababbaababaabbaaabbabbb
+baaabbaababbbbaabbbaaaba
+bababbaababbbbbbaabbbbbb
+ababababbabbaababbaabbbabbaabababaaababbaabaaaabbbbbaaaa
+bbabbabaaaaabaaabbaabbab
+abbbaabbababaabbbaabaaab
+bababaaaabbbbbaaaabbbbbb
+bbabaabbbbabbaabbabaabbaabbbbbaa
+babaabaaabaaabbbbbbabbababaaabbbaaaaababbaabaabb
+abaaaaaabaaabbbabbbaaabaababaabaaabababaaabaabba
+aabbbaaaababbaaaaababbbb
+babaabbaaaaabaaabaabbbabbababbbb
+aabbabbbbbabaaaabbaabbab
+abbabaaaaaaaaaaaabaabbbbaaabbbabaaabbabb
+aaababbbaabbabbbaaabaaba
+babbaabbbabaaaaaaabbbbabbabaabbababbbbabaababbba
+abababbbabbabbaabaaabbbbababbabb
+aaaaabbbbbbbaaaabbbaaabb
+baababaaababaaabbaabaaabaabbabbabbaaaabb
+babaabbbababaabaaababbbb
+babaabaababbbbbbaabbaaba
+babaabbbbabaaaabbbabbbaaaabaaaba
+bbbabbbabbbbbaabbbbaabba
+aaaaaababbabbbaaaaabbabb
+bbabbbaaaababaaaababaaab
+baabaababbbbbbbaaaaababb
+abaababbaaaabbbaaabbabababaababbbbaabaab
+abbbbbaaaababaabbbbababa
+aabbabababbbbbaabbaaabba
+abbaaababaabbbaaaabbaaaabbbabbabbababababaaaaaaabaabaabaaaaabaabbaabaaabaababbbbbbaabbaa
+abbabaaaaaaaababbbbaabba
+bbabbbaaaaabaababbbbbaaabbaaaabababbbabaabbabaababaaababbaabbbbbaababbbb
+abbabaabbbbbaababbabbbbaabbaaaab
+baaaabababaabbabbbbbbaabbaaaaabbbabbbbba
+abbbabbbbbabaabbaaabaabb
+aaaaababbbbabbaabaababba
+baabbbbaaaaabbababababba
+bbbabbaaabbaaaaaabaabbaa
+babbaabbbabbaabbaaababababaaabab
+ababaabbbaaabaaabaaaababbbaababaaababaabbbbbabbaaabbaaaa
+aabbbabaaaaaabaaaaabbbaa
+aabaaabbbbbbbbbaaabababa
+abbaabababbbaabbbabbbbaaaaaaabbaaaababababaabbbabbbababa
+aabbbabbabbaaaaabbbaaabb
+bbbabbbabbaabbbbbbbaaaba
+bbabababaababbaaababbaab
+abbabbbabbbbbaaaabbabaaabbabaabaababbaaaaaabbabb
+abbbbaabbabaaababbabaaab
+aabbbbabaaaabbbaabbaabbbbbaabaaaaaaaaabaaaabbbaabaabaaab
+abaaabababbbbaabbbbbaaba
+bbbbbabbbabbbaaabbaababaaaabbabbaaaaaaabaaaaaaaaabbabaaaabbabbaabbbbaaabaaaabbba
+baabaabaabbbabbbbbaabaaaaaabbbaa
+bbbaaaaabbbbbbaabbaabaabbbbbbbbbabbababaaabbbbbb
+bababaabbabaabbabbbbbabababaaabb
+abaabbabaabaaabbbbaaabba
+babbaababbabbaababbbbaaa
+aabaababbabaababaababbbb
+aaababbaabbaaaaababaaabaaabbbabbbaaabababbbabbbb
+aaaaaabaabaabbbaabaaabaa
+babaabababbabaaaaaaababb
+bbabaabbabaabbbaaaaaaabb
+abbabbbbbaaabbaaaaabaaab
+ababaaaabbabbbaabababaaaaababaabbbaabbaaaababbbb
+babaaaaaababbbbaaabbbaaaabbbbbabbbababba
+bbbbabbbaababbabaabaabba
+babbabbbbaaaaabbbabbbaaaabaabaaa
+aabaaabbaabbbbabbbbababa
+babbabbaaaababbbaabbaaaa
+aabaababbaaabbbbbbbaabbb
+babaaaabbabaabbaabaaabababbaabbbbaaaabbb
+bbaabbbbbbabbbababbbabba
+bbbabaabbaabaabababbbaaa
+bbabaabbbaababbaaaabbbababbaaabaaaaabababaaaabbabbbaaabb
+ababaabababaabbbbbababaa
+abbabbaabbbbabababbababb
+baabbbbaaababbabaaabbaaa
+ababaabaababababaaabbabb
+babbbbaaabaabbbababbaaaa
+aaaabbabbabaaabbbbbaabbb
+babbababaabbbababbabababbababbba
+aabbbabbbaaabbaabbbabaaa
+aaaabbabbbbabbaaaaabbbba
+aaabbaabaaaaabaababaabbaababaaaababaabababbbaaaababbabaa
+babbabbabbaabbaaaaabbbbb
+bbababbbaaaabaaaabbaababbbaabaabaababbbabbbbbbaabbbaababbbbbbaabaaaaabbbaabbbbabaabbbbba
+aabbbabaaaaaabbbbbaabbaababbaaabaabaabbbaabaabbb
+bababaababbbbbaaabbaabab
+baaaaaababaaaaabbabbbbba
+aaababbabaaaababbbabbbaabbbbaabb
+bbabbbaabaaaababbaaaaaba
+abbbbbaaaabbbbababbbaaba
+bbbababbabbbaabbbbbbabaa
+abbbbabaabababbbbabaabaabbbaabba
+bbbbbbbaabbaabaabbbbaaaa
+bbbbbaaabaabaaaabaababbb
+abaaababbbbbbaaaaabbbaab
+abaaaaabbbbaaaabaababbaa
+baaaababbbabaabbaaabaaab
+aaababbbaaabbaababaaaaaabbaaaabaaaaabbaa
+bbabbaabbaaaababbbaababaaabbabba
+abaaaaabbbbaaaabbaaabaab
+ababbbaaabbabbabbabbaaab
+baaabbbbaaabbaababaabbabababbabb
+abbabbbbbbaaabbbbbaaaabb
+baabbbaaabbbabbbbababbaabbbbbbbbabbaaaabbbaababbbaaaaabbbabaabbaaababbbbbabaaaba
+aababbaabbbbbababbbbabbabbababbaabbaabbaaaaaaaab
+bbbbaaabaaabababbbabbababbbaabab
+bbaabababbaaabbbaaaababb
+abbbaabbbaabbaabbaababba
+aabababbbabbbbaabaaaaaabbbaabbabbabbabbb
+babbbbbabbbbbbbaaaaaabaaababbbbaaaabbaaa
+babaabbaaabbabababbbbbbb
+bbbaabaaabaaaaabbabaaabbaabaabaa
+babbababaabaababababaabaababaaab
+bbaaaaababbabbabbbbbaabb
+babbbabbabaaaabbabaabaaa
+babbababbaabbaabbbaabaab
+abbabaabbaaabaaaaabbbabbbbabbabaaababbbbbabaabba
+bababbaabaabbbabbbabbbbb
+babbbbbbbaaaaabbbbababaa
+baaaaaababbabaabbaaaaaba
+aabababbbbaababaabbaabaaaaaabaaabaababba
+abaaababbaabbabbaaaaababaabbaabbabbaaaabbbbaababababaaba
+bbbabbbababbbabbbbbaabaaaababbaababaaaaabaababaaabbaabababbaabab
+aaababbbbbabaabaababbaab
+bbbbaaabbbbabbbabbbbaaaa
+bbbabbababaaababaaaababb
+baabbbbbbbabaababababaabaabbaaaaaabbabaa
+abbabbaaaaaabbbaababbbbb
+bbaabbbbbaaabbbbbbbaabba
+bbbaaaababbabbabbaababab
+baaabbaababaabaaabbbabab
+ababaaaaaabaaabbabaabbaa
+aababaabbababbaababbababbbaabababaabbabababbabaaaaababaaaabbbaabaabaabaa
+bbaababababbabbaababaaab
+aaabababababbbbabbbaabab
+aabaaaaabaaaaabbaaaaababaaabbaabbaabbbabbaababab
+bbaaabaaaaabaabbabaaaaba
+babbbbabbabbbbaaabbaaaaaabbaabbababababb
+abbbbaabaaababbbbabbabbabbaabaaabbbbbbbbbaaaabaabbaaabab
+abbaaaaaabbbbabbabaabbbbaaaabababbbbaaba
+bababaaaababbbbaaaababbaababbaaababaaababababbbbaaabbbba
+baaabbbbabaaaaabbbbbbbbb
+bbbbbabbaaaabaabababbbbb
+ababaaaaaaababbabaaaabba
+abbbbaabbbaabbbabaaababa
+abaaababbabababaaabaabaa
+baaaababaaabaaabbaabaaab
+abbbbabababbabbaaabbbabbaabaaabaaabababaabbbabab
+babaaabaaabaabababbaaaab
+bbabbabbbabbaabbaaaaaabababababbbaabababaaabaababbaabbab
+abbaabbbbabaabaaaaababaa
+bbaabbaaaaababbaabbbaabbbbabbabaaabbbababbaabbaaaabbbbaa
+bbbbababbbbababbbbbabbaaaaaabaabbbbbaabb
+babbabbbabbabbaaabbbbbaa
+abababbbbbabbabbabbaaabb
+bbaabbbabbbbababbbabbaaa
+baabbabbbbbabbabbbabbbba
+aabaababbabbbabbbababbbb
+babbababbbabaababbbaabba
+aaaabbababbbbaabbbabbabbbabaaabbbaababaabaababbb
+abbbaabbabbbbbaababababb
+abbaabaabbbabbaaababbabb
+baabbabbbaabaaaaaaaaabba
+bbaabababaaaaaabababaabaabaaaaabaabbbbbbabbbbaaa
+babaabababbaaaababaababababbbaab
+aaaaabbbbbabaabbbaababab
+bbbbbaababbbbaabaaabbaba
+abbabbaaababaabbbbbaabaabbababab
+bbbabaabababbbabaaaababa
+baaabbbababbaababbbbabba
+aaaabbaabbaabbbabbbbaaaa
+aabaaabbaabbaabbabbbbbab
+bbbababbbababbaaabaaabba
+abbbbbaaabbaaaaaabbaabba
+babaaaababbbbababaaaabbb
+baaabbbaaaababbabbbaaaaa
+bbbababbababbaabbbabbbbb
+aabbbbababaabbbaabaaaaaa
+abaababbaaaaabaababbababababbbaaabaaaababbbaabbb
+babaaaababbaabaabbbbaaaa
+baabbabbabbbabbbaabaababbabaaaaa
+babbbbbbabbbabbbaaabbabbaabababaaabaaaba
+abbabbbaabbaabaabbaaaaaa
+bbbabbaababbbbaabaaababb
+abaabbabaababbaabbaaaabb
+baabbabbbabbbabbabbbaaab
+abbbbaabbababbaababaaaaaaababbaabbababaa
+ababababbbbbabababaaaaaa
+bbbaaaabbabbaabbbabbbabbbbababaa
+bbbbbbbaabbabbbbbbbabbbb
+baaaaaababbabbbabbbbbbbaaaaaaabbbaaababb
+bbabbbababbaaabaaabbabaaabbabbbabbabbbaaababbbab
+bbabbaabbbaaabbbabaaabbbabaabbaabbaaabba
+abaaaaabbbaababbababbbabbbbabaabaabbaabbbbababbbababbaaaabaaabaabbaaabaa
+bbabaabbaabbaabbaabaabbb
+baabbaaabbabababbaababab
+bbaababaaabbbaaababbbaba
+babaaabaabaabaabaaabbaabbaaabbaabaabaaba
+babaabbabaababaabbbaaaaa
+bababbaaabababababaaaaba
+aaaabbabbabbaababbaabbab
+abbabababaaabbbaaaabaabbbbaabaabbababbbbbbbbaaabbaaababbabbbbaaabbaaabab
+bababaabaaaabaaaabababbbabbaaaba
+aabbbbabaabbaabbbbbabaabbaababbabbaaabababbbbbba
+baabbabaaabbbbabbbaaabaa
+bbbbbababababaabaaababaa
+aabaabbaabaaaaabbbbbabababbababb
+baabbabbaabbbbabbaaababa
+aababbaabbaabababbaabaab
+baababaabbbabbbaabaabaab
+aaaaabaaaaaaaabaaabaaaab
+abbabbabaabbabbbabaabbbabaababaababbbbbbaaabbaaaabaaabaa
+aabbbbabbbaabababaababbb
+aabaababbababaaaabbaabba
+aabbaabbbabaabaabbabbbbb
+bababaaaabbbbbaabbbaabbb
+babbbaaababbbaaaaaaabbbb
+aabbbabaabbbabaabbbaabbb
+aaaabbaabbbbabbbbbabaabaabaaabaa
+abbabbaaabbabbbaabbbaaba
+ababaabbbbabababaaabbaaa
+aaabababaaaaabaaaaaaabbbbbbbabababbaaabaabbbaaab
+baaaababbaababaaabababaa
+aaaabbaaabbbabbbbaaaabba
+abaabbbbbaaaaaabaababbaaababbaabaabababa
+abbabbbbababbbaabaabbaaabbbbbbaabbbbabaa
+bbabbabbbbabaabbabbbaaab
+aabbbababbbaaaabaabaabbb
+bbbabaabbaaabbbbbaabaabb
+ababaabaaaaaababaaabbaaa
+baaaaaabbabbabbaabbbaaab
+bbabaabaababaaaaabbabaaaabababba
+aabbbaaaaaabbaabbbabbaabbaabaaaa
+abaaabbbbbaaabbbbaaabbab
+bbabbabbabaaabbbbabbbbbbabbbbbbaababaaaaabbbbbabaaababbabbbabaababaabbbbabbabbab
+babaabaababababaaaabbbba
+bbaabaaababbbbbbbaabaabb
+baabbbabababaaaaaabbbbaabbbaabab
+abbbaaaababaabbabaabbbabbabbaaabaaabbaababbbbaaa
+abbbabaabaababaaabbaaaab
+ababababaabbbbabbbbbbbabbbbabbbaaaaaaabbbaabbabaabaaaabb
+abaaabbbabaabbababbaabaaaaaabbbaaaabbbba
+baaaaabbababababbaaabbab
+babaaabaaabbbaaabaaabbaa
+babbbabbbabaabaabbbbbbbb
+aabbbabbabaaababaaabbabb
+bbaabbaaaaababbaaabbbaab
+aabbbbabbbbabbbaaabaaaab
+abaabbbaababababbabaaabbbabbbaba
+abbaaaaabbabbbabbbaaabba
+aabaababbaabbabbabbaabba
+bbabbabbbabbbbaabaababba
+bbabaabbbbabaabbbbbbaaaa
+abbbbabaabbbaabbaaababbaabbbabbaaaaababb
+bbaaabbbbabaabbaabbbbbbb
+abaaaabababbaaababbbbbbaababbaab
+abaabbbbababaaaabbbaaabb
+aaabaabbaababbbbbbbaaaaaabbbaaba
+aaaaababbaabbaabbabbabbb
+aaaaaaabaabababbbbbaaaaa
+bbbbbaaaababaaaaaaabbaba
+ababbaaababbbaaaaaabbbba
+babaabbbbbabababbaabaaab
+aabbbababbbabaabaabbaaab
+abbbabaaabbbaabbabbaabba
+baabbaababaabbabaabaaaab
+baabbabbaabaababbaababbb
+bbbaaaabaabbbaaaaaaaaaaabaaabbbaabbaaaaaabbbaababaabababababbaabaaabbbab
+baabbabaaaaabbaaabbbabba
+babaaabbabbbaabbabbababa
+bbabbabbaaababbbbbbaaabb
+aaaaababbabababaaaaababa
+babaabbbbbbbbbbababbbbbbbbbaaaabaababaaa
+aaabababaababbaabaaababa
+ababaabbbabaabaabbaaaaaa
+aaaabaaaabbabaaababaabaabababaabbaabbbbbaabbbbba
+baaaaaabbabaabaabbaababb
+aaabababaaabababaabaabba
+abbabaaaabbabbbbbbbbbabbaaaaabab
+bababaaaaababbabbbbbbbbb
+ababbaaabbbbababbaaaaaba
+ababaaaabbbaabaabbaaabaa
+baaabbaabbbaababbaabaaabaaaaabababaabaaabababaaa
+aaabbaabbaabbabbbbbababbabaaaababaaabaab
+bbbbbaaabbaabbaababababb
+aabbbbabaaaaabbbbaabaabb
+abbabbaaaabbaabaaaaababbabbabbbaabbbbbbaabbabaaababbaabaaabbabab
+abbabbababbbbababbbaabaabbbaaababbbaaabb
+bababbaaabaabbabababaaaaabbbabbbaaaaabbb
+babbaabaaabbaabbbbaaabaa
+ababbaaababababaabababbbbbaababaabbbbbbb
+aababaabbbabbaabababababbbbabbbaaaabaaabaaabbabb
+baabaaaabababaaaababbbbb
+bbbbabbbabaaabbbbbbababa
+bbabbbaaaabbbaaabaababbb
+bbbabbabbaabbabbbaababbb
+baabaabaaaaaababaabaaaab
+aabaabbaabaabbbbaaaabaaabbaababbbbbababbbabbbababaaabaabbaabbaabababaaab
+babbababbbbababbabbbbbaaaaabbbaa
+bbaabbbaaabaaabbbaababba
+bbabbbabbbbabbbabbbbaaababbabaaaababbaabaaabaabbabaaabaa
+abbaabbbabbbbabbbaaabbaaaabaabba
+baaaaabbbabaaabababaaabbbabababaaababaaabaaaabbaabbaaababababbbaabbbbaaa
+babbbaaabaaabbbbbbababba
+aabbbbabbaabaaaababbabbb
+baabbbbababbbbbbbbbbaaba
+baabbbabbbaabaaababbaabbabbbababbbabaaab
+bbabbbababbabbbbababbaaabababbbbabaabbaa
+aaabababbbbbababaabababbbbbabbbbbabbbaba
+bbbbabbbbaabbbabbababaaabbbaaabaabbababb
+ababbbbaababbbabbbababba
+abbaaaaabaabaaaabbbbaaba
+aaababababaabbabbbbbbaaaaaaababa
+bbbabbbabaaabbbbbbabbaabbbbabaaa
+bababaabbabbbabbaaabbbaa
+abbbbabbaaaaabbbbababababbbbabbbaaaaabaaaabbaaaa
+bbabbbaaaabaaabbaaaabbaabbabaaab
+abbabaaaaaaaaaaaaaabbabb
+babbbabbbbabaabaabaaaaba
+babbaabaabaaabbbbbbbbbaa
+ababbbbabbbbabbbbababaaaabbaaabbbbbaabba
+aabaababababaabbbbbaaaaa
+abbbbbaaabbbbabbaaaababa
+aaabaaabaabbbaabaabababaaaabaaba
+babbbabbbbaabaaabababbbbbabbababbaabaabb
+babaabbbbbbabbabaaaabbbaabaaabaaaabaabba
+bababaabbabaababbabbbabbbbbbababbabbaaaaaabbabaa
+babaaaabaababaabbbbaabba
+bbaabbbbbaaabbbaaabbbbabbbaaaaabbabbabbababbabaabaaabababbabbbba
+baabbaabbbabbababbbabaaa
+aaaaaaaaababbbababababbbbbabaaaabaaaaababaabbbbb
+aaaabaaabaabbbbbbbabbbabbabbabaabbbbaaabaaaabbbbbabaabaa
+aabaabababbbaabbbbabaabbbbaabababbabbabaaaabaabb
+aabaababbbabaabababbbbab
+bbaabbbabbbabbbabbabbbba
+bbaaaaabaaaabbaaaaaaabba
+bbaaaaabaababbaababbbabbabbabbaa
+aaabaabbbabaabaaaaabbbabaabbbbbabbbaabaa
+aaabbbaabbbbaaabababbbbbabbbbbbbbbbabbbaabbabbbbaaaaaababbbbabbaabbabbaaaababbbb
+aababaabaabbababbababbba
+babaaaaaaaaaaaabaabaabba
+aaabbaabbabbaabbbaabbbbbaabbaaba
+aaababbabbabbabbababbbbb
+abaaabbbbbaabaaaabbaaaba
+bbaababaababbbabaabbbaab
+abbbaabbbaaabbbabaabbbbbaaaaaaabbaaaaabbbbbbabaaabbaaaba
+babaaaabbabaaaaababbabaa
+bbbbaaababbbbaabababbbbb
+abbababbaabaababbbaaaaabaabaabbbbabbabaababababaaaaaabbababbabbbbabbaaaabbbbabaa
+babaaababbabaaaabbaaaaba
+bbabbabaabbbbababbbaaabb
+bbaababaaaaabbbaaaabbaaa
+babaaaaaaabaababbabbabbaabababbbaaabbbaaaabbbbbabbbbaaaa
+babaabbababaaabbbaaaabbb
+aabaababbabbbabababbbbaabaaabaaaaaabbababbbabaaaabaaaaabaaaababaaabbbaaabbaaabbb
+abbbabaabbbaaaabaaabaabb
+bbbbbbbaaaabababaabbbbbb
+ababaaaabbababababbaaabb
+abbabbabbabbaabbbaaaaabbaabababa
+bbabbabaababbbabaaaababb
+babbabbababaaabbabbaaaba
+aabbaaababbaaabbbbaabaabbbbabbbaaabbbbababbbabbaaabaaaabaaaabaabaabbbaab
+bbbbbbbaaabbbabbbbaaaabb
+bbabbaabbbbaabaabbbaaaaa
+bbbabaabbaabbaaabaaabaaabbbbbbbb
+aaabababbaabbbbaaababbbb
+abbbbbbbabaaaaaaabbbbababbababaa
+bbbaaaabaabaaaaabbaabbab
+bbbbabbbaaaababbaabaaaab
+bbaaabbbababbbabbbbbabaa
+aaaabbaaabaababbbbabbabbbbbbbaaaabbbbbba
+aabbbabbaaaaabbbbaaabaab
+abbabbbbbaaaaaabaaabbaaa
+baaaabababbbbaabaababaaaabaaabbbbbbaaaababbababa
+bbbbabbbbbbbabbbbabbabbb
+abbabaaaaabbaabbabaaaaaa
+abbabbaaaababbaaababaababbbaabbbabbaaaab
+abbaabaaaaaaabaaaaabbbaa
+bbbaaaabbaabaabaaabababa
+bbbaababbbbabaaabbbabaabaabababa
+baabaababbabababbbbaaaaa
+baaaabababbaabbbbaabbbabbbbaabab
+baabbbbaababbaaaabbaabbb
+babbbbbbabbbbabbabbabbabaabaaabbaaabbbab
+ababaabbbabbaabbabaababbbbbbbaba
+baabbabbaaabababbaabaabb
+ababababbbabbbabbbababaa
+abbaababaabbbbbabbaaabbabbabaaab
+babbbbaaababbbabbbababba
+abababbbabaaababaabbbbbbbbabbbbbbaaaabbbaabaaababababbba
+aabbaabbbabaabbbbabbbbab
+baabbbbabbbbabbbbaaababa
+aaababbbbbbabbaabbbaaabb
+bbbaaababaabaaabaababbbabaaaaabaaaabbbaa
+baaabaabbabbaaabbaaababa
+bbabaabbaababaaaababbbbb
+ababbbbababbabbababaabaaaaaaaaababababbbaabbbaab
+bbbbbabaabbbaabbaaaaabba
+aaabababbbabbaabbbaabaab
+bbabbabbbabaabbabaababbb
+aaaaaaababbabbabbabbabaa
+abbabaaaaaaaaaaaababbbbb
+babaababbaabbabbabbabbaabababbbaabaabbaa
+aabbbbaaaababbbbabababbabbbababa
+bbbabbaabbabaaaaaaabaaaa
+bbabbabaabbaaaabbbaaaaaa
+bbaabaaabbabaaaabbbbaabb
+bbabbaababbabbaaabbbabbbababbaab
+bbbbababbabbaabbaabbaaab
+aaaabbababbabaaababbbbbbbbbbbababbbababbabbbaabaaaabbaba
+abbbaaaababbbbbaaaabababababbaabaabbbbaabaabaabbbabababa
+bbbbabbbbbbbabbbbbbbbbab
+bbabababbbabaaaababababb
+abbabaaaaaaabbbaaaabbbbb
+baababaaabababbbbabbaaaa
+bbabbabbbabbabbaabaaabba
+aaabababbabaabbaaaabbbbb
+abaaababbaabbbbaaaaabbaaaaaabaaabbabbbabbbabbbbb
+bbaaabbbbbbababbabababba
+bbbbaaabbbabbbabbabaaabbbabaabaaaaaaababbabababbbbbbabaababbabbb
+babbbabbbaaabbabbbabaaabababbaba
+bbbabbbbbbabbabbaababbbb
+baaabaaabbaabbaabaaabbabbababbab
+bbabaaaaabbabbaaabbabaab
+abbaabaabaaaaabbbbbaabba
+aabbbbbaaaabbbbaabaaabbbbbaaabbaaababbbaaabbbaababababbaaabbbaabbbabaaab
+bbbabbbaabbbbababaaabbabaabaabbbbababbaaaaaaabbbaaabbbabaababbaabbaaabaaabababba
+aaaaababbbbbbaaaabaababbabbbbabaaaabbaabaabaabbabbabbbbbaaaaabba
+babbabbabaabbbababaaabaa
+aabaaaaabbbbaaabababbaab
+babaaabbbabaabbbaaabaaba
+bababaaabbaabababbbbaabb
+aabbbababbaabbbaabbababb
+babaabaabbbbaabbaaaaabababaaababaababbabbabbabbaabbbbbaababbaabbaaaabaaa
+aabbbbabaaababbabbaaaaaa
+ababaabbabaababbbbbaaaaa
+aaababbbbaabbbabbbabaabbaabbbabaabbaababaaabbaaa
+bbbbaaabbbaabababaababbb
+ababababaabababbbbababaa
+baaabaaaabaaabbbabbbbbaababaaabaabaaaabaaabaabaaaaabaaaa
+abaabbbabaaabaaaababbbababbbbbaaaabaabaa
+bbaabaaabbbbbbbbbaaabaaababbbbbabababbaabaaaaaba
+babbababaabaaaaaaabaabba
+bbbabaaaabbaabbbaabaabbbaaabababaaababaabbbabaaabbbbaababaaaaaabbabbbaba
+aabaaaaaaabbabbbaabbbbba
+abbbbababbabaaaaaaaaaaaaaabbbaaababbabbabbbbabaa
+aaababbabababaaaabbaabba
+bbbbabababbabbbaabbbabab
+aaababbbbaabaaaabbbaabbb
+bbbaaaabaabaaabbbbaaabab
+ababbbaabaabaabababbbbab
+babaabababbabbbbbbbbabba
+abbbabbbabaaabbaaaaaabbbabababbabaaaaaab
+baaabbbbbababaababbbbbbb
+aabbbaaaaabaaaaaabbababb
+aaaaabaaabababababbbbaaa
+ababaabbaaaabbababaaaaaa
+bbbaaaabaaaabbaabaaabaab
+baaabbbbbbbabbaaabbaaaaababbabbbbbbaabbbbbbabbbabbbaaaab
+bbbbbaabaaaabbabaaaaaaaabbbabbbb
+bbbaabaaaabbabbbabbaabaaaaabbbbbabbababbaabbbababbababab
+bbabbabbbaabbaaaabbabbaaabbbabaababbabbaaaabbbab
+baaabbbababbbabbaabaabbb
+aaaabbaababababaaabbbbbb
+abbbbbaabbbabaabbababbba
+bbbbbbbababbaabbabaaabba
+abbbaabbbabaababbbaaaaabaabbbbaa
+babbaabaabbbbababaaabbab
+baaabbbabaabbbbabbbbaaabaaabbabb
+aabbbabbabbbbabbababaabababaabaabbaaabaabbbbbbbbaabababa
+bbbaabaaababaaaabbaabbaaaabbbabaabababaa
+bababbaababbababaabbabaa
diff --git a/src/main.rs b/src/main.rs
index ea708c7..70c44ea 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -1580,8 +1580,106 @@ fn day18() {
     println!("18b: {}", result);
 }
 
+enum MsgSubRule {
+    CHAR(char),
+    OPTIONS(Vec<Vec<u32>>),
+}
+
+impl MsgSubRule {
+    fn new(input: &str) -> MsgSubRule {
+        /* check for terminating rule with single character */
+        if let Some(pos) = input.find('"') {
+            return MsgSubRule::CHAR(input.chars().nth(pos+1).unwrap());
+        }
+
+        /* we have a list of subrules */
+        let mut options = Vec::new();
+        let options_str : Vec<&str> = input.split(" | ").collect();
+        for opt in options_str {
+            let mut subrules = Vec::new();
+            let values : Vec<&str> = opt.split(' ').collect();
+            for val in values {
+                let val = val.parse::<u32>().unwrap();
+                subrules.push(val);
+            }
+            options.push(subrules);
+        }
+        MsgSubRule::OPTIONS(options)
+    }
+}
+
+struct MsgRules {
+    rules: HashMap<u32, MsgSubRule>,
+}
+
+impl MsgRules {
+    fn new(input: &[String]) -> MsgRules {
+        let mut rules = HashMap::new();
+        for line in input {
+            let parts : Vec<&str> = line.split(": ").collect();
+            let idx = parts[0].parse::<u32>().unwrap();
+            let subrule = MsgSubRule::new(parts[1]);
+            rules.insert(idx, subrule);
+        }
+        MsgRules { rules }
+    }
+
+    fn matches(&self, msg: &str, idx: u32, remaining: &[u32]) -> bool {
+        let rule = &self.rules[&idx];
+
+        if msg.is_empty() {
+            return false;
+        }
+
+        match rule {
+            MsgSubRule::CHAR(c) => {
+                if remaining.is_empty() {
+                    return c.to_string() == msg;
+                } else {
+                    return *c == msg.chars().next().unwrap()
+                        && self.matches(&msg[1..], remaining[0], &remaining[1..]);
+                }
+            },
+            MsgSubRule::OPTIONS(options) => {
+                for option in options {
+                    let next_idx = option[0];
+                    let remaining = [&option[1..], remaining].concat();
+                    if self.matches(msg, next_idx, &remaining) {
+                        return true;
+                    }
+                }
+            },
+        }
+
+        false
+    }
+
+    fn matches_word(&self, msg: &str) -> bool {
+        self.matches(msg, 0, &[])
+    }
+}
+
+fn day19() {
+    let input = read_file("input19");
+    let input : Vec<&str> = input.split("\n\n").collect();
+    let (rules, messages) = (read_lines_str(input[0]), read_lines_str(input[1]));
+
+    let mut msgrules = MsgRules::new(&rules);
+    let match_count = messages.iter()
+                              .filter(|msg| msgrules.matches_word(msg))
+                              .count();
+    println!("19a: {}", match_count);
+
+    msgrules.rules.insert(8,  MsgSubRule::new("42 | 42 8"));
+    msgrules.rules.insert(11, MsgSubRule::new("42 31 | 42 11 31"));
+    let match_count = messages.iter()
+                              .filter(|msg| msgrules.matches_word(msg))
+                              .count();
+    println!("19b: {}", match_count);
+}
+
 fn main() {
-    day18();
+    day19();
 }
 
 #[cfg(test)]
@@ -1972,4 +2070,86 @@ mod tests {
         assert_eq!(eval_expression("5 * 9 * (7 * 3 * 3 + 9 * 3 + (8 + 6 * 4))", true), 669060);
         assert_eq!(eval_expression("((2 + 4 * 9) * (6 + 9 * 8 + 6) + 6) + 2 + 4 * 2", true), 23340);
     }
+
+    #[test]
+    fn test_day19() {
+        let input = "0: 4 1 5\n\
+                     1: 2 3 | 3 2\n\
+                     2: 4 4 | 5 5\n\
+                     3: 4 5 | 5 4\n\
+                     4: \"a\"\n\
+                     5: \"b\"\n";
+        let rules = read_lines_str(input);
+
+        let msgrules = MsgRules::new(&rules);
+
+        assert_eq!(msgrules.matches_word("ababbb"), true);
+        assert_eq!(msgrules.matches_word("abbbab"), true);
+        assert_eq!(msgrules.matches_word("bababa"), false);
+        assert_eq!(msgrules.matches_word("aaabbb"), false);
+        assert_eq!(msgrules.matches_word("aaaabbb"), false);
+
+        let input = "42: 9 14 | 10 1\n\
+                     9: 14 27 | 1 26\n\
+                     10: 23 14 | 28 1\n\
+                     1: \"a\"\n\
+                     11: 42 31\n\
+                     5: 1 14 | 15 1\n\
+                     19: 14 1 | 14 14\n\
+                     12: 24 14 | 19 1\n\
+                     16: 15 1 | 14 14\n\
+                     31: 14 17 | 1 13\n\
+                     6: 14 14 | 1 14\n\
+                     2: 1 24 | 14 4\n\
+                     0: 8 11\n\
+                     13: 14 3 | 1 12\n\
+                     15: 1 | 14\n\
+                     17: 14 2 | 1 7\n\
+                     23: 25 1 | 22 14\n\
+                     28: 16 1\n\
+                     4: 1 1\n\
+                     20: 14 14 | 1 15\n\
+                     3: 5 14 | 16 1\n\
+                     27: 1 6 | 14 18\n\
+                     14: \"b\"\n\
+                     21: 14 1 | 1 14\n\
+                     25: 1 1 | 1 14\n\
+                     22: 14 14\n\
+                     8: 42\n\
+                     26: 14 22 | 1 20\n\
+                     18: 15 15\n\
+                     7: 14 5 | 1 21\n\
+                     24: 14 1\n";
+        let rules = read_lines_str(input);
+
+        let mut msgrules = MsgRules::new(&rules);
+        let messages = [
+            "abbbbbabbbaaaababbaabbbbabababbbabbbbbbabaaaa",
+            "bbabbbbaabaabba",
+            "babbbbaabbbbbabbbbbbaabaaabaaa",
+            "aaabbbbbbaaaabaababaabababbabaaabbababababaaa",
+            "bbbbbbbaaaabbbbaaabbabaaa",
+            "bbbababbbbaaaaaaaabbababaaababaabab",
+            "ababaaaaaabaaab",
+            "ababaaaaabbbaba",
+            "baabbaaaabbaaaababbaababb",
+            "abbbbabbbbaaaababbbbbbaaaababb",
+            "aaaaabbaabaaaaababaa",
+            "aaaabbaaaabbaaa",
+            "aaaabbaabbaaaaaaabbbabbbaaabbaabaaa",
+            "babaaabbbaaabaababbaabababaaab",
+            "aabbbbbaabbbaaaaaabbbbbababaaaaabbaaabba",
+        ];
+        let match_count = messages.iter()
+                                  .filter(|msg| msgrules.matches_word(msg))
+                                  .count();
+        assert_eq!(match_count, 3);
+
+        msgrules.rules.insert(8,  MsgSubRule::new("42 | 42 8"));
+        msgrules.rules.insert(11, MsgSubRule::new("42 31 | 42 11 31"));
+        let match_count = messages.iter()
+                                  .filter(|msg| msgrules.matches_word(msg))
+                                  .count();
+        assert_eq!(match_count, 12);
+    }
 }