src/advent24/advent24.ipynb

   1 {
   2  "cells": [
   3   {
   4    "cell_type": "code",
   5    "execution_count": 1,
   6    "metadata": {},
   7    "outputs": [],
   8    "source": [
   9     "{-# LANGUAGE NegativeLiterals #-}\n",
  10     "{-# LANGUAGE FlexibleContexts #-}\n",
  11     "{-# LANGUAGE OverloadedStrings #-}\n",
  12     "{-# LANGUAGE TypeFamilies #-}"
  13    ]
  14   },
  15   {
  16    "cell_type": "code",
  17    "execution_count": 2,
  18    "metadata": {},
  19    "outputs": [],
  20    "source": [
  21     "-- import Prelude hiding ((++))\n",
  22     "import Data.Text (Text)\n",
  23     "import qualified Data.Text as T\n",
  24     "import qualified Data.Text.IO as TIO\n",
  25     "\n",
  26     "import Text.Megaparsec hiding (State)\n",
  27     "import qualified Text.Megaparsec.Lexer as L\n",
  28     "import Text.Megaparsec.Text (Parser)\n",
  29     "import qualified Control.Applicative as CA\n",
  30     "\n",
  31     "import qualified Data.MultiSet as B -- B for bag\n",
  32     "import qualified Data.Set as S\n",
  33     "\n",
  34     "import Data.Either"
  35    ]
  36   },
  37   {
  38    "cell_type": "code",
  39    "execution_count": 3,
  40    "metadata": {},
  41    "outputs": [],
  42    "source": [
  43     "type Part = B.MultiSet Integer\n",
  44     "type Parts = B.MultiSet Part\n",
  45     "type Candidates = S.Set Part\n",
  46     "data Bridge = Bridge { bridgeParts :: Parts, requiring :: Integer } deriving (Eq, Show, Ord)\n",
  47     "type Bridges = S.Set Bridge"
  48    ]
  49   },
  50   {
  51    "cell_type": "code",
  52    "execution_count": 4,
  53    "metadata": {},
  54    "outputs": [],
  55    "source": [
  56     "-- really persuade Megaparsec not to include newlines in how it consume spaces.\n",
  57     "onlySpace = (char ' ') <|> (char '\\t')\n",
  58     "\n",
  59     "sc :: Parser ()\n",
  60     "sc = L.space (skipSome onlySpace) CA.empty CA.empty\n",
  61     "\n",
  62     "lexeme = L.lexeme sc\n",
  63     "integer = lexeme L.integer\n",
  64     "symbol = L.symbol sc\n",
  65     "slash = symbol \"/\"\n",
  66     "\n",
  67     "partsP = partP `sepBy` newline\n",
  68     "partP = B.fromList <$> integer `sepBy` slash\n",
  69     "\n",
  70     "successfulParse :: Text -> Parts\n",
  71     "successfulParse input = \n",
  72     "        case parse partsP \"input\" input of\n",
  73     "                Left  _error -> B.empty -- TIO.putStr $ T.pack $ parseErrorPretty err\n",
  74     "                Right partsList -> B.fromList partsList"
  75    ]
  76   },
  77   {
  78    "cell_type": "code",
  79    "execution_count": 5,
  80    "metadata": {},
  81    "outputs": [],
  82    "source": [
  83     "sample = T.pack \"42/37\\n28/28\\n29/25\""
  84    ]
  85   },
  86   {
  87    "cell_type": "code",
  88    "execution_count": 6,
  89    "metadata": {},
  90    "outputs": [
  91     {
  92      "data": {
  93       "text/plain": [
  94        "[fromOccurList [(37,1),(42,1)],fromOccurList [(25,1),(29,1)]]"
  95       ]
  96      },
  97      "metadata": {},
  98      "output_type": "display_data"
  99     }
 100    ],
 101    "source": [
 102     "parseTest partsP (T.pack \"42/37\\n29/25\")"
 103    ]
 104   },
 105   {
 106    "cell_type": "code",
 107    "execution_count": 7,
 108    "metadata": {},
 109    "outputs": [
 110     {
 111      "data": {
 112       "text/plain": [
 113        "fromOccurList [(fromOccurList [(25,1),(29,1)],1),(fromOccurList [(28,2)],1),(fromOccurList [(37,1),(42,1)],1)]"
 114       ]
 115      },
 116      "metadata": {},
 117      "output_type": "display_data"
 118     }
 119    ],
 120    "source": [
 121     "sampleParts = successfulParse sample\n",
 122     "sampleParts"
 123    ]
 124   },
 125   {
 126    "cell_type": "code",
 127    "execution_count": 8,
 128    "metadata": {},
 129    "outputs": [
 130     {
 131      "data": {
 132       "text/plain": [
 133        "57"
 134       ]
 135      },
 136      "metadata": {},
 137      "output_type": "display_data"
 138     }
 139    ],
 140    "source": [
 141     "text <- TIO.readFile \"../../data/advent24.txt\"\n",
 142     "parts = successfulParse text\n",
 143     "B.size parts"
 144    ]
 145   },
 146   {
 147    "cell_type": "code",
 148    "execution_count": 9,
 149    "metadata": {},
 150    "outputs": [],
 151    "source": [
 152     "emptyBridge :: Bridge\n",
 153     "emptyBridge = Bridge { bridgeParts = B.empty, requiring = 0}"
 154    ]
 155   },
 156   {
 157    "cell_type": "code",
 158    "execution_count": 10,
 159    "metadata": {},
 160    "outputs": [],
 161    "source": [
 162     "hasPort :: Part -> Integer -> Bool\n",
 163     "hasPort part port = port `B.member` part"
 164    ]
 165   },
 166   {
 167    "cell_type": "code",
 168    "execution_count": 11,
 169    "metadata": {},
 170    "outputs": [],
 171    "source": [
 172     "available :: Parts -> Part -> Bridge -> Bool\n",
 173     "available parts part bridge = B.occur part parts > B.occur part (bridgeParts bridge)"
 174    ]
 175   },
 176   {
 177    "cell_type": "code",
 178    "execution_count": 12,
 179    "metadata": {},
 180    "outputs": [],
 181    "source": [
 182     "candidates :: Parts -> Bridge -> Candidates\n",
 183     "candidates parts bridge = B.toSet $ B.filter canUse parts\n",
 184     "    where needed = requiring bridge\n",
 185     "          canUse p = hasPort p needed && available parts p bridge"
 186    ]
 187   },
 188   {
 189    "cell_type": "code",
 190    "execution_count": 13,
 191    "metadata": {},
 192    "outputs": [
 193     {
 194      "data": {
 195       "text/plain": [
 196        "fromList [fromOccurList [(0,1),(7,1)],fromOccurList [(0,1),(22,1)],fromOccurList [(0,1),(35,1)]]"
 197       ]
 198      },
 199      "metadata": {},
 200      "output_type": "display_data"
 201     }
 202    ],
 203    "source": [
 204     "candidates parts emptyBridge"
 205    ]
 206   },
 207   {
 208    "cell_type": "code",
 209    "execution_count": 14,
 210    "metadata": {},
 211    "outputs": [],
 212    "source": [
 213     "grow :: Bridge -> Part -> Bridge\n",
 214     "grow bridge part = bridge {bridgeParts = bp', requiring = req'}\n",
 215     "    where req = requiring bridge\n",
 216     "          req' = B.findMin $ B.delete req part\n",
 217     "          bp' = B.insert part $ bridgeParts bridge"
 218    ]
 219   },
 220   {
 221    "cell_type": "code",
 222    "execution_count": 15,
 223    "metadata": {},
 224    "outputs": [
 225     {
 226      "data": {
 227       "text/plain": [
 228        "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}]"
 229       ]
 230      },
 231      "metadata": {},
 232      "output_type": "display_data"
 233     }
 234    ],
 235    "source": [
 236     "S.map (grow emptyBridge) $ candidates parts emptyBridge"
 237    ]
 238   },
 239   {
 240    "cell_type": "code",
 241    "execution_count": 16,
 242    "metadata": {},
 243    "outputs": [],
 244    "source": [
 245     "extendOneBridge :: Parts -> Bridge -> Either Bridge Bridges\n",
 246     "extendOneBridge parts bridge = \n",
 247     "    if S.null $ candidates parts bridge\n",
 248     "    then Left bridge\n",
 249     "    else Right (S.map (grow bridge) $ candidates parts bridge)\n",
 250     "                                "
 251    ]
 252   },
 253   {
 254    "cell_type": "code",
 255    "execution_count": 17,
 256    "metadata": {},
 257    "outputs": [],
 258    "source": [
 259     "extendBridges :: Parts -> Bridges -> Bridges -> Bridges\n",
 260     "extendBridges parts bridges completed = \n",
 261     "    if S.null bridges then completed\n",
 262     "                      else extendBridges parts bridges' completed'\n",
 263     "    where updates = map (extendOneBridge parts) $ S.toList bridges\n",
 264     "          newCompleted = lefts updates\n",
 265     "          completed' = S.union completed $ S.fromList newCompleted\n",
 266     "          bridges' = S.unions $ rights updates\n",
 267     "          "
 268    ]
 269   },
 270   {
 271    "cell_type": "code",
 272    "execution_count": 18,
 273    "metadata": {},
 274    "outputs": [],
 275    "source": [
 276     "allBridges parts = extendBridges parts (S.singleton emptyBridge) S.empty"
 277    ]
 278   },
 279   {
 280    "cell_type": "code",
 281    "execution_count": 19,
 282    "metadata": {},
 283    "outputs": [
 284     {
 285      "data": {
 286       "text/plain": [
 287        "49096"
 288       ]
 289      },
 290      "metadata": {},
 291      "output_type": "display_data"
 292     }
 293    ],
 294    "source": [
 295     "S.size $ allBridges parts"
 296    ]
 297   },
 298   {
 299    "cell_type": "code",
 300    "execution_count": 22,
 301    "metadata": {},
 302    "outputs": [],
 303    "source": [
 304     "bridgeStrength :: Bridge -> Integer\n",
 305     "bridgeStrength bridge = B.fold (+) 0 $ B.map partStrength $ bridgeParts bridge\n",
 306     "    where partStrength = sum . B.elems "
 307    ]
 308   },
 309   {
 310    "cell_type": "code",
 311    "execution_count": 25,
 312    "metadata": {},
 313    "outputs": [
 314     {
 315      "data": {
 316       "text/plain": [
 317        "1940"
 318       ]
 319      },
 320      "metadata": {},
 321      "output_type": "display_data"
 322     }
 323    ],
 324    "source": [
 325     "S.findMax $ S.map bridgeStrength $ allBridges parts"
 326    ]
 327   },
 328   {
 329    "cell_type": "code",
 330    "execution_count": 27,
 331    "metadata": {},
 332    "outputs": [],
 333    "source": [
 334     "bridgeLength :: Bridge -> Int\n",
 335     "bridgeLength bridge = B.size $ bridgeParts bridge"
 336    ]
 337   },
 338   {
 339    "cell_type": "code",
 340    "execution_count": 28,
 341    "metadata": {},
 342    "outputs": [],
 343    "source": [
 344     "bestBridge parts = S.findMax $ S.map bridgeStrength longBridges\n",
 345     "    where bridges = allBridges parts\n",
 346     "          longest = S.findMax $ S.map bridgeLength bridges\n",
 347     "          longBridges = S.filter (\\b -> bridgeLength b == longest) bridges\n",
 348     "          "
 349    ]
 350   },
 351   {
 352    "cell_type": "code",
 353    "execution_count": 29,
 354    "metadata": {},
 355    "outputs": [
 356     {
 357      "data": {
 358       "text/plain": [
 359        "1928"
 360       ]
 361      },
 362      "metadata": {},
 363      "output_type": "display_data"
 364     }
 365    ],
 366    "source": [
 367     "bestBridge parts"
 368    ]
 369   },
 370   {
 371    "cell_type": "code",
 372    "execution_count": null,
 373    "metadata": {},
 374    "outputs": [],
 375    "source": []
 376   }
 377  ],
 378  "metadata": {
 379   "kernelspec": {
 380    "display_name": "Haskell",
 381    "language": "haskell",
 382    "name": "haskell"
 383   },
 384   "language_info": {
 385    "codemirror_mode": "ihaskell",
 386    "file_extension": ".hs",
 387    "name": "haskell",
 388    "version": "8.0.2"
 389   }
 390  },
 391  "nbformat": 4,
 392  "nbformat_minor": 2
 393 }