In an infinite array with two rows, the numbers in the top row are denoted

`. . . , A[−2], A[−1], A[0], A[1], A[2], . . .`

and the numbers in the bottom row are denoted

`. . . , B[−2], B[−1], B[0], B[1], B[2], . . .`

For each integer `k`, the entry `A[k]` is directly above
the entry `B[k]` in the array, as shown:


...|A[-2]|A[-1]|A[0]|A[1]|A[2]|...
...|B[-2]|B[-1]|B[0]|B[1]|B[2]|...



For each integer `k`, `A[k]` is the average of the entry to its left, the entry to its right,
and the entry below it; similarly, each entry `B[k]` is the average of the entry to its
left, the entry to its right, and the entry above it.


Given `A[0], A[1], A[2] and A[3]`, determine the value of `A[n]`. (Where range of n is -1000 Inputs and Outputs in BigInt!** 

Adapted from 2018 Euclid Mathematics Contest.
https://www.cemc.uwaterloo.ca/contests/past_contests/2018/2018EuclidContest.pdf

Difficulty: introductory

Starter code:

def find_a(array, n):
	

Solutions:
def find_a(lst,n):
    if n<0: return find_a(lst[::-1], 3-n)
    if n<4: return lst[n]
    a,b,c,d = lst
    for _ in range(n-3):
        a,b,c,d = b, c, d, 6*d-10*c+6*b-a
    return d

def find_a(A, n):
    if 0 <= n < 4: return A[n]
    if n < 0:
        A, n = A[::-1], abs(n) + 3
    B = [0] * 4
    B[1] = 3 * A[1] - A[0] - A[2]
    B[2] = 3 * A[2] - A[1] - A[3]
    B[3] = 3 * B[2] - B[1] - A[2]
    ind = 4
    while ind <= n:
        a = 3 * A[-1] - A[-2] - B[-1]
        b = 3 * B[-1] - B[-2] - A[-1]
        A.append(a)
        B.append(b)
        ind += 1
    return A[-1]

def find_a(array, n):
    if n > 3:
        for i in range(4,n+1):
            array.append(6*array[i-1]+6*array[i-3]-10*array[i-2]-array[i-4])
        return array[-1]
    elif n < 0:
        array = array[::-1]
        for i in range(4,4-n):
            array.append(6*array[i-1]+6*array[i-3]-10*array[i-2]-array[i-4])
        return array[-1]
    else:
        return array[n]

def find_a(array, n):
    if 0 <= n < 4:
        return array[n]
    b1 = 3*array[1] - array[0] - array[2]
    b2 = 3*array[2] - array[1] - array[3]
    b3 = 3*b2 - b1 - array[2]
    b0 = 3*b1 - b2 - array[1]    
    array_b = [b0,b1,b2,b3]
    
    if n > 3:
        count = 3  
    else:
        array.reverse()
        array_b.reverse()
        count = 0
        n = 0 - n 
    while count < n:
        a_next = 3*array[-1] - array[-2] - array_b[-1]
        b_next = 3*array_b[-1] - array_b[-2] - array[-1]
        array.append(a_next)
        array_b.append(b_next)
        count += 1
    
    return array[-1]


def find_a(array, n):
    if n in [0,1,2,3]:
        return array[n]
    b1 = 3*array[1] - array[0] - array[2]
    b2 = 3*array[2] - array[1] - array[3]
    if n > 3:
        ak = array[3]
        bk = 3*b2 - b1 - array[2]
        ap = array[2]
        bp = b2
        i = 3
        while i < n:
            ak, ap = 3 * ak - bk - ap, ak
            bk, bp = 3 * bk - ap - bp, bk
            i += 1
        return ak
    else:
        ak = array[0]
        bk = 3 * b1 - b2 - array[1]
        ap = array[1]
        bp = b1
        i = 0
        while i > n:
            ak, ap = 3 * ak - bk - ap, ak
            bk, bp = 3 * bk - ap - bp, bk
            i -= 1
        return ak

def find_a(array, n):
    if n in range(4): return array[n]
    if n < 0: return find_a([*reversed(array)], 3 - n)
    a1 = array[1]
    a2 = array[2]
    b1 = 3 * array[1] - array[0] - array[2]
    b2 = 3 * array[2] - array[1] - array[3]
    for _ in range(n - 2):
        a1, b1, a2, b2 = a2, b2, 3 * a2 - a1 - b2, 3 * b2 - b1 - a2
    return a2

def find_a(array, n):
    if n >= 0:
        if n < 4:
            return array[n]
        else:
            A = array[:]
            B = [0, 0, 0, 0]
            B[1] = 3 * A[1] - A[0] - A[2]
            B[2] = 3 * A[2] - A[1] - A[3]
            B[0] = 3 * B[1] - B[2] - A[1]
            B[3] = 3 * B[2] - B[1] - A[2]
            for i in range(n - 3):
                A.append("undefined")
                B.append("undefined")
            for i in range(4, len(A)):
                A[i] = 3 * A[i - 1] - A[i - 2] - B[i - 1]
                B[i] = 3 * B[i - 1] - B[i - 2] - A[i - 1]
            return A[-1]
    else:
        A = array[:]
        B = [0, 0, 0, 0]
        B[1] = 3 * A[1] - A[0] - A[2]
        B[2] = 3 * A[2] - A[1] - A[3]
        B[0] = 3 * B[1] - B[2] - A[1]
        B[3] = 3 * B[2] - B[1] - A[2]
        for i in range(-n):
            A = ["undefined"] + A
            B = ["undefined"] + B
        for i in range(-n-1, -1, -1):
            A[i] = 3 * A[i + 1] - A[i + 2] - B[i + 1]
            B[i] = 3 * B[i + 1] - B[i + 2] - A[i + 1]
        return A[0]

def find_a(array, n):
    if 0<=n<4:
        return array[n]
    a = {i:x for i,x in enumerate(array)}
    if n>4:
        for i in range(4,n+1):
            a[i] = -a[i-4]+6*a[i-3]-10*a[i-2]+6*a[i-1]
    else:
        for i in range(-1,n-1,-1):
            a[i] = 6*a[i+1]-10*a[i+2]+6*a[i+3]-a[i+4]
    return a[i]


def find_a(a, n):
    if 0 <= n < len(a):
        return a[n]

    if n < 0:
        n = 3 - n
        a = a[::-1]

    b = [None] * 4
    b[1] = 3*a[1] - a[0] - a[2]
    b[2] = 3*a[2] - a[1] - a[3]
    b[0] = 3*b[1] - a[1] - b[2]
    b[3] = 3*b[2] - b[1] - a[2]
    for _ in range(n-3):
        x = 3*a[-1] - b[-1] - a[-2]
        y = 3*b[-1] - a[-1] - b[-2]
        a.append(x)
        b.append(y)
    return a[-1]

def find_a(array, n):
    if 0 <= n <= 3: return array[n]
    a0 = array[0]
    a1 = array[1]
    a2 = array[2]
    a3 = array[3]
    b1 = 3*a1 - a0 - a2
    b2 = 3*a2 - a1 - a3
    b3 = 3*b2 - b1 - a2
    b0 = 3*b1 - b2 - a1
    if n > 3:
        for k in range(4, n+1, 1):
            an = 3*a3 - a2 - b3
            bn = 3*b3 - b2 - a3
            
            a2, a3 = a3, an
            b2, b3 = b3, bn
            
    else: 
        for k in range(-1, n-1, -1):
            an = 3*a0 - a1 - b0
            bn = 3*b0 - b1 - a0
            
            a0, a1 = an, a0
            b0, b1 = bn, b0
    
    return an