9 "{-# LANGUAGE NegativeLiterals #-}\n",
10 "{-# LANGUAGE FlexibleContexts #-}"
15 "execution_count": 113,
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)"
28 "execution_count": 151,
41 "data Programx = Programx String Int [String]\n",
42 " deriving (Show, Eq)\n",
44 "name (Programx n _ _) = n \n",
45 "weight (Programx _ w _) = w\n",
46 "supports (Programx _ _ s) = s"
55 "data Treex = Treex Programx [Treex] Int deriving (Show, Eq)\n",
56 "root (Treex p _ _) = p\n",
57 "trees (Treex _ t _) = t\n",
58 "tWeight (Treex _ _ w) = w"
67 "onlySpaces = many (oneOf \" \\t\")\n",
68 "parens = between (string \"(\") (string \")\")\n",
70 "commaSep sym = sym `sepBy` (onlySpaces *> string \",\" *> onlySpaces)"
79 "mFile = mLine `sepBy` newline \n",
80 "mLine = Programx <$> sym <*> (onlySpaces *> (parens int)) <*> supportsP\n",
81 "supportsP = (onlySpaces *> (string \"->\") *> onlySpaces *> (commaSep sym)) <|> (pure [])"
90 "parseFile :: String -> Either ParseError [Programx]\n",
91 "parseFile input = parse mFile \"(unknown)\" input\n",
93 "parseLine :: String -> Either ParseError Programx\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": 8,
109 "Right (Programx \"kuvqhnm\" 77 [])"
113 "output_type": "display_data"
117 "parseLine \"kuvqhnm (77)\""
122 "execution_count": 9,
128 "Right (Programx \"dihjv\" 2158 [\"gausx\",\"ncdmp\",\"hozgrub\"])"
132 "output_type": "display_data"
136 "parseLine \"dihjv (2158) -> gausx, ncdmp, hozgrub\""
141 "execution_count": 10,
145 "sample = \"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": 11,
154 "-- sample = \"pbga (66)\\nxhth (57)\""
159 "execution_count": 12,
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": 13,
184 "[Programx \"pbga\" 66 [],Programx \"xhth\" 57 [],Programx \"ebii\" 61 [],Programx \"havc\" 66 [],Programx \"ktlj\" 57 [],Programx \"fwft\" 72 [\"ktlj\",\"cntj\",\"xhth\"],Programx \"qoyq\" 66 [],Programx \"padx\" 45 [\"pbga\",\"havc\",\"qoyq\"],Programx \"tknk\" 41 [\"ugml\",\"padx\",\"fwft\"],Programx \"jptl\" 61 [],Programx \"ugml\" 68 [\"gyxo\",\"ebii\",\"jptl\"],Programx \"gyxo\" 61 [],Programx \"cntj\" 57 []]"
188 "output_type": "display_data"
192 "successfulParse $ parseFile sample"
197 "execution_count": 14,
201 "programs :: [Programx] -> S.Set String\n",
202 "programs = S.fromList . map name"
207 "execution_count": 15,
213 "fromList [\"cntj\",\"ebii\",\"fwft\",\"gyxo\",\"havc\",\"jptl\",\"ktlj\",\"padx\",\"pbga\",\"qoyq\",\"tknk\",\"ugml\",\"xhth\"]"
217 "output_type": "display_data"
221 "pr = programs $ successfulParse $ parseFile sample\n",
227 "execution_count": 16,
231 "supported :: [Programx] -> S.Set String\n",
232 "supported = S.unions . map (S.fromList . supports)"
237 "execution_count": 17,
243 "fromList [\"cntj\",\"ebii\",\"fwft\",\"gyxo\",\"havc\",\"jptl\",\"ktlj\",\"padx\",\"pbga\",\"qoyq\",\"ugml\",\"xhth\"]"
247 "output_type": "display_data"
251 "su = supported $ successfulParse $ parseFile sample\n",
257 "execution_count": 18,
267 "output_type": "display_data"
271 "print $ head $ S.elems $ S.difference pr su"
276 "execution_count": 19,
280 "part1 :: [Programx] -> String\n",
281 "part1 progs = head $ S.elems $ S.difference pr su\n",
282 " where su = supported progs\n",
283 " pr = programs progs"
288 "execution_count": 20,
294 " text <- readFile \"../../data/advent07.txt\"\n",
295 " let progs = successfulParse $ parseFile text\n",
296 " print $ part1 progs"
301 "execution_count": 21,
311 "output_type": "display_data"
320 "execution_count": 28,
324 "makeSingletons :: [Programx] -> ([Treex], [Programx])\n",
325 "makeSingletons programs = (trees, others)\n",
326 " where (sPrograms, others) = partition isLeaf programs\n",
327 " isLeaf pr = null $ supports pr\n",
328 " trees = map makeSTree sPrograms\n",
329 " makeSTree pr = Treex pr [] (weight pr)"
334 "execution_count": 29,
340 "([Treex (Programx \"pbga\" 66 []) [] 66,Treex (Programx \"xhth\" 57 []) [] 57,Treex (Programx \"ebii\" 61 []) [] 61,Treex (Programx \"havc\" 66 []) [] 66,Treex (Programx \"ktlj\" 57 []) [] 57,Treex (Programx \"qoyq\" 66 []) [] 66,Treex (Programx \"jptl\" 61 []) [] 61,Treex (Programx \"gyxo\" 61 []) [] 61,Treex (Programx \"cntj\" 57 []) [] 57],[Programx \"fwft\" 72 [\"ktlj\",\"cntj\",\"xhth\"],Programx \"padx\" 45 [\"pbga\",\"havc\",\"qoyq\"],Programx \"tknk\" 41 [\"ugml\",\"padx\",\"fwft\"],Programx \"ugml\" 68 [\"gyxo\",\"ebii\",\"jptl\"]])"
344 "output_type": "display_data"
348 "makeSingletons $ successfulParse $ parseFile sample"
353 "execution_count": 42,
357 "makeTree :: [Treex] -> Programx -> Treex\n",
358 "makeTree trees program = Treex program subtrees (w + (weight program))\n",
359 " where subtrees = filter (\\t -> (name $ root t) `elem` (supports program)) trees\n",
360 " w = sum $ map tWeight subtrees"
365 "execution_count": 43,
369 "addTreeLayer :: [Treex] -> [Programx] -> ([Treex], [Programx])\n",
370 "addTreeLayer trees programs = (trees', programs')\n",
371 " where (sPrograms, others) = partition isSupporter programs\n",
372 " isSupporter pr = not $ null $ (supports pr) `intersect` roots\n",
373 " roots = map (name . root) trees\n",
374 " trees' = map (makeTree trees) sPrograms\n",
375 " newRoots = map root trees'\n",
376 " programs' = programs \\\\ newRoots\n"
381 "execution_count": 44,
387 "([Treex (Programx \"pbga\" 66 []) [] 66,Treex (Programx \"xhth\" 57 []) [] 57,Treex (Programx \"ebii\" 61 []) [] 61,Treex (Programx \"havc\" 66 []) [] 66,Treex (Programx \"ktlj\" 57 []) [] 57,Treex (Programx \"qoyq\" 66 []) [] 66,Treex (Programx \"jptl\" 61 []) [] 61,Treex (Programx \"gyxo\" 61 []) [] 61,Treex (Programx \"cntj\" 57 []) [] 57],[Programx \"fwft\" 72 [\"ktlj\",\"cntj\",\"xhth\"],Programx \"padx\" 45 [\"pbga\",\"havc\",\"qoyq\"],Programx \"tknk\" 41 [\"ugml\",\"padx\",\"fwft\"],Programx \"ugml\" 68 [\"gyxo\",\"ebii\",\"jptl\"]])"
391 "output_type": "display_data"
395 "(leaves, others) = makeSingletons $ successfulParse $ parseFile sample\n",
401 "execution_count": 45,
407 "([Treex (Programx \"fwft\" 72 [\"ktlj\",\"cntj\",\"xhth\"]) [Treex (Programx \"xhth\" 57 []) [] 57,Treex (Programx \"ktlj\" 57 []) [] 57,Treex (Programx \"cntj\" 57 []) [] 57] 243,Treex (Programx \"padx\" 45 [\"pbga\",\"havc\",\"qoyq\"]) [Treex (Programx \"pbga\" 66 []) [] 66,Treex (Programx \"havc\" 66 []) [] 66,Treex (Programx \"qoyq\" 66 []) [] 66] 243,Treex (Programx \"ugml\" 68 [\"gyxo\",\"ebii\",\"jptl\"]) [Treex (Programx \"ebii\" 61 []) [] 61,Treex (Programx \"jptl\" 61 []) [] 61,Treex (Programx \"gyxo\" 61 []) [] 61] 251],[Programx \"tknk\" 41 [\"ugml\",\"padx\",\"fwft\"]])"
411 "output_type": "display_data"
415 "(trs, oths) = addTreeLayer leaves others\n",
421 "execution_count": 46,
431 "output_type": "display_data"
440 "execution_count": 47,
450 "output_type": "display_data"
459 "execution_count": 52,
465 "([Treex (Programx \"tknk\" 41 [\"ugml\",\"padx\",\"fwft\"]) [Treex (Programx \"fwft\" 72 [\"ktlj\",\"cntj\",\"xhth\"]) [Treex (Programx \"xhth\" 57 []) [] 57,Treex (Programx \"ktlj\" 57 []) [] 57,Treex (Programx \"cntj\" 57 []) [] 57] 243,Treex (Programx \"padx\" 45 [\"pbga\",\"havc\",\"qoyq\"]) [Treex (Programx \"pbga\" 66 []) [] 66,Treex (Programx \"havc\" 66 []) [] 66,Treex (Programx \"qoyq\" 66 []) [] 66] 243,Treex (Programx \"ugml\" 68 [\"gyxo\",\"ebii\",\"jptl\"]) [Treex (Programx \"ebii\" 61 []) [] 61,Treex (Programx \"jptl\" 61 []) [] 61,Treex (Programx \"gyxo\" 61 []) [] 61] 251] 778],[])"
469 "output_type": "display_data"
473 "(trs', oths') = addTreeLayer trs oths\n",
479 "execution_count": 49,
489 "output_type": "display_data"
498 "execution_count": 173,
502 "balancedTree :: Treex -> Bool\n",
503 "balancedTree tr \n",
504 " | null $ trees tr = True\n",
505 " | otherwise = (1==) $ S.size $ S.fromList $ map tWeight $ trees tr"
510 "execution_count": 174,
516 "[True,True,True,True,True,True,True,True,True]"
520 "output_type": "display_data"
524 "map balancedTree leaves"
529 "execution_count": 175,
539 "output_type": "display_data"
543 "map balancedTree trs"
548 "execution_count": 176,
558 "output_type": "display_data"
562 "map balancedTree trs'"
567 "execution_count": 177,
571 "treesByWeight :: Treex -> [Treex]\n",
572 "treesByWeight = sortBy (compare `on` tWeight) . trees"
577 "execution_count": 178,
587 "output_type": "display_data"
591 "map tWeight $ treesByWeight $ head trs'"
596 "execution_count": 179,
600 "oddWeight :: Treex -> Int\n",
601 "oddWeight = tWeight . head . head .filter (\\g -> length g == 1) . groupBy ((==) `on` tWeight) . trees"
606 "execution_count": 180,
610 "oddWeight :: Treex -> Int\n",
611 "oddWeight = head . head .filter (\\g -> length g == 1) . group . sort . map tWeight . trees"
616 "execution_count": 181,
626 "output_type": "display_data"
630 "oddWeight $ head trs'"
635 "execution_count": 182,
639 "-- oddMajorityWeight :: Treex -> (Int, Int)\n",
640 "oddMajorityWeight = extractWeights . oddMajority . groups\n",
641 " where groups = group . sort . map tWeight . trees\n",
642 " oddMajority = partition (\\g -> length g == 1)\n",
643 " extractWeights (o, m) = (head $ head o, head $ head m)"
648 "execution_count": 183,
658 "output_type": "display_data"
662 "oddMajorityWeight $ head trs'"
667 "execution_count": 184,
677 "output_type": "display_data"
681 "weight $ root $ head $ filter (\\t -> tWeight t == 251) $ trees $ head trs' "
686 "execution_count": 185,
696 "output_type": "display_data"
705 "execution_count": 202,
709 "checkTrees :: ([Treex], [Programx]) -> Int\n",
710 "checkTrees (partTrees, programs) =\n",
711 " if all balancedTree partTrees\n",
712 " then trace (show $ length partTrees) checkTrees $ addTreeLayer partTrees programs\n",
714 " oddTreeWeight - oddWeight + majorityWeight\n",
716 " unbalancedTree = head $ filter (not . balancedTree) partTrees\n",
717 " (oddWeight, majorityWeight) = oddMajorityWeight unbalancedTree\n",
718 " unbalancedSubtrees = trees unbalancedTree\n",
719 " oddTreeWeight = weight $ root $ head $ filter (\\t -> tWeight t == oddWeight) $ trees unbalancedTree"
724 "execution_count": 188,
730 "Treex (Programx \"tknk\" 41 [\"ugml\",\"padx\",\"fwft\"]) [Treex (Programx \"fwft\" 72 [\"ktlj\",\"cntj\",\"xhth\"]) [Treex (Programx \"xhth\" 57 []) [] 57,Treex (Programx \"ktlj\" 57 []) [] 57,Treex (Programx \"cntj\" 57 []) [] 57] 243,Treex (Programx \"padx\" 45 [\"pbga\",\"havc\",\"qoyq\"]) [Treex (Programx \"pbga\" 66 []) [] 66,Treex (Programx \"havc\" 66 []) [] 66,Treex (Programx \"qoyq\" 66 []) [] 66] 243,Treex (Programx \"ugml\" 68 [\"gyxo\",\"ebii\",\"jptl\"]) [Treex (Programx \"ebii\" 61 []) [] 61,Treex (Programx \"jptl\" 61 []) [] 61,Treex (Programx \"gyxo\" 61 []) [] 61] 251] 778"
734 "output_type": "display_data"
738 "ubt = head $ filter (not . balancedTree) trs'\n",
744 "execution_count": 189,
750 "[Treex (Programx \"fwft\" 72 [\"ktlj\",\"cntj\",\"xhth\"]) [Treex (Programx \"xhth\" 57 []) [] 57,Treex (Programx \"ktlj\" 57 []) [] 57,Treex (Programx \"cntj\" 57 []) [] 57] 243,Treex (Programx \"padx\" 45 [\"pbga\",\"havc\",\"qoyq\"]) [Treex (Programx \"pbga\" 66 []) [] 66,Treex (Programx \"havc\" 66 []) [] 66,Treex (Programx \"qoyq\" 66 []) [] 66] 243,Treex (Programx \"ugml\" 68 [\"gyxo\",\"ebii\",\"jptl\"]) [Treex (Programx \"ebii\" 61 []) [] 61,Treex (Programx \"jptl\" 61 []) [] 61,Treex (Programx \"gyxo\" 61 []) [] 61] 251]"
754 "output_type": "display_data"
763 "execution_count": 238,
769 "([Treex (Programx \"pbga\" 66 []) [] 66,Treex (Programx \"xhth\" 57 []) [] 57,Treex (Programx \"ebii\" 61 []) [] 61,Treex (Programx \"havc\" 66 []) [] 66,Treex (Programx \"ktlj\" 57 []) [] 57,Treex (Programx \"qoyq\" 66 []) [] 66,Treex (Programx \"jptl\" 61 []) [] 61,Treex (Programx \"gyxo\" 61 []) [] 61,Treex (Programx \"cntj\" 57 []) [] 57],[Programx \"fwft\" 72 [\"ktlj\",\"cntj\",\"xhth\"],Programx \"padx\" 45 [\"pbga\",\"havc\",\"qoyq\"],Programx \"tknk\" 41 [\"ugml\",\"padx\",\"fwft\"],Programx \"ugml\" 68 [\"gyxo\",\"ebii\",\"jptl\"]])"
773 "output_type": "display_data"
777 "sglPrs = makeSingletons $ successfulParse $ parseFile sample\n",
783 "execution_count": 239,
789 "[Treex (Programx \"pbga\" 66 []) [] 66,Treex (Programx \"xhth\" 57 []) [] 57,Treex (Programx \"ebii\" 61 []) [] 61,Treex (Programx \"havc\" 66 []) [] 66,Treex (Programx \"ktlj\" 57 []) [] 57,Treex (Programx \"qoyq\" 66 []) [] 66,Treex (Programx \"jptl\" 61 []) [] 61,Treex (Programx \"gyxo\" 61 []) [] 61,Treex (Programx \"cntj\" 57 []) [] 57]"
793 "output_type": "display_data"
802 "execution_count": 240,
812 "output_type": "display_data"
821 "execution_count": 242,
831 "output_type": "display_data"
835 "all balancedTree leaves"
840 "execution_count": 243,
846 "[Treex (Programx \"pbga\" 66 []) [] 66,Treex (Programx \"xhth\" 57 []) [] 57,Treex (Programx \"ebii\" 61 []) [] 61,Treex (Programx \"havc\" 66 []) [] 66,Treex (Programx \"ktlj\" 57 []) [] 57,Treex (Programx \"qoyq\" 66 []) [] 66,Treex (Programx \"jptl\" 61 []) [] 61,Treex (Programx \"gyxo\" 61 []) [] 61,Treex (Programx \"cntj\" 57 []) [] 57]"
850 "output_type": "display_data"
859 "execution_count": 244,
869 "output_type": "display_data"
873 "balancedTree $ head leaves"
878 "execution_count": 245,
884 "Treex (Programx \"pbga\" 66 []) [] 66"
888 "output_type": "display_data"
897 "execution_count": 246,
901 "-- part2 :: [Programx] -> Int\n",
902 "part2 = checkTrees . makeSingletons \n",
903 "-- part2 prs = all balancedTree $ fst $ addTreeLayer ts os\n",
904 "-- where (ts, os) = makeSingletons prs"
909 "execution_count": 247,
915 " text <- readFile \"../../data/advent07.txt\"\n",
916 " let progs = successfulParse $ parseFile text\n",
917 "-- print $ part1 progs\n",
918 " print $ part2 progs"
923 "execution_count": 248,
929 "<style>/* Styles used for the Hoogle display in the pager */\n",
932 "padding-bottom: 1.3em;\n",
933 "padding-left: 0.4em;\n",
937 "font-family: monospace;\n",
938 "white-space: pre;\n",
945 "font-weight: bold;\n",
948 "font-weight: bold;\n",
952 "margin-left: 0.4em;\n",
954 ".hoogle-package {\n",
955 "font-weight: bold;\n",
956 "font-style: italic;\n",
958 ".hoogle-module {\n",
959 "font-weight: bold;\n",
962 "font-weight: bold;\n",
966 "font-weight: bold;\n",
967 "font-family: monospace;\n",
969 "white-space: pre-wrap;\n",
973 "font-weight: bold;\n",
974 "font-family: monospace;\n",
975 "margin-left: 1em;\n",
978 "font-family: monospace;\n",
983 "font-style: italic;\n",
984 "font-family: monospace;\n",
985 "white-space: pre;\n",
990 "font-weight: bold;\n",
992 ".err-msg.in.collapse {\n",
993 "padding-top: 0.7em;\n",
995 ".highlight-code {\n",
996 "white-space: pre;\n",
997 "font-family: monospace;\n",
999 ".suggestion-warning { \n",
1000 "font-weight: bold;\n",
1001 "color: rgb(200, 130, 0);\n",
1003 ".suggestion-error { \n",
1004 "font-weight: bold;\n",
1007 ".suggestion-name {\n",
1008 "font-weight: bold;\n",
1010 "</style><span class='err-msg'>Prelude.head: empty list</span>"
1013 "Prelude.head: empty list"
1017 "output_type": "display_data"
1025 "cell_type": "code",
1026 "execution_count": null,
1034 "display_name": "Haskell",
1035 "language": "haskell",
1039 "codemirror_mode": "ihaskell",
1040 "file_extension": ".hs",