0
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – AJNeufeld Jul 17 at 13:40
2
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ Type hints don't work in Python 2, but since the OP uses f-strings in his code, this should not be a concern. \$\endgroup\$ – AlexV Jul 17 at 9:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.