--- /dev/null
+{
+ "cells": [
+ {
+ "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": 2,
+ "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 qualified Data.MultiSet as B -- B for bag\n",
+ "import qualified Data.Set as S\n",
+ "\n",
+ "import Data.Either"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 3,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "type Part = B.MultiSet Integer\n",
+ "type Parts = B.MultiSet Part\n",
+ "type Candidates = S.Set Part\n",
+ "data Bridge = Bridge { bridgeParts :: Parts, requiring :: Integer } deriving (Eq, Show, Ord)\n",
+ "type Bridges = S.Set Bridge"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 4,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "-- really persuade Megaparsec not to include newlines in how it consume spaces.\n",
+ "onlySpace = (char ' ') <|> (char '\\t')\n",
+ "\n",
+ "sc :: Parser ()\n",
+ "sc = L.space (skipSome onlySpace) CA.empty CA.empty\n",
+ "\n",
+ "lexeme = L.lexeme sc\n",
+ "integer = lexeme L.integer\n",
+ "symbol = L.symbol sc\n",
+ "slash = symbol \"/\"\n",
+ "\n",
+ "partsP = partP `sepBy` newline\n",
+ "partP = B.fromList <$> integer `sepBy` slash\n",
+ "\n",
+ "successfulParse :: Text -> Parts\n",
+ "successfulParse input = \n",
+ " case parse partsP \"input\" input of\n",
+ " Left _error -> B.empty -- TIO.putStr $ T.pack $ parseErrorPretty err\n",
+ " Right partsList -> B.fromList partsList"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 5,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "sample = T.pack \"42/37\\n28/28\\n29/25\""
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 6,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "[fromOccurList [(37,1),(42,1)],fromOccurList [(25,1),(29,1)]]"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "parseTest partsP (T.pack \"42/37\\n29/25\")"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 7,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "fromOccurList [(fromOccurList [(25,1),(29,1)],1),(fromOccurList [(28,2)],1),(fromOccurList [(37,1),(42,1)],1)]"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "sampleParts = successfulParse sample\n",
+ "sampleParts"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 8,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "57"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "text <- TIO.readFile \"../../data/advent24.txt\"\n",
+ "parts = successfulParse text\n",
+ "B.size parts"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 9,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "emptyBridge :: Bridge\n",
+ "emptyBridge = Bridge { bridgeParts = B.empty, requiring = 0}"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 10,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "hasPort :: Part -> Integer -> Bool\n",
+ "hasPort part port = port `B.member` part"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 11,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "available :: Parts -> Part -> Bridge -> Bool\n",
+ "available parts part bridge = B.occur part parts > B.occur part (bridgeParts bridge)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 12,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "candidates :: Parts -> Bridge -> Candidates\n",
+ "candidates parts bridge = B.toSet $ B.filter canUse parts\n",
+ " where needed = requiring bridge\n",
+ " canUse p = hasPort p needed && available parts p bridge"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 13,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "fromList [fromOccurList [(0,1),(7,1)],fromOccurList [(0,1),(22,1)],fromOccurList [(0,1),(35,1)]]"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "candidates parts emptyBridge"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 14,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "grow :: Bridge -> Part -> Bridge\n",
+ "grow bridge part = bridge {bridgeParts = bp', requiring = req'}\n",
+ " where req = requiring bridge\n",
+ " req' = B.findMin $ B.delete req part\n",
+ " bp' = B.insert part $ bridgeParts bridge"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 15,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "fromList [Bridge {bridgeParts = fromOccurList [(fromOccurList [(0,1),(7,1)],1)], requiring = 7},Bridge {bridgeParts = fromOccurList [(fromOccurList [(0,1),(22,1)],1)], requiring = 22},Bridge {bridgeParts = fromOccurList [(fromOccurList [(0,1),(35,1)],1)], requiring = 35}]"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "S.map (grow emptyBridge) $ candidates parts emptyBridge"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 16,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "extendOneBridge :: Parts -> Bridge -> Either Bridge Bridges\n",
+ "extendOneBridge parts bridge = \n",
+ " if S.null $ candidates parts bridge\n",
+ " then Left bridge\n",
+ " else Right (S.map (grow bridge) $ candidates parts bridge)\n",
+ " "
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 17,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "extendBridges :: Parts -> Bridges -> Bridges -> Bridges\n",
+ "extendBridges parts bridges completed = \n",
+ " if S.null bridges then completed\n",
+ " else extendBridges parts bridges' completed'\n",
+ " where updates = map (extendOneBridge parts) $ S.toList bridges\n",
+ " newCompleted = lefts updates\n",
+ " completed' = S.union completed $ S.fromList newCompleted\n",
+ " bridges' = S.unions $ rights updates\n",
+ " "
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 18,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "allBridges parts = extendBridges parts (S.singleton emptyBridge) S.empty"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 19,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "49096"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "S.size $ allBridges parts"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 22,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "bridgeStrength :: Bridge -> Integer\n",
+ "bridgeStrength bridge = B.fold (+) 0 $ B.map partStrength $ bridgeParts bridge\n",
+ " where partStrength = sum . B.elems "
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 25,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "1940"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "S.findMax $ S.map bridgeStrength $ allBridges parts"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 27,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "bridgeLength :: Bridge -> Int\n",
+ "bridgeLength bridge = B.size $ bridgeParts bridge"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 28,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "bestBridge parts = S.findMax $ S.map bridgeStrength longBridges\n",
+ " where bridges = allBridges parts\n",
+ " longest = S.findMax $ S.map bridgeLength bridges\n",
+ " longBridges = S.filter (\\b -> bridgeLength b == longest) bridges\n",
+ " "
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 29,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "1928"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "bestBridge parts"
+ ]
+ },
+ {
+ "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