X-Git-Url: https://git.njae.me.uk/?a=blobdiff_plain;f=src%2Fadvent20%2Fadvent20.ipynb;fp=src%2Fadvent20%2Fadvent20.ipynb;h=c73e459f21e4eaf1dc98aef0987c0a324abd8367;hb=3a37ea61c6b83fc84fcf3369c77c399a91fd9759;hp=0000000000000000000000000000000000000000;hpb=9c5d774abcb63cc3c97b40d98540fe843e51c03d;p=advent-of-code-17.git diff --git a/src/advent20/advent20.ipynb b/src/advent20/advent20.ipynb new file mode 100644 index 0000000..c73e459 --- /dev/null +++ b/src/advent20/advent20.ipynb @@ -0,0 +1,991 @@ +{ + "cells": [ + { + "cell_type": "code", + "execution_count": 50, + "metadata": {}, + "outputs": [], + "source": [ + "{-# LANGUAGE NegativeLiterals #-}\n", + "{-# LANGUAGE FlexibleContexts #-}\n", + "{-# LANGUAGE OverloadedStrings #-}\n", + "{-# LANGUAGE TypeFamilies #-}\n", + "{-# LANGUAGE BangPatterns #-}" + ] + }, + { + "cell_type": "code", + "execution_count": 106, + "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", + "\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", + "\n", + "import qualified Data.Set as S" + ] + }, + { + "cell_type": "code", + "execution_count": 52, + "metadata": {}, + "outputs": [], + "source": [ + "type Vec = V.Vector Integer\n", + "\n", + "data Particle = Particle \n", + " { position :: Vec\n", + " , velocity :: Vec\n", + " , acceleration :: Vec\n", + " } deriving (Show, Eq)" + ] + }, + { + "cell_type": "code", + "execution_count": 53, + "metadata": {}, + "outputs": [], + "source": [ + "sc :: Parser ()\n", + "sc = L.space (skipSome spaceChar) CA.empty CA.empty\n", + "\n", + "lexeme = L.lexeme sc\n", + "\n", + "integer = lexeme L.integer\n", + "signedInteger = L.signed sc integer\n", + "\n", + "symbol = L.symbol sc\n", + "separator = symbol \", \"\n", + "comma = symbol \",\"\n", + "\n", + "particlesP = particleP `sepBy` space\n", + "particleP = particlify <$> (symbol \"p=\" *> vecP <* separator)\n", + " <*> (symbol \"v=\" *> vecP <* separator)\n", + " <*> (symbol \"a=\" *> vecP)\n", + " where particlify p v a = Particle {position = p, velocity = v, acceleration = a}\n", + "\n", + "\n", + "vecP = V.fromList <$> between (symbol \"<\") (symbol \">\") (signedInteger `sepBy` comma)\n", + "\n", + "\n", + "successfulParse :: Text -> [Particle]\n", + "successfulParse input = \n", + " case parse particlesP \"input\" input of\n", + " Left _error -> [] -- TIO.putStr $ T.pack $ parseErrorPretty err\n", + " Right instructions -> instructions" + ] + }, + { + "cell_type": "code", + "execution_count": 54, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "[-833,-499,-1391]" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "parseTest vecP \"<-833,-499,-1391>\"" + ] + }, + { + "cell_type": "code", + "execution_count": 55, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "Particle {position = [3,0,0], velocity = [2,0,0], acceleration = [-1,0,0]}" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "parseTest particleP \"p=< 3,0,0>, v=<2,0,0>, a=<-1,0,0>\"" + ] + }, + { + "cell_type": "code", + "execution_count": 56, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "Particle {position = [4,0,0], velocity = [0,0,0], acceleration = [-2,0,0]}" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "parseTest particleP \"p=< 4,0,0>, v=< 0,0,0>, a=<-2,0,0>\"" + ] + }, + { + "cell_type": "code", + "execution_count": 57, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "[Particle {position = [3,0,0], velocity = [2,0,0], acceleration = [-1,0,0]},Particle {position = [4,0,0], velocity = [0,0,0], acceleration = [-2,0,0]}]" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "parseTest particlesP \"p=< 3,0,0>, v=<2,0,0>, a=<-1,0,0>\\np=< 4,0,0>, v=< 0,0,0>, a=<-2,0,0>\"" + ] + }, + { + "cell_type": "code", + "execution_count": 58, + "metadata": {}, + "outputs": [], + "source": [ + "(p0:p1:_) = successfulParse \"p=< 3,0,0>, v=<2,0,0>, a=<-1,0,0>\\np=< 4,0,0>, v=< 0,0,0>, a=<-2,0,0>\"" + ] + }, + { + "cell_type": "code", + "execution_count": 59, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "Particle {position = [3,0,0], velocity = [2,0,0], acceleration = [-1,0,0]}" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "p0" + ] + }, + { + "cell_type": "code", + "execution_count": 60, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "Particle {position = [4,0,0], velocity = [0,0,0], acceleration = [-2,0,0]}" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "p1" + ] + }, + { + "cell_type": "code", + "execution_count": 61, + "metadata": {}, + "outputs": [], + "source": [ + "step :: Particle -> Particle\n", + "step particle = particle {position = p', velocity = v'}\n", + " where pv' = V.zipWith3 updatePV (position particle) (velocity particle) (acceleration particle)\n", + " !(p', v') = V.unzip pv'\n", + " updatePV p v a = (p + v + a, v + a)" + ] + }, + { + "cell_type": "code", + "execution_count": 62, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "Particle {position = [-2,0,0], velocity = [-4,0,0], acceleration = [-2,0,0]}" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "step $ step p1" + ] + }, + { + "cell_type": "code", + "execution_count": 63, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "Particle {position = [3,0,0], velocity = [2,0,0], acceleration = [-2,0,1]}" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "p2 = p0 {acceleration = V.fromList [-2, 0, 1]}\n", + "p2" + ] + }, + { + "cell_type": "code", + "execution_count": 64, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "Particle {position = [1,0,3], velocity = [-2,0,2], acceleration = [-2,0,1]}" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "step $ step p2" + ] + }, + { + "cell_type": "code", + "execution_count": 65, + "metadata": {}, + "outputs": [], + "source": [ + "quiescent :: Particle -> Bool\n", + "quiescent particle = and qDimensions\n", + " where qDimensions = V.zipWith3 sameSigns (position particle) (velocity particle) (acceleration particle)\n", + " sameSigns !p !v !a = if a == 0 && v == 0\n", + " then True\n", + " else if a == 0\n", + " then signum p == signum v\n", + " else signum p == signum v && signum v == signum a" + ] + }, + { + "cell_type": "code", + "execution_count": 66, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "False" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "quiescent p2" + ] + }, + { + "cell_type": "code", + "execution_count": 67, + "metadata": {}, + "outputs": [], + "source": [ + "simulate :: [Particle] -> [Particle]\n", + "simulate particles = \n", + " if all quiescent particles\n", + " then particles\n", + " else simulate (map step particles)" + ] + }, + { + "cell_type": "code", + "execution_count": 68, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "[Particle {position = [3,0,0], velocity = [2,0,0], acceleration = [-1,0,0]},Particle {position = [4,0,0], velocity = [0,0,0], acceleration = [-2,0,0]},Particle {position = [3,0,0], velocity = [2,0,0], acceleration = [-2,0,1]}]" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "particles = [p0, p1, p2]\n", + "particles" + ] + }, + { + "cell_type": "code", + "execution_count": 69, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "[Particle {position = [-2,0,0], velocity = [-3,0,0], acceleration = [-1,0,0]},Particle {position = [-26,0,0], velocity = [-10,0,0], acceleration = [-2,0,0]},Particle {position = [-17,0,15], velocity = [-8,0,5], acceleration = [-2,0,1]}]" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "simulate particles" + ] + }, + { + "cell_type": "code", + "execution_count": 70, + "metadata": {}, + "outputs": [], + "source": [ + "pAbs :: Particle -> Particle\n", + "pAbs particle = particle {position = p', velocity = v', acceleration = a'}\n", + " where !p' = V.map abs (position particle)\n", + " !v' = V.map abs (velocity particle)\n", + " !a' = V.map abs (acceleration particle)\n", + " " + ] + }, + { + "cell_type": "code", + "execution_count": 71, + "metadata": { + "scrolled": true + }, + "outputs": [ + { + "data": { + "text/plain": [ + "Particle {position = [3,0,0], velocity = [2,0,0], acceleration = [-2,0,1]}" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "p2" + ] + }, + { + "cell_type": "code", + "execution_count": 72, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "Particle {position = [3,0,0], velocity = [2,0,0], acceleration = [2,0,1]}" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "pAbs p2" + ] + }, + { + "cell_type": "code", + "execution_count": 73, + "metadata": {}, + "outputs": [], + "source": [ + "pMin p1 p2 = Particle {position = p', velocity = v', acceleration = a'}\n", + " where !p' = V.zipWith min (position p1) (position p2)\n", + " !v' = V.zipWith min (velocity p1) (velocity p2)\n", + " !a' = V.zipWith min (acceleration p1) (acceleration p2)" + ] + }, + { + "cell_type": "code", + "execution_count": 74, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "Particle {position = [3,0,0], velocity = [2,0,0], acceleration = [-1,0,0]}" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "p0" + ] + }, + { + "cell_type": "code", + "execution_count": 75, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "Particle {position = [3,0,0], velocity = [2,0,0], acceleration = [-2,0,1]}" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "p2" + ] + }, + { + "cell_type": "code", + "execution_count": 76, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "Particle {position = [3,0,0], velocity = [2,0,0], acceleration = [1,0,0]}" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "pMin (pAbs p0) (pAbs p2)" + ] + }, + { + "cell_type": "code", + "execution_count": 77, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "Particle {position = [3,0,0], velocity = [2,0,0], acceleration = [2,0,1]}" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "pAbs p2" + ] + }, + { + "cell_type": "code", + "execution_count": 78, + "metadata": {}, + "outputs": [], + "source": [ + "clearClosest :: [Particle] -> Maybe Int\n", + "clearClosest particles = elemIndex targetParticle absParticles\n", + " where absParticles = map pAbs particles\n", + " targetParticle = foldl1' pMin absParticles" + ] + }, + { + "cell_type": "code", + "execution_count": 79, + "metadata": {}, + "outputs": [], + "source": [ + "pAbsA :: Particle -> Integer\n", + "pAbsA particle = V.foldl1' (+) $ V.map abs (acceleration particle) " + ] + }, + { + "cell_type": "code", + "execution_count": 80, + "metadata": {}, + "outputs": [], + "source": [ + "pAbsX :: Particle -> Integer\n", + "pAbsX particle = V.foldl1' (+) $ V.map abs (position particle) " + ] + }, + { + "cell_type": "code", + "execution_count": 81, + "metadata": {}, + "outputs": [], + "source": [ + "lowestAcc particles = elemIndices minAcc absAccs\n", + " where absAccs = map pAbsA particles\n", + " minAcc = minimum absAccs" + ] + }, + { + "cell_type": "code", + "execution_count": 82, + "metadata": {}, + "outputs": [], + "source": [ + "main :: IO ()\n", + "main = do \n", + " text <- TIO.readFile \"../../data/advent20.txt\"\n", + " let particles = successfulParse text\n", + "-- print particles\n", + " print $ lowestAcc particles\n", + "-- print $ part2 instrs" + ] + }, + { + "cell_type": "code", + "execution_count": 83, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "[21,457]" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "main" + ] + }, + { + "cell_type": "code", + "execution_count": 84, + "metadata": {}, + "outputs": [], + "source": [ + "-- particles!!21" + ] + }, + { + "cell_type": "code", + "execution_count": 85, + "metadata": {}, + "outputs": [], + "source": [ + "-- particles!!457" + ] + }, + { + "cell_type": "code", + "execution_count": 86, + "metadata": {}, + "outputs": [], + "source": [ + "withMinX particles = minX `elemIndices` absXs\n", + " where absXs = map pAbsX particles\n", + " minX = minimum absXs" + ] + }, + { + "cell_type": "code", + "execution_count": 87, + "metadata": {}, + "outputs": [], + "source": [ + "simulateQ :: [Particle] -> [Particle]\n", + "simulateQ particles = \n", + " if all quiescent particles\n", + " then particles\n", + " else simulateQ (map step particles)" + ] + }, + { + "cell_type": "code", + "execution_count": 88, + "metadata": {}, + "outputs": [], + "source": [ + "simulate :: [Particle] -> [Particle]\n", + "simulate particles = \n", + " if all quiescent particles && length withMinXs == 1\n", + " then particles\n", + " else simulate (map step particles)\n", + " where withMinXs = withMinX particles" + ] + }, + { + "cell_type": "code", + "execution_count": 89, + "metadata": {}, + "outputs": [], + "source": [ + "pf = simulate particles" + ] + }, + { + "cell_type": "code", + "execution_count": 90, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "[0]" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "withMinX pf" + ] + }, + { + "cell_type": "code", + "execution_count": 100, + "metadata": {}, + "outputs": [], + "source": [ + "-- part1 particles = head minInContext\n", + "-- where pf = simulate slowParticles\n", + "-- slowIndices = lowestAcc particles\n", + "-- slowParticles = map (particles !!) slowIndices\n", + "-- minInContext = map (slowIndices !!) $ withMinX pf" + ] + }, + { + "cell_type": "code", + "execution_count": 103, + "metadata": {}, + "outputs": [], + "source": [ + "part1 particles = head $ withMinX pf\n", + " where pf = simulate particles" + ] + }, + { + "cell_type": "code", + "execution_count": 104, + "metadata": {}, + "outputs": [], + "source": [ + "main :: IO ()\n", + "main = do \n", + " text <- TIO.readFile \"../../data/advent20.txt\"\n", + " let particles = successfulParse text\n", + " print $ part1 particles\n", + "-- print $ part2 instrs" + ] + }, + { + "cell_type": "code", + "execution_count": 93, + "metadata": {}, + "outputs": [], + "source": [ + "-- main" + ] + }, + { + "cell_type": "code", + "execution_count": 94, + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "
Use head
Found:
particles !! 0
Why Not:
head particles
" + ], + "text/plain": [ + "Line 1: Use head\n", + "Found:\n", + "particles !! 0\n", + "Why not:\n", + "head particles" + ] + }, + "metadata": {}, + "output_type": "display_data" + }, + { + "data": { + "text/plain": [ + "Particle {position = [-833,-499,-1391], velocity = [84,17,61], acceleration = [-4,1,1]}" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "text <- TIO.readFile \"../../data/advent20.txt\"\n", + "particles = successfulParse text\n", + "particles!!0" + ] + }, + { + "cell_type": "code", + "execution_count": 96, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "[Particle {position = [-59,74,-188], velocity = [-29,97,-150], acceleration = [-1,0,0]},Particle {position = [98,72,-533], velocity = [37,12,-172], acceleration = [0,1,0]}]" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "simulateQ $ map (particles !!) $ lowestAcc particles" + ] + }, + { + "cell_type": "code", + "execution_count": 97, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "[Particle {position = [-59,74,-188], velocity = [-29,97,-150], acceleration = [-1,0,0]},Particle {position = [98,72,-533], velocity = [37,12,-172], acceleration = [0,1,0]}]" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "simulate $ map (particles !!) $ lowestAcc particles" + ] + }, + { + "cell_type": "code", + "execution_count": 105, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "457" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "main" + ] + }, + { + "cell_type": "code", + "execution_count": 116, + "metadata": {}, + "outputs": [], + "source": [ + "removeColliders particles = particles'\n", + " where positions = map position particles\n", + " duplicatePositions = S.fromList $ concat $ filter (\\g -> length g > 1) $ group $ sort positions\n", + " particles' = filter (\\p -> not (S.member (position p) duplicatePositions)) particles" + ] + }, + { + "cell_type": "code", + "execution_count": 117, + "metadata": {}, + "outputs": [], + "source": [ + "simulateC :: Integer -> [Particle] -> [Particle]\n", + "simulateC 0 particles = particles\n", + "simulateC t particles = simulateC (t - 1) (map step particles')\n", + " where particles' = removeColliders particles" + ] + }, + { + "cell_type": "code", + "execution_count": 118, + "metadata": {}, + "outputs": [], + "source": [ + "part2 n particles = length $ simulateC n particles" + ] + }, + { + "cell_type": "code", + "execution_count": 119, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "1000" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "length particles" + ] + }, + { + "cell_type": "code", + "execution_count": 123, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "448" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "part2 500 particles" + ] + }, + { + "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 +}