# leibniz.py

'''
  Challenging Programming in Python
  Habib Izadkhah, Rashid Behzadidoost
  Springer, 2024
  Code 3.17

LeftMost , Positions		Expected output
[1, 2, 3], 3				[3, -1, 0]
[4, 7, 9, 3], 4				[3, 6, -8, 7]
[88, 90, 1, 0, 9], 4		[9, -9, 10, 78]
[20, 95], 2					[95, -75]

'''

'''
  This function takes two arguments:
  a list of values representing
  the leftmost row of a Leibniz triangle
  and positions in the last row of the same triangle
  for which we want values.
'''
def leibniz(leftRow, rowLen):
  results = []
  memo = {}

  '''
    Compute the values in the first column of the
    triangle using the leftmost row.
  '''
  for i in range(len(leftRow)):
    memo[(i, 0)] = leftRow[i]

  '''
    Compute the other values in the triangle
    using the previous row.
  '''
  for i in range(1, len(leftRow)):
    for j in range(1, i+1):
      '''
        Each value in the triangle is
        the difference between the sum
        of the two bottom values
      '''
      value = memo[(i-1, j-1)] - memo[(i, j-1)]
      memo[(i, j)] = value

  '''
    Retrieve the last row of the triangle
    from the memo table
  '''
  for i in range(rowLen):
     results.append (memo[(len(leftRow)-1, i)])
  return results


# ------ main ----------
print( leibniz([88, 90, 1, 0, 9], 4))