{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "{-# LANGUAGE NegativeLiterals #-}\n",
    "{-# LANGUAGE FlexibleContexts #-}\n",
    "{-# LANGUAGE OverloadedStrings #-}\n",
    "{-# LANGUAGE TypeFamilies #-}\n",
    "{-# LANGUAGE BangPatterns #-}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import Data.Text (Text)\n",
    "import qualified Data.Text as T\n",
    "import qualified Data.Text.IO as TIO\n",
    "\n",
    "import Text.Megaparsec hiding (State)\n",
    "import qualified Text.Megaparsec.Lexer as L\n",
    "import Text.Megaparsec.Text (Parser)\n",
    "import qualified Control.Applicative as CA\n",
    "-- import Data.Functor (void)\n",
    "\n",
    "import qualified Data.Map.Strict as M\n",
    "import Data.Map.Strict ((!))\n",
    "\n",
    "-- import Data.Vector ((!), (//))\n",
    "-- import qualified Data.Vector as V\n",
    "\n",
    "import Data.List \n",
    "import qualified Data.Functor as F"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "type Grid = M.Map (Int, Int) Bool\n",
    "-- type Grid = [[Char]]\n",
    "-- type Grid = [[Bool]]\n",
    "\n",
    "type ExplodedGrid = M.Map (Int, Int) Grid\n",
    "\n",
    "data Rule = Rule Grid Grid deriving (Eq, Show)\n",
    "\n",
    "rulePre (Rule g _) = g\n",
    "rulePost (Rule _ g) = g"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "onlySpace = (char ' ') <|> (char '\\t')\n",
    "\n",
    "sc :: Parser ()\n",
    "sc = L.space (skipSome onlySpace) CA.empty CA.empty"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "lexeme  = L.lexeme sc\n",
    "\n",
    "symbol = L.symbol sc\n",
    "rowSep = symbol \"/\"\n",
    "ruleJoin = symbol \"=>\"\n",
    "\n",
    "-- present :: Parser Bool\n",
    "present = id True <$ symbol \"#\"\n",
    "\n",
    "-- absent :: Parser Bool\n",
    "absent = id False <$ symbol \".\"\n",
    "\n",
    "rulesP = ruleP `sepBy` space\n",
    "ruleP = Rule <$> gridP <*> (ruleJoin *> gridP)\n",
    "\n",
    "gridP = gridify <$> rowP `sepBy` rowSep\n",
    "    where gridify g = M.fromList $ concat \n",
    "                                    [map (\\(c, v) -> ((r, c), v)) nr | \n",
    "                                             (r, nr) <- zip [0..] \n",
    "                                                            [zip [0..] r | r <- g]]\n",
    "\n",
    "\n",
    "rowP = some (present <|> absent)\n",
    " \n",
    "successfulParse :: Text -> [Rule]\n",
    "successfulParse input = \n",
    "        case parse rulesP \"input\" input of\n",
    "                Left  _error -> [] -- TIO.putStr $ T.pack $ parseErrorPretty err\n",
    "                Right instructions  -> instructions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Rule (fromList [((0,0),True),((0,1),False),((1,0),False),((1,1),False)]) (fromList [((0,0),False),((0,1),True),((0,2),True),((1,0),False),((1,1),True),((1,2),True),((2,0),True),((2,1),False),((2,2),False)])"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "parseTest ruleP \"#./.. => .##/.##/#..\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Rule (fromList [((0,0),True),((0,1),True),((0,2),False),((1,0),True),((1,1),False),((1,2),True),((2,0),False),((2,1),False),((2,2),False)]) (fromList [((0,0),True),((0,1),False),((0,2),True),((0,3),False),((1,0),False),((1,1),True),((1,2),False),((1,3),False),((2,0),False),((2,1),True),((2,2),True),((2,3),False),((3,0),False),((3,1),False),((3,2),False),((3,3),True)])"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "parseTest ruleP \"##./#.#/... => #.#./.#../.##./...#\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "testRule = head $ successfulParse  \"##./#.#/... => #.#./.#../.##./...#\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Rule (fromList [((0,0),True),((0,1),True),((0,2),False),((1,0),True),((1,1),False),((1,2),True),((2,0),False),((2,1),False),((2,2),False)]) (fromList [((0,0),True),((0,1),False),((0,2),True),((0,3),False),((1,0),False),((1,1),True),((1,2),False),((1,3),False),((2,0),False),((2,1),True),((2,2),True),((2,3),False),((3,0),False),((3,1),False),((3,2),False),((3,3),True)])"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "testRule"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Rule (fromList [((0,0),True),((0,1),False),((1,0),False),((1,1),False)]) (fromList [((0,0),False),((0,1),True),((0,2),True),((1,0),False),((1,1),True),((1,2),True),((2,0),True),((2,1),False),((2,2),False)]),Rule (fromList [((0,0),True),((0,1),True),((0,2),False),((1,0),True),((1,1),False),((1,2),True),((2,0),False),((2,1),False),((2,2),False)]) (fromList [((0,0),True),((0,1),False),((0,2),True),((0,3),False),((1,0),False),((1,1),True),((1,2),False),((1,3),False),((2,0),False),((2,1),True),((2,2),True),((2,3),False),((3,0),False),((3,1),False),((3,2),False),((3,3),True)])]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "parseTest rulesP \"#./.. => .##/.##/#..\\n##./#.#/... => #.#./.#../.##./...#\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Rule (fromList [((0,0),True),((0,1),False),((1,0),False),((1,1),False)]) \n",
    "     (fromList [((0,0),False),((0,1),True),((0,2),True),((1,0),False),((1,1),True),((1,2),True),((2,0),True),((2,1),False),((2,2),False),((2,3),True),((2,4),True),((2,5),False),((3,0),True),((3,1),False),((3,2),True),((4,0),False),((4,1),False),((4,2),False)]),\n",
    "     \n",
    "Rule (fromList []) \n",
    "     (fromList [((0,0),True),((0,1),False),((0,2),True),((0,3),False),((1,0),False),((1,1),True),((1,2),False),((1,3),False),((2,0),False),((2,1),True),((2,2),True),((2,3),False),((3,0),False),((3,1),False),((3,2),False),((3,3),True)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "g = [[False,True,True],[False,True,True],[True,False,False]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[((0,0),False),((0,1),True),((0,2),True),((1,0),False),((1,1),True),((1,2),True),((2,0),True),((2,1),False),((2,2),False)]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "concat [map (\\(c, v) -> ((r, c), v)) nr | (r, nr) <- zip [0..] [zip [0..] r | r <- g]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [],
   "source": [
    "bounds :: M.Map (Int, Int) a -> (Int, Int)\n",
    "bounds grid = (maximum $ map fst $ M.keys grid, maximum $ map snd $ M.keys grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(3,3)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "bounds (rulePost testRule)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "showGrid g = unlines [[showChar $ M.findWithDefault False (r, c) g | \n",
    "                c <- [0..cm] ] | r <- [0..rm] ]\n",
    "    where (rm, cm) = bounds g\n",
    "          showChar True = '#'\n",
    "          showChar False = '.'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#.#.\n",
       ".#..\n",
       ".##.\n",
       "...#"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "putStrLn $ showGrid $ rulePost testRule"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "initialGrid = case parse gridP \"\" \".#./..#/###\" of \n",
    "                Left _ -> M.empty \n",
    "                Right g -> g"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "fromList [((0,0),False),((0,1),True),((0,2),False),((1,0),False),((1,1),False),((1,2),True),((2,0),True),((2,1),True),((2,2),True)]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "initialGrid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ".#.\n",
       "..#\n",
       "###"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "putStrLn $ showGrid initialGrid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "reflectH g = M.fromList [((r, c) , M.findWithDefault False (rm - r, c) g) | r <- [0..rm], c <- [0..cm] ]\n",
    "    where (rm, cm) = bounds g"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "###\n",
       "..#\n",
       ".#."
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "putStrLn $ showGrid $ reflectH initialGrid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "reflectV g = M.fromList [((r, c) , M.findWithDefault False (r, cm - c) g) | r <- [0..rm], c <- [0..cm] ]\n",
    "    where (rm, cm) = bounds g"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ".#.\n",
       "#..\n",
       "###"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "putStrLn $ showGrid $ reflectV initialGrid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "transpose g = M.fromList [((c, r) , M.findWithDefault False (r, c) g) | r <- [0..rm], c <- [0..cm] ]\n",
    "    where (rm, cm) = bounds g"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "..#\n",
       "#.#\n",
       ".##"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "putStrLn $ showGrid $ transpose initialGrid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "allArrangements grid = map (\\f -> f grid) [ id\n",
    "                                          , reflectH\n",
    "                                          , reflectV\n",
    "                                          , transpose\n",
    "                                          , reflectH . transpose\n",
    "                                          , reflectV . transpose\n",
    "                                          , reflectH . reflectV . transpose\n",
    "                                          , reflectV . reflectH\n",
    "                                          ]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[\".#.\\n..#\\n###\\n\",\"###\\n..#\\n.#.\\n\",\".#.\\n#..\\n###\\n\",\"..#\\n#.#\\n.##\\n\",\".##\\n#.#\\n..#\\n\",\"#..\\n#.#\\n##.\\n\",\"##.\\n#.#\\n#..\\n\",\"###\\n#..\\n.#.\\n\"]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "map showGrid $ allArrangements initialGrid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "sampleRulesCompact = successfulParse \"../.# => ##./#../...\\n.#./..#/### => #..#/..../..../#..#\"\n",
    "length sampleRulesCompact"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "expandRule rule = [Rule l (rulePost rule) | l <- allArrangements (rulePre rule)]\n",
    "expandRules = concatMap expandRule"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[\"##.\\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\"]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "[showGrid (rulePre r) ++ \"=>\" ++ showGrid (rulePost r) | r <- expandRule testRule]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "16"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "length $ expandRules sampleRulesCompact"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "readRules = expandRules . successfulParse"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Rule (fromList [((0,0),False),((0,1),False),((1,0),False),((1,1),True)]) (fromList [((0,0),True),((0,1),True),((0,2),False),((1,0),True),((1,1),False),((1,2),False),((2,0),False),((2,1),False),((2,2),False)]),Rule (fromList [((0,0),False),((0,1),True),((1,0),False),((1,1),False)]) (fromList [((0,0),True),((0,1),True),((0,2),False),((1,0),True),((1,1),False),((1,2),False),((2,0),False),((2,1),False),((2,2),False)]),Rule (fromList [((0,0),False),((0,1),False),((1,0),True),((1,1),False)]) (fromList [((0,0),True),((0,1),True),((0,2),False),((1,0),True),((1,1),False),((1,2),False),((2,0),False),((2,1),False),((2,2),False)]),Rule (fromList [((0,0),False),((0,1),False),((1,0),False),((1,1),True)]) (fromList [((0,0),True),((0,1),True),((0,2),False),((1,0),True),((1,1),False),((1,2),False),((2,0),False),((2,1),False),((2,2),False)]),Rule (fromList [((0,0),False),((0,1),True),((1,0),False),((1,1),False)]) (fromList [((0,0),True),((0,1),True),((0,2),False),((1,0),True),((1,1),False),((1,2),False),((2,0),False),((2,1),False),((2,2),False)]),Rule (fromList [((0,0),False),((0,1),False),((1,0),True),((1,1),False)]) (fromList [((0,0),True),((0,1),True),((0,2),False),((1,0),True),((1,1),False),((1,2),False),((2,0),False),((2,1),False),((2,2),False)]),Rule (fromList [((0,0),True),((0,1),False),((1,0),False),((1,1),False)]) (fromList [((0,0),True),((0,1),True),((0,2),False),((1,0),True),((1,1),False),((1,2),False),((2,0),False),((2,1),False),((2,2),False)]),Rule (fromList [((0,0),True),((0,1),False),((1,0),False),((1,1),False)]) (fromList [((0,0),True),((0,1),True),((0,2),False),((1,0),True),((1,1),False),((1,2),False),((2,0),False),((2,1),False),((2,2),False)]),Rule (fromList [((0,0),False),((0,1),True),((0,2),False),((1,0),False),((1,1),False),((1,2),True),((2,0),True),((2,1),True),((2,2),True)]) (fromList [((0,0),True),((0,1),False),((0,2),False),((0,3),True),((1,0),False),((1,1),False),((1,2),False),((1,3),False),((2,0),False),((2,1),False),((2,2),False),((2,3),False),((3,0),True),((3,1),False),((3,2),False),((3,3),True)]),Rule (fromList [((0,0),True),((0,1),True),((0,2),True),((1,0),False),((1,1),False),((1,2),True),((2,0),False),((2,1),True),((2,2),False)]) (fromList [((0,0),True),((0,1),False),((0,2),False),((0,3),True),((1,0),False),((1,1),False),((1,2),False),((1,3),False),((2,0),False),((2,1),False),((2,2),False),((2,3),False),((3,0),True),((3,1),False),((3,2),False),((3,3),True)]),Rule (fromList [((0,0),False),((0,1),True),((0,2),False),((1,0),True),((1,1),False),((1,2),False),((2,0),True),((2,1),True),((2,2),True)]) (fromList [((0,0),True),((0,1),False),((0,2),False),((0,3),True),((1,0),False),((1,1),False),((1,2),False),((1,3),False),((2,0),False),((2,1),False),((2,2),False),((2,3),False),((3,0),True),((3,1),False),((3,2),False),((3,3),True)]),Rule (fromList [((0,0),False),((0,1),False),((0,2),True),((1,0),True),((1,1),False),((1,2),True),((2,0),False),((2,1),True),((2,2),True)]) (fromList [((0,0),True),((0,1),False),((0,2),False),((0,3),True),((1,0),False),((1,1),False),((1,2),False),((1,3),False),((2,0),False),((2,1),False),((2,2),False),((2,3),False),((3,0),True),((3,1),False),((3,2),False),((3,3),True)]),Rule (fromList [((0,0),False),((0,1),True),((0,2),True),((1,0),True),((1,1),False),((1,2),True),((2,0),False),((2,1),False),((2,2),True)]) (fromList [((0,0),True),((0,1),False),((0,2),False),((0,3),True),((1,0),False),((1,1),False),((1,2),False),((1,3),False),((2,0),False),((2,1),False),((2,2),False),((2,3),False),((3,0),True),((3,1),False),((3,2),False),((3,3),True)]),Rule (fromList [((0,0),True),((0,1),False),((0,2),False),((1,0),True),((1,1),False),((1,2),True),((2,0),True),((2,1),True),((2,2),False)]) (fromList [((0,0),True),((0,1),False),((0,2),False),((0,3),True),((1,0),False),((1,1),False),((1,2),False),((1,3),False),((2,0),False),((2,1),False),((2,2),False),((2,3),False),((3,0),True),((3,1),False),((3,2),False),((3,3),True)]),Rule (fromList [((0,0),True),((0,1),True),((0,2),False),((1,0),True),((1,1),False),((1,2),True),((2,0),True),((2,1),False),((2,2),False)]) (fromList [((0,0),True),((0,1),False),((0,2),False),((0,3),True),((1,0),False),((1,1),False),((1,2),False),((1,3),False),((2,0),False),((2,1),False),((2,2),False),((2,3),False),((3,0),True),((3,1),False),((3,2),False),((3,3),True)]),Rule (fromList [((0,0),True),((0,1),True),((0,2),True),((1,0),True),((1,1),False),((1,2),False),((2,0),False),((2,1),True),((2,2),False)]) (fromList [((0,0),True),((0,1),False),((0,2),False),((0,3),True),((1,0),False),((1,1),False),((1,2),False),((1,3),False),((2,0),False),((2,1),False),((2,2),False),((2,3),False),((3,0),True),((3,1),False),((3,2),False),((3,3),True)])]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "sampleRules = readRules \"../.# => ##./#../...\\n.#./..#/### => #..#/..../..../#..#\"\n",
    "sampleRules"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 125,
   "metadata": {},
   "outputs": [],
   "source": [
    "text <- TIO.readFile \"../../data/advent21.txt\"\n",
    "rules = readRules text"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 126,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "864"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "length rules"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "apply rules grid = rulePost thisRule\n",
    "    where ri = head $ findIndices (\\r -> rulePre r == grid) rules\n",
    "          thisRule = rules!!ri"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#..#\n",
       "....\n",
       "....\n",
       "#..#"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "putStrLn $ showGrid $ apply sampleRules initialGrid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [],
   "source": [
    "subGrid :: Int -> Grid -> Int -> Int -> Grid\n",
    "subGrid n g bigR bigC = M.fromList [ ((r, c), \n",
    "                                      M.findWithDefault False (r + rStep, c + cStep) g) \n",
    "                                   | r <- [0..(n - 1)], c <- [0..(n - 1)]\n",
    "                                   ]\n",
    "    where rStep = bigR * n\n",
    "          cStep = bigC * n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [],
   "source": [
    "explodeGrid' :: Int -> Grid -> ExplodedGrid\n",
    "explodeGrid' n g = M.fromList [((bigR, bigC), subGrid n g bigR bigC) | bigR <- [0..bigRm], bigC <- [0..bigCm]]\n",
    "    where (rm, cm) = bounds g\n",
    "          bigRm = (rm + 1) `div` n - 1\n",
    "          bigCm = (cm + 1) `div` n - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "metadata": {},
   "outputs": [],
   "source": [
    "explodeGrid :: Grid -> ExplodedGrid\n",
    "explodeGrid g = if (rm + 1) `rem` 2 == 0 \n",
    "                then explodeGrid' 2 g\n",
    "                else explodeGrid' 3 g\n",
    "    where (rm, cm) = bounds g"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "fromList [((0,0),\"#.\\n..\\n\"),((0,1),\".#\\n..\\n\"),((1,0),\"..\\n#.\\n\"),((1,1),\"..\\n.#\\n\")]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "testEg = explodeGrid $ apply sampleRules initialGrid\n",
    "M.map showGrid testEg"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {},
   "outputs": [],
   "source": [
    "explodedRows eg = [M.filterWithKey (\\(r, _) _ -> r == row) eg | row <- [0..rowMax] ]\n",
    "    where (rowMax, _) = bounds eg"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[fromList [((0,0),fromList [((0,0),True),((0,1),False),((1,0),False),((1,1),False)]),((0,1),fromList [((0,0),False),((0,1),True),((1,0),False),((1,1),False)])],fromList [((1,0),fromList [((0,0),False),((0,1),False),((1,0),True),((1,1),False)]),((1,1),fromList [((0,0),False),((0,1),False),((1,0),False),((1,1),True)])]]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "explodedRows testEg"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {},
   "outputs": [],
   "source": [
    "(>-<) g1 g2 = M.union g1 g2'\n",
    "    where (_, cm) = bounds g1\n",
    "          g2' = M.mapKeys (\\(r, c) -> (r, c + cm + 1)) g2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {},
   "outputs": [],
   "source": [
    "(>|<) g1 g2 = M.union g1 g2'\n",
    "    where (rm, _) = bounds g1\n",
    "          g2' = M.mapKeys (\\(r, c) -> (r + rm + 1, c)) g2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "fromList [((0,0),True),((0,1),False),((1,0),False),((1,1),False)]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "M.findWithDefault M.empty (0, 0) testEg"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<style>/* Styles used for the Hoogle display in the pager */\n",
       ".hoogle-doc {\n",
       "display: block;\n",
       "padding-bottom: 1.3em;\n",
       "padding-left: 0.4em;\n",
       "}\n",
       ".hoogle-code {\n",
       "display: block;\n",
       "font-family: monospace;\n",
       "white-space: pre;\n",
       "}\n",
       ".hoogle-text {\n",
       "display: block;\n",
       "}\n",
       ".hoogle-name {\n",
       "color: green;\n",
       "font-weight: bold;\n",
       "}\n",
       ".hoogle-head {\n",
       "font-weight: bold;\n",
       "}\n",
       ".hoogle-sub {\n",
       "display: block;\n",
       "margin-left: 0.4em;\n",
       "}\n",
       ".hoogle-package {\n",
       "font-weight: bold;\n",
       "font-style: italic;\n",
       "}\n",
       ".hoogle-module {\n",
       "font-weight: bold;\n",
       "}\n",
       ".hoogle-class {\n",
       "font-weight: bold;\n",
       "}\n",
       ".get-type {\n",
       "color: green;\n",
       "font-weight: bold;\n",
       "font-family: monospace;\n",
       "display: block;\n",
       "white-space: pre-wrap;\n",
       "}\n",
       ".show-type {\n",
       "color: green;\n",
       "font-weight: bold;\n",
       "font-family: monospace;\n",
       "margin-left: 1em;\n",
       "}\n",
       ".mono {\n",
       "font-family: monospace;\n",
       "display: block;\n",
       "}\n",
       ".err-msg {\n",
       "color: red;\n",
       "font-style: italic;\n",
       "font-family: monospace;\n",
       "white-space: pre;\n",
       "display: block;\n",
       "}\n",
       "#unshowable {\n",
       "color: red;\n",
       "font-weight: bold;\n",
       "}\n",
       ".err-msg.in.collapse {\n",
       "padding-top: 0.7em;\n",
       "}\n",
       ".highlight-code {\n",
       "white-space: pre;\n",
       "font-family: monospace;\n",
       "}\n",
       ".suggestion-warning { \n",
       "font-weight: bold;\n",
       "color: rgb(200, 130, 0);\n",
       "}\n",
       ".suggestion-error { \n",
       "font-weight: bold;\n",
       "color: red;\n",
       "}\n",
       ".suggestion-name {\n",
       "font-weight: bold;\n",
       "}\n",
       "</style><div class=\"suggestion-name\" style=\"clear:both;\">Redundant bracket</div><div class=\"suggestion-row\" style=\"float: left;\"><div class=\"suggestion-warning\">Found:</div><div class=\"highlight-code\" id=\"haskell\">(M.findWithDefault M.empty (0, 1) testEg) >-<\n",
       "  (M.findWithDefault M.empty (0, 0) testEg)</div></div><div class=\"suggestion-row\" style=\"float: left;\"><div class=\"suggestion-warning\">Why Not:</div><div class=\"highlight-code\" id=\"haskell\">M.findWithDefault M.empty (0, 1) testEg >-<\n",
       "  (M.findWithDefault M.empty (0, 0) testEg)</div></div><div class=\"suggestion-name\" style=\"clear:both;\">Redundant bracket</div><div class=\"suggestion-row\" style=\"float: left;\"><div class=\"suggestion-warning\">Found:</div><div class=\"highlight-code\" id=\"haskell\">(M.findWithDefault M.empty (0, 1) testEg) >-<\n",
       "  (M.findWithDefault M.empty (0, 0) testEg)</div></div><div class=\"suggestion-row\" style=\"float: left;\"><div class=\"suggestion-warning\">Why Not:</div><div class=\"highlight-code\" id=\"haskell\">(M.findWithDefault M.empty (0, 1) testEg) >-<\n",
       "  M.findWithDefault M.empty (0, 0) testEg</div></div>"
      ],
      "text/plain": [
       "Line 1: Redundant bracket\n",
       "Found:\n",
       "(M.findWithDefault M.empty (0, 1) testEg) >-<\n",
       "  (M.findWithDefault M.empty (0, 0) testEg)\n",
       "Why not:\n",
       "M.findWithDefault M.empty (0, 1) testEg >-<\n",
       "  (M.findWithDefault M.empty (0, 0) testEg)Line 1: Redundant bracket\n",
       "Found:\n",
       "(M.findWithDefault M.empty (0, 1) testEg) >-<\n",
       "  (M.findWithDefault M.empty (0, 0) testEg)\n",
       "Why not:\n",
       "(M.findWithDefault M.empty (0, 1) testEg) >-<\n",
       "  M.findWithDefault M.empty (0, 0) testEg"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "\".##.\\n....\\n\""
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "showGrid $ (M.findWithDefault M.empty (0, 1) testEg) >-< (M.findWithDefault M.empty (0, 0) testEg)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<style>/* Styles used for the Hoogle display in the pager */\n",
       ".hoogle-doc {\n",
       "display: block;\n",
       "padding-bottom: 1.3em;\n",
       "padding-left: 0.4em;\n",
       "}\n",
       ".hoogle-code {\n",
       "display: block;\n",
       "font-family: monospace;\n",
       "white-space: pre;\n",
       "}\n",
       ".hoogle-text {\n",
       "display: block;\n",
       "}\n",
       ".hoogle-name {\n",
       "color: green;\n",
       "font-weight: bold;\n",
       "}\n",
       ".hoogle-head {\n",
       "font-weight: bold;\n",
       "}\n",
       ".hoogle-sub {\n",
       "display: block;\n",
       "margin-left: 0.4em;\n",
       "}\n",
       ".hoogle-package {\n",
       "font-weight: bold;\n",
       "font-style: italic;\n",
       "}\n",
       ".hoogle-module {\n",
       "font-weight: bold;\n",
       "}\n",
       ".hoogle-class {\n",
       "font-weight: bold;\n",
       "}\n",
       ".get-type {\n",
       "color: green;\n",
       "font-weight: bold;\n",
       "font-family: monospace;\n",
       "display: block;\n",
       "white-space: pre-wrap;\n",
       "}\n",
       ".show-type {\n",
       "color: green;\n",
       "font-weight: bold;\n",
       "font-family: monospace;\n",
       "margin-left: 1em;\n",
       "}\n",
       ".mono {\n",
       "font-family: monospace;\n",
       "display: block;\n",
       "}\n",
       ".err-msg {\n",
       "color: red;\n",
       "font-style: italic;\n",
       "font-family: monospace;\n",
       "white-space: pre;\n",
       "display: block;\n",
       "}\n",
       "#unshowable {\n",
       "color: red;\n",
       "font-weight: bold;\n",
       "}\n",
       ".err-msg.in.collapse {\n",
       "padding-top: 0.7em;\n",
       "}\n",
       ".highlight-code {\n",
       "white-space: pre;\n",
       "font-family: monospace;\n",
       "}\n",
       ".suggestion-warning { \n",
       "font-weight: bold;\n",
       "color: rgb(200, 130, 0);\n",
       "}\n",
       ".suggestion-error { \n",
       "font-weight: bold;\n",
       "color: red;\n",
       "}\n",
       ".suggestion-name {\n",
       "font-weight: bold;\n",
       "}\n",
       "</style><div class=\"suggestion-name\" style=\"clear:both;\">Redundant bracket</div><div class=\"suggestion-row\" style=\"float: left;\"><div class=\"suggestion-warning\">Found:</div><div class=\"highlight-code\" id=\"haskell\">(M.findWithDefault M.empty (0, 1) testEg) >|<\n",
       "  (M.findWithDefault M.empty (0, 0) testEg)</div></div><div class=\"suggestion-row\" style=\"float: left;\"><div class=\"suggestion-warning\">Why Not:</div><div class=\"highlight-code\" id=\"haskell\">M.findWithDefault M.empty (0, 1) testEg >|<\n",
       "  (M.findWithDefault M.empty (0, 0) testEg)</div></div><div class=\"suggestion-name\" style=\"clear:both;\">Redundant bracket</div><div class=\"suggestion-row\" style=\"float: left;\"><div class=\"suggestion-warning\">Found:</div><div class=\"highlight-code\" id=\"haskell\">(M.findWithDefault M.empty (0, 1) testEg) >|<\n",
       "  (M.findWithDefault M.empty (0, 0) testEg)</div></div><div class=\"suggestion-row\" style=\"float: left;\"><div class=\"suggestion-warning\">Why Not:</div><div class=\"highlight-code\" id=\"haskell\">(M.findWithDefault M.empty (0, 1) testEg) >|<\n",
       "  M.findWithDefault M.empty (0, 0) testEg</div></div>"
      ],
      "text/plain": [
       "Line 1: Redundant bracket\n",
       "Found:\n",
       "(M.findWithDefault M.empty (0, 1) testEg) >|<\n",
       "  (M.findWithDefault M.empty (0, 0) testEg)\n",
       "Why not:\n",
       "M.findWithDefault M.empty (0, 1) testEg >|<\n",
       "  (M.findWithDefault M.empty (0, 0) testEg)Line 1: Redundant bracket\n",
       "Found:\n",
       "(M.findWithDefault M.empty (0, 1) testEg) >|<\n",
       "  (M.findWithDefault M.empty (0, 0) testEg)\n",
       "Why not:\n",
       "(M.findWithDefault M.empty (0, 1) testEg) >|<\n",
       "  M.findWithDefault M.empty (0, 0) testEg"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "\".#\\n..\\n#.\\n..\\n\""
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "showGrid $ (M.findWithDefault M.empty (0, 1) testEg) >|< (M.findWithDefault M.empty (0, 0) testEg)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {},
   "outputs": [],
   "source": [
    "contractExploded :: ExplodedGrid -> Grid\n",
    "contractExploded gs = foldl1 (>|<) $ map (foldl1 (>-<)) rows\n",
    "    where rows = explodedRows gs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\"#..#\\n....\\n....\\n#..#\\n\""
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "showGrid $ contractExploded testEg"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "##.##.\n",
       "#..#..\n",
       "......\n",
       "##.##.\n",
       "#..#..\n",
       "......"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "putStrLn $ showGrid $ contractExploded $ M.map (apply sampleRules) testEg"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 128,
   "metadata": {},
   "outputs": [],
   "source": [
    "applyOnce rules g = contractExploded $ M.map (apply rules) $ explodeGrid g"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 135,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ".#.#.#.#..##..#.##\n",
       ".#.#...#..##....##\n",
       "..####..##..####..\n",
       "..#.#..##.###.#.#.\n",
       "....#..##.###...#.\n",
       "###..##..#..###..#\n",
       "..#.##..#.##.##...\n",
       "....##....##.##.##\n",
       "####..####..#..##.\n",
       "#.#.#.#.#.#.....#.\n",
       "#...#.#...#..##.#.\n",
       "###..####..###...#\n",
       "..#.##..#.##..#.##\n",
       "....##....##....##\n",
       "####..####..####..\n",
       "#.#.#.#.#.#.#.#.#.\n",
       "#...#.#...#.#...#.\n",
       "###..####..####..#"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "putStrLn $ showGrid $ (!! 5) $ iterate (applyOnce rules) initialGrid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 131,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ".#\n",
       "##"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "putStrLn $ showGrid $ (!(1, 2)) $ explodeGrid $ last $ take 3 $ iterate (applyOnce rules) initialGrid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 136,
   "metadata": {},
   "outputs": [],
   "source": [
    "countLit = M.size . M.filter id"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 137,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "countLit initialGrid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 142,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "##.##.\n",
       "#..#..\n",
       "......\n",
       "##.##.\n",
       "#..#..\n",
       "......"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "putStrLn $ showGrid $ (!! 2) $ iterate (applyOnce sampleRules) initialGrid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 143,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "countLit $ (!! 2) $ iterate (applyOnce sampleRules) initialGrid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 144,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "158"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "countLit $ (!! 5) $ iterate (applyOnce rules) initialGrid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 145,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2301762"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "countLit $ (!! 18) $ iterate (applyOnce rules) initialGrid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Haskell",
   "language": "haskell",
   "name": "haskell"
  },
  "language_info": {
   "codemirror_mode": "ihaskell",
   "file_extension": ".hs",
   "name": "haskell",
   "version": "8.0.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}