--- /dev/null
+{
+ "cells": [
+ {
+ "cell_type": "code",
+ "execution_count": 1,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "{-# LANGUAGE NegativeLiterals #-}\n",
+ "{-# LANGUAGE FlexibleContexts #-}"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 113,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "import Text.Parsec \n",
+ "import Text.ParserCombinators.Parsec.Number\n",
+ "import Data.List (partition, intersect, sortBy, groupBy, sort, group, (\\\\))\n",
+ "import qualified Data.Set as S\n",
+ "import Data.Function (on)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 151,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "import Debug.Trace"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 3,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "data Programx = Programx String Int [String]\n",
+ " deriving (Show, Eq)\n",
+ "\n",
+ "name (Programx n _ _) = n \n",
+ "weight (Programx _ w _) = w\n",
+ "supports (Programx _ _ s) = s"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 4,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "data Treex = Treex Programx [Treex] Int deriving (Show, Eq)\n",
+ "root (Treex p _ _) = p\n",
+ "trees (Treex _ t _) = t\n",
+ "tWeight (Treex _ _ w) = w"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 5,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "onlySpaces = many (oneOf \" \\t\")\n",
+ "parens = between (string \"(\") (string \")\")\n",
+ "sym = many lower\n",
+ "commaSep sym = sym `sepBy` (onlySpaces *> string \",\" *> onlySpaces)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 6,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "mFile = mLine `sepBy` newline \n",
+ "mLine = Programx <$> sym <*> (onlySpaces *> (parens int)) <*> supportsP\n",
+ "supportsP = (onlySpaces *> (string \"->\") *> onlySpaces *> (commaSep sym)) <|> (pure [])"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 7,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "parseFile :: String -> Either ParseError [Programx]\n",
+ "parseFile input = parse mFile \"(unknown)\" input\n",
+ "\n",
+ "parseLine :: String -> Either ParseError Programx\n",
+ "parseLine input = parse mLine \"(unknown)\" input\n",
+ "\n",
+ "successfulParse :: Either ParseError [a] -> [a]\n",
+ "successfulParse (Left _) = []\n",
+ "successfulParse (Right a) = a"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 8,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "Right (Programx \"kuvqhnm\" 77 [])"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "parseLine \"kuvqhnm (77)\""
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 9,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "Right (Programx \"dihjv\" 2158 [\"gausx\",\"ncdmp\",\"hozgrub\"])"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "parseLine \"dihjv (2158) -> gausx, ncdmp, hozgrub\""
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 10,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "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)\""
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 11,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "-- sample = \"pbga (66)\\nxhth (57)\""
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 12,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "\"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)\""
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "print sample"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 13,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "[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 []]"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "successfulParse $ parseFile sample"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 14,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "programs :: [Programx] -> S.Set String\n",
+ "programs = S.fromList . map name"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 15,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "fromList [\"cntj\",\"ebii\",\"fwft\",\"gyxo\",\"havc\",\"jptl\",\"ktlj\",\"padx\",\"pbga\",\"qoyq\",\"tknk\",\"ugml\",\"xhth\"]"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "pr = programs $ successfulParse $ parseFile sample\n",
+ "pr"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 16,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "supported :: [Programx] -> S.Set String\n",
+ "supported = S.unions . map (S.fromList . supports)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 17,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "fromList [\"cntj\",\"ebii\",\"fwft\",\"gyxo\",\"havc\",\"jptl\",\"ktlj\",\"padx\",\"pbga\",\"qoyq\",\"ugml\",\"xhth\"]"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "su = supported $ successfulParse $ parseFile sample\n",
+ "su"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 18,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "\"tknk\""
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "print $ head $ S.elems $ S.difference pr su"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 19,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "part1 :: [Programx] -> String\n",
+ "part1 progs = head $ S.elems $ S.difference pr su\n",
+ " where su = supported progs\n",
+ " pr = programs progs"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 20,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "main :: IO ()\n",
+ "main = do \n",
+ " text <- readFile \"../../data/advent07.txt\"\n",
+ " let progs = successfulParse $ parseFile text\n",
+ " print $ part1 progs"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 21,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "\"vtzay\""
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "main"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 28,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "makeSingletons :: [Programx] -> ([Treex], [Programx])\n",
+ "makeSingletons programs = (trees, others)\n",
+ " where (sPrograms, others) = partition isLeaf programs\n",
+ " isLeaf pr = null $ supports pr\n",
+ " trees = map makeSTree sPrograms\n",
+ " makeSTree pr = Treex pr [] (weight pr)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 29,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "([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\"]])"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "makeSingletons $ successfulParse $ parseFile sample"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 42,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "makeTree :: [Treex] -> Programx -> Treex\n",
+ "makeTree trees program = Treex program subtrees (w + (weight program))\n",
+ " where subtrees = filter (\\t -> (name $ root t) `elem` (supports program)) trees\n",
+ " w = sum $ map tWeight subtrees"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 43,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "addTreeLayer :: [Treex] -> [Programx] -> ([Treex], [Programx])\n",
+ "addTreeLayer trees programs = (trees', programs')\n",
+ " where (sPrograms, others) = partition isSupporter programs\n",
+ " isSupporter pr = not $ null $ (supports pr) `intersect` roots\n",
+ " roots = map (name . root) trees\n",
+ " trees' = map (makeTree trees) sPrograms\n",
+ " newRoots = map root trees'\n",
+ " programs' = programs \\\\ newRoots\n"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 44,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "([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\"]])"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "(leaves, others) = makeSingletons $ successfulParse $ parseFile sample\n",
+ "(leaves, others)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 45,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "([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\"]])"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "(trs, oths) = addTreeLayer leaves others\n",
+ "(trs, oths)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 46,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "3"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "length trs"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 47,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "1"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "length oths"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 52,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "([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],[])"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "(trs', oths') = addTreeLayer trs oths\n",
+ "(trs', oths')"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 49,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "[243,243,251]"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "map tWeight trs"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 173,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "balancedTree :: Treex -> Bool\n",
+ "balancedTree tr \n",
+ " | null $ trees tr = True\n",
+ " | otherwise = (1==) $ S.size $ S.fromList $ map tWeight $ trees tr"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 174,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "[True,True,True,True,True,True,True,True,True]"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "map balancedTree leaves"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 175,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "[True,True,True]"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "map balancedTree trs"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 176,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "[False]"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "map balancedTree trs'"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 177,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "treesByWeight :: Treex -> [Treex]\n",
+ "treesByWeight = sortBy (compare `on` tWeight) . trees"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 178,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "[243,243,251]"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "map tWeight $ treesByWeight $ head trs'"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 179,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "oddWeight :: Treex -> Int\n",
+ "oddWeight = tWeight . head . head .filter (\\g -> length g == 1) . groupBy ((==) `on` tWeight) . trees"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 180,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "oddWeight :: Treex -> Int\n",
+ "oddWeight = head . head .filter (\\g -> length g == 1) . group . sort . map tWeight . trees"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 181,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "251"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "oddWeight $ head trs'"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 182,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "-- oddMajorityWeight :: Treex -> (Int, Int)\n",
+ "oddMajorityWeight = extractWeights . oddMajority . groups\n",
+ " where groups = group . sort . map tWeight . trees\n",
+ " oddMajority = partition (\\g -> length g == 1)\n",
+ " extractWeights (o, m) = (head $ head o, head $ head m)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 183,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "(251,243)"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "oddMajorityWeight $ head trs'"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 184,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "68"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "weight $ root $ head $ filter (\\t -> tWeight t == 251) $ trees $ head trs' "
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 185,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "60"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "68 - 251 + 243"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 202,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "checkTrees :: ([Treex], [Programx]) -> Int\n",
+ "checkTrees (partTrees, programs) =\n",
+ " if all balancedTree partTrees\n",
+ " then trace (show $ length partTrees) checkTrees $ addTreeLayer partTrees programs\n",
+ " else \n",
+ " oddTreeWeight - oddWeight + majorityWeight\n",
+ " where \n",
+ " unbalancedTree = head $ filter (not . balancedTree) partTrees\n",
+ " (oddWeight, majorityWeight) = oddMajorityWeight unbalancedTree\n",
+ " unbalancedSubtrees = trees unbalancedTree\n",
+ " oddTreeWeight = weight $ root $ head $ filter (\\t -> tWeight t == oddWeight) $ trees unbalancedTree"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 188,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "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"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "ubt = head $ filter (not . balancedTree) trs'\n",
+ "ubt"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 189,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "[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]"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "trees ubt"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 238,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "([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\"]])"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "sglPrs = makeSingletons $ successfulParse $ parseFile sample\n",
+ "sglPrs"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 239,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "[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]"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "fst sglPrs"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 240,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "60"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "checkTrees sglPrs"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 242,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "True"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "all balancedTree leaves"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 243,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "[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]"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "leaves"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 244,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "True"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "balancedTree $ head leaves"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 245,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "Treex (Programx \"pbga\" 66 []) [] 66"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "head leaves"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 246,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "-- part2 :: [Programx] -> Int\n",
+ "part2 = checkTrees . makeSingletons \n",
+ "-- part2 prs = all balancedTree $ fst $ addTreeLayer ts os\n",
+ "-- where (ts, os) = makeSingletons prs"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 247,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "main :: IO ()\n",
+ "main = do \n",
+ " text <- readFile \"../../data/advent07.txt\"\n",
+ " let progs = successfulParse $ parseFile text\n",
+ "-- print $ part1 progs\n",
+ " print $ part2 progs"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 248,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/html": [
+ "<style>/* Styles used for the Hoogle display in the pager */\n",
+ ".hoogle-doc {\n",
+ "display: block;\n",
+ "padding-bottom: 1.3em;\n",
+ "padding-left: 0.4em;\n",
+ "}\n",
+ ".hoogle-code {\n",
+ "display: block;\n",
+ "font-family: monospace;\n",
+ "white-space: pre;\n",
+ "}\n",
+ ".hoogle-text {\n",
+ "display: block;\n",
+ "}\n",
+ ".hoogle-name {\n",
+ "color: green;\n",
+ "font-weight: bold;\n",
+ "}\n",
+ ".hoogle-head {\n",
+ "font-weight: bold;\n",
+ "}\n",
+ ".hoogle-sub {\n",
+ "display: block;\n",
+ "margin-left: 0.4em;\n",
+ "}\n",
+ ".hoogle-package {\n",
+ "font-weight: bold;\n",
+ "font-style: italic;\n",
+ "}\n",
+ ".hoogle-module {\n",
+ "font-weight: bold;\n",
+ "}\n",
+ ".hoogle-class {\n",
+ "font-weight: bold;\n",
+ "}\n",
+ ".get-type {\n",
+ "color: green;\n",
+ "font-weight: bold;\n",
+ "font-family: monospace;\n",
+ "display: block;\n",
+ "white-space: pre-wrap;\n",
+ "}\n",
+ ".show-type {\n",
+ "color: green;\n",
+ "font-weight: bold;\n",
+ "font-family: monospace;\n",
+ "margin-left: 1em;\n",
+ "}\n",
+ ".mono {\n",
+ "font-family: monospace;\n",
+ "display: block;\n",
+ "}\n",
+ ".err-msg {\n",
+ "color: red;\n",
+ "font-style: italic;\n",
+ "font-family: monospace;\n",
+ "white-space: pre;\n",
+ "display: block;\n",
+ "}\n",
+ "#unshowable {\n",
+ "color: red;\n",
+ "font-weight: bold;\n",
+ "}\n",
+ ".err-msg.in.collapse {\n",
+ "padding-top: 0.7em;\n",
+ "}\n",
+ ".highlight-code {\n",
+ "white-space: pre;\n",
+ "font-family: monospace;\n",
+ "}\n",
+ ".suggestion-warning { \n",
+ "font-weight: bold;\n",
+ "color: rgb(200, 130, 0);\n",
+ "}\n",
+ ".suggestion-error { \n",
+ "font-weight: bold;\n",
+ "color: red;\n",
+ "}\n",
+ ".suggestion-name {\n",
+ "font-weight: bold;\n",
+ "}\n",
+ "</style><span class='err-msg'>Prelude.head: empty list</span>"
+ ],
+ "text/plain": [
+ "Prelude.head: empty list"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "main"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {},
+ "outputs": [],
+ "source": []
+ }
+ ],
+ "metadata": {
+ "kernelspec": {
+ "display_name": "Haskell",
+ "language": "haskell",
+ "name": "haskell"
+ },
+ "language_info": {
+ "codemirror_mode": "ihaskell",
+ "file_extension": ".hs",
+ "name": "haskell",
+ "version": "8.0.2"
+ }
+ },
+ "nbformat": 4,
+ "nbformat_minor": 2
+}