pascal_triangle.py

"""
This implementation demonstrates how to generate the elements of a Pascal's triangle.
The element havingva row index of r and column index of c can be derivedvas follows:
triangle[r][c] = triangle[r-1][c-1]+triangle[r-1][c]

A Pascal's triangle is a triangular array containing binomial coefficients.
https://en.wikipedia.org/wiki/Pascal%27s_triangle
"""


defprint_pascal_triangle(num_rows: int) ->None:
"""
 Print Pascal's triangle for different number of rows
 >>> print_pascal_triangle(5)
 1
 1 1
 1 2 1
 1 3 3 1
 1 4 6 4 1
 """
triangle=generate_pascal_triangle(num_rows)
forrow_idxinrange(num_rows):
# Print left spaces
for_inrange(num_rows-row_idx-1):
print(end=" ")
# Print row values
forcol_idxinrange(row_idx+1):
ifcol_idx!=row_idx:
print(triangle[row_idx][col_idx], end=" ")
else:
print(triangle[row_idx][col_idx], end="")
print()


defgenerate_pascal_triangle(num_rows: int) ->list[list[int]]:
"""
 Create Pascal's triangle for different number of rows
 >>> generate_pascal_triangle(0)
 []
 >>> generate_pascal_triangle(1)
 [[1]]
 >>> generate_pascal_triangle(2)
 [[1], [1, 1]]
 >>> generate_pascal_triangle(3)
 [[1], [1, 1], [1, 2, 1]]
 >>> generate_pascal_triangle(4)
 [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1]]
 >>> generate_pascal_triangle(5)
 [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
 >>> generate_pascal_triangle(-5)
 Traceback (most recent call last):
 ...
 ValueError: The input value of 'num_rows' should be greater than or equal to 0
 >>> generate_pascal_triangle(7.89)
 Traceback (most recent call last):
 ...
 TypeError: The input value of 'num_rows' should be 'int'
 """

ifnotisinstance(num_rows, int):
raiseTypeError("The input value of 'num_rows' should be 'int'")

ifnum_rows==0:
return []
elifnum_rows<0:
raiseValueError(
"The input value of 'num_rows' should be greater than or equal to 0"
 )

triangle: list[list[int]] = []
forcurrent_row_idxinrange(num_rows):
current_row=populate_current_row(triangle, current_row_idx)
triangle.append(current_row)
returntriangle


defpopulate_current_row(triangle: list[list[int]], current_row_idx: int) ->list[int]:
"""
 >>> triangle = [[1]]
 >>> populate_current_row(triangle, 1)
 [1, 1]
 """
current_row= [-1] * (current_row_idx+1)
# first and last elements of current row are equal to 1
current_row[0], current_row[-1] =1, 1
forcurrent_col_idxinrange(1, current_row_idx):
calculate_current_element(
triangle, current_row, current_row_idx, current_col_idx
 )
returncurrent_row


defcalculate_current_element(
triangle: list[list[int]],
current_row: list[int],
current_row_idx: int,
current_col_idx: int,
) ->None:
"""
 >>> triangle = [[1], [1, 1]]
 >>> current_row = [1, -1, 1]
 >>> calculate_current_element(triangle, current_row, 2, 1)
 >>> current_row
 [1, 2, 1]
 """
above_to_left_elt=triangle[current_row_idx-1][current_col_idx-1]
above_to_right_elt=triangle[current_row_idx-1][current_col_idx]
current_row[current_col_idx] =above_to_left_elt+above_to_right_elt


defgenerate_pascal_triangle_optimized(num_rows: int) ->list[list[int]]:
"""
 This function returns a matrix representing the corresponding pascal's triangle
 according to the given input of number of rows of Pascal's triangle to be generated.
 It reduces the operations done to generate a row by half
 by eliminating redundant calculations.

 :param num_rows: Integer specifying the number of rows in the Pascal's triangle
 :return: 2-D List (matrix) representing the Pascal's triangle

 Return the Pascal's triangle of given rows
 >>> generate_pascal_triangle_optimized(3)
 [[1], [1, 1], [1, 2, 1]]
 >>> generate_pascal_triangle_optimized(1)
 [[1]]
 >>> generate_pascal_triangle_optimized(0)
 []
 >>> generate_pascal_triangle_optimized(-5)
 Traceback (most recent call last):
 ...
 ValueError: The input value of 'num_rows' should be greater than or equal to 0
 >>> generate_pascal_triangle_optimized(7.89)
 Traceback (most recent call last):
 ...
 TypeError: The input value of 'num_rows' should be 'int'
 """

ifnotisinstance(num_rows, int):
raiseTypeError("The input value of 'num_rows' should be 'int'")

ifnum_rows==0:
return []
elifnum_rows<0:
raiseValueError(
"The input value of 'num_rows' should be greater than or equal to 0"
 )

result: list[list[int]] = [[1]]

forrow_indexinrange(1, num_rows):
temp_row= [0] +result[-1] + [0]
row_length=row_index+1
# Calculate the number of distinct elements in a row
distinct_elements=sum(divmod(row_length, 2))
row_first_half= [
temp_row[i-1] +temp_row[i] foriinrange(1, distinct_elements+1)
 ]
row_second_half=row_first_half[: (row_index+1) //2]
row_second_half.reverse()
row=row_first_half+row_second_half
result.append(row)

returnresult


defbenchmark() ->None:
"""
 Benchmark multiple functions, with three different length int values.
 """
fromcollections.abcimportCallable
fromtimeitimporttimeit

defbenchmark_a_function(func: Callable, value: int) ->None:
call=f"{func.__name__}({value})"
timing=timeit(f"__main__.{call}", setup="import __main__")
# print(f"{call:38} = {func(value)} -- {timing:.4f} seconds")
print(f"{call:38} -- {timing:.4f} seconds")

forvalueinrange(15): # (1, 7, 14):
forfuncin (generate_pascal_triangle, generate_pascal_triangle_optimized):
benchmark_a_function(func, value)
print()


if__name__=="__main__":
importdoctest

doctest.testmod()
benchmark()