src/task4/task4.ipynb

   1 {
   2  "cells": [
   3   {
   4    "cell_type": "code",
   5    "execution_count": 31,
   6    "metadata": {},
   7    "outputs": [],
   8    "source": [
   9     "tasks_text = [l.strip() for l in open('../../data/04-preparation.txt')]"
  10    ]
  11   },
  12   {
  13    "cell_type": "code",
  14    "execution_count": 32,
  15    "metadata": {},
  16    "outputs": [],
  17    "source": [
  18     "def parse(n_text):\n",
  19     "    ns = n_text.split()\n",
  20     "    return {'name': ns[0], 'time': int(ns[1]), 'prerequisites': ns[2:]}"
  21    ]
  22   },
  23   {
  24    "cell_type": "code",
  25    "execution_count": 33,
  26    "metadata": {},
  27    "outputs": [],
  28    "source": [
  29     "tasks = [parse(l) for l in tasks_text]"
  30    ]
  31   },
  32   {
  33    "cell_type": "markdown",
  34    "metadata": {},
  35    "source": [
  36     "# Part 1\n",
  37     "If it's just me doing all the tasks, the total time is just the sum of the times for all the tasks."
  38    ]
  39   },
  40   {
  41    "cell_type": "code",
  42    "execution_count": 34,
  43    "metadata": {},
  44    "outputs": [
  45     {
  46      "data": {
  47       "text/plain": [
  48        "2215"
  49       ]
  50      },
  51      "execution_count": 34,
  52      "metadata": {},
  53      "output_type": "execute_result"
  54     }
  55    ],
  56    "source": [
  57     "sum(n['time'] for n in tasks)"
  58    ]
  59   },
  60   {
  61    "cell_type": "markdown",
  62    "metadata": {},
  63    "source": [
  64     "# Part 2\n",
  65     "I use two data structures to keep track of the `handled` and `unhandled` tasks. \n",
  66     "\n",
  67     "`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",
  68     "\n",
  69     "`unhanded` tasks are those without a known end time: they're stored in a copy of the `tasks` list."
  70    ]
  71   },
  72   {
  73    "cell_type": "code",
  74    "execution_count": 45,
  75    "metadata": {},
  76    "outputs": [],
  77    "source": [
  78     "handled = {}\n",
  79     "unhandled = tasks[:]"
  80    ]
  81   },
  82   {
  83    "cell_type": "markdown",
  84    "metadata": {},
  85    "source": [
  86     "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`."
  87    ]
  88   },
  89   {
  90    "cell_type": "code",
  91    "execution_count": 36,
  92    "metadata": {},
  93    "outputs": [],
  94    "source": [
  95     "def candidates(unhandled, handled):\n",
  96     "    return [task for task in unhandled \n",
  97     "            if all(p in handled for p in task['prerequisites'])]"
  98    ]
  99   },
 100   {
 101    "cell_type": "markdown",
 102    "metadata": {},
 103    "source": [
 104     "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`. "
 105    ]
 106   },
 107   {
 108    "cell_type": "code",
 109    "execution_count": 46,
 110    "metadata": {},
 111    "outputs": [
 112     {
 113      "name": "stdout",
 114      "output_type": "stream",
 115      "text": [
 116       "27.2 ns ± 0.157 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)\n"
 117      ]
 118     }
 119    ],
 120    "source": [
 121     "while unhandled:\n",
 122     "    for candidate in candidates(unhandled, handled):\n",
 123     "        start_time = max([0] + [handled[p] for p in candidate['prerequisites']])\n",
 124     "        handled[candidate['name']] = start_time + candidate['time']\n",
 125     "        unhandled.remove(candidate)"
 126    ]
 127   },
 128   {
 129    "cell_type": "markdown",
 130    "metadata": {},
 131    "source": [
 132     "We can now look up the largest end time in `handled`."
 133    ]
 134   },
 135   {
 136    "cell_type": "code",
 137    "execution_count": 47,
 138    "metadata": {},
 139    "outputs": [
 140     {
 141      "data": {
 142       "text/plain": [
 143        "413"
 144       ]
 145      },
 146      "execution_count": 47,
 147      "metadata": {},
 148      "output_type": "execute_result"
 149     }
 150    ],
 151    "source": [
 152     "max(time for time in handled.values())"
 153    ]
 154   },
 155   {
 156    "cell_type": "code",
 157    "execution_count": null,
 158    "metadata": {},
 159    "outputs": [],
 160    "source": []
 161   }
 162  ],
 163  "metadata": {
 164   "kernelspec": {
 165    "display_name": "Python 3",
 166    "language": "python",
 167    "name": "python3"
 168   },
 169   "language_info": {
 170    "codemirror_mode": {
 171     "name": "ipython",
 172     "version": 3
 173    },
 174    "file_extension": ".py",
 175    "mimetype": "text/x-python",
 176    "name": "python",
 177    "nbconvert_exporter": "python",
 178    "pygments_lexer": "ipython3",
 179    "version": "3.6.6"
 180   }
 181  },
 182  "nbformat": 4,
 183  "nbformat_minor": 2
 184 }