Algorithm to calculate next set in sequence

Question

I am looking for an algorithm to calculate the next set of operations in a sequence. Here is the simple definition of the sequence.

1. Task 1A will be done every 500 hours
2. Task 2A will be done every 1000 hours
3. Task 3A will be done every 1500 hours

So at t=500, do 1A. At t=1000, do both 1A and 2A, at t=1500 do 1A and 3A, but not 2A as 1500 is not a multiple of 1000. You get the idea.

It would be quite easy if I had the actual time, but I don't. What I have is the history of tasks (eg last time a [1A+2A] was done).

Knowing last time (eg [1A+2A]) is not enough to decide:

• [1A+2A] could be at t=1000: next is [1A+3A] at t=1500
• [1A+2A] could be at t=5000: next is [1A] at t=5500

Is there an algorithm for this? It looks like a familiar problem (some sort of sieve?) but I can't seem to find a solution.

Also it must "scale" as I actually have more than 3 tasks.

Answer 1

If you have enough history to get the last two times each task was done you could reconstruct the original task sequence definitions. When they coincide is incidental.

Answer 2

The sequence must repeat. For the example given, the sequence would be 1A, 1A+2A, 1A+3A, 1A+2A, 1A, 1A+2A+3A. In this situation, you could see how far back the last 1A+2A+3A is and use that distance as an index into an array. In the general case, for a cycle of length N, you could always do it by testing the last N events against all rotations of the cycle, but I suspect that there will usually be some kind of shortcut available, like how many events back the last "do everything" event happened, or how long ago the last "do everything" event happened.

Answer 3

Seems like a greatest common denominator problem.

Answer 4

Prerequisites:

1. Calculate the LCM of the tasks' time; this is the period of a full cycle.
2. Compute the event timeline for the full cycle.

As each task / group of tasks is started, move an index through the timeline.

Answer 5

Bill the Lizard is right. Here is how to determine the task intervals from the history (in Python):

history = [list of tuples like (timestamp, (A, B, ...)), ordered by timestamp]
lastTaskTime = {}
taskIntervals = {}

for timestamp, tasks in history:
    for task in tasks:
        if task not in lastTaskTime:
            lastTaskTime[task] = timestamp
        else:
            lastTimestamp = lastTaskTime[task]
            interval = abs(timestamp - lastTimestamp)
            if task not in taskIntervals or interval < taskIntervals[task]:
                taskIntervals[task] = interval  # Found a shorter interval

            # Always remember the last timestamp
            lastTaskTime[task] = timestamp

# taskIntervals contains the shortest time intervals of each tasks executed at least twice in the past
# lastTaskTime contains the last time each task was executed

To get the set of tasks, which will be executed next:

nextTime = None
nextTasks = []

for task in lastTaskTime:
    lastTime = lastTaskTime[task]
    interval = taskIntervals[task]

    if not nextTime or lastTime + interval < nextTime:
        nextTime = lastTime + interval
        nextTasks = [task]
    elif lastTime + interval == nextTime:
        nextTasks.append(task)

# nextTime contains the time when the next set of tasks will be executed
# nextTasks contains the set of tasks to be executed

Answer 6

This is FizzBuzz in disguise.

Instead of the usual mapping of 3 to "Fizz" and 5 to "Buzz", we have the mappings of 500 to Task 1A, 1000 to Task 2A and 3 to Task 3A and so on.

An exhaustive list of solutions (or near-misses :) ) can be found here: What is your solution to the FizzBuzz problem?