src/advent13/advent13.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 #-}"
  12    ]
  13   },
  14   {
  15    "cell_type": "code",
  16    "execution_count": 4,
  17    "metadata": {},
  18    "outputs": [],
  19    "source": [
  20     "import Data.Text (Text)\n",
  21     "import qualified Data.Text as T\n",
  22     "import qualified Data.Text.IO as TIO\n",
  23     "\n",
  24     "import Text.Megaparsec\n",
  25     "import qualified Text.Megaparsec.Lexer as L\n",
  26     "import Text.Megaparsec.Text (Parser)\n",
  27     "\n",
  28     "import qualified Data.Map.Strict as M\n",
  29     "import Data.Map.Strict ((!))\n",
  30     "\n",
  31     "import qualified Data.Set as S\n",
  32     "import qualified Control.Applicative as CA"
  33    ]
  34   },
  35   {
  36    "cell_type": "code",
  37    "execution_count": 49,
  38    "metadata": {},
  39    "outputs": [],
  40    "source": [
  41     "scanner :: Integer -> Integer -> Integer -> Integer\n",
  42     "scanner depth range t = \n",
  43     "    let t' = (t + depth) `mod` ((range - 1) * 2)\n",
  44     "    in if t' < range\n",
  45     "       then t' \n",
  46     "       else t' + (t' - range + 1) * -2"
  47    ]
  48   },
  49   {
  50    "cell_type": "code",
  51    "execution_count": 48,
  52    "metadata": {},
  53    "outputs": [],
  54    "source": [
  55     "sc :: Parser ()\n",
  56     "sc = L.space (skipSome spaceChar) CA.empty CA.empty\n",
  57     "\n",
  58     "lexeme  = L.lexeme sc\n",
  59     "integer = lexeme L.integer\n",
  60     "symb = L.symbol sc\n",
  61     "\n",
  62     "scannersP = many scannerP\n",
  63     "\n",
  64     "scannerP = (,) <$> integer <*> (symb \":\" *> integer)\n",
  65     "\n",
  66     "successfulParse :: Text -> [(Integer, Integer)]\n",
  67     "successfulParse input = \n",
  68     "        case parse scannersP \"input\" input of\n",
  69     "                Left  err   -> [] -- TIO.putStr $ T.pack $ parseErrorPretty err\n",
  70     "                Right scanners -> scanners"
  71    ]
  72   },
  73   {
  74    "cell_type": "markdown",
  75    "metadata": {},
  76    "source": [
  77     "[0,1,2,3,4, 3, 2, 1,0,1,2,3] res = t' + x\n",
  78     "[0,1,2,3,4, 5, 6, 7,0,1,2,3] t'\n",
  79     "[           0, 1, 2          t' - len\n",
  80     "           -2,-4,-6          x\n",
  81     "\n",
  82     "cycle is 5 + (5-2) = 8\n",
  83     "\n",
  84     "if t' <= 5 then t' else 5 - t' + 1\n",
  85     "\n",
  86     "\n",
  87     "0 1 2 3 4 5 6 7 8 \n",
  88     "S . . . . . . .\n",
  89     ". S . . . . . .\n",
  90     ". . S . . . . .\n",
  91     ". . . S . . . .\n",
  92     ". . . . S . . .\n",
  93     ". . . . . S . .\n",
  94     ". . . . . . S .\n",
  95     ". . . . . . . S\n",
  96     "\n"
  97    ]
  98   },
  99   {
 100    "cell_type": "code",
 101    "execution_count": 50,
 102    "metadata": {},
 103    "outputs": [
 104     {
 105      "data": {
 106       "text/plain": [
 107        "[0,1,2,3,4,3,2,1,0,1,2,3,4,3,2,1,0,1,2,3,4]"
 108       ]
 109      },
 110      "metadata": {},
 111      "output_type": "display_data"
 112     }
 113    ],
 114    "source": [
 115     "s50 = scanner 0 5\n",
 116     "map s50 [0..20]"
 117    ]
 118   },
 119   {
 120    "cell_type": "code",
 121    "execution_count": 51,
 122    "metadata": {},
 123    "outputs": [
 124     {
 125      "data": {
 126       "text/plain": [
 127        "[0,1,2,1,0,1,2,1,0,1,2,1,0,1,2,1,0,1,2,1,0]"
 128       ]
 129      },
 130      "metadata": {},
 131      "output_type": "display_data"
 132     }
 133    ],
 134    "source": [
 135     "s30 = scanner 0 3\n",
 136     "map s30 [0..20]"
 137    ]
 138   },
 139   {
 140    "cell_type": "code",
 141    "execution_count": 52,
 142    "metadata": {},
 143    "outputs": [
 144     {
 145      "data": {
 146       "text/plain": [
 147        "[3,2,1,0,1,2,3,2,1,0,1,2,3,2,1,0,1,2,3,2,1]"
 148       ]
 149      },
 150      "metadata": {},
 151      "output_type": "display_data"
 152     }
 153    ],
 154    "source": [
 155     "map (scanner 3 4) [0..20]"
 156    ]
 157   },
 158   {
 159    "cell_type": "code",
 160    "execution_count": 53,
 161    "metadata": {},
 162    "outputs": [
 163     {
 164      "data": {
 165       "text/plain": [
 166        "[0,1,2,0]"
 167       ]
 168      },
 169      "metadata": {},
 170      "output_type": "display_data"
 171     }
 172    ],
 173    "source": [
 174     "[scanner 0 3 0, scanner 1 2 0, scanner 4 4 0, scanner 6 4 0]"
 175    ]
 176   },
 177   {
 178    "cell_type": "code",
 179    "execution_count": 55,
 180    "metadata": {},
 181    "outputs": [],
 182    "source": [
 183     "sample = [(0, 3), (1, 2), (4, 4), (6, 4)]"
 184    ]
 185   },
 186   {
 187    "cell_type": "code",
 188    "execution_count": 58,
 189    "metadata": {},
 190    "outputs": [
 191     {
 192      "data": {
 193       "text/plain": [
 194        "24"
 195       ]
 196      },
 197      "metadata": {},
 198      "output_type": "display_data"
 199     }
 200    ],
 201    "source": [
 202     "sum $ map (uncurry (*)) $ filter (\\(d, r) -> scanner d r 0 == 0) sample "
 203    ]
 204   },
 205   {
 206    "cell_type": "code",
 207    "execution_count": 61,
 208    "metadata": {},
 209    "outputs": [],
 210    "source": [
 211     "part1 :: [(Integer, Integer)] -> Integer\n",
 212     "part1 = sum . map (uncurry (*)) . filter (\\(d, r) -> scanner d r 0 == 0)"
 213    ]
 214   },
 215   {
 216    "cell_type": "code",
 217    "execution_count": 65,
 218    "metadata": {},
 219    "outputs": [],
 220    "source": [
 221     "main :: IO ()\n",
 222     "main = do \n",
 223     "        text <- TIO.readFile \"../../data/advent13.txt\"\n",
 224     "        let instrs = successfulParse text\n",
 225     "        print $ part1 instrs"
 226    ]
 227   },
 228   {
 229    "cell_type": "code",
 230    "execution_count": 66,
 231    "metadata": {},
 232    "outputs": [
 233     {
 234      "data": {
 235       "text/plain": [
 236        "1904"
 237       ]
 238      },
 239      "metadata": {},
 240      "output_type": "display_data"
 241     }
 242    ],
 243    "source": [
 244     "main"
 245    ]
 246   },
 247   {
 248    "cell_type": "code",
 249    "execution_count": 68,
 250    "metadata": {},
 251    "outputs": [],
 252    "source": [
 253     "scanify = map (uncurry scanner)"
 254    ]
 255   },
 256   {
 257    "cell_type": "code",
 258    "execution_count": 76,
 259    "metadata": {},
 260    "outputs": [],
 261    "source": [
 262     "canPass scannersF t = all (\\s -> s t /= 0) scannersF"
 263    ]
 264   },
 265   {
 266    "cell_type": "code",
 267    "execution_count": 77,
 268    "metadata": {},
 269    "outputs": [],
 270    "source": [
 271     "scs = scanify sample"
 272    ]
 273   },
 274   {
 275    "cell_type": "code",
 276    "execution_count": 82,
 277    "metadata": {},
 278    "outputs": [
 279     {
 280      "data": {
 281       "text/plain": [
 282        "10"
 283       ]
 284      },
 285      "metadata": {},
 286      "output_type": "display_data"
 287     }
 288    ],
 289    "source": [
 290     "head $ filter (canPass scs) [0..]"
 291    ]
 292   },
 293   {
 294    "cell_type": "code",
 295    "execution_count": 81,
 296    "metadata": {},
 297    "outputs": [
 298     {
 299      "data": {
 300       "text/plain": [
 301        "[2,1,2,2]"
 302       ]
 303      },
 304      "metadata": {},
 305      "output_type": "display_data"
 306     }
 307    ],
 308    "source": [
 309     "map (\\s -> s 10) scs"
 310    ]
 311   },
 312   {
 313    "cell_type": "code",
 314    "execution_count": 83,
 315    "metadata": {},
 316    "outputs": [],
 317    "source": [
 318     "part2 scannerDefs = head $ filter (canPass scanners) [0..]\n",
 319     "    where scanners = scanify scannerDefs"
 320    ]
 321   },
 322   {
 323    "cell_type": "code",
 324    "execution_count": 84,
 325    "metadata": {},
 326    "outputs": [],
 327    "source": [
 328     "main :: IO ()\n",
 329     "main = do \n",
 330     "        text <- TIO.readFile \"../../data/advent13.txt\"\n",
 331     "        let instrs = successfulParse text\n",
 332     "        print $ part1 instrs\n",
 333     "        print $ part2 instrs"
 334    ]
 335   },
 336   {
 337    "cell_type": "code",
 338    "execution_count": 85,
 339    "metadata": {},
 340    "outputs": [
 341     {
 342      "data": {
 343       "text/plain": [
 344        "1904\n",
 345        "3833504"
 346       ]
 347      },
 348      "metadata": {},
 349      "output_type": "display_data"
 350     }
 351    ],
 352    "source": [
 353     "main"
 354    ]
 355   },
 356   {
 357    "cell_type": "markdown",
 358    "metadata": {},
 359    "source": []
 360   }
 361  ],
 362  "metadata": {
 363   "kernelspec": {
 364    "display_name": "Haskell",
 365    "language": "haskell",
 366    "name": "haskell"
 367   },
 368   "language_info": {
 369    "codemirror_mode": "ihaskell",
 370    "file_extension": ".hs",
 371    "name": "haskell",
 372    "version": "8.0.2"
 373   }
 374  },
 375  "nbformat": 4,
 376  "nbformat_minor": 2
 377 }