src/advent20/advent20.ipynb

   1 {
   2  "cells": [
   3   {
   4    "cell_type": "code",
   5    "execution_count": 50,
   6    "metadata": {},
   7    "outputs": [],
   8    "source": [
   9     "{-# LANGUAGE NegativeLiterals #-}\n",
  10     "{-# LANGUAGE FlexibleContexts #-}\n",
  11     "{-# LANGUAGE OverloadedStrings #-}\n",
  12     "{-# LANGUAGE TypeFamilies #-}\n",
  13     "{-# LANGUAGE BangPatterns #-}"
  14    ]
  15   },
  16   {
  17    "cell_type": "code",
  18    "execution_count": 106,
  19    "metadata": {},
  20    "outputs": [],
  21    "source": [
  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.Map.Strict as M\n",
  32     "import Data.Map.Strict ((!))\n",
  33     "\n",
  34     "import Data.Vector ((!), (//))\n",
  35     "import qualified Data.Vector as V\n",
  36     "\n",
  37     "import Data.List \n",
  38     "\n",
  39     "import qualified Data.Set as S"
  40    ]
  41   },
  42   {
  43    "cell_type": "code",
  44    "execution_count": 52,
  45    "metadata": {},
  46    "outputs": [],
  47    "source": [
  48     "type Vec = V.Vector Integer\n",
  49     "\n",
  50     "data Particle = Particle \n",
  51     "                    { position :: Vec\n",
  52     "                    , velocity :: Vec\n",
  53     "                    , acceleration :: Vec\n",
  54     "                    } deriving (Show, Eq)"
  55    ]
  56   },
  57   {
  58    "cell_type": "code",
  59    "execution_count": 53,
  60    "metadata": {},
  61    "outputs": [],
  62    "source": [
  63     "sc :: Parser ()\n",
  64     "sc = L.space (skipSome spaceChar) CA.empty CA.empty\n",
  65     "\n",
  66     "lexeme  = L.lexeme sc\n",
  67     "\n",
  68     "integer       = lexeme L.integer\n",
  69     "signedInteger = L.signed sc integer\n",
  70     "\n",
  71     "symbol = L.symbol sc\n",
  72     "separator = symbol \", \"\n",
  73     "comma = symbol \",\"\n",
  74     "\n",
  75     "particlesP = particleP `sepBy` space\n",
  76     "particleP = particlify <$> (symbol \"p=\" *> vecP <* separator)\n",
  77     "                       <*> (symbol \"v=\" *> vecP <* separator)\n",
  78     "                       <*> (symbol \"a=\" *> vecP)\n",
  79     "    where particlify p v a = Particle {position = p, velocity = v, acceleration = a}\n",
  80     "\n",
  81     "\n",
  82     "vecP = V.fromList <$> between (symbol \"<\") (symbol \">\") (signedInteger `sepBy` comma)\n",
  83     "\n",
  84     "\n",
  85     "successfulParse :: Text -> [Particle]\n",
  86     "successfulParse input = \n",
  87     "        case parse particlesP \"input\" input of\n",
  88     "                Left  _error -> [] -- TIO.putStr $ T.pack $ parseErrorPretty err\n",
  89     "                Right instructions  -> instructions"
  90    ]
  91   },
  92   {
  93    "cell_type": "code",
  94    "execution_count": 54,
  95    "metadata": {},
  96    "outputs": [
  97     {
  98      "data": {
  99       "text/plain": [
 100        "[-833,-499,-1391]"
 101       ]
 102      },
 103      "metadata": {},
 104      "output_type": "display_data"
 105     }
 106    ],
 107    "source": [
 108     "parseTest vecP \"<-833,-499,-1391>\""
 109    ]
 110   },
 111   {
 112    "cell_type": "code",
 113    "execution_count": 55,
 114    "metadata": {},
 115    "outputs": [
 116     {
 117      "data": {
 118       "text/plain": [
 119        "Particle {position = [3,0,0], velocity = [2,0,0], acceleration = [-1,0,0]}"
 120       ]
 121      },
 122      "metadata": {},
 123      "output_type": "display_data"
 124     }
 125    ],
 126    "source": [
 127     "parseTest particleP \"p=< 3,0,0>, v=<2,0,0>, a=<-1,0,0>\""
 128    ]
 129   },
 130   {
 131    "cell_type": "code",
 132    "execution_count": 56,
 133    "metadata": {},
 134    "outputs": [
 135     {
 136      "data": {
 137       "text/plain": [
 138        "Particle {position = [4,0,0], velocity = [0,0,0], acceleration = [-2,0,0]}"
 139       ]
 140      },
 141      "metadata": {},
 142      "output_type": "display_data"
 143     }
 144    ],
 145    "source": [
 146     "parseTest particleP \"p=< 4,0,0>, v=< 0,0,0>, a=<-2,0,0>\""
 147    ]
 148   },
 149   {
 150    "cell_type": "code",
 151    "execution_count": 57,
 152    "metadata": {},
 153    "outputs": [
 154     {
 155      "data": {
 156       "text/plain": [
 157        "[Particle {position = [3,0,0], velocity = [2,0,0], acceleration = [-1,0,0]},Particle {position = [4,0,0], velocity = [0,0,0], acceleration = [-2,0,0]}]"
 158       ]
 159      },
 160      "metadata": {},
 161      "output_type": "display_data"
 162     }
 163    ],
 164    "source": [
 165     "parseTest particlesP \"p=< 3,0,0>, v=<2,0,0>, a=<-1,0,0>\\np=< 4,0,0>, v=< 0,0,0>, a=<-2,0,0>\""
 166    ]
 167   },
 168   {
 169    "cell_type": "code",
 170    "execution_count": 58,
 171    "metadata": {},
 172    "outputs": [],
 173    "source": [
 174     "(p0:p1:_) = successfulParse \"p=< 3,0,0>, v=<2,0,0>, a=<-1,0,0>\\np=< 4,0,0>, v=< 0,0,0>, a=<-2,0,0>\""
 175    ]
 176   },
 177   {
 178    "cell_type": "code",
 179    "execution_count": 59,
 180    "metadata": {},
 181    "outputs": [
 182     {
 183      "data": {
 184       "text/plain": [
 185        "Particle {position = [3,0,0], velocity = [2,0,0], acceleration = [-1,0,0]}"
 186       ]
 187      },
 188      "metadata": {},
 189      "output_type": "display_data"
 190     }
 191    ],
 192    "source": [
 193     "p0"
 194    ]
 195   },
 196   {
 197    "cell_type": "code",
 198    "execution_count": 60,
 199    "metadata": {},
 200    "outputs": [
 201     {
 202      "data": {
 203       "text/plain": [
 204        "Particle {position = [4,0,0], velocity = [0,0,0], acceleration = [-2,0,0]}"
 205       ]
 206      },
 207      "metadata": {},
 208      "output_type": "display_data"
 209     }
 210    ],
 211    "source": [
 212     "p1"
 213    ]
 214   },
 215   {
 216    "cell_type": "code",
 217    "execution_count": 61,
 218    "metadata": {},
 219    "outputs": [],
 220    "source": [
 221     "step :: Particle -> Particle\n",
 222     "step particle = particle {position = p', velocity = v'}\n",
 223     "    where pv' = V.zipWith3 updatePV (position particle) (velocity particle) (acceleration particle)\n",
 224     "          !(p', v') = V.unzip pv'\n",
 225     "          updatePV p v a = (p + v + a, v + a)"
 226    ]
 227   },
 228   {
 229    "cell_type": "code",
 230    "execution_count": 62,
 231    "metadata": {},
 232    "outputs": [
 233     {
 234      "data": {
 235       "text/plain": [
 236        "Particle {position = [-2,0,0], velocity = [-4,0,0], acceleration = [-2,0,0]}"
 237       ]
 238      },
 239      "metadata": {},
 240      "output_type": "display_data"
 241     }
 242    ],
 243    "source": [
 244     "step $ step p1"
 245    ]
 246   },
 247   {
 248    "cell_type": "code",
 249    "execution_count": 63,
 250    "metadata": {},
 251    "outputs": [
 252     {
 253      "data": {
 254       "text/plain": [
 255        "Particle {position = [3,0,0], velocity = [2,0,0], acceleration = [-2,0,1]}"
 256       ]
 257      },
 258      "metadata": {},
 259      "output_type": "display_data"
 260     }
 261    ],
 262    "source": [
 263     "p2 = p0 {acceleration = V.fromList [-2, 0, 1]}\n",
 264     "p2"
 265    ]
 266   },
 267   {
 268    "cell_type": "code",
 269    "execution_count": 64,
 270    "metadata": {},
 271    "outputs": [
 272     {
 273      "data": {
 274       "text/plain": [
 275        "Particle {position = [1,0,3], velocity = [-2,0,2], acceleration = [-2,0,1]}"
 276       ]
 277      },
 278      "metadata": {},
 279      "output_type": "display_data"
 280     }
 281    ],
 282    "source": [
 283     "step $ step p2"
 284    ]
 285   },
 286   {
 287    "cell_type": "code",
 288    "execution_count": 65,
 289    "metadata": {},
 290    "outputs": [],
 291    "source": [
 292     "quiescent :: Particle -> Bool\n",
 293     "quiescent particle = and qDimensions\n",
 294     "    where qDimensions = V.zipWith3 sameSigns (position particle) (velocity particle) (acceleration particle)\n",
 295     "          sameSigns !p !v !a = if a == 0 && v == 0\n",
 296     "                               then True\n",
 297     "                               else if a == 0\n",
 298     "                                    then signum p == signum v\n",
 299     "                                    else signum p == signum v && signum v == signum a"
 300    ]
 301   },
 302   {
 303    "cell_type": "code",
 304    "execution_count": 66,
 305    "metadata": {},
 306    "outputs": [
 307     {
 308      "data": {
 309       "text/plain": [
 310        "False"
 311       ]
 312      },
 313      "metadata": {},
 314      "output_type": "display_data"
 315     }
 316    ],
 317    "source": [
 318     "quiescent p2"
 319    ]
 320   },
 321   {
 322    "cell_type": "code",
 323    "execution_count": 67,
 324    "metadata": {},
 325    "outputs": [],
 326    "source": [
 327     "simulate :: [Particle] -> [Particle]\n",
 328     "simulate particles = \n",
 329     "    if all quiescent particles\n",
 330     "    then particles\n",
 331     "    else simulate (map step particles)"
 332    ]
 333   },
 334   {
 335    "cell_type": "code",
 336    "execution_count": 68,
 337    "metadata": {},
 338    "outputs": [
 339     {
 340      "data": {
 341       "text/plain": [
 342        "[Particle {position = [3,0,0], velocity = [2,0,0], acceleration = [-1,0,0]},Particle {position = [4,0,0], velocity = [0,0,0], acceleration = [-2,0,0]},Particle {position = [3,0,0], velocity = [2,0,0], acceleration = [-2,0,1]}]"
 343       ]
 344      },
 345      "metadata": {},
 346      "output_type": "display_data"
 347     }
 348    ],
 349    "source": [
 350     "particles = [p0, p1, p2]\n",
 351     "particles"
 352    ]
 353   },
 354   {
 355    "cell_type": "code",
 356    "execution_count": 69,
 357    "metadata": {},
 358    "outputs": [
 359     {
 360      "data": {
 361       "text/plain": [
 362        "[Particle {position = [-2,0,0], velocity = [-3,0,0], acceleration = [-1,0,0]},Particle {position = [-26,0,0], velocity = [-10,0,0], acceleration = [-2,0,0]},Particle {position = [-17,0,15], velocity = [-8,0,5], acceleration = [-2,0,1]}]"
 363       ]
 364      },
 365      "metadata": {},
 366      "output_type": "display_data"
 367     }
 368    ],
 369    "source": [
 370     "simulate particles"
 371    ]
 372   },
 373   {
 374    "cell_type": "code",
 375    "execution_count": 70,
 376    "metadata": {},
 377    "outputs": [],
 378    "source": [
 379     "pAbs :: Particle -> Particle\n",
 380     "pAbs particle = particle {position = p', velocity = v', acceleration = a'}\n",
 381     "    where !p' = V.map abs (position particle)\n",
 382     "          !v' = V.map abs (velocity particle)\n",
 383     "          !a' = V.map abs (acceleration particle)\n",
 384     "    "
 385    ]
 386   },
 387   {
 388    "cell_type": "code",
 389    "execution_count": 71,
 390    "metadata": {
 391     "scrolled": true
 392    },
 393    "outputs": [
 394     {
 395      "data": {
 396       "text/plain": [
 397        "Particle {position = [3,0,0], velocity = [2,0,0], acceleration = [-2,0,1]}"
 398       ]
 399      },
 400      "metadata": {},
 401      "output_type": "display_data"
 402     }
 403    ],
 404    "source": [
 405     "p2"
 406    ]
 407   },
 408   {
 409    "cell_type": "code",
 410    "execution_count": 72,
 411    "metadata": {},
 412    "outputs": [
 413     {
 414      "data": {
 415       "text/plain": [
 416        "Particle {position = [3,0,0], velocity = [2,0,0], acceleration = [2,0,1]}"
 417       ]
 418      },
 419      "metadata": {},
 420      "output_type": "display_data"
 421     }
 422    ],
 423    "source": [
 424     "pAbs p2"
 425    ]
 426   },
 427   {
 428    "cell_type": "code",
 429    "execution_count": 73,
 430    "metadata": {},
 431    "outputs": [],
 432    "source": [
 433     "pMin p1 p2 = Particle {position = p', velocity = v', acceleration = a'}\n",
 434     "    where !p' = V.zipWith min (position p1) (position p2)\n",
 435     "          !v' = V.zipWith min (velocity p1) (velocity p2)\n",
 436     "          !a' = V.zipWith min (acceleration p1) (acceleration p2)"
 437    ]
 438   },
 439   {
 440    "cell_type": "code",
 441    "execution_count": 74,
 442    "metadata": {},
 443    "outputs": [
 444     {
 445      "data": {
 446       "text/plain": [
 447        "Particle {position = [3,0,0], velocity = [2,0,0], acceleration = [-1,0,0]}"
 448       ]
 449      },
 450      "metadata": {},
 451      "output_type": "display_data"
 452     }
 453    ],
 454    "source": [
 455     "p0"
 456    ]
 457   },
 458   {
 459    "cell_type": "code",
 460    "execution_count": 75,
 461    "metadata": {},
 462    "outputs": [
 463     {
 464      "data": {
 465       "text/plain": [
 466        "Particle {position = [3,0,0], velocity = [2,0,0], acceleration = [-2,0,1]}"
 467       ]
 468      },
 469      "metadata": {},
 470      "output_type": "display_data"
 471     }
 472    ],
 473    "source": [
 474     "p2"
 475    ]
 476   },
 477   {
 478    "cell_type": "code",
 479    "execution_count": 76,
 480    "metadata": {},
 481    "outputs": [
 482     {
 483      "data": {
 484       "text/plain": [
 485        "Particle {position = [3,0,0], velocity = [2,0,0], acceleration = [1,0,0]}"
 486       ]
 487      },
 488      "metadata": {},
 489      "output_type": "display_data"
 490     }
 491    ],
 492    "source": [
 493     "pMin (pAbs p0) (pAbs p2)"
 494    ]
 495   },
 496   {
 497    "cell_type": "code",
 498    "execution_count": 77,
 499    "metadata": {},
 500    "outputs": [
 501     {
 502      "data": {
 503       "text/plain": [
 504        "Particle {position = [3,0,0], velocity = [2,0,0], acceleration = [2,0,1]}"
 505       ]
 506      },
 507      "metadata": {},
 508      "output_type": "display_data"
 509     }
 510    ],
 511    "source": [
 512     "pAbs p2"
 513    ]
 514   },
 515   {
 516    "cell_type": "code",
 517    "execution_count": 78,
 518    "metadata": {},
 519    "outputs": [],
 520    "source": [
 521     "clearClosest :: [Particle] -> Maybe Int\n",
 522     "clearClosest particles = elemIndex targetParticle absParticles\n",
 523     "    where absParticles = map pAbs particles\n",
 524     "          targetParticle = foldl1' pMin absParticles"
 525    ]
 526   },
 527   {
 528    "cell_type": "code",
 529    "execution_count": 79,
 530    "metadata": {},
 531    "outputs": [],
 532    "source": [
 533     "pAbsA :: Particle -> Integer\n",
 534     "pAbsA particle = V.foldl1' (+) $ V.map abs (acceleration particle)  "
 535    ]
 536   },
 537   {
 538    "cell_type": "code",
 539    "execution_count": 80,
 540    "metadata": {},
 541    "outputs": [],
 542    "source": [
 543     "pAbsX :: Particle -> Integer\n",
 544     "pAbsX particle = V.foldl1' (+) $ V.map abs (position particle)  "
 545    ]
 546   },
 547   {
 548    "cell_type": "code",
 549    "execution_count": 81,
 550    "metadata": {},
 551    "outputs": [],
 552    "source": [
 553     "lowestAcc particles = elemIndices minAcc absAccs\n",
 554     "    where absAccs = map pAbsA particles\n",
 555     "          minAcc = minimum absAccs"
 556    ]
 557   },
 558   {
 559    "cell_type": "code",
 560    "execution_count": 82,
 561    "metadata": {},
 562    "outputs": [],
 563    "source": [
 564     "main :: IO ()\n",
 565     "main = do \n",
 566     "        text <- TIO.readFile \"../../data/advent20.txt\"\n",
 567     "        let particles = successfulParse text\n",
 568     "--         print particles\n",
 569     "        print $ lowestAcc particles\n",
 570     "--         print $ part2 instrs"
 571    ]
 572   },
 573   {
 574    "cell_type": "code",
 575    "execution_count": 83,
 576    "metadata": {},
 577    "outputs": [
 578     {
 579      "data": {
 580       "text/plain": [
 581        "[21,457]"
 582       ]
 583      },
 584      "metadata": {},
 585      "output_type": "display_data"
 586     }
 587    ],
 588    "source": [
 589     "main"
 590    ]
 591   },
 592   {
 593    "cell_type": "code",
 594    "execution_count": 84,
 595    "metadata": {},
 596    "outputs": [],
 597    "source": [
 598     "-- particles!!21"
 599    ]
 600   },
 601   {
 602    "cell_type": "code",
 603    "execution_count": 85,
 604    "metadata": {},
 605    "outputs": [],
 606    "source": [
 607     "-- particles!!457"
 608    ]
 609   },
 610   {
 611    "cell_type": "code",
 612    "execution_count": 86,
 613    "metadata": {},
 614    "outputs": [],
 615    "source": [
 616     "withMinX particles = minX `elemIndices` absXs\n",
 617     "    where absXs = map pAbsX particles\n",
 618     "          minX = minimum absXs"
 619    ]
 620   },
 621   {
 622    "cell_type": "code",
 623    "execution_count": 87,
 624    "metadata": {},
 625    "outputs": [],
 626    "source": [
 627     "simulateQ :: [Particle] -> [Particle]\n",
 628     "simulateQ particles = \n",
 629     "    if all quiescent particles\n",
 630     "    then particles\n",
 631     "    else simulateQ (map step particles)"
 632    ]
 633   },
 634   {
 635    "cell_type": "code",
 636    "execution_count": 88,
 637    "metadata": {},
 638    "outputs": [],
 639    "source": [
 640     "simulate :: [Particle] -> [Particle]\n",
 641     "simulate particles = \n",
 642     "    if all quiescent particles && length withMinXs == 1\n",
 643     "    then particles\n",
 644     "    else simulate (map step particles)\n",
 645     "    where withMinXs = withMinX particles"
 646    ]
 647   },
 648   {
 649    "cell_type": "code",
 650    "execution_count": 89,
 651    "metadata": {},
 652    "outputs": [],
 653    "source": [
 654     "pf = simulate particles"
 655    ]
 656   },
 657   {
 658    "cell_type": "code",
 659    "execution_count": 90,
 660    "metadata": {},
 661    "outputs": [
 662     {
 663      "data": {
 664       "text/plain": [
 665        "[0]"
 666       ]
 667      },
 668      "metadata": {},
 669      "output_type": "display_data"
 670     }
 671    ],
 672    "source": [
 673     "withMinX pf"
 674    ]
 675   },
 676   {
 677    "cell_type": "code",
 678    "execution_count": 100,
 679    "metadata": {},
 680    "outputs": [],
 681    "source": [
 682     "-- part1 particles = head minInContext\n",
 683     "--         where pf = simulate slowParticles\n",
 684     "--               slowIndices = lowestAcc particles\n",
 685     "--               slowParticles = map (particles !!) slowIndices\n",
 686     "--               minInContext = map (slowIndices !!) $ withMinX pf"
 687    ]
 688   },
 689   {
 690    "cell_type": "code",
 691    "execution_count": 103,
 692    "metadata": {},
 693    "outputs": [],
 694    "source": [
 695     "part1 particles = head $ withMinX pf\n",
 696     "        where pf = simulate particles"
 697    ]
 698   },
 699   {
 700    "cell_type": "code",
 701    "execution_count": 104,
 702    "metadata": {},
 703    "outputs": [],
 704    "source": [
 705     "main :: IO ()\n",
 706     "main = do \n",
 707     "        text <- TIO.readFile \"../../data/advent20.txt\"\n",
 708     "        let particles = successfulParse text\n",
 709     "        print $ part1 particles\n",
 710     "--         print $ part2 instrs"
 711    ]
 712   },
 713   {
 714    "cell_type": "code",
 715    "execution_count": 93,
 716    "metadata": {},
 717    "outputs": [],
 718    "source": [
 719     "-- main"
 720    ]
 721   },
 722   {
 723    "cell_type": "code",
 724    "execution_count": 94,
 725    "metadata": {},
 726    "outputs": [
 727     {
 728      "data": {
 729       "text/html": [
 730        "<style>/* Styles used for the Hoogle display in the pager */\n",
 731        ".hoogle-doc {\n",
 732        "display: block;\n",
 733        "padding-bottom: 1.3em;\n",
 734        "padding-left: 0.4em;\n",
 735        "}\n",
 736        ".hoogle-code {\n",
 737        "display: block;\n",
 738        "font-family: monospace;\n",
 739        "white-space: pre;\n",
 740        "}\n",
 741        ".hoogle-text {\n",
 742        "display: block;\n",
 743        "}\n",
 744        ".hoogle-name {\n",
 745        "color: green;\n",
 746        "font-weight: bold;\n",
 747        "}\n",
 748        ".hoogle-head {\n",
 749        "font-weight: bold;\n",
 750        "}\n",
 751        ".hoogle-sub {\n",
 752        "display: block;\n",
 753        "margin-left: 0.4em;\n",
 754        "}\n",
 755        ".hoogle-package {\n",
 756        "font-weight: bold;\n",
 757        "font-style: italic;\n",
 758        "}\n",
 759        ".hoogle-module {\n",
 760        "font-weight: bold;\n",
 761        "}\n",
 762        ".hoogle-class {\n",
 763        "font-weight: bold;\n",
 764        "}\n",
 765        ".get-type {\n",
 766        "color: green;\n",
 767        "font-weight: bold;\n",
 768        "font-family: monospace;\n",
 769        "display: block;\n",
 770        "white-space: pre-wrap;\n",
 771        "}\n",
 772        ".show-type {\n",
 773        "color: green;\n",
 774        "font-weight: bold;\n",
 775        "font-family: monospace;\n",
 776        "margin-left: 1em;\n",
 777        "}\n",
 778        ".mono {\n",
 779        "font-family: monospace;\n",
 780        "display: block;\n",
 781        "}\n",
 782        ".err-msg {\n",
 783        "color: red;\n",
 784        "font-style: italic;\n",
 785        "font-family: monospace;\n",
 786        "white-space: pre;\n",
 787        "display: block;\n",
 788        "}\n",
 789        "#unshowable {\n",
 790        "color: red;\n",
 791        "font-weight: bold;\n",
 792        "}\n",
 793        ".err-msg.in.collapse {\n",
 794        "padding-top: 0.7em;\n",
 795        "}\n",
 796        ".highlight-code {\n",
 797        "white-space: pre;\n",
 798        "font-family: monospace;\n",
 799        "}\n",
 800        ".suggestion-warning { \n",
 801        "font-weight: bold;\n",
 802        "color: rgb(200, 130, 0);\n",
 803        "}\n",
 804        ".suggestion-error { \n",
 805        "font-weight: bold;\n",
 806        "color: red;\n",
 807        "}\n",
 808        ".suggestion-name {\n",
 809        "font-weight: bold;\n",
 810        "}\n",
 811        "</style><div class=\"suggestion-name\" style=\"clear:both;\">Use head</div><div class=\"suggestion-row\" style=\"float: left;\"><div class=\"suggestion-warning\">Found:</div><div class=\"highlight-code\" id=\"haskell\">particles !! 0</div></div><div class=\"suggestion-row\" style=\"float: left;\"><div class=\"suggestion-warning\">Why Not:</div><div class=\"highlight-code\" id=\"haskell\">head particles</div></div>"
 812       ],
 813       "text/plain": [
 814        "Line 1: Use head\n",
 815        "Found:\n",
 816        "particles !! 0\n",
 817        "Why not:\n",
 818        "head particles"
 819       ]
 820      },
 821      "metadata": {},
 822      "output_type": "display_data"
 823     },
 824     {
 825      "data": {
 826       "text/plain": [
 827        "Particle {position = [-833,-499,-1391], velocity = [84,17,61], acceleration = [-4,1,1]}"
 828       ]
 829      },
 830      "metadata": {},
 831      "output_type": "display_data"
 832     }
 833    ],
 834    "source": [
 835     "text <- TIO.readFile \"../../data/advent20.txt\"\n",
 836     "particles = successfulParse text\n",
 837     "particles!!0"
 838    ]
 839   },
 840   {
 841    "cell_type": "code",
 842    "execution_count": 96,
 843    "metadata": {},
 844    "outputs": [
 845     {
 846      "data": {
 847       "text/plain": [
 848        "[Particle {position = [-59,74,-188], velocity = [-29,97,-150], acceleration = [-1,0,0]},Particle {position = [98,72,-533], velocity = [37,12,-172], acceleration = [0,1,0]}]"
 849       ]
 850      },
 851      "metadata": {},
 852      "output_type": "display_data"
 853     }
 854    ],
 855    "source": [
 856     "simulateQ $ map (particles !!) $ lowestAcc particles"
 857    ]
 858   },
 859   {
 860    "cell_type": "code",
 861    "execution_count": 97,
 862    "metadata": {},
 863    "outputs": [
 864     {
 865      "data": {
 866       "text/plain": [
 867        "[Particle {position = [-59,74,-188], velocity = [-29,97,-150], acceleration = [-1,0,0]},Particle {position = [98,72,-533], velocity = [37,12,-172], acceleration = [0,1,0]}]"
 868       ]
 869      },
 870      "metadata": {},
 871      "output_type": "display_data"
 872     }
 873    ],
 874    "source": [
 875     "simulate $ map (particles !!) $ lowestAcc particles"
 876    ]
 877   },
 878   {
 879    "cell_type": "code",
 880    "execution_count": 105,
 881    "metadata": {},
 882    "outputs": [
 883     {
 884      "data": {
 885       "text/plain": [
 886        "457"
 887       ]
 888      },
 889      "metadata": {},
 890      "output_type": "display_data"
 891     }
 892    ],
 893    "source": [
 894     "main"
 895    ]
 896   },
 897   {
 898    "cell_type": "code",
 899    "execution_count": 116,
 900    "metadata": {},
 901    "outputs": [],
 902    "source": [
 903     "removeColliders particles = particles'\n",
 904     "    where positions = map position particles\n",
 905     "          duplicatePositions = S.fromList $ concat $ filter (\\g -> length g > 1) $ group $ sort positions\n",
 906     "          particles' = filter (\\p -> not (S.member (position p) duplicatePositions)) particles"
 907    ]
 908   },
 909   {
 910    "cell_type": "code",
 911    "execution_count": 117,
 912    "metadata": {},
 913    "outputs": [],
 914    "source": [
 915     "simulateC :: Integer -> [Particle] -> [Particle]\n",
 916     "simulateC 0 particles = particles\n",
 917     "simulateC t particles = simulateC (t - 1) (map step particles')\n",
 918     "    where particles' = removeColliders particles"
 919    ]
 920   },
 921   {
 922    "cell_type": "code",
 923    "execution_count": 118,
 924    "metadata": {},
 925    "outputs": [],
 926    "source": [
 927     "part2 n particles = length $ simulateC n particles"
 928    ]
 929   },
 930   {
 931    "cell_type": "code",
 932    "execution_count": 119,
 933    "metadata": {},
 934    "outputs": [
 935     {
 936      "data": {
 937       "text/plain": [
 938        "1000"
 939       ]
 940      },
 941      "metadata": {},
 942      "output_type": "display_data"
 943     }
 944    ],
 945    "source": [
 946     "length particles"
 947    ]
 948   },
 949   {
 950    "cell_type": "code",
 951    "execution_count": 138,
 952    "metadata": {},
 953    "outputs": [
 954     {
 955      "data": {
 956       "text/plain": [
 957        "448"
 958       ]
 959      },
 960      "metadata": {},
 961      "output_type": "display_data"
 962     }
 963    ],
 964    "source": [
 965     "part2 40 particles"
 966    ]
 967   },
 968   {
 969    "cell_type": "code",
 970    "execution_count": 137,
 971    "metadata": {},
 972    "outputs": [
 973     {
 974      "data": {
 975       "text/plain": [
 976        "[(10,1000),(11,979),(12,979),(13,973),(14,955),(15,932),(16,921),(17,906),(18,874),(19,858),(20,831),(21,821),(22,809),(23,795),(24,791),(25,771),(26,752),(27,723),(28,703),(29,669),(30,648),(31,634),(32,622),(33,617),(34,589),(35,570),(36,542),(37,522),(38,494),(39,481),(40,448),(41,448),(42,448),(43,448),(44,448),(45,448)]"
 977       ]
 978      },
 979      "metadata": {},
 980      "output_type": "display_data"
 981     }
 982    ],
 983    "source": [
 984     "[(n, part2 n particles) | n <- [10..45]]"
 985    ]
 986   },
 987   {
 988    "cell_type": "code",
 989    "execution_count": null,
 990    "metadata": {},
 991    "outputs": [],
 992    "source": []
 993   }
 994  ],
 995  "metadata": {
 996   "kernelspec": {
 997    "display_name": "Haskell",
 998    "language": "haskell",
 999    "name": "haskell"
1000   },
1001   "language_info": {
1002    "codemirror_mode": "ihaskell",
1003    "file_extension": ".hs",
1004    "name": "haskell",
1005    "version": "8.0.2"
1006   }
1007  },
1008  "nbformat": 4,
1009  "nbformat_minor": 2
1010 }