I am trying to write an algorithm in Python to link quantities in a FIFO fashion between two different series (of length N). The input is two lists, ‘instructions’ and ‘responses’.

The two lists represent signed integer values of two time series, the first of which encodes an instruction (e.g. move some distance), while the second represents the actions of the responder to the received instructions. The responder always intends to match the system target (instructions’ cumulative sum), and in general falls short on the first iteration; however over enough steps, the responder eventually catches up. In some cases it may ‘overshoot’ the target, whether that be ‘too positive’, or ‘too negative’.

The goal of the algorithm is to distinguish what quantity of each response belongs to the current instruction, and what quantity belongs to an earlier instruction (and then link this quantity to the original instruction index). The intended output is in an allocation matrix of size (NxN), which describes how the quantities of each response are to be allocated to each instruction. The matrix is naturally lower-triangular (as response quantities cannot be allocated to future instructions).

For example, consider the series:

import pandas as pd
instructions = [100, 50, 20, 0, -50, -100]
responses = [80, 40, 10, 40, -20, -130]
df = pd.DataFrame({'instructions': instructions,
                   'responses': responses})

By plotting the cumulative sums, one can visualise the trajectory of the target and realised positions. The response series catches up with the instructions after step 3 and again after step 5.

In terms of allocation we can see:

• At step 0, all of the 80 should be linked to the instruction, leaving 20 remaining
• At step 1, 20 of the total 40 should be linked to the instruction at step 0 (and the other 20 should be linked to the instruction at step 1)
• At step 2, all of the total 10 should be linked to the instruction at step 1 (which is still unrealised)
• At step 3, 20 of the total 40 should be linked to the instruction at step 1, and the other 20 should be linked to the instruction at step 2. The response series has caught up with the target at this point.
• At step 4, all of the total -20 is allocated to step 4, leaving -30 to go
• At step 5, -30 of the total -130 is allocated to the previous step, and -100 is allocated to step 5, bringing the responder back in line

This is encoded in the allocation matrix like:

I have approached this as below, but this doesn’t capture all the possible edge cases. I am particularly concerned by how to handle:

• If the response overshoots the target
• If the position crosses zero and / or signs are flipped
• If the target moves closer to zero before the response catches up, so there is ‘too much’ to allocate. In this case I believe I need to add dummy quantities to ensure the responder has moved the same total quantity (absolute cumsum?) as the instructor, but unsure where/how to do this.

import numpy as np
def allocate_responses(instructions, responses):
    n = len(instructions)
    allocation_matrix = np.zeros((n,n))
    
    # Loop over the lower-triangular elements of the allocation matrix
    for i in range(n):
        for j in range(i + 1):
            if instructions[j] == 0 or responses[i] == 0:
                continue
            
            # Initialise the allocation amount as the lesser of the instruction or the response
            allocation_amount = min(abs(instructions[j]), abs(responses[i]))
            
            # Assuming the instructor has not turned back on itself before the responder caught up:
            if instructions[j] > 0 and responses[i] > 0:
                allocation_matrix[i][j] += allocation_amount
                instructions[j] -= allocation_amount
                responses[i] -= allocation_amount
            
            # Same but instructions went negative
            elif instructions[j] < 0 and responses[i] < 0:
                allocation_matrix[i][j] -= allocation_amount
                instructions[j] += allocation_amount
                responses[i] += allocation_amount

    return allocation_matrix

Is there a simpler way of storing state (e.g. in a series of NxN matrices) and solving this using matrix operations without a nested loop, that can handle the edge cases? I feel like there must be.