X-Git-Url: https://git.njae.me.uk/?a=blobdiff_plain;f=src%2Fadvent07%2Fadvent07.ipynb;fp=src%2Fadvent07%2Fadvent07.ipynb;h=2e1248249625b2d41158b7411305c25fd06ff0f4;hb=6761ab55989d276c113c7604b52356789a79c5ca;hp=0000000000000000000000000000000000000000;hpb=c5de1ed5aa60fd9879727b3ab86130f58552da8e;p=advent-of-code-17.git

diff --git a/src/advent07/advent07.ipynb b/src/advent07/advent07.ipynb
new file mode 100644
index 0000000..2e12482
--- /dev/null
+++ b/src/advent07/advent07.ipynb
@@ -0,0 +1,1047 @@
+{
+ "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
+}