src/advent15/advent15.ipynb

   1 {
   2  "cells": [
   3   {
   4    "cell_type": "code",
   5    "execution_count": 1,
   6    "metadata": {},
   7    "outputs": [],
   8    "source": [
   9     "import Data.Word\n",
  10     "import Data.Bits"
  11    ]
  12   },
  13   {
  14    "cell_type": "code",
  15    "execution_count": 2,
  16    "metadata": {},
  17    "outputs": [],
  18    "source": [
  19     "a :: Word8\n",
  20     "a=156"
  21    ]
  22   },
  23   {
  24    "cell_type": "code",
  25    "execution_count": 3,
  26    "metadata": {},
  27    "outputs": [],
  28    "source": [
  29     "b :: Word16\n",
  30     "b = 202"
  31    ]
  32   },
  33   {
  34    "cell_type": "code",
  35    "execution_count": 4,
  36    "metadata": {},
  37    "outputs": [
  38     {
  39      "data": {
  40       "text/html": [
  41        "<style>/* Styles used for the Hoogle display in the pager */\n",
  42        ".hoogle-doc {\n",
  43        "display: block;\n",
  44        "padding-bottom: 1.3em;\n",
  45        "padding-left: 0.4em;\n",
  46        "}\n",
  47        ".hoogle-code {\n",
  48        "display: block;\n",
  49        "font-family: monospace;\n",
  50        "white-space: pre;\n",
  51        "}\n",
  52        ".hoogle-text {\n",
  53        "display: block;\n",
  54        "}\n",
  55        ".hoogle-name {\n",
  56        "color: green;\n",
  57        "font-weight: bold;\n",
  58        "}\n",
  59        ".hoogle-head {\n",
  60        "font-weight: bold;\n",
  61        "}\n",
  62        ".hoogle-sub {\n",
  63        "display: block;\n",
  64        "margin-left: 0.4em;\n",
  65        "}\n",
  66        ".hoogle-package {\n",
  67        "font-weight: bold;\n",
  68        "font-style: italic;\n",
  69        "}\n",
  70        ".hoogle-module {\n",
  71        "font-weight: bold;\n",
  72        "}\n",
  73        ".hoogle-class {\n",
  74        "font-weight: bold;\n",
  75        "}\n",
  76        ".get-type {\n",
  77        "color: green;\n",
  78        "font-weight: bold;\n",
  79        "font-family: monospace;\n",
  80        "display: block;\n",
  81        "white-space: pre-wrap;\n",
  82        "}\n",
  83        ".show-type {\n",
  84        "color: green;\n",
  85        "font-weight: bold;\n",
  86        "font-family: monospace;\n",
  87        "margin-left: 1em;\n",
  88        "}\n",
  89        ".mono {\n",
  90        "font-family: monospace;\n",
  91        "display: block;\n",
  92        "}\n",
  93        ".err-msg {\n",
  94        "color: red;\n",
  95        "font-style: italic;\n",
  96        "font-family: monospace;\n",
  97        "white-space: pre;\n",
  98        "display: block;\n",
  99        "}\n",
 100        "#unshowable {\n",
 101        "color: red;\n",
 102        "font-weight: bold;\n",
 103        "}\n",
 104        ".err-msg.in.collapse {\n",
 105        "padding-top: 0.7em;\n",
 106        "}\n",
 107        ".highlight-code {\n",
 108        "white-space: pre;\n",
 109        "font-family: monospace;\n",
 110        "}\n",
 111        ".suggestion-warning { \n",
 112        "font-weight: bold;\n",
 113        "color: rgb(200, 130, 0);\n",
 114        "}\n",
 115        ".suggestion-error { \n",
 116        "font-weight: bold;\n",
 117        "color: red;\n",
 118        "}\n",
 119        ".suggestion-name {\n",
 120        "font-weight: bold;\n",
 121        "}\n",
 122        "</style><div class=\"suggestion-name\" style=\"clear:both;\">Redundant bracket</div><div class=\"suggestion-row\" style=\"float: left;\"><div class=\"suggestion-warning\">Found:</div><div class=\"highlight-code\" id=\"haskell\">(fromIntegral a) * b</div></div><div class=\"suggestion-row\" style=\"float: left;\"><div class=\"suggestion-warning\">Why Not:</div><div class=\"highlight-code\" id=\"haskell\">fromIntegral a * b</div></div>"
 123       ],
 124       "text/plain": [
 125        "Line 1: Redundant bracket\n",
 126        "Found:\n",
 127        "(fromIntegral a) * b\n",
 128        "Why not:\n",
 129        "fromIntegral a * b"
 130       ]
 131      },
 132      "metadata": {},
 133      "output_type": "display_data"
 134     },
 135     {
 136      "data": {
 137       "text/plain": [
 138        "31512"
 139       ]
 140      },
 141      "metadata": {},
 142      "output_type": "display_data"
 143     }
 144    ],
 145    "source": [
 146     "(fromIntegral a) * b"
 147    ]
 148   },
 149   {
 150    "cell_type": "code",
 151    "execution_count": 5,
 152    "metadata": {},
 153    "outputs": [
 154     {
 155      "data": {
 156       "text/plain": [
 157        "24"
 158       ]
 159      },
 160      "metadata": {},
 161      "output_type": "display_data"
 162     }
 163    ],
 164    "source": [
 165     "(156 * 202) `mod` 256"
 166    ]
 167   },
 168   {
 169    "cell_type": "markdown",
 170    "metadata": {},
 171    "source": [
 172     "Generator A starts with 873\n",
 173     "\n",
 174     "Generator B starts with 583"
 175    ]
 176   },
 177   {
 178    "cell_type": "code",
 179    "execution_count": 6,
 180    "metadata": {},
 181    "outputs": [],
 182    "source": [
 183     "generator :: Word64 -> Word64 -> Word64 -> Word64\n",
 184     "generator divisor factor n = fromIntegral $ fromIntegral n * factor `rem` divisor"
 185    ]
 186   },
 187   {
 188    "cell_type": "code",
 189    "execution_count": 7,
 190    "metadata": {},
 191    "outputs": [],
 192    "source": [
 193     "generatorA = generator 2147483647 16807\n",
 194     "generatorB = generator 2147483647 48271"
 195    ]
 196   },
 197   {
 198    "cell_type": "code",
 199    "execution_count": 8,
 200    "metadata": {},
 201    "outputs": [],
 202    "source": [
 203     "toWord16 :: Word64 -> Word16\n",
 204     "toWord16 = fromIntegral"
 205    ]
 206   },
 207   {
 208    "cell_type": "code",
 209    "execution_count": 9,
 210    "metadata": {},
 211    "outputs": [
 212     {
 213      "data": {
 214       "text/plain": [
 215        "[43879,63289,58186,5831,38948]"
 216       ]
 217      },
 218      "metadata": {},
 219      "output_type": "display_data"
 220     }
 221    ],
 222    "source": [
 223     "map toWord16 $ take 5 $ drop 1 $ iterate generatorA 65"
 224    ]
 225   },
 226   {
 227    "cell_type": "code",
 228    "execution_count": 10,
 229    "metadata": {},
 230    "outputs": [
 231     {
 232      "data": {
 233       "text/plain": [
 234        "[54071,34184,58186,52231,10244]"
 235       ]
 236      },
 237      "metadata": {},
 238      "output_type": "display_data"
 239     }
 240    ],
 241    "source": [
 242     "map toWord16 $ take 5 $ drop 1 $ iterate generatorB 8921"
 243    ]
 244   },
 245   {
 246    "cell_type": "code",
 247    "execution_count": 11,
 248    "metadata": {},
 249    "outputs": [],
 250    "source": [
 251     "stream :: (Word64 -> Word64) -> Word64 -> [Word16]\n",
 252     "stream gen n0 = map toWord16 $ drop 1 $ iterate gen n0"
 253    ]
 254   },
 255   {
 256    "cell_type": "code",
 257    "execution_count": 12,
 258    "metadata": {},
 259    "outputs": [
 260     {
 261      "data": {
 262       "text/plain": [
 263        "588"
 264       ]
 265      },
 266      "metadata": {},
 267      "output_type": "display_data"
 268     }
 269    ],
 270    "source": [
 271     "length $ filter (uncurry (==)) $ take 40000000 $ zip (stream generatorA 65) (stream generatorB 8921)"
 272    ]
 273   },
 274   {
 275    "cell_type": "code",
 276    "execution_count": 13,
 277    "metadata": {},
 278    "outputs": [
 279     {
 280      "data": {
 281       "text/plain": [
 282        "631"
 283       ]
 284      },
 285      "metadata": {},
 286      "output_type": "display_data"
 287     }
 288    ],
 289    "source": [
 290     "length $ filter (uncurry (==)) $ take 40000000 $ zip (stream generatorA 873) (stream generatorB 583)"
 291    ]
 292   },
 293   {
 294    "cell_type": "code",
 295    "execution_count": 14,
 296    "metadata": {},
 297    "outputs": [],
 298    "source": [
 299     "filteredStream :: Word16 -> [Word16] -> [Word16]\n",
 300     "filteredStream f stream = filter (\\n -> n .&. f == 0) stream"
 301    ]
 302   },
 303   {
 304    "cell_type": "code",
 305    "execution_count": 15,
 306    "metadata": {},
 307    "outputs": [
 308     {
 309      "data": {
 310       "text/plain": [
 311        "[38948,48816,54372,43440,40536]"
 312       ]
 313      },
 314      "metadata": {},
 315      "output_type": "display_data"
 316     }
 317    ],
 318    "source": [
 319     "take 5 $ filteredStream 3 $ stream generatorA 65"
 320    ]
 321   },
 322   {
 323    "cell_type": "code",
 324    "execution_count": 16,
 325    "metadata": {},
 326    "outputs": [
 327     {
 328      "data": {
 329       "text/plain": [
 330        "38948"
 331       ]
 332      },
 333      "metadata": {},
 334      "output_type": "display_data"
 335     }
 336    ],
 337    "source": [
 338     "toWord16 1352636452"
 339    ]
 340   },
 341   {
 342    "cell_type": "code",
 343    "execution_count": 17,
 344    "metadata": {},
 345    "outputs": [
 346     {
 347      "data": {
 348       "text/plain": [
 349        "[1352636452,1992081072,530830436,1980017072,740335192]"
 350       ]
 351      },
 352      "metadata": {},
 353      "output_type": "display_data"
 354     }
 355    ],
 356    "source": [
 357     "take 5 $ filter (\\n -> n .&. 3 == 0) $ iterate generatorA 65"
 358    ]
 359   },
 360   {
 361    "cell_type": "code",
 362    "execution_count": 29,
 363    "metadata": {},
 364    "outputs": [
 365     {
 366      "data": {
 367       "text/plain": [
 368        "[1233683848,862516352,1159784568,1616057672,412269392]"
 369       ]
 370      },
 371      "metadata": {},
 372      "output_type": "display_data"
 373     }
 374    ],
 375    "source": [
 376     "take 5 $ filter (\\n -> n .&. 7 == 0) $ iterate generatorB 8921"
 377    ]
 378   },
 379   {
 380    "cell_type": "code",
 381    "execution_count": 34,
 382    "metadata": {},
 383    "outputs": [],
 384    "source": [
 385     "solE = length $ filter (uncurry (==)) $ take 5000000 $ zip fsA fsB\n",
 386     "    where fsA = filteredStream 3 $ stream generatorA 65\n",
 387     "          fsB = filteredStream 7 $ stream generatorB 8921"
 388    ]
 389   },
 390   {
 391    "cell_type": "code",
 392    "execution_count": 35,
 393    "metadata": {},
 394    "outputs": [
 395     {
 396      "data": {
 397       "text/plain": [
 398        "309"
 399       ]
 400      },
 401      "metadata": {},
 402      "output_type": "display_data"
 403     }
 404    ],
 405    "source": [
 406     "solE"
 407    ]
 408   },
 409   {
 410    "cell_type": "code",
 411    "execution_count": 32,
 412    "metadata": {},
 413    "outputs": [],
 414    "source": [
 415     "sol = length $ filter (uncurry (==)) $ take 5000000 $ zip fsA fsB\n",
 416     "    where fsA = filteredStream 3 $ stream generatorA 873\n",
 417     "          fsB = filteredStream 7 $ stream generatorB 583"
 418    ]
 419   },
 420   {
 421    "cell_type": "code",
 422    "execution_count": 33,
 423    "metadata": {},
 424    "outputs": [
 425     {
 426      "data": {
 427       "text/plain": [
 428        "279"
 429       ]
 430      },
 431      "metadata": {},
 432      "output_type": "display_data"
 433     }
 434    ],
 435    "source": [
 436     "sol"
 437    ]
 438   },
 439   {
 440    "cell_type": "code",
 441    "execution_count": null,
 442    "metadata": {},
 443    "outputs": [],
 444    "source": []
 445   }
 446  ],
 447  "metadata": {
 448   "kernelspec": {
 449    "display_name": "Haskell",
 450    "language": "haskell",
 451    "name": "haskell"
 452   },
 453   "language_info": {
 454    "codemirror_mode": "ihaskell",
 455    "file_extension": ".hs",
 456    "name": "haskell",
 457    "version": "8.0.2"
 458   }
 459  },
 460  "nbformat": 4,
 461  "nbformat_minor": 2
 462 }