Task 4 done

diff --git a/data/04-preparation.txt b/data/04-preparation.txt
new file mode 100644 (file)
index 0000000..6a937c1
--- /dev/null
+++ b/data/04-preparation.txt
@@ -0,0 +1,149 @@
+lobster 17
+kebab 13
+beer 19
+ginger 16 pizza yoghurt burger
+skate 14 walnut
+dumpling 10 chicken zucchini granola pancake squash albacore
+bread 20 catfish raddish kebab mint beef antelope
+squash 14 applesauce walnut
+chocolate 17
+carrot 10 peanut
+butternut 10
+mutton 13 fondue turnip acorn courgette beer
+duck 10 rocket jerky
+noodle 10 pepper barley jambalaya
+hamburger 17 donut avocado turnip peanut spaghetti cumin
+crab 17 water raddish turnip
+mustard 16 stock squash coriander
+jelly 15 yoghurt venison caraway
+burger 17 spaghetti bagels waffle chowder
+bluefish 18 corn kangaroo enchilada
+onion 19 pancake caraway bison parsnip watercress spaghetti antelope
+coley 14 chimichanga caraway cumin pancake donut beer
+bagels 16 meatball onion parsnip applesauce peanut pizza beer
+haddock 20 fondue broccoli
+applesauce 12 pepper watercress cumin donut
+babaganoosh 12 crab
+date 14 tomato bagels carrot hummus fondue
+grapes 17 antelope
+ketchup 16 donut parsely caraway sushi
+cumin 17 beer
+stock 20 olive parsnip fondue bison fajita kingfish chicken
+cake 11 coley chimichanga cumin beer hummus donut caraway
+quesadilla 10
+cabbage 18 mayonnaise applesauce
+kingfish 18
+rocket 11
+guancamole 13 hummus
+zucchini 14 pancake
+eggroll 12 antelope onion chimichanga cake
+albacore 13 parsnip pepper honey peanut pizza onion
+muffin 20 hazelnut clam eggroll enchilada juice
+pizza 20 cumin chimichanga coley beer caraway parsnip donut
+donut 11 caraway cumin beer chimichanga
+kale 14 toast turnip bagels olive
+sugarsnap 12 donut
+alfalfa 12 carrot ketchup kingfish
+lasagna 14 porter lobster hummus albacore cake
+courgette 19
+sushi 16 applesauce watercress
+tomato 14 pancake caraway
+cress 14 zucchini pancake granola chicken parsnip meatball olive
+watercress 17 hummus cumin bison coley parsnip meatball carrot
+pepper 12 pancake donut coley caraway parsnip avocado peanut
+antelope 17 hummus coley pancake tomato cumin
+corn 17 venison pepper lobster avocado granola meatball parsnip
+beef 10 hummus date chowder parsely clam skate kangaroo
+pork 11 raddish skate burger pepperoni catfish water porter
+spinach 12 lettuce granola bagels squash
+curry 19 buritto wine raddish gumbo linguine arugala
+walnut 14 onion hummus tomato guancamole
+jerky 13
+basil 15 clam potato ziti dumpling hazelnut corn
+venison 17 albacore salt lobster cheese sushi honey
+sugar 19 bison cake cashew chimichanga celery honey quiche
+almond 17
+bisque 15 squash granola lamb rocket linguine asparagus bison
+port 13 sushi
+pancake 17 chimichanga beer caraway donut cumin
+linguine 13 gumbo yoghurt broccoli hamburger cumin
+porter 19 beer fajita hummus asparagus parsnip parsely cumin
+tuna 17 olive thyme cereal
+caraway 18 beer cumin
+thyme 17 clam onion
+cheese 11 fajita tomato onion donut spaghetti chimichanga
+swede 20
+enchilada 11 apple bisque swede ginger cumin kale
+hazelnut 13 lobster meatball yoghurt mayonnaise onion acorn waffle
+apple 19 fajita parsnip hazelnut
+broccoli 15
+pepperoni 20
+salt 15
+coffee 15 haddock arugala potato
+artichoke 19 rocket onion hummus buritto jambalaya lasagna cashew
+buritto 17 cress courgette swede sugarsnap peanut clam
+cupcake 14 pork jelly
+cereal 19 cabbage clam chips
+mint 14 lamb lettuce carrot flour quiche hummus
+avocado 15 spaghetti onion coley donut watercress caraway beer
+halibut 14 tomato pancake mutton carrot raddish
+milkshake 17 date donut ginger goose courgette
+edimame 10 acorn sugarsnap alfalfa carrot
+milk 17 garlic donut toast walnut
+spaghetti 10
+granola 14
+stout 12 salt parsnip eggroll fish lettuce skate
+chowder 17 meatball bison
+lamb 17 lettuce rocket
+water 11 sugarsnap pancake yoghurt
+rosemary 10
+hummus 10 coley beer tomato pizza parsnip caraway
+parsnip 15
+garlic 12
+turnip 19 meatball avocado hummus caraway pancake applesauce
+kangaroo 14 tomato
+lettuce 17 asparagus honey spaghetti donut tomato watercress
+arugala 19 stout
+asparagus 10 bagels donut tomato hummus cake
+cashew 17 pizza corn donut applesauce clam pepper onion
+kiwi 11
+waffle 11 albacore spaghetti chimichanga sushi lettuce
+raddish 17
+gnocchi 16 kangaroo pancake
+bison 15
+cookie 11 jambalaya avocado bison grapes kangaroo applesauce quesadilla
+bacon 12 turnip gumbo antelope kebab gnocchi pizza spaghetti
+chimichanga 17 caraway
+ziti 10 zucchini spaghetti burger waffle
+moose 16 haddock
+toast 17
+flour 11
+coriander 17 corn barley kale spaghetti sushi watercress dumpling
+yoghurt 14 olive walnut cumin porter salt
+fondue 20
+catfish 20 olive coley rocket fajita hummus
+bruscetta 11 parsely quesadilla mint
+clam 13
+honey 13 caraway cumin applesauce bison antelope turnip chimichanga
+chicken 12 pizza cumin
+celery 13 jerky yoghurt rosemary bread
+chips 17 edimame watercress kale
+potato 20
+camel 17 granola fish
+meatball 15 peanut cumin pancake parsnip
+acorn 16 beer onion asparagus albacore waffle applesauce chowder
+jambalaya 16
+parsely 14 chicken cake spaghetti donut watercress cumin hummus
+peanut 15 cake parsnip donut
+olive 17 chimichanga tomato watercress walnut guancamole hummus
+gumbo 14
+fish 10 yoghurt quiche turnip eggroll crab ziti
+goose 14
+mayonnaise 18 raddish gnocchi albacore peanut courgette
+quiche 12 granola cumin chimichanga olive avocado cheese
+juice 13 dumpling kebab chicken
+ostrich 12 olive meatball
+barley 16 asparagus catfish
+wine 20 guancamole broccoli
+falafel 11 salt garlic bluefish chocolate cookie
+fajita 17 beer applesauce bagels cumin

