Project P039
Task planner
Tasks with a length in days and the tasks each one needs first: an order that respects every dependency (Kahn's algorithm), each task's earliest start, finish and slack, a small chart, and the critical path that decides the total. A dependency that closes a cycle is named at once, and no plan is made until the cycle is broken.
2 modules · 2 recorded sessionstext-menu UI in the terminalupdated 2026-10-10
Every screen below was recorded under CPython. When this page was built, the EML interpreter replayed each session from the same input and printed the same bytes.
About
Up to 15 tasks, each with a length in days and the tasks it needs finished first. The plan puts the tasks in an order that respects every dependency, gives each one its earliest start, its finish and its slack - how many days it can slip without delaying the end - draws them as a small chart, and names the critical path, the chain of tasks that decides how long the whole thing takes. A dependency that closes a cycle is accepted but named at once, and no plan is possible until one of its links is removed.
main.eml- the menu, tasks and dependencies with their checks, and the plan on screenplan.eml- the order, the schedule, the critical path and the cycles
How each part works:
- The order is Kahn's algorithm, as in the corpus case
topological-sort: take a task whose prerequisites are all done, again and again. When several are ready, the one added first goes first, so the same tasks always give the same plan. Tasks that wait, directly or through others, on a cycle can never be taken; the plan names them and one cycle among them. - The schedule is the critical path method. Going forward through the order, a task starts when its last prerequisite finishes. Going back, a task may finish as late as the earliest start of anything that waits for it, or the end of the project if nothing does; its slack is the difference. Lengthening a task by its slack leaves the total as it is, and one day more makes it one day longer.
- The critical path starts from the task that finishes last and steps back through prerequisites that have no slack and finish exactly when the next task starts. When there are two such chains, the other tasks with no slack are listed too.
- A new dependency closes a cycle when the task it points to already waits, through some chain, for the task that gets it. The chain is found by a depth-first search and shown as "a needs b, b needs c, c needs a".
- The chart shows # for working days and - for slack, one character per day, for plans of up to 60 days.
What is checked: names of 1 to 12 letters, digits or hyphens, each different in any case, at most 15 tasks; 1 to 30 days; a dependency between two different existing tasks, not one already there. An empty answer cancels.
Sessions: sessions/basic.in plans a small building job of eight tasks: 24 days, plumbing with one day of slack, the critical path through wiring. It then makes framing need wiring - a cycle, named at once - shows that no plan is possible, removes that dependency, and adds a four-day tiles task after plumbing, which uses up plumbing's slack and makes a second critical chain. sessions/bad-input.in gives menu choices 0 and x, the lists and the plan with no tasks, names with a space, of 13 characters and with !, days 0, 31 and x, a name used twice in another case, a task that needs itself, a dependency given twice, a three-task cycle and the plan it blocks, the removal of dependencies that are not there, and fifteen tasks with a sixteenth refused; the last plan has twelve tasks with seven days of slack each.
Built on the verified corpus case topological-sort (Kahn's algorithm, which also shows a cycle when tasks are left over).
Recorded sessions
What the screen shows while someone uses the program. Each typed line appears after its prompt, the way a terminal shows it.
bad-input
interpreter: byte-equal== Task planner ==
Tasks with their length in days, and the tasks each one needs finished first.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 0
Pick a number from 1 to 6.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> x
Pick a number from 1 to 6.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 4
No tasks yet.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 5
No tasks yet.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 3
task>
Cancelled.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 2
Add at least two tasks first.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 1
task name> a b
A name is 1 to 12 letters, digits or hyphens.
task name> thirteen-char
A name is 1 to 12 letters, digits or hyphens.
task name> bad!
A name is 1 to 12 letters, digits or hyphens.
task name> Write
days (1 to 30)> 0
Type a number from 1 to 30.
days (1 to 30)> 31
Type a number from 1 to 30.
days (1 to 30)> x
Type a number from 1 to 30.
days (1 to 30)>
Cancelled.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 1
task name> Write
days (1 to 30)> 5
Write added: 5 days.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 1
task name> write
There is already a task called Write.
task name>
Cancelled.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 2
Add at least two tasks first.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 1
task name> Test
days (1 to 30)> 2
Test added: 2 days.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 1
task name> Ship
days (1 to 30)> 1
Ship added: 1 day.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 2
task> Tset
There is no task called Tset.
task> Test
needs which task first> Test
A task cannot need itself.
needs which task first> Write
Test now needs Write first.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 2
task> Test
needs which task first> Write
Test already needs Write.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 2
task> Ship
needs which task first> Test
Ship now needs Test first.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 2
task> Write
needs which task first> Ship
Write now needs Ship first.
That closes a cycle: Write needs Ship, Ship needs Test, Test needs Write. No plan is possible until one of these is removed.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 5
No plan: Write, Test and Ship can never start, because of a cycle - Write needs Ship, Ship needs Test, Test needs Write.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 3
task> Write
It needs Ship.
no longer needs> 3
There is no task called 3.
no longer needs> Write
Write does not need Write.
no longer needs> Test
Write does not need Test.
no longer needs> Ship
Write no longer needs Ship.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 3
task> Write
Write needs nothing.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 1
task name> task-4
days (1 to 30)> 1
task-4 added: 1 day.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 1
task name> task-5
days (1 to 30)> 1
task-5 added: 1 day.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 1
task name> task-6
days (1 to 30)> 1
task-6 added: 1 day.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 1
task name> task-7
days (1 to 30)> 1
task-7 added: 1 day.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 1
task name> task-8
days (1 to 30)> 1
task-8 added: 1 day.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 1
task name> task-9
days (1 to 30)> 1
task-9 added: 1 day.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 1
task name> task-10
days (1 to 30)> 1
task-10 added: 1 day.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 1
task name> task-11
days (1 to 30)> 1
task-11 added: 1 day.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 1
task name> task-12
days (1 to 30)> 1
task-12 added: 1 day.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 1
task name> task-13
days (1 to 30)> 1
task-13 added: 1 day.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 1
task name> task-14
days (1 to 30)> 1
task-14 added: 1 day.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 1
task name> task-15
days (1 to 30)> 1
task-15 added: 1 day.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 1
That makes 15 tasks, the most.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 4
Write (5 days)
Test (2 days), needs Write
Ship (1 day), needs Test
task-4 (1 day)
task-5 (1 day)
task-6 (1 day)
task-7 (1 day)
task-8 (1 day)
task-9 (1 day)
task-10 (1 day)
task-11 (1 day)
task-12 (1 day)
task-13 (1 day)
task-14 (1 day)
task-15 (1 day)
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 5
15 tasks, 8 days in all. Start and finish count days from the beginning.
task days start finish slack # = working, - = slack
Write 5 0 5 0 #####
Test 2 5 7 0 ##
Ship 1 7 8 0 #
task-4 1 0 1 7 #-------
task-5 1 0 1 7 #-------
task-6 1 0 1 7 #-------
task-7 1 0 1 7 #-------
task-8 1 0 1 7 #-------
task-9 1 0 1 7 #-------
task-10 1 0 1 7 #-------
task-11 1 0 1 7 #-------
task-12 1 0 1 7 #-------
task-13 1 0 1 7 #-------
task-14 1 0 1 7 #-------
task-15 1 0 1 7 #-------
Critical path: Write -> Test -> Ship (8 days). A delay to any of these delays the end.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 6
Bye.
What was typed (92 lines)
0
x
4
5
3
2
1
a b
thirteen-char
bad!
Write
0
31
x
1
Write
5
1
write
2
1
Test
2
1
Ship
1
2
Tset
Test
Test
Write
2
Test
Write
2
Ship
Test
2
Write
Ship
5
3
Write
3
Write
Test
Ship
3
Write
1
task-4
1
1
task-5
1
1
task-6
1
1
task-7
1
1
task-8
1
1
task-9
1
1
task-10
1
1
task-11
1
1
task-12
1
1
task-13
1
1
task-14
1
1
task-15
1
1
4
5
6
basic
interpreter: byte-equal== Task planner ==
Tasks with their length in days, and the tasks each one needs finished first.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 1
task name> design
days (1 to 30)> 3
design added: 3 days.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 1
task name> permit
days (1 to 30)> 5
permit added: 5 days.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 1
task name> foundation
days (1 to 30)> 4
foundation added: 4 days.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 1
task name> framing
days (1 to 30)> 6
framing added: 6 days.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 1
task name> wiring
days (1 to 30)> 3
wiring added: 3 days.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 1
task name> plumbing
days (1 to 30)> 2
plumbing added: 2 days.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 1
task name> inspect
days (1 to 30)> 1
inspect added: 1 day.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 1
task name> paint
days (1 to 30)> 2
paint added: 2 days.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 2
task> permit
needs which task first> design
permit now needs design first.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 2
task> foundation
needs which task first> permit
foundation now needs permit first.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 2
task> framing
needs which task first> foundation
framing now needs foundation first.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 2
task> wiring
needs which task first> framing
wiring now needs framing first.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 2
task> plumbing
needs which task first> framing
plumbing now needs framing first.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 2
task> inspect
needs which task first> wiring
inspect now needs wiring first.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 2
task> inspect
needs which task first> plumbing
inspect now needs plumbing first.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 2
task> paint
needs which task first> inspect
paint now needs inspect first.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 4
design (3 days)
permit (5 days), needs design
foundation (4 days), needs permit
framing (6 days), needs foundation
wiring (3 days), needs framing
plumbing (2 days), needs framing
inspect (1 day), needs wiring and plumbing
paint (2 days), needs inspect
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 5
8 tasks, 24 days in all. Start and finish count days from the beginning.
task days start finish slack # = working, - = slack
design 3 0 3 0 ###
permit 5 3 8 0 #####
foundation 4 8 12 0 ####
framing 6 12 18 0 ######
wiring 3 18 21 0 ###
plumbing 2 18 20 1 ##-
inspect 1 21 22 0 #
paint 2 22 24 0 ##
Critical path: design -> permit -> foundation -> framing -> wiring -> inspect -> paint (24 days). A delay to any of these delays the end.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 2
task> framing
needs which task first> wiring
framing now needs wiring first.
That closes a cycle: framing needs wiring, wiring needs framing. No plan is possible until one of these is removed.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 5
No plan: framing, wiring, plumbing, inspect and paint can never start, because of a cycle - framing needs wiring, wiring needs framing.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 3
task> framing
It needs foundation and wiring.
no longer needs> wiring
framing no longer needs wiring.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 5
8 tasks, 24 days in all. Start and finish count days from the beginning.
task days start finish slack # = working, - = slack
design 3 0 3 0 ###
permit 5 3 8 0 #####
foundation 4 8 12 0 ####
framing 6 12 18 0 ######
wiring 3 18 21 0 ###
plumbing 2 18 20 1 ##-
inspect 1 21 22 0 #
paint 2 22 24 0 ##
Critical path: design -> permit -> foundation -> framing -> wiring -> inspect -> paint (24 days). A delay to any of these delays the end.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 1
task name> tiles
days (1 to 30)> 4
tiles added: 4 days.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 2
task> tiles
needs which task first> plumbing
tiles now needs plumbing first.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 5
9 tasks, 24 days in all. Start and finish count days from the beginning.
task days start finish slack # = working, - = slack
design 3 0 3 0 ###
permit 5 3 8 0 #####
foundation 4 8 12 0 ####
framing 6 12 18 0 ######
wiring 3 18 21 0 ###
plumbing 2 18 20 0 ##
inspect 1 21 22 0 #
paint 2 22 24 0 ##
tiles 4 20 24 0 ####
Critical path: design -> permit -> foundation -> framing -> wiring -> inspect -> paint (24 days). A delay to any of these delays the end.
Also with no slack: plumbing and tiles.
1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit
choice> 6
Bye.
What was typed (66 lines)
1
design
3
1
permit
5
1
foundation
4
1
framing
6
1
wiring
3
1
plumbing
2
1
inspect
1
1
paint
2
2
permit
design
2
foundation
permit
2
framing
foundation
2
wiring
framing
2
plumbing
framing
2
inspect
wiring
2
inspect
plumbing
2
paint
inspect
4
5
2
framing
wiring
5
3
framing
wiring
5
1
tiles
4
2
tiles
plumbing
5
6
Modules
The program as written, entry module first. Each module transpiles to its own Python file, which is what eml project run executes.
main.eml(entry)
eml# P039 task planner: tasks with a length in days and the tasks each one
# needs finished first. The plan puts them in an order that respects every
# dependency, gives each its earliest start, its finish and its slack, and
# names the critical path - the chain that decides how long the whole thing
# takes. A dependency that closes a cycle is accepted but named at once, and
# no plan is possible until the cycle is broken.
import plan
15 => most_tasks
30 => longest_task
60 => widest_chart
def trim(s):
0 => i
len(s) => j
while i < j and s[i] == " ":
i + 1 => i
while j > i and s[j - 1] == " ":
j - 1 => j
return s[i:j]
def lower(s):
"ABCDEFGHIJKLMNOPQRSTUVWXYZ" => big
"abcdefghijklmnopqrstuvwxyz" => small
"" => out
for c in s:
0 => k
while k < 26 and big[k] != c:
k + 1 => k
if k < 26:
out + small[k] => out
else:
out + c => out
return out
def is_name(s):
if s == "" or len(s) > 12:
return False
for c in s:
if not (c in "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789-"):
return False
return True
def number(s):
if s == "" or len(s) > 3:
return -1
0 => n
for c in s:
if not (c in "0123456789"):
return -1
n * 10 + int(c) => n
return n
def days_text(d):
if d == 1:
return "1 day"
return str(d) + " days"
def contains(xs, x):
for y in xs:
if y == x:
return True
return False
def find(names, s):
for i in [0:len(names) - 1]:
if lower(names[i]) == lower(s):
return i
return -1
def ask_task(names, prompt):
# The number of an existing task, or -1 when the answer is empty.
while True:
trim(input(prompt)) => answer
if answer == "":
return -1
find(names, answer) => t
if t >= 0:
return t
("There is no task called " + answer + ".") ^0
def chain_text(names, chain):
# [a, b, c, a] as "a needs b, b needs c, c needs a".
"" => out
for i in [0:len(chain) - 2]:
if out != "":
out + ", " => out
out + names[chain[i]] + " needs " + names[chain[i + 1]] => out
return out
def listed(names, tasks):
"" => out
for i in [0:len(tasks) - 1]:
if i > 0 and i == len(tasks) - 1:
out + " and " => out
elif i > 0:
out + ", " => out
out + names[tasks[i]] => out
return out
def add_task(state):
state[0] => names
if len(names) == most_tasks:
("That makes " + str(most_tasks) + " tasks, the most.") ^0
return state
while True:
trim(input("task name> ")) => name
if name == "":
"Cancelled." ^0
return state
if not is_name(name):
"A name is 1 to 12 letters, digits or hyphens." ^0
elif find(names, name) >= 0:
("There is already a task called " + names[find(names, name)] + ".") ^0
else:
while True:
trim(input("days (1 to " + str(longest_task) + ")> ")) => answer
if answer == "":
"Cancelled." ^0
return state
number(answer) => d
if d >= 1 and d <= longest_task:
(name + " added: " + days_text(d) + ".") ^0
return [names + [name], state[1] + [d], state[2] + [[]]]
("Type a number from 1 to " + str(longest_task) + ".") ^0
def add_need(state):
state[0] => names
state[2] => needs
if len(names) < 2:
"Add at least two tasks first." ^0
return state
ask_task(names, "task> ") => t
if t == -1:
"Cancelled." ^0
return state
while True:
ask_task(names, "needs which task first> ") => p
if p == -1:
"Cancelled." ^0
return state
if p == t:
"A task cannot need itself." ^0
elif contains(needs[t], p):
(names[t] + " already needs " + names[p] + ".") ^0
return state
else:
needs[0:t] + [needs[t] + [p]] + needs[t + 1:len(needs)] => needs
(names[t] + " now needs " + names[p] + " first.") ^0
plan.cycle_through(needs, t, p) => c
if len(c) > 0:
("That closes a cycle: " + chain_text(names, c) + ". No plan is possible until one of these is removed.") ^0
return [names, state[1], needs]
def drop_need(state):
state[0] => names
state[2] => needs
ask_task(names, "task> ") => t
if t == -1:
"Cancelled." ^0
return state
if len(needs[t]) == 0:
(names[t] + " needs nothing.") ^0
return state
("It needs " + listed(names, needs[t]) + ".") ^0
while True:
ask_task(names, "no longer needs> ") => p
if p == -1:
"Cancelled." ^0
return state
if contains(needs[t], p):
[] => kept
for q in needs[t]:
if q != p:
kept + [q] => kept
(names[t] + " no longer needs " + names[p] + ".") ^0
return [names, state[1], needs[0:t] + [kept] + needs[t + 1:len(needs)]]
(names[t] + " does not need " + names[p] + ".") ^0
def pad(s, width):
while len(s) < width:
s + " " => s
return s
def right(s, width):
while len(s) < width:
" " + s => s
return s
def show_tasks(state):
state[0] => names
if len(names) == 0:
"No tasks yet." ^0
return 0
for t in [0:len(names) - 1]:
"" => after
if len(state[2][t]) > 0:
", needs " + listed(names, state[2][t]) => after
(" " + names[t] + " (" + days_text(state[1][t]) + ")" + after) ^0
return 0
def show_plan(state):
state[0] => names
state[1] => days
state[2] => needs
if len(names) == 0:
"No tasks yet." ^0
return 0
plan.order(needs) => seq
if len(seq) < len(names):
[] => stuck
for t in [0:len(names) - 1]:
if not contains(seq, t):
stuck + [t] => stuck
("No plan: " + listed(names, stuck) + " can never start, because of a cycle - " + chain_text(names, plan.some_cycle(needs, stuck)) + ".") ^0
return 0
plan.schedule(needs, days, seq) => sch
sch[3] => total
(str(len(names)) + " tasks, " + days_text(total) + " in all. Start and finish count days from the beginning.") ^0
" task days start finish slack" => header
if total <= widest_chart:
header + " " + "#" + " = working, - = slack" => header
header ^0
for t in seq:
(" " + pad(names[t], 12) + right(str(days[t]), 6) + right(str(sch[0][t]), 7) + right(str(sch[1][t]), 8) + right(str(sch[2][t]), 7)) => line
if total <= widest_chart:
line + " " + " " * sch[0][t] + "#" * days[t] + "-" * sch[2][t] => line
line ^0
plan.critical_path(needs, seq, sch) => cp
"" => chain
for t in cp:
if chain != "":
chain + " -> " => chain
chain + names[t] => chain
("Critical path: " + chain + " (" + days_text(total) + "). A delay to any of these delays the end.") ^0
[] => others
for t in seq:
if sch[2][t] == 0 and not contains(cp, t):
others + [t] => others
if len(others) > 0:
("Also with no slack: " + listed(names, others) + ".") ^0
return 0
"== Task planner ==" ^0
"Tasks with their length in days, and the tasks each one needs finished first." ^0
[[], [], []] => state
True => running
while running:
"" ^0
"1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit" ^0
trim(input("choice> ")) => choice
if choice == "1":
add_task(state) => state
elif choice == "2":
add_need(state) => state
elif choice == "3":
drop_need(state) => state
elif choice == "4":
show_tasks(state)
elif choice == "5":
show_plan(state)
elif choice == "6":
False => running
else:
"Pick a number from 1 to 6." ^0
"Bye." ^0
Python projection (main.py)
import plan
most_tasks = 15
longest_task = 30
widest_chart = 60
def trim(s):
i = 0
j = len(s)
while i < j and s[i] == " ":
i = i + 1
while j > i and s[j - 1] == " ":
j = j - 1
return s[i:j]
def lower(s):
big = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
small = "abcdefghijklmnopqrstuvwxyz"
out = ""
for c in s:
k = 0
while k < 26 and big[k] != c:
k = k + 1
if k < 26:
out = out + small[k]
else:
out = out + c
return out
def is_name(s):
if s == "" or len(s) > 12:
return False
for c in s:
if not c in "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789-":
return False
return True
def number(s):
if s == "" or len(s) > 3:
return -1
n = 0
for c in s:
if not c in "0123456789":
return -1
n = n * 10 + int(c)
return n
def days_text(d):
if d == 1:
return "1 day"
return str(d) + " days"
def contains(xs, x):
for y in xs:
if y == x:
return True
return False
def find(names, s):
for i in range(0, len(names)):
if lower(names[i]) == lower(s):
return i
return -1
def ask_task(names, prompt):
while True:
answer = trim(input(prompt))
if answer == "":
return -1
t = find(names, answer)
if t >= 0:
return t
print("There is no task called " + answer + ".")
def chain_text(names, chain):
out = ""
for i in range(0, len(chain) - 2+1):
if out != "":
out = out + ", "
out = out + names[chain[i]] + " needs " + names[chain[i + 1]]
return out
def listed(names, tasks):
out = ""
for i in range(0, len(tasks)):
if i > 0 and i == len(tasks) - 1:
out = out + " and "
elif i > 0:
out = out + ", "
out = out + names[tasks[i]]
return out
def add_task(state):
names = state[0]
if len(names) == most_tasks:
print("That makes " + str(most_tasks) + " tasks, the most.")
return state
while True:
name = trim(input("task name> "))
if name == "":
print("Cancelled.")
return state
if not is_name(name):
print("A name is 1 to 12 letters, digits or hyphens.")
elif find(names, name) >= 0:
print("There is already a task called " + names[find(names, name)] + ".")
else:
while True:
answer = trim(input("days (1 to " + str(longest_task) + ")> "))
if answer == "":
print("Cancelled.")
return state
d = number(answer)
if d >= 1 and d <= longest_task:
print(name + " added: " + days_text(d) + ".")
return [names + [name], state[1] + [d], state[2] + [[]]]
print("Type a number from 1 to " + str(longest_task) + ".")
def add_need(state):
names = state[0]
needs = state[2]
if len(names) < 2:
print("Add at least two tasks first.")
return state
t = ask_task(names, "task> ")
if t == -1:
print("Cancelled.")
return state
while True:
p = ask_task(names, "needs which task first> ")
if p == -1:
print("Cancelled.")
return state
if p == t:
print("A task cannot need itself.")
elif contains(needs[t], p):
print(names[t] + " already needs " + names[p] + ".")
return state
else:
needs = needs[0:t] + [needs[t] + [p]] + needs[t + 1:len(needs)]
print(names[t] + " now needs " + names[p] + " first.")
c = plan.cycle_through(needs, t, p)
if len(c) > 0:
print("That closes a cycle: " + chain_text(names, c) + ". No plan is possible until one of these is removed.")
return [names, state[1], needs]
def drop_need(state):
names = state[0]
needs = state[2]
t = ask_task(names, "task> ")
if t == -1:
print("Cancelled.")
return state
if len(needs[t]) == 0:
print(names[t] + " needs nothing.")
return state
print("It needs " + listed(names, needs[t]) + ".")
while True:
p = ask_task(names, "no longer needs> ")
if p == -1:
print("Cancelled.")
return state
if contains(needs[t], p):
kept = []
for q in needs[t]:
if q != p:
kept = kept + [q]
print(names[t] + " no longer needs " + names[p] + ".")
return [names, state[1], needs[0:t] + [kept] + needs[t + 1:len(needs)]]
print(names[t] + " does not need " + names[p] + ".")
def pad(s, width):
while len(s) < width:
s = s + " "
return s
def right(s, width):
while len(s) < width:
s = " " + s
return s
def show_tasks(state):
names = state[0]
if len(names) == 0:
print("No tasks yet.")
return 0
for t in range(0, len(names)):
after = ""
if len(state[2][t]) > 0:
after = ", needs " + listed(names, state[2][t])
print(" " + names[t] + " (" + days_text(state[1][t]) + ")" + after)
return 0
def show_plan(state):
names = state[0]
days = state[1]
needs = state[2]
if len(names) == 0:
print("No tasks yet.")
return 0
seq = plan.order(needs)
if len(seq) < len(names):
stuck = []
for t in range(0, len(names)):
if not contains(seq, t):
stuck = stuck + [t]
print("No plan: " + listed(names, stuck) + " can never start, because of a cycle - " + chain_text(names, plan.some_cycle(needs, stuck)) + ".")
return 0
sch = plan.schedule(needs, days, seq)
total = sch[3]
print(str(len(names)) + " tasks, " + days_text(total) + " in all. Start and finish count days from the beginning.")
header = " task days start finish slack"
if total <= widest_chart:
header = header + " " + "#" + " = working, - = slack"
print(header)
for t in seq:
line = " " + pad(names[t], 12) + right(str(days[t]), 6) + right(str(sch[0][t]), 7) + right(str(sch[1][t]), 8) + right(str(sch[2][t]), 7)
if total <= widest_chart:
line = line + " " + " " * sch[0][t] + "#" * days[t] + "-" * sch[2][t]
print(line)
cp = plan.critical_path(needs, seq, sch)
chain = ""
for t in cp:
if chain != "":
chain = chain + " -> "
chain = chain + names[t]
print("Critical path: " + chain + " (" + days_text(total) + "). A delay to any of these delays the end.")
others = []
for t in seq:
if sch[2][t] == 0 and not contains(cp, t):
others = others + [t]
if len(others) > 0:
print("Also with no slack: " + listed(names, others) + ".")
return 0
print("== Task planner ==")
print("Tasks with their length in days, and the tasks each one needs finished first.")
state = [[], [], []]
running = True
while running:
print("")
print("1) add a task 2) add a dependency 3) remove a dependency 4) tasks 5) plan 6) quit")
choice = trim(input("choice> "))
if choice == "1":
state = add_task(state)
elif choice == "2":
state = add_need(state)
elif choice == "3":
state = drop_need(state)
elif choice == "4":
show_tasks(state)
elif choice == "5":
show_plan(state)
elif choice == "6":
running = False
else:
print("Pick a number from 1 to 6.")
print("Bye.")
plan.eml
eml# P039 task planner - the order and the schedule. Tasks are numbered in the
# order they were added; needs[t] lists the tasks t waits for.
def order(needs):
# Kahn's algorithm, as in the corpus case topological-sort: repeatedly
# take a task whose prerequisites are all done. When several are ready,
# the one added first goes first, so the plan never depends on chance.
# Returns the tasks in order; if a cycle blocks some, they are missing.
len(needs) => n
[False] * n => done
[] => out
True => moving
while moving:
-1 => pick
for t in [0:n - 1]:
if pick == -1 and not done[t]:
True => ready
for p in needs[t]:
if not done[p]:
False => ready
if ready:
t => pick
if pick == -1:
False => moving
else:
True => done[pick]
out + [pick] => out
return out
def path(needs, start, goal):
# A chain of "waits for" from start to goal, or [] if there is none
# (depth-first, prerequisites in the order they were given).
[[start]] => stack
[False] * len(needs) => seen
while len(stack) > 0:
stack[len(stack) - 1] => chain
stack[0:len(stack) - 1] => stack
chain[len(chain) - 1] => t
if t == goal and len(chain) > 1:
return chain
if not seen[t]:
True => seen[t]
len(needs[t]) - 1 => i
while i >= 0:
stack + [chain + [needs[t][i]]] => stack
i - 1 => i
return []
def cycle_through(needs, t, p):
# If t now waits for p and p already waits (perhaps through others)
# for t, the cycle t -> p -> ... -> t; otherwise [].
path(needs, p, t) => back
if len(back) == 0:
return []
return [t] + back
def some_cycle(needs, stuck):
# One cycle among the tasks a plan could not place: follow the first
# stuck prerequisite until a task comes round again.
[False] * len(needs) => is_stuck
for t in stuck:
True => is_stuck[t]
[stuck[0]] => walk
while True:
walk[len(walk) - 1] => t
-1 => nxt
for p in needs[t]:
if nxt == -1 and is_stuck[p]:
p => nxt
for i in [0:len(walk) - 1]:
if walk[i] == nxt:
return walk[i:len(walk)] + [nxt]
walk + [nxt] => walk
def schedule(needs, days, seq):
# The critical path method over a valid order: a task starts when its
# last prerequisite finishes (forward pass), and may finish as late as
# the earliest start of what waits for it without delaying the end
# (backward pass). Returns [start, finish, slack, total].
len(needs) => n
[0] * n => start
[0] * n => finish
for t in seq:
0 => s
for p in needs[t]:
if finish[p] > s:
finish[p] => s
s => start[t]
s + days[t] => finish[t]
0 => total
for t in [0:n - 1]:
if finish[t] > total:
finish[t] => total
[total] * n => latest
len(seq) - 1 => i
while i >= 0:
seq[i] => t
for u in [0:n - 1]:
for p in needs[u]:
if p == t and latest[u] - days[u] < latest[t]:
latest[u] - days[u] => latest[t]
i - 1 => i
[] => slack
for t in [0:n - 1]:
slack + [latest[t] - finish[t]] => slack
return [start, finish, slack, total]
def critical_path(needs, seq, sch):
# A chain of tasks with no slack from the first to the end: start at the
# task finishing last and step back to a prerequisite that finishes
# exactly when it starts.
sch[0] => start
sch[1] => finish
sch[2] => slack
-1 => t
for u in seq:
if slack[u] == 0 and finish[u] == sch[3] and t == -1:
u => t
[t] => chain
True => going
while going:
-1 => back
for p in needs[t]:
if back == -1 and finish[p] == start[t] and slack[p] == 0:
p => back
if back == -1:
False => going
else:
[back] + chain => chain
back => t
return chain
Python projection (plan.py)
def order(needs):
n = len(needs)
done = [False] * n
out = []
moving = True
while moving:
pick = -1
for t in range(0, n):
if pick == -1 and not done[t]:
ready = True
for p in needs[t]:
if not done[p]:
ready = False
if ready:
pick = t
if pick == -1:
moving = False
else:
done[pick] = True
out = out + [pick]
return out
def path(needs, start, goal):
stack = [[start]]
seen = [False] * len(needs)
while len(stack) > 0:
chain = stack[len(stack) - 1]
stack = stack[0:len(stack) - 1]
t = chain[len(chain) - 1]
if t == goal and len(chain) > 1:
return chain
if not seen[t]:
seen[t] = True
i = len(needs[t]) - 1
while i >= 0:
stack = stack + [chain + [needs[t][i]]]
i = i - 1
return []
def cycle_through(needs, t, p):
back = path(needs, p, t)
if len(back) == 0:
return []
return [t] + back
def some_cycle(needs, stuck):
is_stuck = [False] * len(needs)
for t in stuck:
is_stuck[t] = True
walk = [stuck[0]]
while True:
t = walk[len(walk) - 1]
nxt = -1
for p in needs[t]:
if nxt == -1 and is_stuck[p]:
nxt = p
for i in range(0, len(walk)):
if walk[i] == nxt:
return walk[i:len(walk)] + [nxt]
walk = walk + [nxt]
def schedule(needs, days, seq):
n = len(needs)
start = [0] * n
finish = [0] * n
for t in seq:
s = 0
for p in needs[t]:
if finish[p] > s:
s = finish[p]
start[t] = s
finish[t] = s + days[t]
total = 0
for t in range(0, n):
if finish[t] > total:
total = finish[t]
latest = [total] * n
i = len(seq) - 1
while i >= 0:
t = seq[i]
for u in range(0, n):
for p in needs[u]:
if p == t and latest[u] - days[u] < latest[t]:
latest[t] = latest[u] - days[u]
i = i - 1
slack = []
for t in range(0, n):
slack = slack + [latest[t] - finish[t]]
return [start, finish, slack, total]
def critical_path(needs, seq, sch):
start = sch[0]
finish = sch[1]
slack = sch[2]
t = -1
for u in seq:
if slack[u] == 0 and finish[u] == sch[3] and t == -1:
t = u
chain = [t]
going = True
while going:
back = -1
for p in needs[t]:
if back == -1 and finish[p] == start[t] and slack[p] == 0:
back = p
if back == -1:
going = False
else:
chain = [back] + chain
t = back
return chain