david.py

# First initialize the array with all positions 0
array_2d = None
calculated_values = None
# save the total number of rows and the total number of columns in global variables
rows_n = 0
columns_n = 0

testing = False

# Now make the function to obtain the values at y_row, and x_column
def obtainValue(y_row, x_column):
	# I assume that the indexes for columns start from 1 and not from 0 because of the example.
	#
	# First check if they are asking for a case value.
	#
	# x_column goes first because it has priority, since it doesn't matter if the row is 0, if you are at the last column you return a 1.
	#
	if calculated_values[y_row][x_column-1]:
		return array_2d[y_row][x_column-1]
	if x_column == (columns_n):
		array_2d[y_row][x_column-1] = 1
		calculated_values[y_row][x_column-1] = True
		return 1
	if y_row == 0:
		array_2d[y_row][x_column-1] = 0
		calculated_values[y_row][x_column-1] = True
		return 0
	# First we checked if this value already exists in our array.
	#
	# If the program reaches this point it means it was not a case value
	# So we need to use recursion.
	#
	# Calculate the values
	top = obtainValue(y_row-1, x_column)
	topRight = obtainValue(y_row-1, x_column+1)
	# I only calculate top left if the column is not equal to one
	topLeft = obtainValue(y_row-1, x_column-1) if (x_column != 1) else 0
	# if we are testing we print recursion values
	result = top + topLeft + topRight
	if testing:
		print 'top: '+str(top)
		print 'topRight: '+str(topRight)
		print 'topLeft: '+str(topLeft)
	# Now set up the array in this position to true
	array_2d[y_row][x_column-1] = result
	calculated_values[y_row][x_column-1] = True
	return result

def calculateInitialArray(columns_n_tmp, rows_n_tmp):
	# Always call this function first.
	rows_n = rows_n_tmp
	columns_n = columns_n_tmp
	array_2d = [  [  0 for a in range(1, columns_n + 1)  ] for b in range (rows_n)  ]
	calculated_values = [  [  False for a in range(1, columns_n + 1)  ] for b in range (rows_n)  ]
	return rows_n, columns_n, array_2d, calculated_values


rows_n, columns_n, array_2d, calculated_values = calculateInitialArray(10, 11)
obtainValue(1, 9)

# now at any point you could print array_2d to see values calcuated

def showArray():
	for n in array_2d:
		print n

showArray()