A triangle of numbers path maximized using a greedy algorithm. It's not the most efficient way since I'm a beginner this is the best I could do. I need your feedback on how to make it better in terms of maximizing the total. It works in a way that it chooses the highest value of the adjacent numbers in the next row. No brute forcing(might take forever with big numbers). I also included a lot of functions that do different things(check the docstrings) including making triangle of size n, reading a triangle from a file ... I want your feedback on how to make things better in terms of optimization/style...
from time import time
import random
def make_row(n, not_str=False):
"""Makes a row of size n; not_str = True to return integers.
Returns a list containing row, if not_str = True, a list of strings(numbers) is returned."""
temp = []
for i in range(n):
if not_str:
temp.append((random.randint(10, 99)))
else:
temp.append(str(random.randint(10, 99)))
return temp
def make_triangle(n, not_str=False):
"""Makes a triangle of numbers of size n.
Returns triangle, a list of lists(rows); if not_str = True, a list of strings is returned else: integers."""
triangle = []
for i in range(1, n + 1):
if not_str:
temp = make_row(i, not_str)
triangle.append(temp)
else:
temp = make_row(i)
triangle.append(temp)
return triangle
def save_triangle(n, filename):
"""Assumes filename a string(name of the file) and n size of the triangle to make.
Writes triangle to 'filename'."""
triangle = make_triangle(n)
triangle_file = open(filename, 'a+')
for row in triangle:
row = ' '. join(row)
triangle_file.writelines(row + '\n')
triangle_file.close()
def triangle_to_list(triangle, p=False):
"""Assumes triangle a list or a string and p = True to print triangle.
Returns a list of lists(rows) containing integers."""
# If triangle is not a list(ex: a .txt file or a string, clean from new lines and spaces.
if not isinstance(triangle, list):
rows = triangle.split('\n')
# If p, print the triangle of numbers and the size.
if p:
print(f'Triangle of size {len(rows)}')
print()
for rw in rows:
print(''.join(rw))
# Clean from spaces
while '' in rows:
rows.remove('')
row_nums = [x.split(' ') for x in rows]
all_rows = []
# Convert strings to integers.
for row in row_nums:
temp = []
for num in row:
temp.append(int(num))
all_rows.append(temp)
# Returns a list of integers.
return all_rows
# If triangle is produced using make_triangle, it's a list.
if isinstance(triangle, list):
rows = triangle
# If p, print the triangle of numbers and the size.
if p:
print(f'Triangle of size {len(rows)}')
print()
# Convert from integers to strings to print using .join().
list_of_strings_to_print = []
for row in rows:
temp = []
for number in row:
temp.append(str(number))
list_of_strings_to_print.append(temp)
for row in list_of_strings_to_print:
print(' '.join(row))
print()
# Returns a list of integers.
return rows
def triangle_file_list(filename, p=False):
"""Assumes 'filename' contains a triangle of numbers(strings), p = True to print. Returns a list of lists(rows) containing integers."""
with open(filename, 'r') as tri:
triangle_file = tri.read()
#
if p:
print(triangle_file)
raw_triangle = ''.join(triangle_file)
return triangle_to_list(raw_triangle)
def maximize_path(rows, p=False):
"""Assumes rows is a list of lists containing all rows and p = True to print path.
Returns total of the maximum path.
"""
start = 0
total = 0
# This list contains number, index in the row (to prevent miscalculations in case of row duplicates), next number).
choice_combinations = []
while start < len(rows) - 1:
for index, number in enumerate(rows[start]):
next_max = (max(rows[start + 1][index], rows[start + 1][index + 1]))
if next_max == rows[start + 1][index]:
choice_combinations.append((number, index, next_max))
if next_max == rows[start + 1][index + 1]:
choice_combinations.append((number, index + 1, next_max))
start += 1
final_choices = [choice_combinations[0]]
for number, index, next_number in choice_combinations[1:]:
# Performing 2 checks: check by number and check by index.
if number == final_choices[-1][-1] and any((index == final_choices[-1][1], final_choices[-1][1] == index - 1)):
final_choices.append((number, index, next_number))
for item in final_choices:
total += item[0]
total += final_choices[-1][-1]
# If p, print the maximum path, sum.
if p:
print('Maximum path:')
for item in final_choices:
print(f'{item[0]} --> ', end='')
print(final_choices[-1][-1])
print()
print(f'Maximum sum: {total}')
return total
def test_triangles(n, one=False):
"""Assumes n is the maximum size of the triangles to print, prints n triangles, n paths, n sums, n times.
If one = True, prints only one triangle of size n."""
time_all = time()
if one:
time1 = time()
tr = make_triangle(n, True)
rws = triangle_to_list(tr, True)
maximize_path(rws, True)
print()
print(f'Total time: {time() - time_all} seconds.')
else:
for i in range(2, n + 1):
time1 = time()
tr = make_triangle(i, True)
rws = triangle_to_list(tr, True)
maximize_path(rws, True)
print()
print(f'Time taken: {time() - time1} seconds.')
print()
print(f'Total time: {time() - time_all} seconds')
if __name__ == '__main__':
test_triangles(20, True)
