src/advent07/advent07-Copy1.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": 2,
  16    "metadata": {},
  17    "outputs": [],
  18    "source": [
  19     "import Text.Parsec \n",
  20     "import Text.ParserCombinators.Parsec.Number\n",
  21     "import Data.List (partition, intersect, sortBy, groupBy, sort, group, (\\\\))\n",
  22     "import qualified Data.Set as S\n",
  23     "import Data.Function (on)"
  24    ]
  25   },
  26   {
  27    "cell_type": "code",
  28    "execution_count": 3,
  29    "metadata": {},
  30    "outputs": [],
  31    "source": [
  32     "import Debug.Trace"
  33    ]
  34   },
  35   {
  36    "cell_type": "code",
  37    "execution_count": 4,
  38    "metadata": {},
  39    "outputs": [],
  40    "source": [
  41     "data Program = Program String Int [String]\n",
  42     "                deriving (Show, Eq)\n",
  43     "\n",
  44     "name (Program n _ _) = n \n",
  45     "weight (Program _ w _) = w\n",
  46     "supports (Program _ _ s) = s"
  47    ]
  48   },
  49   {
  50    "cell_type": "code",
  51    "execution_count": 52,
  52    "metadata": {},
  53    "outputs": [],
  54    "source": [
  55     "data Tree = Tree Program [Tree] Int deriving (Show, Eq)\n",
  56     "root (Tree p _ _) = p\n",
  57     "branches (Tree _ b _) = b\n",
  58     "tWeight (Tree _ _ w) = w"
  59    ]
  60   },
  61   {
  62    "cell_type": "code",
  63    "execution_count": 6,
  64    "metadata": {},
  65    "outputs": [],
  66    "source": [
  67     "onlySpaces = many (oneOf \" \\t\")\n",
  68     "parens = between (string \"(\") (string \")\")\n",
  69     "sym = many lower\n",
  70     "commaSep sym = sym `sepBy` (onlySpaces *> string \",\" *> onlySpaces)"
  71    ]
  72   },
  73   {
  74    "cell_type": "code",
  75    "execution_count": 19,
  76    "metadata": {},
  77    "outputs": [],
  78    "source": [
  79     "mFile = mLine `sepBy` newline \n",
  80     "mLine = Program <$> sym <*> (onlySpaces *> (parens int)) <*> supportsP\n",
  81     "supportsP = (onlySpaces *> (string \"->\") *> onlySpaces *> (commaSep sym)) <|> (pure [])"
  82    ]
  83   },
  84   {
  85    "cell_type": "code",
  86    "execution_count": 20,
  87    "metadata": {},
  88    "outputs": [],
  89    "source": [
  90     "parseFile :: String -> Either ParseError [Program]\n",
  91     "parseFile input = parse mFile \"(unknown)\" input\n",
  92     "\n",
  93     "parseLine :: String -> Either ParseError Program\n",
  94     "parseLine input = parse mLine \"(unknown)\" input\n",
  95     "\n",
  96     "successfulParse :: Either ParseError [a] -> [a]\n",
  97     "successfulParse (Left _) = []\n",
  98     "successfulParse (Right a) = a"
  99    ]
 100   },
 101   {
 102    "cell_type": "code",
 103    "execution_count": 21,
 104    "metadata": {},
 105    "outputs": [
 106     {
 107      "data": {
 108       "text/plain": [
 109        "Right (Program \"kuvqhnm\" 77 [])"
 110       ]
 111      },
 112      "metadata": {},
 113      "output_type": "display_data"
 114     }
 115    ],
 116    "source": [
 117     "parseLine \"kuvqhnm (77)\""
 118    ]
 119   },
 120   {
 121    "cell_type": "code",
 122    "execution_count": 22,
 123    "metadata": {},
 124    "outputs": [
 125     {
 126      "data": {
 127       "text/plain": [
 128        "Right (Program \"dihjv\" 2158 [\"gausx\",\"ncdmp\",\"hozgrub\"])"
 129       ]
 130      },
 131      "metadata": {},
 132      "output_type": "display_data"
 133     }
 134    ],
 135    "source": [
 136     "parseLine \"dihjv (2158) -> gausx, ncdmp, hozgrub\""
 137    ]
 138   },
 139   {
 140    "cell_type": "code",
 141    "execution_count": 38,
 142    "metadata": {},
 143    "outputs": [],
 144    "source": [
 145     "sampleT = \"pbga (66)\\nxhth (57)\\nebii (61)\\nhavc (66)\\nktlj (57)\\nfwft (72) -> ktlj, cntj, xhth\\nqoyq (66)\\npadx (45) -> pbga, havc, qoyq\\ntknk (41) -> ugml, padx, fwft\\njptl (61)\\nugml (68) -> gyxo, ebii, jptl\\ngyxo (61)\\ncntj (57)\""
 146    ]
 147   },
 148   {
 149    "cell_type": "code",
 150    "execution_count": 39,
 151    "metadata": {},
 152    "outputs": [],
 153    "source": [
 154     "-- sample = \"pbga (66)\\nxhth (57)\""
 155    ]
 156   },
 157   {
 158    "cell_type": "code",
 159    "execution_count": 40,
 160    "metadata": {},
 161    "outputs": [
 162     {
 163      "data": {
 164       "text/plain": [
 165        "\"pbga (66)\\nxhth (57)\\nebii (61)\\nhavc (66)\\nktlj (57)\\nfwft (72) -> ktlj, cntj, xhth\\nqoyq (66)\\npadx (45) -> pbga, havc, qoyq\\ntknk (41) -> ugml, padx, fwft\\njptl (61)\\nugml (68) -> gyxo, ebii, jptl\\ngyxo (61)\\ncntj (57)\""
 166       ]
 167      },
 168      "metadata": {},
 169      "output_type": "display_data"
 170     }
 171    ],
 172    "source": [
 173     "print sampleT"
 174    ]
 175   },
 176   {
 177    "cell_type": "code",
 178    "execution_count": 41,
 179    "metadata": {},
 180    "outputs": [
 181     {
 182      "data": {
 183       "text/plain": [
 184        "[Program \"pbga\" 66 [],Program \"xhth\" 57 [],Program \"ebii\" 61 [],Program \"havc\" 66 [],Program \"ktlj\" 57 [],Program \"fwft\" 72 [\"ktlj\",\"cntj\",\"xhth\"],Program \"qoyq\" 66 [],Program \"padx\" 45 [\"pbga\",\"havc\",\"qoyq\"],Program \"tknk\" 41 [\"ugml\",\"padx\",\"fwft\"],Program \"jptl\" 61 [],Program \"ugml\" 68 [\"gyxo\",\"ebii\",\"jptl\"],Program \"gyxo\" 61 [],Program \"cntj\" 57 []]"
 185       ]
 186      },
 187      "metadata": {},
 188      "output_type": "display_data"
 189     }
 190    ],
 191    "source": [
 192     "sample = successfulParse $ parseFile sampleT\n",
 193     "sample"
 194    ]
 195   },
 196   {
 197    "cell_type": "code",
 198    "execution_count": 27,
 199    "metadata": {},
 200    "outputs": [],
 201    "source": [
 202     "allPrograms :: [Program] -> S.Set String\n",
 203     "allPrograms = S.fromList . map name"
 204    ]
 205   },
 206   {
 207    "cell_type": "code",
 208    "execution_count": 42,
 209    "metadata": {},
 210    "outputs": [
 211     {
 212      "data": {
 213       "text/plain": [
 214        "fromList [\"cntj\",\"ebii\",\"fwft\",\"gyxo\",\"havc\",\"jptl\",\"ktlj\",\"padx\",\"pbga\",\"qoyq\",\"tknk\",\"ugml\",\"xhth\"]"
 215       ]
 216      },
 217      "metadata": {},
 218      "output_type": "display_data"
 219     }
 220    ],
 221    "source": [
 222     "pr = allPrograms sample\n",
 223     "pr"
 224    ]
 225   },
 226   {
 227    "cell_type": "code",
 228    "execution_count": 29,
 229    "metadata": {},
 230    "outputs": [],
 231    "source": [
 232     "supported :: [Program] -> S.Set String\n",
 233     "supported = S.unions . map (S.fromList . supports)"
 234    ]
 235   },
 236   {
 237    "cell_type": "code",
 238    "execution_count": 43,
 239    "metadata": {},
 240    "outputs": [
 241     {
 242      "data": {
 243       "text/plain": [
 244        "fromList [\"cntj\",\"ebii\",\"fwft\",\"gyxo\",\"havc\",\"jptl\",\"ktlj\",\"padx\",\"pbga\",\"qoyq\",\"ugml\",\"xhth\"]"
 245       ]
 246      },
 247      "metadata": {},
 248      "output_type": "display_data"
 249     }
 250    ],
 251    "source": [
 252     "su = supported sample\n",
 253     "su"
 254    ]
 255   },
 256   {
 257    "cell_type": "code",
 258    "execution_count": 44,
 259    "metadata": {},
 260    "outputs": [
 261     {
 262      "data": {
 263       "text/plain": [
 264        "\"tknk\""
 265       ]
 266      },
 267      "metadata": {},
 268      "output_type": "display_data"
 269     }
 270    ],
 271    "source": [
 272     "print $ head $ S.elems $ S.difference pr su"
 273    ]
 274   },
 275   {
 276    "cell_type": "code",
 277    "execution_count": 33,
 278    "metadata": {},
 279    "outputs": [],
 280    "source": [
 281     "part1 :: [Program] -> String\n",
 282     "part1 progs = head $ S.elems $ S.difference pr su\n",
 283     "    where su = supported progs\n",
 284     "          pr = allPrograms progs"
 285    ]
 286   },
 287   {
 288    "cell_type": "code",
 289    "execution_count": 34,
 290    "metadata": {},
 291    "outputs": [],
 292    "source": [
 293     "main :: IO ()\n",
 294     "main = do \n",
 295     "        text <- readFile \"../../data/advent07.txt\"\n",
 296     "        let progs = successfulParse $ parseFile text\n",
 297     "        print $ part1 progs"
 298    ]
 299   },
 300   {
 301    "cell_type": "code",
 302    "execution_count": 35,
 303    "metadata": {},
 304    "outputs": [
 305     {
 306      "data": {
 307       "text/plain": [
 308        "\"vtzay\""
 309       ]
 310      },
 311      "metadata": {},
 312      "output_type": "display_data"
 313     }
 314    ],
 315    "source": [
 316     "main"
 317    ]
 318   },
 319   {
 320    "cell_type": "code",
 321    "execution_count": 36,
 322    "metadata": {},
 323    "outputs": [],
 324    "source": [
 325     "enTree :: Program -> Tree\n",
 326     "enTree program = Tree program [] (weight program)"
 327    ]
 328   },
 329   {
 330    "cell_type": "code",
 331    "execution_count": 37,
 332    "metadata": {},
 333    "outputs": [],
 334    "source": [
 335     "leaves :: [Program] -> [Program]\n",
 336     "leaves = filter (null . supports)"
 337    ]
 338   },
 339   {
 340    "cell_type": "code",
 341    "execution_count": 45,
 342    "metadata": {},
 343    "outputs": [
 344     {
 345      "data": {
 346       "text/plain": [
 347        "[Tree (Program \"pbga\" 66 []) [] 66,Tree (Program \"xhth\" 57 []) [] 57,Tree (Program \"ebii\" 61 []) [] 61,Tree (Program \"havc\" 66 []) [] 66,Tree (Program \"ktlj\" 57 []) [] 57,Tree (Program \"qoyq\" 66 []) [] 66,Tree (Program \"jptl\" 61 []) [] 61,Tree (Program \"gyxo\" 61 []) [] 61,Tree (Program \"cntj\" 57 []) [] 57]"
 348       ]
 349      },
 350      "metadata": {},
 351      "output_type": "display_data"
 352     }
 353    ],
 354    "source": [
 355     "map enTree (leaves sample)"
 356    ]
 357   },
 358   {
 359    "cell_type": "code",
 360    "execution_count": 46,
 361    "metadata": {},
 362    "outputs": [],
 363    "source": [
 364     "forestNames :: [Tree] -> [String]\n",
 365     "forestNames = map (name . root)"
 366    ]
 367   },
 368   {
 369    "cell_type": "code",
 370    "execution_count": 47,
 371    "metadata": {},
 372    "outputs": [
 373     {
 374      "data": {
 375       "text/plain": [
 376        "[\"pbga\",\"xhth\",\"ebii\",\"havc\",\"ktlj\",\"qoyq\",\"jptl\",\"gyxo\",\"cntj\"]"
 377       ]
 378      },
 379      "metadata": {},
 380      "output_type": "display_data"
 381     }
 382    ],
 383    "source": [
 384     "forestNames $ map enTree $ leaves sample"
 385    ]
 386   },
 387   {
 388    "cell_type": "code",
 389    "execution_count": 48,
 390    "metadata": {},
 391    "outputs": [
 392     {
 393      "data": {
 394       "text/plain": [
 395        "Program \"ugml\" 68 [\"gyxo\",\"ebii\",\"jptl\"]"
 396       ]
 397      },
 398      "metadata": {},
 399      "output_type": "display_data"
 400     }
 401    ],
 402    "source": [
 403     "head $ filter (\\p -> name p == \"ugml\") sample"
 404    ]
 405   },
 406   {
 407    "cell_type": "code",
 408    "execution_count": 50,
 409    "metadata": {},
 410    "outputs": [],
 411    "source": [
 412     "sampleLeaves = leaves sample\n",
 413     "sampleBranch = sample \\\\ sampleLeaves"
 414    ]
 415   },
 416   {
 417    "cell_type": "code",
 418    "execution_count": 51,
 419    "metadata": {},
 420    "outputs": [
 421     {
 422      "data": {
 423       "text/plain": [
 424        "[Program \"fwft\" 72 [\"ktlj\",\"cntj\",\"xhth\"],Program \"padx\" 45 [\"pbga\",\"havc\",\"qoyq\"],Program \"tknk\" 41 [\"ugml\",\"padx\",\"fwft\"],Program \"ugml\" 68 [\"gyxo\",\"ebii\",\"jptl\"]]"
 425       ]
 426      },
 427      "metadata": {},
 428      "output_type": "display_data"
 429     }
 430    ],
 431    "source": [
 432     "sampleBranch"
 433    ]
 434   },
 435   {
 436    "cell_type": "code",
 437    "execution_count": 65,
 438    "metadata": {},
 439    "outputs": [],
 440    "source": [
 441     "forest0 = map enTree sampleLeaves"
 442    ]
 443   },
 444   {
 445    "cell_type": "code",
 446    "execution_count": 63,
 447    "metadata": {},
 448    "outputs": [
 449     {
 450      "data": {
 451       "text/plain": [
 452        "[Tree (Program \"pbga\" 66 []) [] 66,Tree (Program \"xhth\" 57 []) [] 57,Tree (Program \"ebii\" 61 []) [] 61,Tree (Program \"havc\" 66 []) [] 66,Tree (Program \"ktlj\" 57 []) [] 57,Tree (Program \"qoyq\" 66 []) [] 66,Tree (Program \"jptl\" 61 []) [] 61,Tree (Program \"gyxo\" 61 []) [] 61,Tree (Program \"cntj\" 57 []) [] 57]"
 453       ]
 454      },
 455      "metadata": {},
 456      "output_type": "display_data"
 457     }
 458    ],
 459    "source": [
 460     "forest0"
 461    ]
 462   },
 463   {
 464    "cell_type": "code",
 465    "execution_count": 66,
 466    "metadata": {},
 467    "outputs": [],
 468    "source": [
 469     "canBuild :: Program -> [Tree] -> Bool\n",
 470     "canBuild program trees = all (\\p -> p `elem` roots) $ supports program\n",
 471     "    where roots = map (name . root) trees"
 472    ]
 473   },
 474   {
 475    "cell_type": "code",
 476    "execution_count": 67,
 477    "metadata": {},
 478    "outputs": [
 479     {
 480      "data": {
 481       "text/html": [
 482        "<style>/* Styles used for the Hoogle display in the pager */\n",
 483        ".hoogle-doc {\n",
 484        "display: block;\n",
 485        "padding-bottom: 1.3em;\n",
 486        "padding-left: 0.4em;\n",
 487        "}\n",
 488        ".hoogle-code {\n",
 489        "display: block;\n",
 490        "font-family: monospace;\n",
 491        "white-space: pre;\n",
 492        "}\n",
 493        ".hoogle-text {\n",
 494        "display: block;\n",
 495        "}\n",
 496        ".hoogle-name {\n",
 497        "color: green;\n",
 498        "font-weight: bold;\n",
 499        "}\n",
 500        ".hoogle-head {\n",
 501        "font-weight: bold;\n",
 502        "}\n",
 503        ".hoogle-sub {\n",
 504        "display: block;\n",
 505        "margin-left: 0.4em;\n",
 506        "}\n",
 507        ".hoogle-package {\n",
 508        "font-weight: bold;\n",
 509        "font-style: italic;\n",
 510        "}\n",
 511        ".hoogle-module {\n",
 512        "font-weight: bold;\n",
 513        "}\n",
 514        ".hoogle-class {\n",
 515        "font-weight: bold;\n",
 516        "}\n",
 517        ".get-type {\n",
 518        "color: green;\n",
 519        "font-weight: bold;\n",
 520        "font-family: monospace;\n",
 521        "display: block;\n",
 522        "white-space: pre-wrap;\n",
 523        "}\n",
 524        ".show-type {\n",
 525        "color: green;\n",
 526        "font-weight: bold;\n",
 527        "font-family: monospace;\n",
 528        "margin-left: 1em;\n",
 529        "}\n",
 530        ".mono {\n",
 531        "font-family: monospace;\n",
 532        "display: block;\n",
 533        "}\n",
 534        ".err-msg {\n",
 535        "color: red;\n",
 536        "font-style: italic;\n",
 537        "font-family: monospace;\n",
 538        "white-space: pre;\n",
 539        "display: block;\n",
 540        "}\n",
 541        "#unshowable {\n",
 542        "color: red;\n",
 543        "font-weight: bold;\n",
 544        "}\n",
 545        ".err-msg.in.collapse {\n",
 546        "padding-top: 0.7em;\n",
 547        "}\n",
 548        ".highlight-code {\n",
 549        "white-space: pre;\n",
 550        "font-family: monospace;\n",
 551        "}\n",
 552        ".suggestion-warning { \n",
 553        "font-weight: bold;\n",
 554        "color: rgb(200, 130, 0);\n",
 555        "}\n",
 556        ".suggestion-error { \n",
 557        "font-weight: bold;\n",
 558        "color: red;\n",
 559        "}\n",
 560        ".suggestion-name {\n",
 561        "font-weight: bold;\n",
 562        "}\n",
 563        "</style><span class='err-msg'>&lt;interactive&gt;:1:30: error:<br/>    • Couldn't match type ‘IHaskell51.Tree’<br/>                     with ‘Tree’<br/>      NB: ‘Tree’ is defined at &lt;interactive&gt;:1:1-55<br/>          ‘IHaskell51.Tree’ is defined at &lt;interactive&gt;:1:1-55<br/>      Expected type: [Tree]<br/>        Actual type: [IHaskell51.Tree]<br/>    • In the second argument of ‘canBuild’, namely ‘forest0’<br/>      In the expression: canBuild (head sampleBranch) forest0<br/>      In an equation for ‘it’: it = canBuild (head sampleBranch) forest0</span>"
 564       ],
 565       "text/plain": [
 566        "<interactive>:1:30: error:\n",
 567        "    • Couldn't match type ‘Ghci51.Tree’\n",
 568        "                     with ‘Tree’\n",
 569        "      NB: ‘Tree’ is defined at <interactive>:1:1-55\n",
 570        "          ‘Ghci51.Tree’ is defined at <interactive>:1:1-55\n",
 571        "      Expected type: [Tree]\n",
 572        "        Actual type: [Ghci51.Tree]\n",
 573        "    • In the second argument of ‘canBuild’, namely ‘forest0’\n",
 574        "      In the expression: canBuild (head sampleBranch) forest0\n",
 575        "      In an equation for ‘it’: it = canBuild (head sampleBranch) forest0"
 576       ]
 577      },
 578      "metadata": {},
 579      "output_type": "display_data"
 580     }
 581    ],
 582    "source": [
 583     "canBuild (head sampleBranch) forest0"
 584    ]
 585   },
 586   {
 587    "cell_type": "code",
 588    "execution_count": null,
 589    "metadata": {},
 590    "outputs": [],
 591    "source": []
 592   }
 593  ],
 594  "metadata": {
 595   "kernelspec": {
 596    "display_name": "Haskell",
 597    "language": "haskell",
 598    "name": "haskell"
 599   },
 600   "language_info": {
 601    "codemirror_mode": "ihaskell",
 602    "file_extension": ".hs",
 603    "name": "haskell",
 604    "version": "8.0.2"
 605   }
 606  },
 607  "nbformat": 4,
 608  "nbformat_minor": 2
 609 }