{
"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'><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>"
],
"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
}