--- /dev/null
+{
+ "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
+}
projects / advent-of-code-17.git / blobdiff