# Triangle of numbers maximum path - Greedy algorithm Python

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]
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], final_choices[-1] == index - 1)):
final_choices.append((number, index, next_number))
for item in final_choices:
total += item
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} --> ', 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)

• A greedy algorithm will not always give you the maximum, as it can be “baited” to follow a path which will avoid larger numbers later on. An exhaustive search is $O(2^N)$, so will not work for larger triangles. The “clever” approach is only $O(N^2)$. Since this is Project Euler #18 or #67 (from your deleted question), I’ll leave the discovery of the clever algorithm to you. But as a hint, you only need to look at pairs of rows. Top down 1&2, then 2&3, then 3&4, etc.; or bottom up. Another hint: Space requirement is $O(N)$ if you do not modify the input data. – AJNeufeld Jul 17 at 13:40

## 1 Answer

General suggestions:

1. black can automatically format your code to be more idiomatic.
2. isort can group and sort your imports automatically.
3. flake8 with a strict complexity limit will give you more hints to write idiomatic Python:

[flake8]
max-complexity = 4
ignore = W503,E203


That limit is not absolute by any means, but it's worth thinking hard whether you can keep it low whenever validation fails. For example, I'm working with a team on an application since a year now, and our complexity limit is up to 7 in only one place.

4. I would then recommend adding type hints everywhere (I'm not sure whether they work with Python 2 though) and validating them using a strict mypy configuration:

[mypy]
check_untyped_defs = true
disallow_untyped_defs = true
ignore_missing_imports = true
no_implicit_optional = true
warn_redundant_casts = true
warn_return_any = true
warn_unused_ignores = true


Specific suggestions:

1. Double negatives are really hard to follow. not_str=False is one such instance.
2. Boolean parameters are a code smell. Better to make two methods, optionally calling a third containing the common logic.
3. Naming is really important for maintainability - the only difference between names and comments is that names are actual code, and can trivially be refactored by tools. Names like temp, i, n, one and rws make the code unnecessarily hard to follow.
• Type hints don't work in Python 2, but since the OP uses f-strings in his code, this should not be a concern. – AlexV Jul 17 at 9:10