FilesExpand file tree

master

/

pascal_triangle.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

189 lines (161 loc) · 6.04 KB

master

/

pascal_triangle.py

Copy path

Top

File metadata and controls

• Code
• Blame

189 lines (161 loc) · 6.04 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

"""

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

"""

def print_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)

for row_idx in range(num_rows):

# Print left spaces

for _ in range(num_rows - row_idx - 1):

print(end=" ")

# Print row values

for col_idx in range(row_idx + 1):

if col_idx != row_idx:

print(triangle[row_idx][col_idx], end=" ")

else:

print(triangle[row_idx][col_idx], end="")

print()

def generate_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'

"""

if not isinstance(num_rows, int):

raise TypeError("The input value of 'num_rows' should be 'int'")

if num_rows == 0:

return []

elif num_rows < 0:

raise ValueError(

"The input value of 'num_rows' should be greater than or equal to 0"

)

triangle: list[list[int]] = []

for current_row_idx in range(num_rows):

current_row = populate_current_row(triangle, current_row_idx)

triangle.append(current_row)

return triangle

def populate_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

for current_col_idx in range(1, current_row_idx):

calculate_current_element(

triangle, current_row, current_row_idx, current_col_idx

)

return current_row

def calculate_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

def generate_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'

"""

if not isinstance(num_rows, int):

raise TypeError("The input value of 'num_rows' should be 'int'")

if num_rows == 0:

return []

elif num_rows < 0:

raise ValueError(

"The input value of 'num_rows' should be greater than or equal to 0"

)

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

for row_index in range(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] for i in range(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)

return result

def benchmark() -> None:

"""

Benchmark multiple functions, with three different length int values.

"""

from collections.abc import Callable

from timeit import timeit

def benchmark_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")

for value in range(15): # (1, 7, 14):

for func in (generate_pascal_triangle, generate_pascal_triangle_optimized):

benchmark_a_function(func, value)

print()

if __name__ == "__main__":

import doctest

doctest.testmod()

benchmark()