2020-19 part 1 in haskell

3 files changed, 583 insertions, 0 deletions

diff --git a/2020/19-Monster_Messages/example b/2020/19-Monster_Messages/example
new file mode 100644
index 0000000..1500b6f
--- /dev/null
+++ b/2020/19-Monster_Messages/example
@@ -0,0 +1,12 @@
+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
diff --git a/2020/19-Monster_Messages/first.hs b/2020/19-Monster_Messages/first.hs
new file mode 100644
index 0000000..56a0cbb
--- /dev/null
+++ b/2020/19-Monster_Messages/first.hs
@@ -0,0 +1,91 @@
+-- requires cabal install --lib megaparsec parser-combinators
+module Main (main) where
+import Control.Monad (void, when)
+import Data.Either
+import Data.List (foldl')
+import Data.Maybe (isJust)
+import Data.Map qualified as M
+import Data.Void (Void)
+import Text.Megaparsec
+import Text.Megaparsec.Char
+import System.Exit (die)
+
+exampleExpectedOutput = 2
+
+type Match = Char
+type RuleID = Int
+type Action = [RuleID]
+type Rule = Either Match [Action]
+type Message = String
+data Input = Input { rules :: M.Map RuleID Rule
+                   , messages :: [Message]
+                   } deriving (Show)
+
+type Parser = Parsec Void String
+
+parseInt :: Parser Int
+parseInt = do
+  n <- some digitChar
+  void $ optional (char ' ')
+  return $ read n
+
+parseMatch :: Parser Match
+parseMatch = do
+  void $ char '"'
+  c <- letterChar
+  void $ char '"'
+  return c
+
+parseAction :: Parser Action
+parseAction = some (parseInt <* optional (char ' '))
+
+parseRule :: Parser (RuleID, Rule)
+parseRule = do
+  id <- some digitChar
+  void $ string ": "
+  rule <- (Left <$> parseMatch) <|> (Right <$> some (parseAction <* optional (string "| ")))
+  void $ char '\n'
+  return $ (read id, rule)
+
+parseInput' :: Parser Input
+parseInput' = do
+  rules <- M.fromList <$> some parseRule
+  void $ char '\n'
+  messages <- some (some letterChar <* (optional $ char '\n'))
+  void eof
+  return $ Input rules messages
+
+parseInput :: String -> IO Input
+parseInput filename = do
+  input <- readFile filename
+  case runParser parseInput' filename input of
+    Left bundle -> die $ errorBundlePretty bundle
+    Right input' -> return input'
+
+compute :: Input -> Int
+compute (Input rules messages) = length . filter id $ map isValid messages
+  where
+    isValid :: Message -> Bool
+    isValid msg = case matches 0 msg of
+      Just "" -> True
+      otherwise -> False
+    matches :: RuleID -> Message -> Maybe Message
+    matches ruleId msg = case rules M.! ruleId of
+      Left c -> if head msg == c then (Just $ tail msg) else Nothing
+      Right actions -> case map (processAction msg) actions of
+        Nothing:a:_ -> a
+        a:_ -> a
+        otherwise -> Nothing
+    processAction :: Message -> Action -> Maybe Message
+    processAction msg action = foldl' step (Just msg) action
+    step :: Maybe Message -> RuleID -> Maybe Message
+    step Nothing _ = Nothing
+    step (Just msg) ruleID = matches ruleID msg
+
+main :: IO ()
+main = do
+  example <- parseInput "example"
+  let exampleOutput = compute example
+  when  (exampleOutput /= exampleExpectedOutput)  (die $ "example failed: got " ++ show exampleOutput ++ " instead of " ++ show exampleExpectedOutput)
+  input <- parseInput "input"
+  print $ compute input
diff --git a/2020/19-Monster_Messages/input b/2020/19-Monster_Messages/input
new file mode 100644
index 0000000..f648638
--- /dev/null
+++ b/2020/19-Monster_Messages/input
@@ -0,0 +1,480 @@
+66: 69 116 | 9 115
+91: 95 9 | 109 69
+14: 110 69 | 15 9
+4: 119 9 | 61 69
+17: 9 23 | 69 93
+37: 118 69 | 94 9
+68: 9 80 | 69 19
+117: 37 9 | 45 69
+132: 9 109
+74: 9 25 | 69 126
+102: 122 9 | 6 69
+98: 89 9 | 99 69
+113: 83 9 | 7 69
+92: 9 16 | 69 50
+33: 9 39 | 69 133
+134: 95 69 | 7 9
+57: 9 7 | 69 110
+31: 9 66 | 69 51
+47: 9 3 | 69 83
+21: 69 123 | 9 129
+104: 9 86 | 69 7
+40: 69 24 | 9 34
+32: 9 44 | 69 88
+45: 49 69 | 48 9
+2: 69 88 | 9 23
+5: 3 9 | 110 69
+108: 20 86
+76: 97 9 | 113 69
+56: 9 121 | 69 58
+29: 69 13 | 9 82
+123: 86 20
+46: 23 69 | 95 9
+19: 7 69 | 109 9
+12: 93 9 | 95 69
+75: 85 9 | 128 69
+127: 93 69 | 83 9
+61: 9 7 | 69 23
+78: 9 132 | 69 107
+121: 88 69 | 23 9
+60: 33 69 | 76 9
+73: 26 69 | 100 9
+116: 9 60 | 69 75
+93: 69 9
+38: 9 106 | 69 110
+107: 9 7 | 69 86
+82: 5 69 | 64 9
+58: 44 69 | 23 9
+34: 69 57 | 9 104
+124: 69 106 | 9 44
+109: 69 9 | 9 9
+48: 69 44 | 9 83
+28: 9 83 | 69 7
+64: 9 93 | 69 7
+54: 9 102 | 69 40
+94: 83 69 | 7 9
+80: 9 86 | 69 3
+62: 86 69 | 83 9
+42: 125 69 | 70 9
+71: 69 112 | 9 114
+8: 42
+131: 69 44 | 9 7
+88: 69 9 | 9 69
+87: 15 69 | 7 9
+3: 9 9 | 69 69
+9: "b"
+41: 21 69 | 78 9
+65: 9 69 | 69 20
+128: 134 69 | 101 9
+44: 9 69 | 69 69
+51: 9 18 | 69 54
+55: 69 79 | 9 5
+95: 69 69 | 69 9
+110: 9 69
+22: 92 69 | 10 9
+67: 9 44 | 69 23
+7: 9 20 | 69 69
+90: 69 96 | 9 68
+53: 111 9 | 27 69
+125: 69 72 | 9 22
+11: 42 31
+23: 9 69 | 9 9
+114: 69 105 | 9 131
+81: 53 69 | 29 9
+69: "a"
+1: 86 9 | 95 69
+18: 9 73 | 69 90
+83: 20 20
+130: 89 69 | 47 9
+89: 44 9 | 93 69
+15: 9 9
+0: 8 11
+105: 69 110
+13: 135 9 | 14 69
+6: 69 105 | 9 132
+103: 120 69 | 71 9
+85: 1 69 | 2 9
+96: 89 9 | 12 69
+101: 69 95 | 9 23
+39: 69 15 | 9 109
+133: 88 69 | 65 9
+86: 69 20 | 9 9
+122: 127 9 | 43 69
+20: 69 | 9
+52: 69 109 | 9 3
+119: 15 69 | 88 9
+77: 9 7 | 69 93
+50: 87 9 | 61 69
+129: 9 65 | 69 110
+97: 69 95 | 9 93
+111: 59 69 | 35 9
+115: 69 84 | 9 41
+84: 36 69 | 4 9
+72: 117 9 | 74 69
+135: 110 69
+112: 62 69 | 124 9
+43: 69 3 | 9 15
+118: 109 9 | 93 69
+49: 69 23 | 9 83
+26: 69 67
+63: 106 9 | 44 69
+70: 103 69 | 81 9
+25: 17 9 | 77 69
+36: 91 9 | 32 69
+10: 69 98 | 9 56
+30: 9 109 | 69 3
+126: 9 28 | 69 63
+16: 9 38 | 69 30
+99: 106 9 | 109 69
+59: 23 9 | 3 69
+120: 130 9 | 55 69
+27: 69 91 | 9 108
+24: 46 69 | 52 9
+35: 9 93 | 69 109
+100: 9 101 | 69 80
+106: 69 69
+79: 44 69 | 65 9
+
+bbabbbaaaaaabbabbaabaaabbaababbbabbbabbbababbbbbbbbabbbbbbabaaaa
+aabbbabbabaaaababbbaaabb
+baababbbaababaaaabbaababbabbbaaabaaaabbbaaaabbaaabbaabba
+abbbbaaabbaaaababbbabaaabbbabbbbbabaabab
+aaabbbbbabbbbbabbabbaabbaaaaababababbbbaaaaabbbabbbbabbababbaaabaaaababa
+bbbabaaaabbaaabbbababababababaaaabaabbbabaaaabbbabbabbabbbaaabbaaabaaaaa
+bbaaaabbaabbbaabbabaaaba
+abaabbabbaaaaabbbbbabaabbabbbababaaababb
+baaaaabbbabbbbbbabababba
+baaabbbaabbaabababbbaaab
+baaaabaababbbbbababbbbaaabbabbaabbababababababbabbbabaab
+baabbaaaaaaaaaababbaaabaaabbabaaabbababaaaabaaaaabbaabaaababaabbbaabbbaaaabbabbbabbbbbbb
+ababbbaaabaabaababababbabbbaabbaaaabbbbbababbabaabbbbbaa
+abaabbaabbbbbbbaaaabbbbaaaababba
+ababaaabbaabbaaabbbaaaba
+bababbbbbaabbabbabbabaaaabaababababababababaabab
+bbaaaaababbbaababbbbbbaa
+abaabababababbbaababaaaa
+aabbababaaaababababbbbba
+aabaababbbaaababbabbabab
+baababababbbabbbbbbbbaba
+bbbbaaaabbababaabbbabbabababbbab
+baaabbbbbbabbbbbaaaabaaa
+ababbbbabbaabbaaaababbaaaababaaabbbbaaabababbabbaababbbb
+bbbbaababababbbbbabbaabbbabaaaba
+abbbabbababbbaaaababbbbb
+abbbbbabbabbabbbbaaabbabbaaaabbbbbaabaaabaabbaba
+aabbabbabbbbbbabbbabbaaa
+bbbbaaaabaababbbbabbbbab
+bbababaaabbaaabbabaaaabb
+bbbbbbbabaabababbbbababbbabbbaaaababaaaa
+abbbbbaabbabbbaabbbababbababbaabbaaabbab
+aaabaabbbbabababaaaabababababaabbbabbabb
+abbabbabbbaaaabbabaaaababbbaabbabaaabaaa
+babbbabbbbbabaaababaaabb
+bbaaaaabaabbaaaabbbabbbb
+abaaabbbbaababbaaabaaaab
+bababaababbaaabbaaaabaab
+bbaabaabbabaaaaabbbbbbbaaabaaabaaaabbbaabbaabbbabbaaaabaaabbabbbbbaaaaaabaabaaaaabbaaaba
+abbabababbbbababbbaabaab
+ababababaabbaabbbbabbaaa
+bbbbbaabbbbabaaabaaaabba
+aababaaabababbbabbababababaabbbaabbaaabababbaabbbaabbbaa
+aabbaabaabbbbabbaabababb
+aabaaaaaabbbbbbbabababbbbabaaaabbbaabbba
+bbaaaaabaaabaabbaabaaaab
+aaaaaaaaabbaaaaabbbbaaababaaabab
+baababbaaaaaababbbbaaabb
+abbbbaabaabbaabbbaaabbaaabbbbabbabbbaaaabaaaaaaaaabaabba
+baabaabaaabbbabbbbaaaabaabaaaaabaaabaabbbabaabbb
+abaaaaabbabbbabbbababbaaaabaaabbaabbababbabbbabababaabaabaabbbaa
+aaaaaaabababbbbaaabaaabaababababababbabb
+abbbabaabbabaababaaaabaa
+abbbbbaabababbbbbabaaaba
+aabbaabbbaabaaaabbaaabba
+bbabababaaaaabaabbbbaabaaaaababb
+aabbaabbbbbbbaabaaabaaba
+bbbbbaabbabbbbbbabbbaaab
+bbababbaabbbbabbbaabbbab
+baaabbbbbababbaaaaabbbab
+bbaabbbbbbbbbababaaaabbbbaaaababbbaababa
+aabaabababbbbaabaaaaabba
+abaabbbbaabbbaaabbbabbba
+baabaaaaabbbaabaaabababb
+baaabababbbababbaaaaaabb
+babaababbaaaababbaabbaaaaaaabababbbbbbaabbaaabbbaaaabbabaaaaaabbaabbaaaaaabbbaaaaaabaaba
+aaabaabbaaaababaaaaaaaabaabbbbbb
+abbbababababbbbabaaaabab
+abaabaabbbabababaaabbaaa
+bbbbababaabaaaaaaabbbabbaababaabababaaabbbbabbab
+bbbbaaabaabbbabbabbbabbabaababbbbababaaa
+bbaabbbbaaabbabbaaababaaaabaaababbaabbba
+aabaabbabbabbbaaaaaaabbb
+aabbabaababbbabbaabbbbab
+baababbbbbbbbbabbabbaaaababaabab
+babbaababbaabbaaaaaaaaba
+aaabbbbabbaaaabbaaabbaaa
+aaaabbbbbaaababaababbbbabababbababaabbab
+baaaaabbbaaabaababbaaabbabaabbaabbbbaaaababbaaaa
+babbabaabbbbaaaababbbbaabbbbabbb
+abbbbabaaabababababaabab
+bbaaaaabababaababababbab
+ababbaabaabbaaaabaabbaba
+bbaabbaaabaababaaaabababbbbbaaba
+babbbbaaaabbabbaaabbbbbb
+baaabbaabababbaaabababaa
+aaaabbbabaabababbabbaababbbbabbaaaabaabbaaaabababbbaabbb
+bbbbbbabbaaabbaaabbbbaabbbabaababbbbbaaabbabaaabbabbbbba
+baabaabaaabaabbaaabbababbabbabaabbabbaabbaaabaab
+babaaaaaabbbbaabbbbbbaba
+bbbaababaabbbabbaaababba
+bababbbbbaaabbbbabbbabbaababbaababbbaaabbbbaaaba
+abbbababbbbbaaabbabbaaab
+bababaababaabbbabaaabbbbbaabababbbbaabaa
+bbbaabbbaabbbbbaabaaabaaaaabbbbbaababbbbbbababbabbabababaaaababaaaabaabb
+baaaaabbabaabaaaabbbbaaaaababababbbbabbb
+bbbbaabbbbaaabbbbaabbbaabaaababbbbaababb
+abaaaabaaabbababbbaabbba
+bbabaabbbbaabbaaababbaabaaababaa
+aababbbaabaabbbaaababbaabaaabaaaaabbbbba
+babbaabbbbbbaabaaabbabbaaabbabaabbaabbab
+aababaabbbbababbaabbbaababbabbabbaaaabaaabbaabaabbbaaabb
+abaabbbbabaabbaababaaaba
+aabbbaabbaaabababbaaabba
+baabaaaaaaaabababaaaabab
+bbaaaabbbaaabbbaabababba
+bbaaaaabaabaaabbaaaaabbb
+baaababaabbaaaaababbbbbbabbbbbaabbbbbbabababbbaa
+abbbbabaababaabaaaaabaab
+baaababaabbbabbbbaabbaab
+abaabbaabababaababbaaaaaababaabb
+abaababaaabbabbaabaaabba
+bbaababbaabaaabbbababaabbbbabbab
+babbaaaaabbabbbaabababbb
+aabbaaabbabbbbaaaabbbbba
+bababaaababaaababbbabbba
+bababbbaabbaabababbbabbbbbababababbbbbaabaaababb
+abbabbbababbbbaaaabbaabbaabbaaaaabbabbaa
+aaaabababbabbbaaaabaabaaabbabbabbbbbaaaabbaaaababaabbabbbbbbbbbababbabaaaabbbaab
+bbbaaaaabbaabbbaaabaabbaabaaababbabbbbbabbbabaab
+bbaaaababbbaababbabbbaab
+aabaaabaaaabaabbbbabbaaababbababbabaababbbbaabba
+aaaabababaababbaaabaaabaababaababbaaabbbbabbbaab
+bbaabbaaaaaaabababbabbbabaaaabbb
+ababbababbabaababbbabbbb
+bbbbbbabbbaabbbbbbbabbbbbbbbbbaaaabbbbabaaabaaba
+aabaaababbaabbaababbaabaabbaabbaababbbbb
+bbaaaaabbbbaabbabbabbabaabaaaaaababaabab
+aababaaabbbbaabbbbababbabbabaaaabaaaababbaaaababbabbbaabbaaabaab
+aabbaaaaabbbaaaaabbaaaaabbbabaab
+aababbbabbbaababaabababaababbbaaabaaabab
+bbbaaaababaaabaaaaaabbabaababbbaabababaaaaaabaabaaababab
+abaaaabbabababbaababbbab
+bbabaabbaababababaabbbbb
+babbabaabbabbbbbaaabaabbbabbaaaabaaabbba
+aaaaabaababbabaaabbabbbb
+bbaaaabbaabaaabbbaabbaba
+abaaababaaabbbbbbbabbababbaaabaa
+bbbbaababbbabaaababbabab
+ababababaababaaabababbbbaaabbaababbbbabababaabba
+babbaabaabaabbbbbaabaaaaaaabaabbbaabbabb
+aaabaaaaababbaabaabbabaaabaabbabbbbbbaaabaaabaaa
+baaabbaabaabaabbbaabbbab
+aaaabbbaabaabbbbabbbbbaabbbbbbbbababbbaa
+bbabbbaabababaababbaabaa
+bbabaabaabbababaabaaaaabaaaaaaaabbbaabba
+bbaababbbaabbaaabaaaaaba
+baabbabbabbababbbbbbbbaabbbaaaaabaaaabbb
+babaaabaaababbabbabaaaaaaaabbaaaaabbabbabaaabbbabbaabbab
+babbabaaabaaaabaabbbababbaaaabba
+abbababaaabaabbaabbbaaaabbaabaababbbbbabaabbbaaaaaababbaabbbbbbb
+abbabbbaabaabaaaaababaabaaaabbbbabbaaaaababababbbbabbaabaabbababaaaabaabaaabababbbabbaab
+bbaababbaaaaabaaaabbbaababbbbbab
+babbbabbaaabaaababaabbbabbbaaaba
+aaabaaabbaababbaabbbbbaaaabbbaba
+bbaaabababaaaabaababaabaaabbbabbbbbbaabbbbaabbaababbbbabbbabbabbbababbab
+abbbabbabbbbaaababbbbaabbaaaaaab
+babbbabbaabbaabaaabbaaabbbbbaaabbaababbbaaaaaabb
+aabbaabaabaabbabbbbbbbbabbbaabbb
+abaaaaabbbbbaababaaaabab
+abbbbbbaaabaaaaabbabaaaa
+bbbbbbbaaabababaaaabaaba
+bababbaababaaaaababaaaba
+abbbaababaababbbbbbbabbabbbaabaa
+abbbbbaabbbababababbbbbbbaaaabaabbbaaaba
+abaaaabaabaaabbbbaababaa
+bbaabaaaaaaaababaabbaabbabbbbbbabaabbbbabbababba
+baabbaabaaaaabaabaabaabbbbabbbab
+bbaaabbaaabbabbaaaaaaabbbbbaabbabbaaaaaabaabbbaa
+aaaaaaabbbbbbbabbbababaabbababbb
+abbbabbbbabbbaaaabababbb
+aaabaaabaaaabbabaaaabbbb
+babbaaaabbbbbbabbabbabba
+ababababaabbabaabbabbbbbbaabbbaa
+aabbbaabaaaaaaabaaababbb
+aaaaabaaaaabbbbaaaaabbababaabbababaabababaaaabaa
+abbbbaabbbabaabbababaaabaaabaaabbaaaabbabbaaabba
+aaabbbbabbbbaabaababababbababbbabaabaabbbbbaabbb
+abbbababbaababbababaabaa
+ababaaababbbbaabbbabbabb
+babbbbbbbaababbbbbbabaaaabababbbbaabbabb
+aabaaabbaabbaaaabaaaabab
+abbbabbbbababbbbbbabababababaabbaabbbbba
+bbbabaaaaababaabaaaabbaa
+bbbbaaabbabbaababbbaabba
+ababababbaaababababaaaaaaaabababbaaabbbbbbaaabaaaaababbabaaaabba
+bababbbbbbaaababaababaabaabbababbbbbbbba
+baababbaaabaabababbaabba
+bbbaababbbbbbbbabbaabbab
+babbbbaababbbbbbbaabbbba
+aaabaabbabbbbaabbbaababa
+abbbaaaaaaaaabaabbabbaab
+aabababbababaabaabbbbbbbaabbaababbaaaaaaaaabbbbaaaaabbaa
+bababbbbaaababababbabababbbbbbbaababaaaaaaabbaaa
+bbbbaaababbabbababababaa
+bbbbbaabaaaababbaabbbbba
+baabbaaabbbbabbbbbabaabaaabaabbbaabbbbbb
+bababbaababbbbbbbaaaaabbbbaaabab
+aabbaaabbbbbbbabaababbabbbaaabaa
+bbbbaaabbaababbaaababbab
+ababbaabaabbababbaaaabaa
+baabaabbabbbabbbbaaaabbb
+abbabbbabbbaababbbbaabba
+abaaabbaaaabbabbababaabbbaaaababbaaabbbbaaabaabb
+baabaabbbaaaaabbbabbaaaaaabbabbbbbbaabbb
+abbaabababaabababbaababbabbaabaa
+bbaaaaaabbaaaabaaabbababababbbab
+aabbaaabbababbaabbbbabbbbaababababbaabba
+bbbbaabbaababaababbbbaabbbabbbbaababbbaaabbbbbbbbbababbb
+aaaaababaaaababaabbbababaabababaabbaaabbbabbbbab
+aaabbbbabbabaabbbbaaabaa
+bbabababbabaaabbbbbaaaba
+aabbabbabbbabababaaabaab
+bbbbaabbabbbabbbaabbbbbabaabababaaabbbab
+baaabbbbaabbbabbbbaaaaaaabbbaabbaababbbb
+bbaaabababbbaabaabbbaababababbabbbbabbab
+bbbaaaababbaaababbbabbabbbbbbaaaababaabb
+abaababbbabbbbabaababbabbaaaaabbbaababaaabbaabaabbababaaabaababb
+ababbaabaabaabbaabbabaaa
+bababbaababbaababaabbaabaabaaaaabaabaabaaababbabbbabaaaa
+babaaaaaaabbbabbaaabbbaa
+abbbbaabbbbbaababbbaababaaaaaaababababbb
+bbabababbababbbbbbbbbaaa
+aabbbaabbababbaaaabaaababbabbabb
+baababbbabbbbbbabbbbbbbaaaabababbaaabbab
+bababbbbabaabbaaabbbbaaabaaaabbb
+abbaabaaabababbbaaaaaaaaaabbaabbbaabaabb
+bbabbbbbbbabbbbabbbbaabbabaaaabbbaabbaba
+bbaabbaabbababaabbaaababbabaaabb
+bbaaaabbbaabaababbbbabbaababaabb
+aaaaaaababaabbbabbbbabaa
+bbbbaabaabababbabbaabaaabbababbaababbbbbaaaabbaabbbabbbabbaababb
+abaaabbbbbbbababbbaababa
+abaaaababbbbabbaabababba
+aababbbabbbbaabbbababbbbabaaaaababbbaabbbababbab
+bbbbaaaaabaabaabbbbbababbaaaaaba
+babbaaaabaabbaabaaaaabba
+bbbbaaaabaababbabbbaabba
+ababababbbaaaaaaabbabaab
+bababbbabbbaababaabbabaaabbabbbabbabbbab
+baabaaabbabbbbbbbbbbbaabaabababa
+ababbbbaabaaaabababbbbba
+aaaaababbbabbbaababaaaba
+baabababbaaaaabbbbababbb
+bbbbabbabaabaaaababbbbba
+aababaaabbabbbabbbbbbabbbbbaabbbbaabbabb
+bbabaabaabbabababbbabaaaabaabaaababaaaba
+aabbbbaaabbbbabbbabbabab
+abaababaababbbbbbababbab
+bbbabaaaabbbbabaaaabbabb
+aabbaabbabbabbabbabbabba
+bbababababaabbbbbabaaaab
+bbbbaaaaaabaaabbbaabbbbb
+aaaababbbaababababbabbaa
+abaabbaaaabaaabababbbbba
+aababbaabbaaababbbbbbbbababbaabb
+babbbababbbbbaabbaabbbabbaaaababbbaabbabbbbaaabbaabbbabbbaababaa
+bbaaaaabbaabaabaabbaaabbababaababaabaabbabbabbaabbaaabbababbbbab
+abbabbbabaabaabbabbbaaab
+babbababbaabbabaabaaabbabbababbbaaababbb
+baababbbbbababaaababaaaabbabbaaa
+bbbabaaaaaabbbaaaaaabbabbabababbabbbbaaaaaababab
+ababaaabbaaabbbbababaaabbbbbaaaababbaabaabbbbabbbbabbaaa
+abaaaaababbaaaaabbabbbaabaaaabaababaaaba
+abaabababaabbaabbbbaaaab
+babbbbbbbaaabbaaabbbbababbaaabbbabababaabbbaaaba
+baabaaabaaaaaaabbbabaabbbbabbaba
+aababbaaabbbaaaaabababba
+abbbbabaabaabbaaaaaaaaababbbaaaabbabbaaababaaaab
+bbaaaabbaababaabaabaaabaabbabbbb
+bababaabbabbbaaabbaabaaa
+bbbaabababbbbaabbabbabaabbaabaaa
+babaaaaaabaaabbbbbababbb
+abbbbbaabaabaabababbabba
+baababbaaabbababababbbaa
+aaabbbbaaaabababbabaabba
+abaabbbabbbaabababaaabab
+babbbaaaaabaaabababbbaba
+abaabaabbabbaabaabaababb
+aaaaaaabbabbaabaaaabbbab
+bbabbbaabaabaababbaaaaab
+bbaaaabbbbbbbbabababaabb
+bbaababbbaaabbbabbaabbab
+aaababababbabbabbabbabab
+aabbaaaababaaaaaabbbabbaabaabbbaababaaaa
+aabaaaaaabbaabababaaabab
+baabaaabbbbababaababbbbb
+ababababbbbbaababbaabaaa
+bbbababaaababbbaabaaabab
+bbbababbbbababababababbb
+baababbbbbbbbbabaabbbbaabbbbbaaa
+ababbbbaaabbaabbbbaabbbb
+baababbababababbbbbbbbbaabbbbaabbbaaaaabbbaabbab
+abaabbbabaababbaabbaabaa
+aabbabbabbbbaaaaabaababb
+baababbaabbaababaabaaaaabbbabbba
+aabaaaaabbbbababbbbbaaaabbbabaabaababbab
+aaaaaaaaabbaaabababbbbab
+baaabbbbabbbaaaaababbbab
+abaababaaababaaabababbaaabbbababbbabbbaaaaababbaaaaaabbaaaabbbbb
+aabbbaaaabaabaaabbbbbbababbbbaaabbbabbaa
+babbaaaaaabbbaaaabbbbbaaaabbabbabbbaabaa
+bbbababbbabbbbaaaabaabaa
+babbbabbabbbbbaaabbabbbb
+aababaaabbaaaaababaaaaaabbbbbbababababbbbaaaabbabaababaababbabbaabbbbaaababababa
+bbbabaaabaababbaaabaaaab
+baabaababbabbbbbbaabbbbb
+bbbbbbabaaababbbabbabbaabaabbbba
+bababbabbaabbaaabaababbbabbbaababbabbaaaaababbabbbbbaaabbabbaaaaabaabbba
+abbaaabbabbababaabaaabaa
+bbaaababaabbabaaabaaabaa
+bbabbbaaaaaaaaaaaaaabaab
+bbaaaaabbbababbabbbaaabb
+aaaaaaabababbabababaaaab
+abbabbabbabbbbaabbabbabb
+aabaaaaaabbbaaaaaabbabababaaabbbbbabaaabbabaabaabaaaabaa
+bbbbbaabbbaaaaaababbbbbbaaaabbababbaabbbabbbbbabbaaaabab
+aaabaaaaabbbabaabbaaaaba
+aababaabaabbaaaabaaaaaaa
+aaaabbbaaaabababaabbbaababbabaaabaaaaaaa
+baabbaabbaabaabbbababbbbbbbabbaa
+bbbaababbbbbaaaaaaaabaab
+bababaabbabbabaabbabbaaa
+baabbaaababaaaaabbaaaaaabbbabbbaaabbbaaabbbabaaaaababbbbbbbaaaab
+abbaababbaababababaabbaaababbaababbaabbbaaaaaabb
+babbabaaaaababbaabbaabaabbbbabba
+babbaabbbabbaabbaaaabaab
+aababbaaaaabaaabaabbbaabaabbabbaabbbbbbabbaabbbbbababaaa
+aaaabbbababaaaaaaabaabbb
+bbaababbabbbaaaaababaaabbbabbbbaaabbbbaababbababbbabbabb
+aababbbaaaabaaaaabaababb
+baaababbabbbbbbbbabaaabbabaabaabbbabbaba
+abbabbabaaaaaabbaaabbabbbbbabaababbababbbbbaabba
+abbbbabaaabbababbbbaaaba
+abbbaababbabbabbbaabbabbbbabaaaa
+abbbbaabaabbbabbaaaabbaa
+aaabbbbaaaaabbababbaaabbaaaaabbb
+bbbbaaabaaabaaabbaabbbaa
+babbbabbbabbabaaabbabbbb
+ababbbbaabbbabbbaaabbaaa
+bbabbbbbababbaabaaaabbbb
+bbbababbbbbbbbbabbbabbbb
+abbbabbbbababbbbabbabbbb