X-Git-Url: https://git.njae.me.uk/?a=blobdiff_plain;f=src%2Finfi%2Finfi.ipynb;fp=src%2Finfi%2Finfi.ipynb;h=14382fc2f12efaee5b02ee28e0c7686596ab9369;hb=ff1b31bb7b09c4ac1b485942698747b03bd9d9e3;hp=0000000000000000000000000000000000000000;hpb=0d74c4bcfaedfc5ba517406010bea1497473c7e7;p=advent-of-code-17.git

diff --git a/src/infi/infi.ipynb b/src/infi/infi.ipynb
new file mode 100644
index 0000000..14382fc
--- /dev/null
+++ b/src/infi/infi.ipynb
@@ -0,0 +1,429 @@
+{
+ "cells": [
+  {
+   "cell_type": "markdown",
+   "metadata": {},
+   "source": [
+    "# [Bonus problem from Infi](https://aoc.infi.nl/)"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 1,
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "{-# LANGUAGE NegativeLiterals #-}\n",
+    "{-# LANGUAGE FlexibleContexts #-}\n",
+    "{-# LANGUAGE OverloadedStrings #-}\n",
+    "{-# LANGUAGE TypeFamilies #-}"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 95,
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "-- import Prelude hiding ((++))\n",
+    "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",
+    "\n",
+    "import Data.List (nub, sort)"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 3,
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "type Position = (Integer, Integer)"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 5,
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "sc :: Parser ()\n",
+    "sc = L.space (skipSome spaceChar) CA.empty CA.empty\n",
+    "\n",
+    "lexeme = L.lexeme sc\n",
+    "integer = lexeme L.integer\n",
+    "signedInteger = L.signed sc integer\n",
+    "symbol = L.symbol sc\n",
+    "comma = symbol \",\"\n",
+    "\n",
+    "pointP :: Parser Position\n",
+    "pointP = (,) <$> signedInteger <* comma <*> signedInteger\n",
+    "\n",
+    "startPosP = between (symbol \"[\") (symbol \"]\") pointP\n",
+    "stepP = between (symbol \"(\") (symbol \")\") pointP\n",
+    "\n",
+    "descriptionP = (,) <$> (some startPosP) <*> (some stepP)\n",
+    "-- descriptionP = (,) <$> (startPosP `sepBy` space) <*> (stepP `sepBy` space)"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 6,
+   "metadata": {},
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "[(1,2),(3,4)]"
+      ]
+     },
+     "metadata": {},
+     "output_type": "display_data"
+    }
+   ],
+   "source": [
+    "parseTest (some stepP) \"(1,2)(3,4)\""
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 7,
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "successfulParse :: Text -> ([Position], [Position])\n",
+    "successfulParse input = \n",
+    "        case parse descriptionP \"input\" input of\n",
+    "                Left  _error -> ([], [])\n",
+    "                Right description -> description"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 8,
+   "metadata": {},
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "([(0,0),(1,1)],[(1,0),(0,-1),(0,1),(-1,0),(-1,0),(0,1),(0,-1),(1,0)])"
+      ]
+     },
+     "metadata": {},
+     "output_type": "display_data"
+    }
+   ],
+   "source": [
+    "sampleT = T.pack \"[0,0][1,1](1,0)(0,-1)(0,1)(-1,0)(-1,0)(0,1)(0,-1)(1,0)\"\n",
+    "sample = successfulParse sampleT\n",
+    "sample"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 9,
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "chunks :: Int -> [b] -> [[b]]\n",
+    "chunks n xs = (take n xs) : if null xs' then [] else chunks n xs'\n",
+    "    where xs' = drop n xs"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 10,
+   "metadata": {},
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "[\"abc\",\"def\",\"ghi\",\"jkl\"]"
+      ]
+     },
+     "metadata": {},
+     "output_type": "display_data"
+    }
+   ],
+   "source": [
+    "chunks 3 \"abcdefghijkl\""
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 11,
+   "metadata": {},
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "([(0,0),(1,1)],[[(1,0),(0,-1)],[(0,1),(-1,0)],[(-1,0),(0,1)],[(0,-1),(1,0)]])"
+      ]
+     },
+     "metadata": {},
+     "output_type": "display_data"
+    }
+   ],
+   "source": [
+    "(starts, unchunkedSteps) = successfulParse sampleT\n",
+    "steps = chunks (length starts) unchunkedSteps\n",
+    "(starts, steps)"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 15,
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "(+:) (a, b) (c, d) = (a + c, b + d)"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 23,
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "-- applySteps = zipWith (+:)"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 22,
+   "metadata": {},
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "[(1,0),(1,0)]"
+      ]
+     },
+     "metadata": {},
+     "output_type": "display_data"
+    }
+   ],
+   "source": [
+    "zipWith (+:) starts (head steps)"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 24,
+   "metadata": {},
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "[[(0,0),(1,1)],[(1,0),(1,0)],[(1,1),(0,0)],[(0,1),(0,1)],[(0,0),(1,1)]]"
+      ]
+     },
+     "metadata": {},
+     "output_type": "display_data"
+    }
+   ],
+   "source": [
+    "scanl applySteps starts steps"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 32,
+   "metadata": {},
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "2"
+      ]
+     },
+     "metadata": {},
+     "output_type": "display_data"
+    }
+   ],
+   "source": [
+    "length $ filter ((1 ==) . length . nub) $ scanl applySteps starts steps"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 63,
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "visited = scanl (zipWith (+:))"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 64,
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "intersections = filter ((== 1) . length . nub)"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 65,
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "part1 = length . intersections"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 78,
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "bounds ps = ( minimum $ map fst ps\n",
+    "            , maximum $ map fst ps\n",
+    "            , minimum $ map snd ps\n",
+    "            , maximum $ map snd ps\n",
+    "            )"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 118,
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "showPoints (minr, maxr, minc, maxc) ps = unlines [ [ if (r, c) `elem` ps then '*' else ' ' | r <- [minr..maxr] ] | c <- [minc..maxc] ]"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 127,
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "main :: IO ()\n",
+    "main = do \n",
+    "        text <- TIO.readFile \"../../data/infi.txt\"\n",
+    "        let (starts, unchunkedSteps) = successfulParse text\n",
+    "        let steps = chunks (length starts) unchunkedSteps\n",
+    "        let points = visited starts steps\n",
+    "        print $ part1 points\n",
+    "        let bds = bounds $ nub $ concat points\n",
+    "        putStrLn $ showPoints bds $ nub $ concat $ intersections points"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 128,
+   "metadata": {},
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "535\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": [
+    "main"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 107,
+   "metadata": {},
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "\"  \\n  \\n\""
+      ]
+     },
+     "metadata": {},
+     "output_type": "display_data"
+    }
+   ],
+   "source": [
+    "showPoints $ nub $ concat $ visited starts steps"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 114,
+   "metadata": {},
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "[(0,0),(1,1)]"
+      ]
+     },
+     "metadata": {},
+     "output_type": "display_data"
+    }
+   ],
+   "source": [
+    "starts"
+   ]
+  },
+  {
+   "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
+}