9 "{-# LANGUAGE NegativeLiterals #-}\n",
10 "{-# LANGUAGE FlexibleContexts #-}"
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)"
41 "data Program = Program String Int [String]\n",
42 " deriving (Show, Eq)\n",
44 "name (Program n _ _) = n \n",
45 "weight (Program _ w _) = w\n",
46 "supports (Program _ _ s) = s"
51 "execution_count": 52,
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"
67 "onlySpaces = many (oneOf \" \\t\")\n",
68 "parens = between (string \"(\") (string \")\")\n",
70 "commaSep sym = sym `sepBy` (onlySpaces *> string \",\" *> onlySpaces)"
75 "execution_count": 19,
79 "mFile = mLine `sepBy` newline \n",
80 "mLine = Program <$> sym <*> (onlySpaces *> (parens int)) <*> supportsP\n",
81 "supportsP = (onlySpaces *> (string \"->\") *> onlySpaces *> (commaSep sym)) <|> (pure [])"
86 "execution_count": 20,
90 "parseFile :: String -> Either ParseError [Program]\n",
91 "parseFile input = parse mFile \"(unknown)\" input\n",
93 "parseLine :: String -> Either ParseError Program\n",
94 "parseLine input = parse mLine \"(unknown)\" input\n",
96 "successfulParse :: Either ParseError [a] -> [a]\n",
97 "successfulParse (Left _) = []\n",
98 "successfulParse (Right a) = a"
103 "execution_count": 21,
109 "Right (Program \"kuvqhnm\" 77 [])"
113 "output_type": "display_data"
117 "parseLine \"kuvqhnm (77)\""
122 "execution_count": 22,
128 "Right (Program \"dihjv\" 2158 [\"gausx\",\"ncdmp\",\"hozgrub\"])"
132 "output_type": "display_data"
136 "parseLine \"dihjv (2158) -> gausx, ncdmp, hozgrub\""
141 "execution_count": 38,
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)\""
150 "execution_count": 39,
154 "-- sample = \"pbga (66)\\nxhth (57)\""
159 "execution_count": 40,
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)\""
169 "output_type": "display_data"
178 "execution_count": 41,
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 []]"
188 "output_type": "display_data"
192 "sample = successfulParse $ parseFile sampleT\n",
198 "execution_count": 27,
202 "allPrograms :: [Program] -> S.Set String\n",
203 "allPrograms = S.fromList . map name"
208 "execution_count": 42,
214 "fromList [\"cntj\",\"ebii\",\"fwft\",\"gyxo\",\"havc\",\"jptl\",\"ktlj\",\"padx\",\"pbga\",\"qoyq\",\"tknk\",\"ugml\",\"xhth\"]"
218 "output_type": "display_data"
222 "pr = allPrograms sample\n",
228 "execution_count": 29,
232 "supported :: [Program] -> S.Set String\n",
233 "supported = S.unions . map (S.fromList . supports)"
238 "execution_count": 43,
244 "fromList [\"cntj\",\"ebii\",\"fwft\",\"gyxo\",\"havc\",\"jptl\",\"ktlj\",\"padx\",\"pbga\",\"qoyq\",\"ugml\",\"xhth\"]"
248 "output_type": "display_data"
252 "su = supported sample\n",
258 "execution_count": 44,
268 "output_type": "display_data"
272 "print $ head $ S.elems $ S.difference pr su"
277 "execution_count": 33,
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"
289 "execution_count": 34,
295 " text <- readFile \"../../data/advent07.txt\"\n",
296 " let progs = successfulParse $ parseFile text\n",
297 " print $ part1 progs"
302 "execution_count": 35,
312 "output_type": "display_data"
321 "execution_count": 36,
325 "enTree :: Program -> Tree\n",
326 "enTree program = Tree program [] (weight program)"
331 "execution_count": 37,
335 "leaves :: [Program] -> [Program]\n",
336 "leaves = filter (null . supports)"
341 "execution_count": 45,
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]"
351 "output_type": "display_data"
355 "map enTree (leaves sample)"
360 "execution_count": 46,
364 "forestNames :: [Tree] -> [String]\n",
365 "forestNames = map (name . root)"
370 "execution_count": 47,
376 "[\"pbga\",\"xhth\",\"ebii\",\"havc\",\"ktlj\",\"qoyq\",\"jptl\",\"gyxo\",\"cntj\"]"
380 "output_type": "display_data"
384 "forestNames $ map enTree $ leaves sample"
389 "execution_count": 48,
395 "Program \"ugml\" 68 [\"gyxo\",\"ebii\",\"jptl\"]"
399 "output_type": "display_data"
403 "head $ filter (\\p -> name p == \"ugml\") sample"
408 "execution_count": 50,
412 "sampleLeaves = leaves sample\n",
413 "sampleBranch = sample \\\\ sampleLeaves"
418 "execution_count": 51,
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\"]]"
428 "output_type": "display_data"
437 "execution_count": 65,
441 "forest0 = map enTree sampleLeaves"
446 "execution_count": 63,
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]"
456 "output_type": "display_data"
465 "execution_count": 66,
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"
476 "execution_count": 67,
482 "<style>/* Styles used for the Hoogle display in the pager */\n",
485 "padding-bottom: 1.3em;\n",
486 "padding-left: 0.4em;\n",
490 "font-family: monospace;\n",
491 "white-space: pre;\n",
498 "font-weight: bold;\n",
501 "font-weight: bold;\n",
505 "margin-left: 0.4em;\n",
507 ".hoogle-package {\n",
508 "font-weight: bold;\n",
509 "font-style: italic;\n",
511 ".hoogle-module {\n",
512 "font-weight: bold;\n",
515 "font-weight: bold;\n",
519 "font-weight: bold;\n",
520 "font-family: monospace;\n",
522 "white-space: pre-wrap;\n",
526 "font-weight: bold;\n",
527 "font-family: monospace;\n",
528 "margin-left: 1em;\n",
531 "font-family: monospace;\n",
536 "font-style: italic;\n",
537 "font-family: monospace;\n",
538 "white-space: pre;\n",
543 "font-weight: bold;\n",
545 ".err-msg.in.collapse {\n",
546 "padding-top: 0.7em;\n",
548 ".highlight-code {\n",
549 "white-space: pre;\n",
550 "font-family: monospace;\n",
552 ".suggestion-warning { \n",
553 "font-weight: bold;\n",
554 "color: rgb(200, 130, 0);\n",
556 ".suggestion-error { \n",
557 "font-weight: bold;\n",
560 ".suggestion-name {\n",
561 "font-weight: bold;\n",
563 "</style><span class='err-msg'><interactive>:1:30: error:<br/> • Couldn't match type ‘IHaskell51.Tree’<br/> with ‘Tree’<br/> NB: ‘Tree’ is defined at <interactive>:1:1-55<br/> ‘IHaskell51.Tree’ is defined at <interactive>: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>"
566 "<interactive>:1:30: error:\n",
567 " • Couldn't match type ‘Ghci51.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"
579 "output_type": "display_data"
583 "canBuild (head sampleBranch) forest0"
588 "execution_count": null,
596 "display_name": "Haskell",
597 "language": "haskell",
601 "codemirror_mode": "ihaskell",
602 "file_extension": ".hs",