aboutsummaryrefslogtreecommitdiff
path: root/2023
diff options
context:
space:
mode:
authorJulien Dessaux2023-12-12 23:20:00 +0100
committerJulien Dessaux2023-12-12 23:20:00 +0100
commit9bf579968e2921d53fb95bc3d0666e89e878bbec (patch)
tree862a4f5094dd519f3dd57e8138d193bcaa869a2f /2023
parent2023-11 in haskell (diff)
downloadadvent-of-code-9bf579968e2921d53fb95bc3d0666e89e878bbec.tar.gz
advent-of-code-9bf579968e2921d53fb95bc3d0666e89e878bbec.tar.bz2
advent-of-code-9bf579968e2921d53fb95bc3d0666e89e878bbec.zip
2023-12 part 1 in haskell
Diffstat (limited to '')
-rw-r--r--2023/12-Hot_Springs/example6
-rw-r--r--2023/12-Hot_Springs/first.hs74
-rw-r--r--2023/12-Hot_Springs/input1000
3 files changed, 1080 insertions, 0 deletions
diff --git a/2023/12-Hot_Springs/example b/2023/12-Hot_Springs/example
new file mode 100644
index 0000000..e925935
--- /dev/null
+++ b/2023/12-Hot_Springs/example
@@ -0,0 +1,6 @@
+???.### 1,1,3
+.??..??...?##. 1,1,3
+?#?#?#?#?#?#?#? 1,3,1,6
+????.#...#... 4,1,1
+????.######..#####. 1,6,5
+?###???????? 3,2,1
diff --git a/2023/12-Hot_Springs/first.hs b/2023/12-Hot_Springs/first.hs
new file mode 100644
index 0000000..46788ee
--- /dev/null
+++ b/2023/12-Hot_Springs/first.hs
@@ -0,0 +1,74 @@
+-- requires cabal install --lib megaparsec parser-combinators
+module Main (main) where
+
+import Control.Applicative.Permutations
+import Control.Monad (void, when)
+import Data.Char qualified as C
+import Data.Either
+import Data.Functor
+import Data.List qualified as L
+import Data.Map qualified as M
+import Data.Maybe
+import Data.Set qualified as S
+import Data.Vector qualified as V
+import Data.Void (Void)
+import Text.Megaparsec
+import Text.Megaparsec.Char
+
+import Debug.Trace
+
+exampleExpectedOutput = 21
+
+data Tile = Broken | Operational | Unknown deriving Eq
+instance Show Tile where
+ show Broken = "#"
+ show Operational = "."
+ show Unknown = "?"
+data Row = Row [Tile] [Int] deriving Show
+type Input = [Row]
+
+type Parser = Parsec Void String
+
+parseNumber :: Parser Int
+parseNumber = read <$> some digitChar <* optional (char ',')
+
+parseTile :: Parser Tile
+parseTile = char '#' $> Broken
+ <|> char '.' $> Operational
+ <|> char '?' $> Unknown
+
+parseRow :: Parser Row
+parseRow = Row <$> some parseTile <* space
+ <*> some parseNumber <* eol
+
+parseInput' :: Parser Input
+parseInput' = some parseRow <* eof
+
+parseInput :: String -> IO Input
+parseInput filename = do
+ input <- readFile filename
+ case runParser parseInput' filename input of
+ Left bundle -> error $ errorBundlePretty bundle
+ Right input' -> return input'
+
+valid :: [Int] -> [Tile] -> Bool
+valid record tiles = map length (L.filter (L.any (/= Operational)) $ L.group tiles) == record
+
+permutations :: [Tile] -> [[Tile]]
+permutations [] = [[]]
+permutations (Unknown:xs) = permutations (Operational:xs) ++ permutations (Broken:xs)
+permutations (x:xs) = map (x:) $ permutations xs
+
+compute :: Input -> Int
+compute = sum . map compute'
+ where
+ compute' :: Row -> Int
+ compute' (Row tiles record) = length . filter (valid record) $ permutations tiles
+
+main :: IO ()
+main = do
+ example <- parseInput "example"
+ let exampleOutput = compute example
+ when (exampleOutput /= exampleExpectedOutput) (error $ "example failed: got " ++ show exampleOutput ++ " instead of " ++ show exampleExpectedOutput)
+ input <- parseInput "input"
+ print $ compute input
diff --git a/2023/12-Hot_Springs/input b/2023/12-Hot_Springs/input
new file mode 100644
index 0000000..94f50ac
--- /dev/null
+++ b/2023/12-Hot_Springs/input
@@ -0,0 +1,1000 @@
+??#.?#?#??? 1,3,1
+?????.??.???. 1,1,1
+??????.??..? 2,1,2
+.??#???.??? 3,1,1
+??##?#?????.. 5,1
+?#?#?????. 1,1,2
+#??????????. 1,1,7
+??.??#.??#?? 1,3,2,1
+.?#....??? 2,1
+#?.?#..?#???? 1,2,1,1
+?#?.?#???? 2,4
+??.?.#?????? 2,1,1,2
+#??#????.?##??#????. 1,4,1,3,1,3
+?##?????????? 2,2,2
+??#??.#??#???? 5,4,2
+????????.? 1,3,1
+?####..?.?##??#?? 5,6
+#?.???#???.???. 1,1,4,1,1
+?#?..????#?##??? 1,4,5
+?#??.##???? 1,4
+.??#?.???. 1,2,2
+..#?#?.???.??#? 3,2,2
+.??#?????.?##??## 3,1,3,3
+#???#?????#?#?? 2,2,1,1,1
+##??.??#??.#?.?? 3,4,1,1
+???????.#?? 2,2
+??.?#?????? 1,3,1
+?????#???.?#?????#? 8,3,1,2
+#?.#??#?#??#?.???#?? 1,6,3,1,2
+..???.???#????.? 1,1,3,1,1
+??#?#???#??????#?##? 7,4,5
+??.???#???#.## 1,4,2,2
+???##..?.? 3,1,1
+?.##????#?.?# 1,4,1,1
+?#???????? 1,1,3
+??.??#?????#???? 3,5
+?#???????#?.? 4,1,1
+?#???????..?.?. 8,1
+.???????????.#?#?? 8,4
+??#?????#????? 5,7
+.??.??#????.???. 2,1,2,3
+..#????.##..?? 5,2
+?###.?.????..#???# 4,1,1,1,5
+??#?#?#??????? 3,2,1,2
+????#.?#?? 1,3
+.#?..#.?????. 2,1,4
+.?#?#?.?#?? 4,2
+???##??.??#???????. 7,7,1
+???###???#???.#. 5,4,1
+???????#??#???#? 1,11
+?.???.?#?#?#??#? 1,1,1,1,4
+#.???.##?????? 1,1,5
+?.??#??#?# 6,1
+?..??????#???.?##? 3,5,2
+?.?#.?#?#? 2,3
+..?.?????. 1,1,3
+?#??????##?##.?#???? 3,8,4
+?.#?????#.?#...?.# 1,1,4,1,1,1
+?????#?..#???? 1,1,2
+.??#.##???.? 2,2,1
+.#?##???..???? 7,1,1
+?????????. 4,1
+.?#?#.????? 1,1,2
+?.?#.?#??.??.. 1,1,3,1
+.???.#?#???#.?? 3,1,5,2
+??#??.??????. 3,1,2
+?#?##??.??. 4,2
+.?.???##???.? 1,7
+??????####????? 1,6,1
+??#.?#????#????. 2,8
+?#?#?#?.#?.???#????? 6,1,9
+#??##.##???????????. 5,6,4
+????.????.?? 1,1,1,1
+.?#?.?.???? 2,4
+?.#??###???? 7,1
+#????#??.?#?????? 1,4,1,1,1
+?#?????.??? 4,2,1
+#.??????????# 1,2,6
+?#???.??????.??#? 4,1,1,3
+?????..#?#? 2,3
+..???#.?#????? 4,2,2
+?.???.??#?#?## 1,1,1,6
+.?###?#.?#??.??#??? 5,2,2
+##??????????#??????? 2,6,6,2
+.????#?#??#?#.???# 7,1,1,4
+.?#??..#?.???????? 3,2,5,1
+??????#???#??? 1,8
+????#?????..?#?. 7,1
+??#?.?..#?.?# 2,1,1,1
+#?#??????? 1,1,1
+?.?#?#?.?. 1,1,1
+.???#????#??. 6,2
+?????.?#???# 1,3,1
+????#?.??#??. 1,1,4
+?#??##???? 6,1
+?.#?##???#? 4,2
+?????#???????. 5,5
+????.#????..?? 1,1,5,1
+..???????#? 1,2,2
+.#?.?#?.?..#.?? 1,2,1,1,2
+.##???.?.?????? 3,1,1,5
+??.?#?#??????.????? 7,1
+.??.??#???.. 1,5
+?#??????.##.?????? 3,1,2,2,1
+?????????#???.? 1,1,3
+?????.?????????#??#? 4,6,5
+.#?.#?.?##?# 2,2,5
+.?????????#?#?#??? 1,1,6
+.?#.??????#.???? 2,6,2
+????.????.?#??#??# 1,1,2,6,1
+.##?###.???#?. 6,3
+??#????#????? 8,1
+?.?#????#?#?????? 1,6,2,3
+.???#?.???.??# 5,1,1,1
+??????.#?????.#.? 1,1,3,2,1
+?????.?..??? 4,1,1
+?#???##???.#. 3,2,1
+?.???????.??##.#???. 1,1,4,3,1,1
+????.#?.????#???## 1,1,1,6
+?#.?..#??##.?####?? 1,1,5,6
+.??????###?.???? 10,2
+???#..??.??? 1,2,1,3
+??????#.###??.??.? 2,1,2,4,1,1
+.?.??##??? 1,6
+???#?#.???.#.? 4,1,1,1
+??.?#??????#.?#??#. 6,1,5
+????.#???? 1,2,1
+?.?##??.????????. 3,2,3
+??#?#??##???#? 10,2
+?#??.??.?###?????.? 1,1,2,6,1,1
+????#??#?.# 5,1
+??.??#???#????#?#.? 1,1,1,10,1
+??????..??#?#?#? 2,3,4,1
+????#?.????# 1,4,1,1
+?????##..???#???. 3,3
+?#??#??#??.?????#?. 9,5
+?#?#..##?.#??? 3,3,1,1
+??##???##?.??#.? 3,5,3,1
+#???.#??..?#??.#?? 4,3,2,1,2
+#??#???##?.?# 1,3,3,2
+..##.??.???##?..?? 2,6,1
+?????#??.???.#? 3,3,1,1,2
+?.??...#?????#. 1,7
+???#??#?#???# 9,1
+????.????#???#??? 1,1,11
+.???????.#.????????? 4,1,1,1,3,1
+?#?#????????#. 1,4,4
+?#?????###??#.??# 2,7,1,1,1
+??.??.#?????#?##?? 1,1,10,1
+?????.?????? 3,1,2
+???.?#??###???? 1,3,7
+.??##?##??#????.? 12,1
+?.??##???#...? 4,1,1
+.??.????.???#? 1,2,3
+?????#??#?.?.?? 1,5,1,1
+.?...????????# 1,2,5
+.??.?????. 1,2,1
+.#...?#??.#???##? 1,2,2,3
+??????????.#? 2,5,2
+.????.??#. 1,3
+#?##???#?.? 4,1,1
+????#?#??.# 2,4,1
+??.?#?#???# 3,2
+.#??#??.?#?#??#????? 1,3,10
+?#?.#????####?#??#.? 2,3,10
+???#????#? 4,3
+?#??.?#??# 4,4
+??????#?#?.?.???#??? 7,1,2
+??..#????.??.???.?. 1,5,1,3,1
+##?.#.#????? 2,1,5
+?#####??.??..??? 7,1,1
+.######??.#??? 7,4
+.#?..#.?#??? 2,1,2,1
+.#???????? 2,2
+?????.##???#??.?.. 4,7
+???#.?#??###???? 1,1,1,5
+..?#????.????#?? 1,2,4
+??#?#?????? 6,1
+#?????#????#?#?#..# 1,5,1,3,1,1
+.?#?#?????? 7,1
+..?#??#?.????# 5,1
+...??#?..?#?##? 3,5
+?#??.??????#? 2,7
+??????.???..????.... 2,2
+?##?#?.??##?#?????? 5,6,1
+??????.??? 4,2
+????#..#????#??###?# 3,1,11,1
+??##????????# 6,1,1,1
+#??##??????#? 1,10
+???.#????.???#????? 1,3,6
+????#????? 4,4
+.????##??????#. 9,1
+?.??#?.???#?#.. 1,2,5
+#..????#?#?????? 1,8,1,1
+?##???.?##??.? 6,5
+.???????#??##?.? 1,7
+????.????#?.?? 2,4,1
+#???#??#???#? 1,2,7
+?..#?#..??.??#??##?? 1,3,2,7
+?.##??##????##????#. 13,2
+????????.??? 1,3,1
+???.???##??#?.? 2,7,1
+.???.#.#.??#. 1,1,1,2
+##.?###.#??.?? 2,3,1,1
+?????.???.???#?##??. 1,8
+.???#?#??????##???? 1,1,1,4,5
+???#.??????.# 2,4,1
+??#?#???#???#.?#?#? 10,2,4
+?#?##??..??????##? 4,1,1,1,2
+.?.?????.?????? 1,1
+???.???.???? 3,2,4
+??.????#?##?? 1,5,2,1
+#?#?????#?.? 1,5,1,1
+.???..???.#? 2,1,2
+#?#?????#?? 3,6
+?#??#?????#?##.??#? 1,2,1,5,1,1
+????.??.?#?.?? 2,3
+??.###.?????? 2,3,5
+?.??????#...???? 1,4,1,1,2
+.??#???##?.?????? 3,3,4
+??##????.?.#?# 7,1,1,1
+#?????????.??????? 1,5,1,5,1
+?#???#???????#????? 5,2,1,5
+#?##?????#..# 5,1,1,1
+#?#?#??#?##?.?????. 12,1,3
+.???#??#?. 1,2
+????????..???#.??.?? 2,3
+????.????????##.??. 3,1,8,1
+#?.#.????????# 1,1,4,1
+###?#?????#?#?? 3,3,1,1,1
+???????#?#? 1,4
+??#????#.. 2,1
+..????#???????.?? 2,3
+.???#??##??##?? 8,2
+???#??#??#??###? 7,4
+????????##???? 2,8,1
+?.#??#??.#???#?## 1,6,1,2,2
+.?#?..?.?##? 2,3
+?.#?#??#?# 1,6
+##?.??#??#??#?# 3,6,1,1
+??????#??.? 2,5
+?##?.?????.???#??? 3,1,5
+??..??#?#????? 1,9
+?#.??????.?????. 1,5,5
+??#?#???#??.. 1,6
+?.??##?#???? 1,2,4
+.???.????? 1,2
+?#?????#?.?? 5,1,1
+.????#????? 2,2,1
+#?#???###?????????. 11,3
+???##??#.##????# 1,2,1,7
+#?????..#??#????? 1,4,4,2
+.?.?..?????#?## 1,1,6
+???.?#?#???.??.?? 2,1,4,1,1
+???##???..#??.#??? 5,1,1,1,1,1
+#???.????????? 1,1,3,1
+??.??.?.?? 1,1,2
+?.?#?????????.? 2,3
+??.??.?#?##???? 2,7
+.??????????#??#?. 10,2
+?#..?.#??? 1,1,1
+..?#?????##????#?#? 3,10
+?#?.??.?.#?#??? 3,5
+?????.??#?#??? 4,6
+?#?????##?#.?? 10,1
+??#???##????#?#? 1,8,1,1
+.???????#..??#? 1,1,2,3
+#????.###?..?.??# 2,1,4,1,3
+???.#.????.???#???? 1,1,1,4,1,5
+#?.?#?#??.???##?.#? 1,4,1,3,1
+??.???#??#?#?# 1,11
+?????#?#?#.???. 7,1,1
+??.??#???#???????#?. 8,4
+.????.?????## 3,1,2
+??????.???#.?. 5,1,1,1
+.###????.???#??.??#. 5,5,1
+????#??.?????#????## 1,3,11
+#??????????. 3,3
+????#????#??# 1,7,1
+?#???????#?.##??? 3,1,1,2,2
+??#??..#??? 2,1,1
+???##..??##????#???? 1,2,9
+??#??#..?#????? 4,1,2
+??##?.???#?##??##?? 3,1,4,4
+.#?#??????.? 1,2,4
+?#?##?#????.???.?# 11,1,1
+??????????? 2,1
+??.??????.??#?#????? 1,2,1,5,1,1
+.##?#??#.???? 7,3
+??????#?????##??#. 1,2,4,2,2
+.?.??.??.?.? 1,1,2,1
+?????????? 1,3
+???.???.?? 1,2
+??.??#??????.??# 1,9,1,1
+.???.?.?#??.?.? 1,1,2,1,1
+##.????#?#??? 2,7,1
+.????????? 1,1,1
+???#???.#.??? 1,3,1,1
+????#?#?#??#?.?# 3,1,4,2,1
+????#????#?#?.#. 2,8,1
+????#????????##???.? 2,2,9,1
+??..????????#??....? 4,3
+..?.?####.?.#?#. 1,4,3
+??.????.??? 4,1
+?????.??#.? 3,2,1
+??#????????#.? 5,4
+???#?#????.??#??? 9,2
+????..?????# 1,1,4,1
+?????#..??????#?? 3,6
+??.????#???.#?????. 1,6,3,1
+??.#.???#?#?#???? 1,1,8,2
+#..??#?#?#? 1,6
+.?.#?#????#?.#.#?? 1,1,6,1,1,1
+#???????.??#??.?## 5,1,5,2
+???.#??.####?#?#?. 1,1,9
+????..????#????#??? 2,10
+.??.??.??#? 1,1,1
+#.?#??#??.#? 1,2,1,1
+??.??.??????#???#?. 2,9
+.?.?.#??...??.?.?... 3,1
+???#????###?.???.??? 1,9,1,1
+???#??????#???.???#? 1,10,1,1,2
+.?.?????#?????.???? 1,6,1,2,1
+??#??????#.?.??. 4,1,1,2
+?????#???..??#?? 6,4
+?.####?..??.? 5,2
+??.???#?..#?#????# 1,1,1,6,1
+??.??##????????? 8,1
+.??#?#?????????????? 1,1,1,1,1,9
+??#?##??#?#?# 5,1,1,1
+.?#???#.????#???. 6,1,2,1
+?.?..?????##??? 1,1,1,4
+??#???#??. 2,3
+?#??????????#?? 1,2,1,3,1
+.????????#??#??.?. 3,7,1
+??.#??.???# 1,3,4
+?#.##???##??#??.?? 1,3,3,1,2
+?#?.?.#??. 1,2
+?#???##?#???#??? 1,13
+???????#?#?????#??. 1,10
+.????#.?..???# 4,4
+.???##.###.?#.?? 1,2,3,2,2
+?.?##????? 1,3,1
+#?#?##???###..??#??? 6,5,5
+?#?#???#??#??.# 10,1
+#??????#??##? 1,1,1,5
+####???###.?.????# 6,3,1,2
+.#??.?#??? 3,3,1
+??#???#.????..?#??? 7,1,1,1,1
+?..?????????..#.???? 4,1
+??##???.##? 4,1,2
+?.?????#???##?.?#??? 1,1,1,8,1,1
+?.?#?????##?##??#? 2,8
+?#?.?#??.? 1,1,1
+??.????..#.?????.? 1,1,1,1,5,1
+?##??#??????. 5,1,1
+.?.????##? 1,2
+???##?#.#??????? 5,8
+#?????..?#??#????# 4,1,1,1,2
+#??.??#?.#?. 1,1,2,1
+?.?#?#?#???????.??.? 5,3
+???#??#????#?? 2,7
+????#?????#???.???# 1,9,1,1
+#?.??.???..?#.?? 2,1,2,1,2
+.###?.???.?? 4,2,1
+???#?.#.?##.???#? 1,2,1,2,5
+#?????????#?#????? 1,1,1,8,2
+???????#?#??.?????? 1,10,1
+??#.???#??#. 3,4,2
+?#??##.?#.#?## 6,1,4
+????###?#??? 1,3,2,1
+..??????#? 2,2
+.??#??##???? 1,2,4
+.?????##?#???.? 2,4,4
+?##?#??#?.??# 4,1,1,1
+.#?#???##??#?.#?##?? 8,1,5
+??#.#.#??#?#.?##?# 1,1,1,1,1,5
+.#??#?.??##??#???? 1,1,9,1
+#??.???#?? 2,2
+???????.#.?# 1,1,1,2
+???????.?#???# 1,4,2,2
+????#??#??#?.# 1,4,1,1
+?#.???#??#????.? 1,9
+???##?????#?#??#. 5,6
+??#???##???#?#???. 2,12
+?#?.??.???? 3,1,3
+?#??.?.??????.. 1,1,1,1,2
+#??#?.????.. 1,1,4
+?#?#?.???????????. 2,1,1,1,1,2
+?.?????????##???#? 1,5,2,2
+###??.?.???.#?? 4,1,2
+???#?????#???#.# 1,1,9,1
+??.#??..?..??? 1,2,1
+.?#?.?.?????...?? 2,2
+????..???#?#??? 1,7
+?????#???.????? 1,5,1,1
+?????????????? 2,5
+???#??.??. 4,1,1
+#??????.#???????# 2,1,6,1
+?.#???.?.? 1,1,1
+.?????#????.? 3,5
+???.?????#.??#????? 6,3
+??#?###????.?.#??.# 7,2,1,1,1
+#???##?.??.???????? 6,1,1,1,1,1
+??.?.???#?.?.??#. 5,2
+#..?#???#?#???? 1,2,7
+.???#?#?#????? 9,1
+???.???#?#?#.??#? 2,2,5,3
+????????????? 1,1,1,2
+#?????.??????### 4,2,5
+.#????#????#?? 3,1,1,2
+???????#.#????????? 2,1,1,2,4,1
+?##.??#??. 2,3
+?????????#???.?#??? 2,1,1,5,5
+????????.#?#?#.. 7,5
+?.?.??#?????.? 1,6
+?#.?#?#?.???? 1,3,1,2
+..#??....??#?????? 2,9
+.?.?#?#?????? 6,1
+??#?#.???? 3,1
+?#??#?????? 5,1
+#.????#???.#.??.?? 1,3,1,1,1,1
+.?###????.???? 3,1,1,2
+?#???#?.##?#???? 1,2,6,1
+#??#??????#..??#? 1,1,5,2
+..?#?.???? 2,3
+#????..?.?..????. 5,1,4
+.?.???????#.#????? 1,1,1,1,6
+.??.??.????? 1,2,1,1
+#???.??????# 3,1,1,1
+.#???#?#?# 1,4,1
+???##?#?#?###????? 11,1
+?.?#?#???#??.#. 8,1
+???#?????..#?#??? 8,5
+??...??#?#?##?????#? 1,15
+..?????#???#?? 7,2
+??????????#?#? 1,5,2,1
+????#?#?.??..#??.? 5,2
+.??##??#?.#? 4,1,1
+??????????#?? 1,10
+?#??#????????. 5,3,1
+??.???????.???##??. 1,1,1,2,6
+???###.#?? 1,3,1
+.?..#..??#.???? 1,1,1,1,3
+#????????#?.?#?##.. 2,1,2,4
+??.?.????????. 1,7
+??#?#?????#?#? 5,3
+??#???#?#??.?????.? 9,3
+#??.?????#??????# 2,2,2,4
+.#??.????? 1,1,1
+..##???.?? 2,1,1
+???.??.?????? 2,2,3,1
+?????##..??.?? 1,4,1
+?..?#??.?#?#???????? 4,8,2
+????????.?# 4,2
+#.????#?#? 1,5
+??#????#????###???? 2,1,9
+??##?????.?????. 4,1
+?#?##?#..????.???.? 6,1
+?#?.#????#???.#? 3,1,3,1,1
+#?#??????? 3,5
+#????#?#?? 2,4
+.?#??#?????##???? 5,7
+????.??#??..??? 4,1
+.##..?..??#??##??. 2,9
+..???#??.## 5,2
+??.??##?????????.?#? 12,3
+.?.?#?..???##? 2,5
+?#??.?#.?. 3,1
+?????#?#???.???.? 1,7,1,1
+???.#...#? 1,1,2
+??????#???#??. 1,3,3
+??#?.??#?##?.? 2,4
+?.#???????#? 1,1,4,2
+???#??????. 4,1
+???#????..#.?? 4,1
+#?...???..?#? 2,1,1,2
+??##???#??#?????# 2,7,3
+???.??????...? 2,2
+?#???????#?. 5,1
+?.?#?#.?.# 4,1
+????##?#???????.?.?# 9,1,1,1,1
+?#????#??#.?? 2,1,1,2
+????#??.??????#??.. 2,7
+###?.?#??? 4,1,1
+?.?##?#..?.???#.? 4,4
+.?#?##???#???.# 1,3,5,1
+.?#.#?##????. 2,8
+????###?#?? 1,1,5
+????..?#???#???. 3,9
+#?####?#..? 1,6,1
+???.???.?#????.? 3,3
+????.????#?..?? 1,3
+.#???.#.??#???? 4,1,2,1
+?.?#???????????. 1,1,8,1
+.??.????#?????? 1,1,3,2
+?.???.##??####? 1,8
+??##?????#??????#? 5,9,1
+##????????.??? 5,2,1
+#????.??#??#?.???#?# 4,6,4,1
+##?##.??.#??#?#??# 5,1,4,1,1
+????#??##?? 1,1,5
+?..#?#??#.???? 1,6,1
+?#???.??.?####???.?. 4,1,8,1
+.???#????#????#? 6,6
+.#??#???#?.? 1,6
+??#???..#? 1,1
+.????###?.? 1,6
+??.?#????.?? 1,2,2,1
+.??????##?#. 1,1,4
+.??#??.???????.??? 3,6
+?.???.???###? 1,1,1,4
+?#????.#???.? 2,1,1,1
+??#?????#??. 1,1,1,1
+????????...?.?##?. 6,1,3
+?.?.???#.?. 1,1
+.??#.?#?#?.??##? 1,1,4,3
+#???.#.????? 1,1,1,4
+??.#?#????? 3,2
+?.??#????? 1,7
+?????#?###?#??. 1,5,3
+????#?##?#????.??.# 8,5,1,1
+?.??#?.??#.? 3,2
+.###????#?????? 3,7,1
+???###??##?????#?? 8,3
+#.?#??#??#?.?##?#?#? 1,1,2,2,8
+#????????????#? 3,1,3,1
+..?????##.?#???#? 2,4,1,2
+??..??????.# 1,1,2,1
+#???#?#?.#?????## 1,5,1,6
+?????##??#??? 1,5,2,1
+?#?#??#????????.? 3,4,3,1
+??.?##?#??#??? 1,5,1,1
+?.????####.? 1,5
+.#..????#?##??.?#..? 1,2,6,2,1
+.#???..#?.?#?????. 4,1,6
+?##?#??#?#?#????.? 6,1,3,1,1
+.?##???####?????#??# 11,1,1,2
+.#.??.##????? 1,2,1,1
+.#??.?.###?.? 3,4
+?.????..?#..#??? 1,2,2,1,2
+????#?????#.????.?.# 6,1,1,1,1,1
+??????..??#??#???? 1,3,4,1,1
+?.???????. 1,1,1
+???..??.?##??#??.?. 3,1,7,1
+???.??..?? 1,1,1
+?#.??##?.. 2,4
+#...??.????? 1,1,1,1
+??.??#?##??.?? 1,6
+?#?..???#####?.? 2,7
+???#??#??.?#?..?###? 7,2,5
+#?#???????.???? 7,1,1,1
+.#???#??#??? 1,2,2,1
+??#???#?????.?#?? 1,1,5,2
+?????.?.?#??#?? 3,1,5
+.#?.???????? 1,3
+?????#??##?#??.#? 1,4,6,1
+??????#?#??#?.??#??? 6,4,4
+.??.??#??.??#??? 1,2,4
+??????.?#?.????. 1,1,1,1,3
+?#??????#. 5,1
+?#???#?#.#??#.?#?? 7,2,1,1
+##??????#????#? 3,5,1
+#.#???#??#??.? 1,1,7,1
+???..??#?????.? 1,3,3
+??#????.???#???.?# 4,5,1,1
+?#??.?#.?? 4,1,1
+.????#???#? 5,3
+.??????#?#??# 1,1,2,4
+?.???#??????...? 1,1,1,4,1
+.?#..?.???? 1,1
+.#?#?????????????? 3,2,1,1,2
+?????#????#?#??.?.?? 10,1
+.?.??????? 1,3
+##?????#..?#??.?? 8,3
+?.?#??#????????#? 1,4,4,3
+?#??.???.?#????#? 3,1,3,1
+##???#?#####?????.? 4,9,1,1
+???.??#??#?.?. 1,2,2,1
+?#?#?.????#???? 4,2,3
+????????#????.? 5,4
+.?#??#????#??#. 6,1,1
+????#???#??.??#? 4,2,2
+..???????# 4,1
+??????#??#??.???? 11,1
+?##.??#.??????? 2,1,2
+.?.??????..?.?????. 5,1
+.??#??.#??????#????? 1,1,1,1,1,8
+?#?.???.#?? 3,2,3
+??.?##????? 3,2
+?..#?###??.??? 7,2
+?.?#?.#??? 1,1,3
+??#..???#??.?. 1,5
+??#??#??.##?#??##.? 7,8
+..?.??.?##. 1,3
+???#?##???#??. 1,11
+?.???.??##??#. 1,1,5
+??#?#??#??????? 1,1,7,1
+???#?.???..#.???. 1,2,3,1,2
+.##?.?#???????.?? 2,8,1
+??.?????#?. 2,2
+#????#??.??#??#?#..# 1,5,3,3,1
+???#?.?.?????????## 1,2,1,3,1,2
+#??????#??.? 3,2,1,1
+#??#..??#????.? 1,1,4,1
+??.?##?#?#..??# 1,2,1,1,2
+?????.??#?#?#??##.? 2,11
+.?????..?. 1,1,1
+?.#???.???#????#? 1,1,1,2,4
+????.?.?#. 1,2
+????#?##????#? 9,1
+?...?????...??#????? 2,3
+?#??..##.? 3,2
+?####????????.???? 4,4,2
+?????????????? 4,3,1,1
+????###?#..??.#? 2,4,1,1,1
+??????##?#?? 3,2,3
+?.#???.##????? 2,1,2,1
+??#?????#???? 2,1,3,1
+??.?#???##??#. 1,1,7
+??????????#?????? 3,2,3
+?????#??.#??? 5,1
+#.???????##?.??#?. 1,8,2
+??##????.#?# 4,2,1,1
+#?.??????.????##? 1,4,3,2
+?#..??..#.?? 1,1,1,1
+?????..?#???????#? 3,10
+#?##???????#????. 5,1,2,1,1
+?#??#??????#?? 2,4,3
+????..????????.#???# 3,1,3,1,2,1
+.???#??.??? 1,3,2
+?.#?..#???.?#?? 1,1,1,1,3
+.?????????#?.###?.. 9,3
+???????#?? 2,1,2
+##.?????.?... 2,1,1,1
+.????.????? 4,3
+??.?#?.?.#? 1,2,1
+.??.?????..?.?# 4,1
+.##.???###??????#?? 2,4,3,3
+#.?##???.#?#???????. 1,3,1,3,3
+??#???????##. 3,5
+?.??.?#??.?? 2,1,2
+??#??###?#?.#?. 8,1
+????#???#?.##.?? 9,2
+#?#????????.. 4,1,1,1
+?..?.?.#????# 1,2
+?.???#?????.#?? 4,1,3
+??.?????.??.???.?.? 2,2
+?????.?.#. 3,1,1
+???.????.?##??##???? 2,3,5
+#??#??.#.?#? 5,1,1
+..?#??#???..#? 8,2
+?.??.??.?.#??.## 2,2,1,1,2
+??????#?#.???#..#? 1,1,3,1,1,1
+?#???????#?? 1,5
+??#?#??#??#?#?????? 12,1,1
+????????#???. 1,1
+.?.???#??#? 1,5
+???#??#?.???? 7,1,1
+??.#??#?????##?? 1,1,3,1,2
+??????????? 1,3,3
+?#?.???#?????? 2,1,3,1
+?????#????#??????? 5,1,1,1,1,1
+?#?#????.???#..?. 4,1,4,1
+????#?#???##??#?.#?? 1,4,6,1
+?#?#?#?##???????. 12,1
+??.????##???.? 1,1,4,1
+#??##.#?.#??##?. 1,3,1,5
+.##.???..#??#?? 2,3,4
+???.??????##?? 1,8
+????##???#??..???? 7,4
+???????.#?. 3,1,2
+???#?.##?? 5,2
+?.??#?.?????? 1,4,1,1
+?.#??.?.?#?#?. 2,4
+.?..#????# 1,1,1
+.#??#???????##??.? 5,1,1,3,1
+??????#??? 2,4
+??#??????.??##????? 3,4,1,5
+.??.?#????#..? 2,3
+..?.?????##?#????#?? 1,14
+???????##??#? 5,2
+????.?#??????????? 2,1,7,1,1
+#????##???? 1,6
+?#?.??.??.? 1,2,2
+????????#. 1,5
+.#?#???.#?????.? 6,6
+????????#?. 1,2
+#??#??##??##?. 8,4
+???##?????...???? 2,2,4
+?#.??.##??????. 1,2,4,1,1
+#??#..##?...?? 1,2,2,2
+.#??????????. 3,1,1,1
+.???.?###?..?#????? 4,2
+???.??.?##.#? 1,2,2
+#.???????? 1,5
+.??????????.????.?? 3,3
+.??????????????.?. 5,5,1
+?#???#?#????#??? 2,4,1,1
+#?##??.?#? 6,1
+??????.?#? 3,2
+??#???????????#.#?.? 1,1,1,6,1,1
+?.#.??????.??.? 1,1,6,1,1
+?.#?#?#.?.?###?? 5,1,6
+.??#?##?#???.?.#.?? 10,1
+??.??###????#. 1,1,6,1
+??..???.#?.?? 1,1
+??..?..?????.?? 1,2
+???.??#?#??#??? 1,1,4,2
+????#??????..????? 7,1,2,1
+?#?#???#.?.?.?#??#. 3,1,1,1,2,1
+??????..#?.? 3,1
+????.???#??###? 2,1,7
+.?.#??###?#?#???#? 1,1,13
+??.??#?#????.#???? 3,2
+????#??#.???#. 1,4,2
+#????.??.?#???..? 5,1,4
+?#??.???#?????#? 3,1,9
+??##??#?????#??. 7,1,1
+????????#????.#??? 3,8,1,1
+???##????#???? 5,5
+??????.???.? 2,1,1
+?????#?#????????#??? 1,6,4,1
+??????##??? 3,3,1
+.#???????. 2,3
+????#????????#.#?? 2,4,2,2
+#..##?????.????.? 1,6,1,1
+???????.???#??..#?? 3,6,2
+??#????#??#.? 2,2,1
+?.?????#?# 1,5
+???##..?.?#.??? 1,2,1,1,1
+??#.?.?#?? 2,1,3
+.??#.?.?????????. 3,1,1,4
+?#???#???.#?? 1,2,1,1
+?.?.?#.??.?.###???? 1,1,1,1,1,6
+??#..#??##??.? 1,7,1
+.?.?.?.????##?? 1,1,1,1,5
+?#??#??#???##???? 2,11,1
+.???????.##?? 1,2,4
+?##???????? 2,4,1
+.#?#?????#?.?? 4,3,1
+?#???#?..##?#?#?.?.? 2,4,2,4
+?#???#??.?#????. 3,1,5
+?#???#?###????#.?? 10,3
+##???.#??# 4,1,2
+#??#.?.#??#??#??.? 1,1,1,7,1
+???#??????.??##????# 8,3,3
+???##??#?#????? 8,1
+.#?#??#?#?#.#?????? 8,1,6
+?.???##??###??#.?? 9,1,1
+??.?.???#?.? 1,1,3,1
+#??????#??##.#.?#. 12,1,2
+????#??#??.??? 2,7,2
+???.#?#.?#????## 1,1,1,8
+???.???#?.?.?. 3,1,1,1
+#????#????.??????#? 8,1,4,2
+?##??.?#.?#.??#??? 4,1,1,1,1,1
+????####?? 7,1
+??????#.??.#. 2,2,2,1
+?###?????????. 8,1
+??#.?#????#?.#.??# 2,7,1,1,1
+????.?#???#???. 1,8
+??#?###????#???.?#?? 1,1,8,1,2,1
+???.?#?#.#..???? 1,1,3,1,2
+?.????#?.??? 1,1,1,2
+???#????###?????##?? 4,6,3
+?..?#?#?#???.????? 1,9,1,1
+#?##????#? 4,2
+???????.?.?#??? 1,3,3
+?.??#?????#???#?? 7,1,1,1
+???.??.???#..??#? 1,2,1,1,4
+?#??.?.?#.?. 2,1
+.?#.?????. 2,2
+?????????? 1,2,2
+.????..??#.? 2,1,1,1
+?????????.???? 1,1,3,1
+??#?#??#???..?.??. 10,1,1
+.??#??##???#??##?? 3,3,9
+.???#???????#????? 1,2,3,1,1,1
+??.???.?.????????#?? 3,3,3
+#???????#? 2,3,2
+#??????????.??#?#? 1,1,2,2,5
+?#?????#??.?.??# 4,4,3
+.?#..?.???# 1,1,4
+.#????#?.?# 1,3,1
+???????????####.# 1,1,1,7,1
+####???#????????.?# 5,3,1,2,2
+??????.???#?? 1,1,6
+????##.??#?.. 3,2
+?????##?.?.#??????? 1,6,3,1,1
+?.???#.??.??#?#. 2,5
+?????.?#?. 1,1,2
+???.?????#??.?#?#.? 1,3,4
+?????#?#?????#??#?#? 1,8,1,6
+?.??.???#.???.?..?? 2,4,1,1,2
+???????????##?.??## 1,1,3,5,3
+.?#?.#.?.??.?.???.? 2,1,1,1,3,1
+.?.#.??.??? 1,1,2
+.?????##.. 1,2
+..??#????????#.?#?? 4,1,5,3
+????????.?#??.? 2,2,1,3,1
+???..####?##??? 2,10
+?.?.??#??. 1,3,1
+#???.??.#..? 3,1,1,1
+##.#?#???#####?????? 2,3,10
+?###?##?.?###?#??? 8,6
+?????###?#?.?.??##. 9,1,4
+??.???.##??###????#? 1,1,13
+?.??##.??.?#?.. 3,3
+?.??????##?.??.?.? 1,1,5,1,1,1
+.????#????.??????? 4,1,3,1
+.?????????##????? 1,11,1
+?????#??#?#? 4,1,1
+#.#??#???..??##????? 1,5,1,4,3
+??#..??.??????#?# 1,1,1,9
+???#.??#?? 1,1,1
+.#??.#?????#??. 1,1,7,1
+?##?????##? 3,4
+????????#.???#?.??? 3,1,1,1,2,2
+?.?#?#??#? 1,4
+?????#.??#?#?.???.?# 1,1,1,5,1,2
+??#?###..#??#?? 6,5
+??????????#??#??.#?? 1,6,2,1,1
+???#??????#?. 5,2
+??##????????## 9,2
+?#??????????#? 1,4,5
+??.?##??#?.#.?? 1,4,1,1,1
+???#??##??#?. 3,6
+???.?????..#??#? 2,2,1,2,1
+.??.????.??#? 1,3,1,2
+??.?.????#? 1,1,1
+???????????.....#?#. 11,1,1
+.?.#????#??.??.?##?. 8,3
+?????????????? 4,4
+?.???#??#??????#??? 3,9,1
+????#??.?? 3,1
+?.??#??#??#.?#.? 9,1,1
+??#??#??????. 7,1
+???##?.#?.??.??? 2,3,1,1,1
+??#?#??#?#???.??#. 1,9,3
+????????#.?????? 6,1,6
+???#?????? 2,4
+?????????..?. 2,5
+?##???????.??# 3,2,1,2
+??.?????.?? 2,5,1
+????????.. 1,2
+#??..??.?..??##??# 1,1,1,1,4,1
+????#????.??.??? 5,1
+?#?.??.??. 1,1,1
+???..#?#??#???#? 1,1,1,2,6
+???????##?. 2,1,3
+??.##??????#???? 3,1,2,1,1
+??.??..????? 2,1,1,2
+???????#??.#?.?## 1,5,1,2
+?#?#?##??##?#?? 12,1
+#..?.#?????.???#???? 1,1,1,3,2,2
+???????...??#?#. 3,2,5
+.??#.??#??.?? 3,1,3,1
+?#????#?#? 1,4
+?#?????#?.????#? 2,3,1,1
+####?????????????? 4,1,1,1,1,1
+#??.#???#??.??.. 1,1,2,1,2
+?????..?#??#??? 4,1,3,1
+..???#????.??#?.???. 6,2,1
+#?#???????#??? 3,5
+????#??????#? 1,3,6
+.??.??.?###?#????#.# 1,1,6,2,1
+.#????????? 3,3,1
+.?.#?#??.?????#??#. 1,2,1,1,4
+##.??????.??? 2,1,2,2
+#???#???.?.? 1,1,1
+?.?.#?????#? 2,4
+???.#????.#??. 2,2
+.?????##?????#???? 9,4
+?#?????????#?? 2,1,3,1
+??.#??.?????#???.? 1,2,6,1
+?.#?#?..?#???. 4,2,1
+.?????..?.???.?? 1,2,3
+?#??#???#???.??#??? 1,9,1,1
+??.?????..?? 1,3,1
+?.#??#????#? 1,1,4
+?.?.??.??#?#? 1,5
+???.??.???#?#??#??# 1,1,1,12
+?.##??#.#? 5,1
+??.????#???.. 1,2,1,2
+???#???..#.? 1,1,1,1
+?.???#??.?#?#??##??# 1,5,1,2,3,1
+????##????.?#?#.? 7,4
+#???##.????? 1,4,1,1
+##?.???.???#? 3,1,1
+????.??#?????? 1,1,4,4
+???#?.##?????? 2,2,1
+???#..??#?##??????? 4,9
+?##?..##.???##???# 3,2,7
+??????????##??????.? 1,1,1,5,3,1
+..??#.?.?# 1,1,1
+???#.???#? 4,1,2
+#.??????#?##??#???. 1,3,11
+?.???#???.??#????.?? 1,6,5,2
+#?..?.????? 1,1,2
+?#?????.?????..?# 3,3,1,2
+?????#?????????#.? 8,1,2,1,1
+??.?.#?#???#??# 1,1,10
+????#???.???????#?? 5,1,10
+??##????##?.??# 3,2,2,1,1
+..#?#?.?.???.#?? 4,2,3
+????#??????????. 1,5,3
+?###??..?#?..# 5,3,1
+??#??..????.?? 3,3,1
+?.#.?#??#? 1,1,5
+???????#?????..?? 9,1,1
+.????????##??.? 2,2,3,1
+.????.???.?#??.??? 1,2,1,2,3
+?.??.?.#?????????.?. 6,1,1
+.??.?.???.?#?#. 1,2,3
+?.?????#####??#?.??? 10,1
+??#.?.???# 1,1,1
+??.??????#?? 1,5,3
+????.????#.???.#? 1,1,2,2,2
+#???#.??????# 2,2,5
+###.?##?.??#. 3,4,2
+#??.??#?###??# 2,2,3,1
+.#???#?#?? 1,5
+.????..???###? 2,7
+.##.??##?? 2,3,1
+??#??#?????## 3,5,2
+.?.??#?##???? 6,1
+??##.?#?#?? 2,4
+?.??#?#????.#. 1,1,6,1
+?.???????..?##??? 6,3
+?????.??#???#??? 1,3,8
+.??#????.??????? 3,1,1,1,1
+..???#.????.###???.? 4,1,6
+?????#?..??##????? 2,1,9
+?.?.??????#??#???? 1,3,10
+??????#?#?? 5,1,1
+?.???#?..??.?.??#?? 1,4,1,1,1,3
+?.??###?#?????##.? 1,12
+?#???#??#?????? 4,1,1,1,1
+???#????.?????.??? 1,6,1,2,1
+?##.#?#?#???.?.??#?? 2,8,1,4
+?#??#??.?#?????#?#? 6,2,4
+#??#?????# 1,2,4
+.#?.?#??.??#?.? 1,2,1,4,1
+?..?#?#?..?#?? 3,1
+???..???.??????#?? 3,1,1,2,3
+?##?#?.?#???#??.?? 2,2,8,2
+?????#??.??#??? 1,1
+?##??#?????????##. 3,12
+##.??#??.#?#?.?#.? 2,3,3,2
+????#.?????#?? 1,2,5
+.?.#???#..?# 3,1,1
+????##..??.???? 4,2
+?.?.?##?????? 3,3
+.???.??###???????#. 1,1,12
+??..##????#???#? 1,4,2,1
+????????#? 2,1,3
+?##??????.???.?#?? 3,1,1,2,3
+#.????.#?#?????##??? 1,1,1,5,2,1
+#?#????#???.???#?.?? 8,1,1,3,1
+?.???.#???.. 1,3,2
+...#..????#?#??# 1,1,5,1
+?.#??.?????. 3,1
+#?..#??????#?#?? 2,1,1,4,1
+?#??.?.?????#??.. 2,5
+??????.?.?????##..? 1,1,1,1,7,1
+?.#???#???. 1,3
+????.?#?????.# 2,1,3,1
+???..?.???????#?#?? 3,1,1,1,3,1
+?#????#?## 3,5
+..??????.###? 4,3
+.??.?##???? 1,4
+????.???...??? 3,2,3
+??????#?..? 2,3
+?#.????#.?.??.#?.?? 1,1,2,2,1,2
+?#?##?.?##??...???# 5,3,4
+???.??????. 1,2,1
+#??..???????##? 2,1,1,3
+??#?...????.?.?????# 1,1,2,1,6
+#???#??#?#???###?? 1,5,1,1,5
+??#???##??????.?? 1,2,3,4,2
+???.???#.##? 1,2,2
+???????##.????. 3,3,4
+#???#?.?#?. 3,1,2
+.???????.#????? 3,1,1,3
+???.?.##.. 1,2
+???.#??#??? 1,1,4
+??????.??#.?#???#? 1,1,1,1,1,3
+????#??.??.???? 4,1
+??.#??#?????????#??# 1,5,1,3,1,1
+??????.#??.??? 1,1,1,3
+??.?#???.????#?#??? 1,3,1,4,1
+????????#?#.? 3,4
+?##.??#??##.. 2,7
+????.??.#??##?.#? 1,1,1,5,2
+?.#???##???##????.? 1,4,6
+???#??????#..? 2,1,1,2
+?.??????.????#???? 1,2,3,5
+.????#??.? 1,5
+.?.????#??# 1,1,2