diff --git a/src/task4/task4.hs b/src/task4/task4.hs
new file mode 100644 (file)
index 0000000..82ad288
--- /dev/null
+++ b/src/task4/task4.hs
@@ -0,0 +1,94 @@
+{-# LANGUAGE OverloadedStrings #-}
+
+-- import Data.List (foldl')        -- import the strict fold
+import Data.List
+
+import Data.Text (Text)
+import qualified Data.Text as T
+import qualified Data.Text.IO as TIO
+
+import qualified Data.HashMap.Strict as M
+import Data.HashMap.Strict ((!))
+
+import Data.Void (Void)
+
+import Text.Megaparsec -- hiding (State)
+import Text.Megaparsec.Char
+import qualified Text.Megaparsec.Char.Lexer as L
+import qualified Control.Applicative as CA
+
+
+type TaskName = String
+type Preconditions = [TaskName]
+
+data Task = Task { name :: TaskName
+                 , duration :: Int
+                 , preconditions :: Preconditions
+                 } deriving (Show, Eq)
+
+
+type CompletedTasks = M.HashMap TaskName Int
+
+main :: IO ()
+main = do 
+        task_text <- TIO.readFile "data/04-preparation.txt"
+        let tasks = successfulParse task_text
+        print $ part1 tasks
+        print $ part2 tasks
+
+
+part1 :: [Task] -> Int
+part1 = sum . (map duration)
+
+part2 :: [Task] -> Int
+part2 tasks = maximum $ M.elems $ timeAllTasks tasks M.empty
+
+timeAllTasks :: [Task] -> CompletedTasks -> CompletedTasks
+timeAllTasks tasks completed 
+    | null tasks = completed
+    | otherwise  = timeAllTasks notDoable completed'
+        where (doable, notDoable) = doableTasks completed tasks
+              completed' = foldl' completeTask completed doable
+
+doableTasks :: CompletedTasks -> [Task] -> ([Task], [Task])
+doableTasks completed tasks = partition (allSatisfied completed) tasks
+
+allSatisfied :: CompletedTasks -> Task -> Bool
+allSatisfied completed task =
+    all (\n -> n `M.member` completed) (preconditions task)
+
+
+completeTask :: CompletedTasks -> Task -> CompletedTasks
+completeTask completed task = M.insert (name task) (duration task + startTime) completed
+    where startTime = if null $ preconditions task
+                      then 0
+                      else maximum $ map (\p -> completed!p) $ preconditions task
+
+
+
+-- Parse the input file
+
+type Parser = Parsec Void Text
+
+-- don't treat newlines as automatically-consumed whitespace
+sc :: Parser ()
+sc = L.space (skipSome (char ' ')) CA.empty CA.empty
+
+lexeme  = L.lexeme sc
+integer = lexeme L.decimal
+symb = L.symbol sc
+
+-- tasks is just a sequence of many individual tasks
+tasksP = many taskP
+
+-- a task is name, duration, preconditions, followed by newline
+taskP = taskify <$> nameP <*> integer <*> (many nameP) <* newline
+  where taskify n d ns = Task {name = n, duration = d, preconditions = ns}
+
+nameP = lexeme (some letterChar)
+
+successfulParse :: Text -> [Task]
+successfulParse input = 
+        case parse tasksP "input" input of
+                Left  _error -> [] -- TIO.putStr $ T.pack $ parseErrorPretty err
+                Right tasks  -> tasks
\ No newline at end of file

diff --git a/src/task4/task4.ipynb b/src/task4/task4.ipynb
new file mode 100644 (file)
index 0000000..c10469a
--- /dev/null
+++ b/src/task4/task4.ipynb
@@ -0,0 +1,184 @@
+{
+ "cells": [
+  {
+   "cell_type": "code",
+   "execution_count": 31,
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "tasks_text = [l.strip() for l in open('../../data/04-preparation.txt')]"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 32,
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "def parse(n_text):\n",
+    "    ns = n_text.split()\n",
+    "    return {'name': ns[0], 'time': int(ns[1]), 'prerequisites': ns[2:]}"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 33,
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "tasks = [parse(l) for l in tasks_text]"
+   ]
+  },
+  {
+   "cell_type": "markdown",
+   "metadata": {},
+   "source": [
+    "# Part 1\n",
+    "If it's just me doing all the tasks, the total time is just the sum of the times for all the tasks."
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 34,
+   "metadata": {},
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "2215"
+      ]
+     },
+     "execution_count": 34,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "sum(n['time'] for n in tasks)"
+   ]
+  },
+  {
+   "cell_type": "markdown",
+   "metadata": {},
+   "source": [
+    "# Part 2\n",
+    "I use two data structures to keep track of the `handled` and `unhandled` tasks. \n",
+    "\n",
+    "`handled` tasks have all their prerequisites completed and have a known end time: they're stored in a `dict` of task name -> end time. \n",
+    "\n",
+    "`unhanded` tasks are those without a known end time: they're stored in a copy of the `tasks` list."
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 45,
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "handled = {}\n",
+    "unhandled = tasks[:]"
+   ]
+  },
+  {
+   "cell_type": "markdown",
+   "metadata": {},
+   "source": [
+    "The `candidate` tasks are those where we don't know the end time, but we know enough to work it out. They are the tasks where all their prerequisites are in `handled`."
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 36,
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "def candidates(unhandled, handled):\n",
+    "    return [task for task in unhandled \n",
+    "            if all(p in handled for p in task['prerequisites'])]"
+   ]
+  },
+  {
+   "cell_type": "markdown",
+   "metadata": {},
+   "source": [
+    "For each `candidate`, the earliest we can start the task is the latest end time of any of its prerequisites (or zero, for those tasks with no prerequisites). We then record its end time in the `handled` dict, and remove the task from `unhandled`. "
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 46,
+   "metadata": {},
+   "outputs": [
+    {
+     "name": "stdout",
+     "output_type": "stream",
+     "text": [
+      "27.2 ns ± 0.157 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)\n"
+     ]
+    }
+   ],
+   "source": [
+    "while unhandled:\n",
+    "    for candidate in candidates(unhandled, handled):\n",
+    "        start_time = max([0] + [handled[p] for p in candidate['prerequisites']])\n",
+    "        handled[candidate['name']] = start_time + candidate['time']\n",
+    "        unhandled.remove(candidate)"
+   ]
+  },
+  {
+   "cell_type": "markdown",
+   "metadata": {},
+   "source": [
+    "We can now look up the largest end time in `handled`."
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 47,
+   "metadata": {},
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "413"
+      ]
+     },
+     "execution_count": 47,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "max(time for time in handled.values())"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": null,
+   "metadata": {},
+   "outputs": [],
+   "source": []
+  }
+ ],
+ "metadata": {
+  "kernelspec": {
+   "display_name": "Python 3",
+   "language": "python",
+   "name": "python3"
+  },
+  "language_info": {
+   "codemirror_mode": {
+    "name": "ipython",
+    "version": 3
+   },
+   "file_extension": ".py",
+   "mimetype": "text/x-python",
+   "name": "python",
+   "nbconvert_exporter": "python",
+   "pygments_lexer": "ipython3",
+   "version": "3.6.6"
+  }
+ },
+ "nbformat": 4,
+ "nbformat_minor": 2
+}