## A407
## Joan Ginés i Ametllé

from functools import reduce
from collections import deque


# RC(X,f): residual encoding of the numerical list X using the model f
def RC(X,f): return [x-z for x,z in zip(X, [f(k) for k in range(1,len(X)+1)])]

# RD(Y,f): residual decoding of the numerical list Y using the model f
def RD(Y,f): return [y+z for y,z in zip(Y, [f(k) for k in range(1,len(Y)+1)])]

# Test RC + RD
X = [41, 43, 46, 52, 62, 71, 82, 98, 115, 131]
f = lambda x: x**2 - x + 41

Y = RC(X,f); X2 = RD(Y,f)

print('Original list:', X)
print('Residual encoded list:', Y)
print('Residual decoded list:', X2)
if X2 != X: print('ERROR: RC + RD did not work')


'''
n_for is a generator that iterates through a list using a window of size n
Eg. L = [1,2,3,4,5] with window of size n = 3 would generate the sequence: 
[0,0,1], [0,1,2], [1,2,3], [2,3,4], [3,4,5]
'''
def n_for(L,n):
    L = [0]*(n-1) + L
    it = iter(L)
    Q = deque((next(it) for _ in range(n)), maxlen = n)
    yield list(Q)
    for elem in it:
        Q.append(elem)
        yield list(Q)

# PC(X): predictive encoding of the numerical list X
def PC(X): return [x[2]-(x[0]+x[1])/2 for x in n_for(X,3)]

# PD(Y): predictive decoding of the numerical list Y (reduce left to right)
def PD(Y): return reduce(lambda x,y: x + [y + (x[-1]+x[-2])/2], Y, [0,0])[2:]

# Test PC + PD
X = [2.0, 8.1, 12.6, 25.7, 40.0, 51.6, 66.3, 82.7, 95.0]
Y = PC(X); X2 = PD(Y)

print('Original list:', X)
print('Predictive encoded list:', Y)
print('Predictive decoded list:', X2)
if X2 != X: print('ERROR: PC + PD did not work')