src/advent10/advent10.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 #-}"
  11    ]
  12   },
  13   {
  14    "cell_type": "code",
  15    "execution_count": 113,
  16    "metadata": {},
  17    "outputs": [],
  18    "source": [
  19     "import Data.List.Split (splitOn, chunksOf)\n",
  20     "import Data.Char (ord, chr)\n",
  21     "import Data.Bits\n",
  22     "import Numeric (showHex)\n",
  23     "import Text.Printf"
  24    ]
  25   },
  26   {
  27    "cell_type": "code",
  28    "execution_count": 2,
  29    "metadata": {},
  30    "outputs": [],
  31    "source": [
  32     "extract items from len = take len $ drop from $ items ++ items"
  33    ]
  34   },
  35   {
  36    "cell_type": "code",
  37    "execution_count": 24,
  38    "metadata": {},
  39    "outputs": [],
  40    "source": [
  41     "-- replace original replacement from \n",
  42     "--     | from + length replacement <= length original = replacement ++ drop (length replacement) original\n",
  43     "--     | otherwise = drop (length original) extended ++ \n",
  44     "--             where extended = take from original ++ replacement ++ drop suflen original\n",
  45     "--                   suflen = from + length replacement - length original "
  46    ]
  47   },
  48   {
  49    "cell_type": "code",
  50    "execution_count": 51,
  51    "metadata": {},
  52    "outputs": [],
  53    "source": [
  54     "replace original replacement from = take (length original) (start ++ replacement ++ remainder)\n",
  55     "    where excess = drop (length original - from) replacement\n",
  56     "          stub = drop (length excess) original\n",
  57     "          start = take from (excess ++ stub)\n",
  58     "          remainder = drop (length $ start ++ replacement) original "
  59    ]
  60   },
  61   {
  62    "cell_type": "code",
  63    "execution_count": 52,
  64    "metadata": {},
  65    "outputs": [
  66     {
  67      "data": {
  68       "text/plain": [
  69        "[0,1,2]"
  70       ]
  71      },
  72      "metadata": {},
  73      "output_type": "display_data"
  74     }
  75    ],
  76    "source": [
  77     "extract [0, 1, 2, 3, 4] 0 3"
  78    ]
  79   },
  80   {
  81    "cell_type": "code",
  82    "execution_count": 53,
  83    "metadata": {},
  84    "outputs": [
  85     {
  86      "data": {
  87       "text/plain": [
  88        "[2,1,0]"
  89       ]
  90      },
  91      "metadata": {},
  92      "output_type": "display_data"
  93     }
  94    ],
  95    "source": [
  96     "reverse [0,1,2]"
  97    ]
  98   },
  99   {
 100    "cell_type": "code",
 101    "execution_count": 54,
 102    "metadata": {},
 103    "outputs": [],
 104    "source": [
 105     "l0 = [0,1,2,3,4]"
 106    ]
 107   },
 108   {
 109    "cell_type": "code",
 110    "execution_count": 55,
 111    "metadata": {},
 112    "outputs": [
 113     {
 114      "data": {
 115       "text/plain": [
 116        "[2,1,0,3,4]"
 117       ]
 118      },
 119      "metadata": {},
 120      "output_type": "display_data"
 121     }
 122    ],
 123    "source": [
 124     "replace l0 (reverse $ extract l0 0 3) 0"
 125    ]
 126   },
 127   {
 128    "cell_type": "code",
 129    "execution_count": 56,
 130    "metadata": {},
 131    "outputs": [
 132     {
 133      "data": {
 134       "text/plain": [
 135        "[4,0,1]"
 136       ]
 137      },
 138      "metadata": {},
 139      "output_type": "display_data"
 140     }
 141    ],
 142    "source": [
 143     "extract l0 4 3"
 144    ]
 145   },
 146   {
 147    "cell_type": "code",
 148    "execution_count": 57,
 149    "metadata": {},
 150    "outputs": [
 151     {
 152      "data": {
 153       "text/plain": [
 154        "[0,4,2,3,1]"
 155       ]
 156      },
 157      "metadata": {},
 158      "output_type": "display_data"
 159     }
 160    ],
 161    "source": [
 162     "replace l0 (reverse $ extract l0 4 3) 4"
 163    ]
 164   },
 165   {
 166    "cell_type": "markdown",
 167    "metadata": {},
 168    "source": [
 169     "0 1 2 3 4\n",
 170     "0 1 2 3 [4]\n",
 171     "0 1) 2 3 ([4]\n",
 172     "0 4) 2 3 (1\n",
 173     "\n",
 174     "0 1 2 3   4  | 0 1  2 3 4\n",
 175     "0 1 2 3  [4] | 0 1  2 3 4\n",
 176     "0 1 2 3 ([4] | 0 1) 2 3 4\n",
 177     "0 1 2 3 ( 1  | 0 4) 2 3 4\n",
 178     "\n",
 179     "\n",
 180     "  0  1 2  3 4 | 0 1 2 3 4\n",
 181     " [0] 1 2  3 4 | 0 1 2 3 4\n",
 182     "([0] 1 2) 3 4 | 0 1 2 3 4\n",
 183     "( 2  1 0) 3 4 | 0 1 2 3 4"
 184    ]
 185   },
 186   {
 187    "cell_type": "code",
 188    "execution_count": 58,
 189    "metadata": {},
 190    "outputs": [],
 191    "source": [
 192     "tie original start len = replace original replacement start\n",
 193     "    where replacement = reverse $ extract original start len"
 194    ]
 195   },
 196   {
 197    "cell_type": "code",
 198    "execution_count": 59,
 199    "metadata": {},
 200    "outputs": [
 201     {
 202      "data": {
 203       "text/html": [
 204        "<style>/* Styles used for the Hoogle display in the pager */\n",
 205        ".hoogle-doc {\n",
 206        "display: block;\n",
 207        "padding-bottom: 1.3em;\n",
 208        "padding-left: 0.4em;\n",
 209        "}\n",
 210        ".hoogle-code {\n",
 211        "display: block;\n",
 212        "font-family: monospace;\n",
 213        "white-space: pre;\n",
 214        "}\n",
 215        ".hoogle-text {\n",
 216        "display: block;\n",
 217        "}\n",
 218        ".hoogle-name {\n",
 219        "color: green;\n",
 220        "font-weight: bold;\n",
 221        "}\n",
 222        ".hoogle-head {\n",
 223        "font-weight: bold;\n",
 224        "}\n",
 225        ".hoogle-sub {\n",
 226        "display: block;\n",
 227        "margin-left: 0.4em;\n",
 228        "}\n",
 229        ".hoogle-package {\n",
 230        "font-weight: bold;\n",
 231        "font-style: italic;\n",
 232        "}\n",
 233        ".hoogle-module {\n",
 234        "font-weight: bold;\n",
 235        "}\n",
 236        ".hoogle-class {\n",
 237        "font-weight: bold;\n",
 238        "}\n",
 239        ".get-type {\n",
 240        "color: green;\n",
 241        "font-weight: bold;\n",
 242        "font-family: monospace;\n",
 243        "display: block;\n",
 244        "white-space: pre-wrap;\n",
 245        "}\n",
 246        ".show-type {\n",
 247        "color: green;\n",
 248        "font-weight: bold;\n",
 249        "font-family: monospace;\n",
 250        "margin-left: 1em;\n",
 251        "}\n",
 252        ".mono {\n",
 253        "font-family: monospace;\n",
 254        "display: block;\n",
 255        "}\n",
 256        ".err-msg {\n",
 257        "color: red;\n",
 258        "font-style: italic;\n",
 259        "font-family: monospace;\n",
 260        "white-space: pre;\n",
 261        "display: block;\n",
 262        "}\n",
 263        "#unshowable {\n",
 264        "color: red;\n",
 265        "font-weight: bold;\n",
 266        "}\n",
 267        ".err-msg.in.collapse {\n",
 268        "padding-top: 0.7em;\n",
 269        "}\n",
 270        ".highlight-code {\n",
 271        "white-space: pre;\n",
 272        "font-family: monospace;\n",
 273        "}\n",
 274        ".suggestion-warning { \n",
 275        "font-weight: bold;\n",
 276        "color: rgb(200, 130, 0);\n",
 277        "}\n",
 278        ".suggestion-error { \n",
 279        "font-weight: bold;\n",
 280        "color: red;\n",
 281        "}\n",
 282        ".suggestion-name {\n",
 283        "font-weight: bold;\n",
 284        "}\n",
 285        "</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\">(start + len + skip) `mod` (length original)</div></div><div class=\"suggestion-row\" style=\"float: left;\"><div class=\"suggestion-warning\">Why Not:</div><div class=\"highlight-code\" id=\"haskell\">(start + len + skip) `mod` length original</div></div>"
 286       ],
 287       "text/plain": [
 288        "Line 3: Redundant bracket\n",
 289        "Found:\n",
 290        "(start + len + skip) `mod` (length original)\n",
 291        "Why not:\n",
 292        "(start + len + skip) `mod` length original"
 293       ]
 294      },
 295      "metadata": {},
 296      "output_type": "display_data"
 297     }
 298    ],
 299    "source": [
 300     "step (original, start, skip) len = (replaced, start', skip + 1)\n",
 301     "    where replaced = tie original start len\n",
 302     "          start' = (start + len + skip) `mod` (length original)"
 303    ]
 304   },
 305   {
 306    "cell_type": "code",
 307    "execution_count": 60,
 308    "metadata": {},
 309    "outputs": [
 310     {
 311      "data": {
 312       "text/plain": [
 313        "[0,1,2,3,4]"
 314       ]
 315      },
 316      "metadata": {},
 317      "output_type": "display_data"
 318     }
 319    ],
 320    "source": [
 321     "[0..4]"
 322    ]
 323   },
 324   {
 325    "cell_type": "code",
 326    "execution_count": 61,
 327    "metadata": {},
 328    "outputs": [
 329     {
 330      "data": {
 331       "text/plain": [
 332        "([2,1,0,3,4],3,1)"
 333       ]
 334      },
 335      "metadata": {},
 336      "output_type": "display_data"
 337     }
 338    ],
 339    "source": [
 340     "step ([0..4], 0, 0) 3"
 341    ]
 342   },
 343   {
 344    "cell_type": "code",
 345    "execution_count": 66,
 346    "metadata": {},
 347    "outputs": [
 348     {
 349      "data": {
 350       "text/plain": [
 351        "([3,4,2,1,0],4,4)"
 352       ]
 353      },
 354      "metadata": {},
 355      "output_type": "display_data"
 356     }
 357    ],
 358    "source": [
 359     "foldl step ([0..4], 0, 0) [3, 4, 1, 5]"
 360    ]
 361   },
 362   {
 363    "cell_type": "code",
 364    "execution_count": 79,
 365    "metadata": {},
 366    "outputs": [],
 367    "source": [
 368     "part1 :: [Int] -> Int\n",
 369     "part1 lengths = (tied!!0) * (tied!!1)\n",
 370     "    where (tied, _, _) = foldl step ([0..255], 0, 0) lengths"
 371    ]
 372   },
 373   {
 374    "cell_type": "code",
 375    "execution_count": 101,
 376    "metadata": {},
 377    "outputs": [],
 378    "source": [
 379     "part2 text = tied\n",
 380     "    where lengths = p2lengths text\n",
 381     "          (tied, _, _) = foldl step ([0..255], 0, 0) lengths"
 382    ]
 383   },
 384   {
 385    "cell_type": "code",
 386    "execution_count": 102,
 387    "metadata": {},
 388    "outputs": [],
 389    "source": [
 390     "main :: IO ()\n",
 391     "main = do \n",
 392     "        text <- readFile \"../../data/advent10.txt\"\n",
 393     "        let instrs = map read $ splitOn \",\" text\n",
 394     "        print $ part1 instrs\n",
 395     "        print $ part2 text"
 396    ]
 397   },
 398   {
 399    "cell_type": "code",
 400    "execution_count": 103,
 401    "metadata": {},
 402    "outputs": [
 403     {
 404      "data": {
 405       "text/plain": [
 406        "38415\n",
 407        "[166,221,219,74,89,118,226,182,77,185,188,87,238,181,229,173,45,68,84,147,10,194,196,201,55,80,171,119,186,54,154,46,52,161,9,149,135,255,180,210,129,214,127,18,51,236,56,78,24,187,97,25,131,70,143,106,211,218,189,224,179,220,41,141,240,233,76,26,253,207,159,172,86,241,136,215,12,197,112,62,23,138,0,169,99,50,235,205,122,103,116,71,251,160,206,22,4,202,252,40,234,242,193,39,32,191,63,217,152,117,33,163,61,213,164,133,6,16,110,58,102,43,126,67,31,30,95,199,2,183,1,208,239,96,20,13,57,66,38,132,177,195,44,203,247,65,14,227,100,82,151,3,28,150,98,146,140,37,42,120,168,91,83,27,209,148,176,250,101,162,145,79,115,15,228,192,142,104,155,29,19,53,49,35,128,5,184,248,222,123,124,216,178,64,113,198,244,245,246,167,47,11,170,212,109,114,237,94,144,69,243,254,121,231,59,108,17,153,249,34,72,7,130,21,200,175,81,134,105,137,75,165,156,174,232,125,92,88,8,93,157,223,225,48,111,85,107,204,36,158,90,139,190,230,60,73]"
 408       ]
 409      },
 410      "metadata": {},
 411      "output_type": "display_data"
 412     }
 413    ],
 414    "source": [
 415     "main"
 416    ]
 417   },
 418   {
 419    "cell_type": "code",
 420    "execution_count": 85,
 421    "metadata": {},
 422    "outputs": [
 423     {
 424      "data": {
 425       "text/plain": [
 426        "97"
 427       ]
 428      },
 429      "metadata": {},
 430      "output_type": "display_data"
 431     }
 432    ],
 433    "source": [
 434     "ord 'a'"
 435    ]
 436   },
 437   {
 438    "cell_type": "code",
 439    "execution_count": 86,
 440    "metadata": {},
 441    "outputs": [
 442     {
 443      "data": {
 444       "text/plain": [
 445        "'a'"
 446       ]
 447      },
 448      "metadata": {},
 449      "output_type": "display_data"
 450     }
 451    ],
 452    "source": [
 453     "chr 97"
 454    ]
 455   },
 456   {
 457    "cell_type": "code",
 458    "execution_count": 88,
 459    "metadata": {},
 460    "outputs": [
 461     {
 462      "data": {
 463       "text/plain": [
 464        "4"
 465       ]
 466      },
 467      "metadata": {},
 468      "output_type": "display_data"
 469     }
 470    ],
 471    "source": [
 472     "7 `xor` 3"
 473    ]
 474   },
 475   {
 476    "cell_type": "code",
 477    "execution_count": 112,
 478    "metadata": {},
 479    "outputs": [
 480     {
 481      "data": {
 482       "text/plain": [
 483        "\"ff\""
 484       ]
 485      },
 486      "metadata": {},
 487      "output_type": "display_data"
 488     }
 489    ],
 490    "source": [
 491     "showHex 255 \"\""
 492    ]
 493   },
 494   {
 495    "cell_type": "code",
 496    "execution_count": 116,
 497    "metadata": {},
 498    "outputs": [
 499     {
 500      "data": {
 501       "text/plain": [
 502        "ff"
 503       ]
 504      },
 505      "metadata": {},
 506      "output_type": "display_data"
 507     }
 508    ],
 509    "source": [
 510     "printf \"%02x\" 255"
 511    ]
 512   },
 513   {
 514    "cell_type": "code",
 515    "execution_count": 93,
 516    "metadata": {},
 517    "outputs": [],
 518    "source": [
 519     "p2lengths text = take (length chunk * 64) $ cycle chunk\n",
 520     "    where chunk = map ord text ++ [17, 31, 73, 47, 23]"
 521    ]
 522   },
 523   {
 524    "cell_type": "code",
 525    "execution_count": 117,
 526    "metadata": {},
 527    "outputs": [],
 528    "source": [
 529     "densify ns = concatMap (printf \"%02x\") codes\n",
 530     "    where chunks = chunksOf 16 ns\n",
 531     "          compress = foldl1 xor\n",
 532     "          codes = map compress chunks"
 533    ]
 534   },
 535   {
 536    "cell_type": "code",
 537    "execution_count": 126,
 538    "metadata": {},
 539    "outputs": [],
 540    "source": [
 541     "part2 :: String -> String\n",
 542     "part2 text = densify tied\n",
 543     "    where lengths = p2lengths text\n",
 544     "          (tied, _, _) = foldl step ([0..255], 0, 0) lengths"
 545    ]
 546   },
 547   {
 548    "cell_type": "code",
 549    "execution_count": 121,
 550    "metadata": {},
 551    "outputs": [
 552     {
 553      "data": {
 554       "text/plain": [
 555        "a2582a3a0e66e6e86e3812dcb672a272"
 556       ]
 557      },
 558      "metadata": {},
 559      "output_type": "display_data"
 560     }
 561    ],
 562    "source": [
 563     "putStrLn $ part2 \"\""
 564    ]
 565   },
 566   {
 567    "cell_type": "code",
 568    "execution_count": 122,
 569    "metadata": {},
 570    "outputs": [
 571     {
 572      "data": {
 573       "text/plain": [
 574        "33efeb34ea91902bb2f59c9920caa6cd"
 575       ]
 576      },
 577      "metadata": {},
 578      "output_type": "display_data"
 579     }
 580    ],
 581    "source": [
 582     "putStrLn $ part2 \"AoC 2017\""
 583    ]
 584   },
 585   {
 586    "cell_type": "code",
 587    "execution_count": 123,
 588    "metadata": {},
 589    "outputs": [
 590     {
 591      "data": {
 592       "text/plain": [
 593        "3efbe78a8d82f29979031a4aa0b16a9d"
 594       ]
 595      },
 596      "metadata": {},
 597      "output_type": "display_data"
 598     }
 599    ],
 600    "source": [
 601     "putStrLn $ part2 \"1,2,3\""
 602    ]
 603   },
 604   {
 605    "cell_type": "code",
 606    "execution_count": 124,
 607    "metadata": {},
 608    "outputs": [
 609     {
 610      "data": {
 611       "text/plain": [
 612        "63960835bcdc130f0b66d7ff4f6a5a8e"
 613       ]
 614      },
 615      "metadata": {},
 616      "output_type": "display_data"
 617     }
 618    ],
 619    "source": [
 620     "putStrLn $ part2 \"1,2,4\""
 621    ]
 622   },
 623   {
 624    "cell_type": "code",
 625    "execution_count": 129,
 626    "metadata": {},
 627    "outputs": [],
 628    "source": [
 629     "main :: IO ()\n",
 630     "main = do \n",
 631     "        text <- readFile \"../../data/advent10.txt\"\n",
 632     "        let instrs = map read $ splitOn \",\" text\n",
 633     "        print $ part1 instrs\n",
 634     "        putStrLn $ part2 text"
 635    ]
 636   },
 637   {
 638    "cell_type": "code",
 639    "execution_count": 130,
 640    "metadata": {},
 641    "outputs": [
 642     {
 643      "data": {
 644       "text/plain": [
 645        "38415\n",
 646        "9de8846431eef262be78f590e39a4848"
 647       ]
 648      },
 649      "metadata": {},
 650      "output_type": "display_data"
 651     }
 652    ],
 653    "source": [
 654     "main"
 655    ]
 656   },
 657   {
 658    "cell_type": "code",
 659    "execution_count": null,
 660    "metadata": {},
 661    "outputs": [],
 662    "source": []
 663   }
 664  ],
 665  "metadata": {
 666   "kernelspec": {
 667    "display_name": "Haskell",
 668    "language": "haskell",
 669    "name": "haskell"
 670   },
 671   "language_info": {
 672    "codemirror_mode": "ihaskell",
 673    "file_extension": ".hs",
 674    "name": "haskell",
 675    "version": "8.0.2"
 676   }
 677  },
 678  "nbformat": 4,
 679  "nbformat_minor": 2
 680 }