Editor

A Tiny Event Loop

#194 · Iterators and generators · Expert · 260 XP · about 60 min

Async frameworks run many tasks on one thread by pausing and resuming them. Generators can pause too, so you can build a small event loop out of them.

Write run_tasks(tasks). tasks is a list of (name, generator) pairs. The loop has a clock that starts at 0 and a ready queue that starts with the tasks in the order given. It repeats these steps, in this order, until every task has finished:

  • First, if the ready queue is empty, move the clock forward to the earliest time a sleeping task wakes up, and put every task waking at that time on the queue, in the order they went to sleep.
  • Then take the task at the front of the queue and resume it with send(value), where value is what it is owed: None the first time, and otherwise what the rules below say.
  • Last, look at what the task did and follow the matching rule below.

The rules for what the task did:

  • It yielded None (a bare yield): it goes to the back of the queue. When resumed, it is sent the clock time.
  • It yielded a positive integer k: it sleeps and wakes at clock + k. When resumed, it is sent the clock time at which it woke.
  • It yielded a generator: it waits for it. That generator becomes a new child task at the back of the queue. When the child finishes, the waiting task goes to the back of the queue and is sent the child's return value.
  • It finished (raised StopIteration): it leaves the loop. For a task from the original list, record (clock, name, return value). A child task is not recorded; it wakes its parent as described above.

Return the list of records in the order the tasks finished.

Examples

def worker(rounds):
    for _ in range(rounds):
        yield
    return rounds

run_tasks([('a', worker(2)), ('b', worker(1))])
# returns [(0, 'b', 1), (0, 'a', 2)]

def alarm(delay, label):
    woke = yield delay
    return label + '@' + str(woke)

run_tasks([('tea', alarm(5, 'tea')), ('toast', alarm(2, 'toast'))])
# returns [(2, 'toast', 'toast@2'), (5, 'tea', 'tea@5')]

def fetch(item, delay):
    yield delay
    return item.upper()

def main():
    x = yield fetch('x', 3)
    y = yield fetch('y', 1)
    return x + y

run_tasks([('main', main())])
# returns [(4, 'main', 'XY')]

In the last example, main waits for the first fetch, which sleeps until time 3 and returns 'X'; then it waits for the second, which sleeps until time 4. The clock only moves when nobody is ready, so turns taken at the same moment cost no time.

Constraints

  • Up to 200 tasks, each yielding up to 1,000 times, and clock times stay below 10^9
  • A task only ever yields None, a positive integer or a generator

Fastest solvers

Leaderboard

First solves only, ranked by stars and then time.