{
"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": [
"<interactive>:1:30: error:
• Couldn't match type ‘IHaskell51.Tree’
with ‘Tree’
NB: ‘Tree’ is defined at <interactive>:1:1-55
‘IHaskell51.Tree’ is defined at <interactive>:1:1-55
Expected type: [Tree]
Actual type: [IHaskell51.Tree]
• In the second argument of ‘canBuild’, namely ‘forest0’
In the expression: canBuild (head sampleBranch) forest0
In an equation for ‘it’: it = canBuild (head sampleBranch) forest0"
],
"text/plain": [
":1:30: error:\n",
" • Couldn't match type ‘Ghci51.Tree’\n",
" with ‘Tree’\n",
" NB: ‘Tree’ is defined at :1:1-55\n",
" ‘Ghci51.Tree’ is defined at :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
}