-- Author: Yuchen Pei (me@ypei.me)
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###/###/### => ##../..#./##../..#."