1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
{-
Copyright (C) 2017 Yuchen Pei.
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU Affero General Public License as
published by the Free Software Foundation, either version 3 of the
License, or (at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU Affero General Public
License along with this program. If not, see
<https://www.gnu.org/licenses/>.
-}
import Data.List (transpose)
import Data.List.Split (splitOn)
import Data.Map (Map)
import qualified Data.Map as Map
groupD2 :: [([[Char]] -> [[Char]])]
groupD2 = [id, r, t, r . t, t . r . t, r . t . r . t, t . r . t . r . t, r . t . r . t . r . t]
where r = reverse
t = transpose
parseLine :: [Char] -> ([[Char]], [[Char]])
parseLine line = (splitOn "/" xs, splitOn "/" ys)
where [xs, ys] = splitOn " => " line
parseInput :: [Char] -> [([[Char]], [[Char]])]
parseInput xs = parseLine <$> lines xs
getMap :: [([[Char]], [[Char]])] -> Map [[Char]] [[Char]]
getMap xs = Map.fromList [(sigma x, y) | sigma <- groupD2, (x, y) <- xs]
step :: Int -> [[Char]] -> Int
step n xs
| n == 0 = length $ filter (=='#') $ mconcat xs
| otherwise = step (n - 1) (f (if even $ length xs then 2 else 3) xs [])
f :: Int -> [[Char]] -> [[Char]] -> [[Char]]
f _ [] ys = ys
f k xs ys = f k (drop k xs) $ ys ++ (g k (take k xs) (replicate (k + 1) ""))
g :: Int -> [[Char]] -> [[Char]] -> [[Char]]
g k xs ys
| null $ mconcat xs = ys
| otherwise = g k (drop k <$> xs) $ zipWith (++) ys (table Map.! (take k <$> xs))
table :: Map [[Char]] [[Char]]
table = getMap $ parseInput input
initShape :: [[Char]]
initShape = [".#.", "..#", "###"]
solve1 :: Int
solve1 = step 18 initShape
input0 :: [Char]
input0 = "../.# => ##./#../...\n.#./..#/### => #..#/..../..../#..#"
input = "../.. => #.#/#../...\n#./.. => #.#/#.#/.#.\n##/.. => #../.##/##.\n.#/#. => ..#/..#/..#\n##/#. => ##./.#./#..\n##/## => .../.#./.#.\n.../.../... => ..#./##.#/#.##/##.#\n#../.../... => #.##/..../##../###.\n.#./.../... => ##.#/###./#.##/#.#.\n##./.../... => ##.#/#.##/.#../##.#\n#.#/.../... => ...#/..#./.#.#/.###\n###/.../... => ..../#..#/#.##/##..\n.#./#../... => .#../.#.#/..#./.###\n##./#../... => ..##/#.##/#.../#.#.\n..#/#../... => .##./#.##/.#../##..\n#.#/#../... => #.../.##./...#/###.\n.##/#../... => #.##/..##/.#.#/##..\n###/#../... => #..#/...#/..#./...#\n.../.#./... => .###/.#../..#./####\n#../.#./... => ####/#.../.###/##..\n.#./.#./... => ####/#..#/####/#..#\n##./.#./... => .#../..##/..##/#..#\n#.#/.#./... => .#.#/#.##/#.#./.#.#\n###/.#./... => #.##/#.../###./#..#\n.#./##./... => ###./#.../..../.###\n##./##./... => #.##/###./...#/###.\n..#/##./... => .#.#/###./..#./#...\n#.#/##./... => #.#./##../##../..##\n.##/##./... => ..../..#./.##./.#.#\n###/##./... => #.../.#../#.#./#..#\n.../#.#/... => ##../#.##/.##./.##.\n#../#.#/... => #.#./##.#/.###/.###\n.#./#.#/... => ..../####/####/.#.#\n##./#.#/... => #.##/.###/##../#...\n#.#/#.#/... => ###./..##/#.#./####\n###/#.#/... => .##./..../###./....\n.../###/... => ###./.##./##../.###\n#../###/... => .#../#.../###./...#\n.#./###/... => #.#./#.#./####/###.\n##./###/... => ...#/##../###./#.#.\n#.#/###/... => .#.#/#.#./..#./.##.\n###/###/... => ..../#.##/...#/##..\n..#/.../#.. => ...#/#.##/#..#/..##\n#.#/.../#.. => ..#./##.#/.#.#/..##\n.##/.../#.. => ..##/##../#.#./#.##\n###/.../#.. => #.##/###./...#/.##.\n.##/#../#.. => ##../#.##/##.#/##..\n###/#../#.. => #.##/##../.##./.#.#\n..#/.#./#.. => #..#/##../.###/#.#.\n#.#/.#./#.. => .###/#.##/#.#./####\n.##/.#./#.. => #.#./#.../#.##/...#\n###/.#./#.. => .##./.#.#/#.#./.#.#\n.##/##./#.. => .###/.#.#/...#/#.#.\n###/##./#.. => .###/#.##/#.##/#.#.\n#../..#/#.. => #.../##../.##./###.\n.#./..#/#.. => #.../#.##/#.../###.\n##./..#/#.. => ####/..../##.#/.###\n#.#/..#/#.. => ..##/##.#/#.##/#..#\n.##/..#/#.. => ..#./##.#/#.#./..##\n###/..#/#.. => ..##/...#/#..#/#..#\n#../#.#/#.. => #.../..../#.../#.##\n.#./#.#/#.. => ##../####/.#.#/##..\n##./#.#/#.. => .#../..../#.../.##.\n..#/#.#/#.. => .#../.#.#/.#.#/..#.\n#.#/#.#/#.. => ..#./#.##/#.#./..##\n.##/#.#/#.. => #.##/..##/...#/####\n###/#.#/#.. => .##./.#.#/###./#..#\n#../.##/#.. => ..##/.###/.#../##.#\n.#./.##/#.. => #.##/.##./.##./.###\n##./.##/#.. => .##./.#../..../..##\n#.#/.##/#.. => ..../#.#./##.#/###.\n.##/.##/#.. => #..#/..../##.#/..#.\n###/.##/#.. => ####/##.#/#..#/##..\n#../###/#.. => #.#./###./.###/#...\n.#./###/#.. => ##.#/#..#/#.##/..#.\n##./###/#.. => ..#./...#/..##/...#\n..#/###/#.. => .#.#/..../..##/..##\n#.#/###/#.. => #..#/..#./.#../..#.\n.##/###/#.. => .#.#/..../#..#/...#\n###/###/#.. => #.##/##../.#../....\n.#./#.#/.#. => ..../####/.###/.#.#\n##./#.#/.#. => #.##/...#/####/####\n#.#/#.#/.#. => ..#./##../..../#...\n###/#.#/.#. => ####/#.##/###./...#\n.#./###/.#. => ...#/..#./...#/..#.\n##./###/.#. => .##./#.../.#.#/.###\n#.#/###/.#. => ..../..../.#.#/#.##\n###/###/.#. => ..#./###./##.#/....\n#.#/..#/##. => .###/.#../..#./####\n###/..#/##. => #.##/..#./#..#/....\n.##/#.#/##. => #.../##../####/.##.\n###/#.#/##. => ###./..#./..#./##..\n#.#/.##/##. => #.../##../##.#/#.##\n###/.##/##. => ..#./#..#/#.##/####\n.##/###/##. => .#.#/.###/...#/.#..\n###/###/##. => ####/..../.#.#/...#\n#.#/.../#.# => ##.#/#..#/.##./...#\n###/.../#.# => #.#./.#../...#/...#\n###/#../#.# => .#.#/.#../##../##..\n#.#/.#./#.# => ###./#.../####/.#.#\n###/.#./#.# => ##../#.#./..##/##.#\n###/##./#.# => ####/..../###./.##.\n#.#/#.#/#.# => ...#/.##./##../.###\n###/#.#/#.# => ..#./.##./##.#/.#..\n#.#/###/#.# => ...#/..../..#./...#\n###/###/#.# => #.#./#.#./##../....\n###/#.#/### => #.../##.#/.#../..#.\n###/###/### => ##../..#./##../..#."
|
