mirage maintenance

approach

deltas yields the sequence, then its differences, then the differences of those, until a row is all zeros.

part 1 extrapolates to the right: going back up the stack, each row gets a new last element equal to its own last element plus the one just added below. part 2 does the same on the left with deques, prepending the first element minus the one below.

the trick

build the difference rows, then walk back up adding one value per row.

def extrapolate_right(history):
    s = list(deltas(history))
    while len(s) > 1:
        last = s.pop()
        s[-1].append(s[-1][-1] + last[-1])
    return s.pop()[-1]

def extrapolate_left(history):
    s = [deque(ss) for ss in deltas(history)]
    while len(s) > 1:
        last = s.pop()
        s[-1].appendleft(s[-1][0] - last[0])
    return s.pop()[0]