{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "{-# LANGUAGE NegativeLiterals #-}\n",
    "{-# LANGUAGE FlexibleContexts #-}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "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": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "import Debug.Trace"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "data Program = Program String Int [String]\n",
    "                deriving (Show, Eq)\n",
    "\n",
    "name (Program n _ _) = n \n",
    "weight (Program _ w _) = w\n",
    "supports (Program _ _ s) = s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [],
   "source": [
    "data Tree = Tree Program [Tree] Int deriving (Show, Eq)\n",
    "root (Tree p _ _) = p\n",
    "branches (Tree _ b _) = b\n",
    "tWeight (Tree _ _ w) = w"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "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": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "mFile = mLine `sepBy` newline \n",
    "mLine = Program <$> sym <*> (onlySpaces *> (parens int)) <*> supportsP\n",
    "supportsP = (onlySpaces *> (string \"->\") *> onlySpaces *> (commaSep sym)) <|> (pure [])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "parseFile :: String -> Either ParseError [Program]\n",
    "parseFile input = parse mFile \"(unknown)\" input\n",
    "\n",
    "parseLine :: String -> Either ParseError Program\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": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Right (Program \"kuvqhnm\" 77 [])"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "parseLine \"kuvqhnm (77)\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Right (Program \"dihjv\" 2158 [\"gausx\",\"ncdmp\",\"hozgrub\"])"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "parseLine \"dihjv (2158) -> gausx, ncdmp, hozgrub\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "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)\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [],
   "source": [
    "-- sample = \"pbga (66)\\nxhth (57)\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "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 sampleT"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[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 []]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "sample = successfulParse $ parseFile sampleT\n",
    "sample"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "allPrograms :: [Program] -> S.Set String\n",
    "allPrograms = S.fromList . map name"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "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 = allPrograms sample\n",
    "pr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "supported :: [Program] -> S.Set String\n",
    "supported = S.unions . map (S.fromList . supports)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "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 sample\n",
    "su"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "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": 33,
   "metadata": {},
   "outputs": [],
   "source": [
    "part1 :: [Program] -> String\n",
    "part1 progs = head $ S.elems $ S.difference pr su\n",
    "    where su = supported progs\n",
    "          pr = allPrograms progs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "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": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\"vtzay\""
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "main"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "enTree :: Program -> Tree\n",
    "enTree program = Tree program [] (weight program)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "leaves :: [Program] -> [Program]\n",
    "leaves = filter (null . supports)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[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]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "map enTree (leaves sample)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [],
   "source": [
    "forestNames :: [Tree] -> [String]\n",
    "forestNames = map (name . root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[\"pbga\",\"xhth\",\"ebii\",\"havc\",\"ktlj\",\"qoyq\",\"jptl\",\"gyxo\",\"cntj\"]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "forestNames $ map enTree $ leaves sample"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Program \"ugml\" 68 [\"gyxo\",\"ebii\",\"jptl\"]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "head $ filter (\\p -> name p == \"ugml\") sample"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [],
   "source": [
    "sampleLeaves = leaves sample\n",
    "sampleBranch = sample \\\\ sampleLeaves"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Program \"fwft\" 72 [\"ktlj\",\"cntj\",\"xhth\"],Program \"padx\" 45 [\"pbga\",\"havc\",\"qoyq\"],Program \"tknk\" 41 [\"ugml\",\"padx\",\"fwft\"],Program \"ugml\" 68 [\"gyxo\",\"ebii\",\"jptl\"]]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "sampleBranch"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [],
   "source": [
    "forest0 = map enTree sampleLeaves"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[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]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "forest0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [],
   "source": [
    "canBuild :: Program -> [Tree] -> Bool\n",
    "canBuild program trees = all (\\p -> p `elem` roots) $ supports program\n",
    "    where roots = map (name . root) trees"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "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'>&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>"
      ],
      "text/plain": [
       "<interactive>:1:30: error:\n",
       "    • Couldn't match type ‘Ghci51.Tree’\n",
       "                     with ‘Tree’\n",
       "      NB: ‘Tree’ is defined at <interactive>:1:1-55\n",
       "          ‘Ghci51.Tree’ is defined at <interactive>:1:1-55\n",
       "      Expected type: [Tree]\n",
       "        Actual type: [Ghci51.Tree]\n",
       "    • In the second argument of ‘canBuild’, namely ‘forest0’\n",
       "      In the expression: canBuild (head sampleBranch) forest0\n",
       "      In an equation for ‘it’: it = canBuild (head sampleBranch) forest0"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "canBuild (head sampleBranch) forest0"
   ]
  },
  {
   "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
}