<gh_stars>0
#!/usr/bin/env python3

"""problem_067.py

Problem 67: Maximum path sum II

By starting at the top of the triangle below and moving to adjacent numbers on
the row below, the maximum total from top to bottom is 23.

       3
      7 4
     2 4 6
    8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom of the triangle contained in the file
FILE_NAME.

NOTE: This is a much more difficult version of Problem 18. It is not possible
to try every route to solve this problem, as there are 2^99 altogether! If you
could check one trillion (10^12) routes every second it would take over twenty
billion years to check them all. There is an efficient algorithm to solve it. 
"""

__author__ = '<NAME>'

import common.fileio as fio
import problem_018 as p018


# PARAMETERS ##################################################################


FILE_NAME = '../input/067.txt'  # default: '../input/067.txt'


# SOLUTION ####################################################################


def solve() -> int:
    return p018.max_triangle_path(list(fio.ints_from_file(FILE_NAME)))


if __name__ == '__main__':
    print(solve())

#!/usr/bin/env python3

"""problem_067.py

Problem 67: Maximum path sum II

By starting at the top of the triangle below and moving to adjacent numbers on
the row below, the maximum total from top to bottom is 23.

       3
      7 4
     2 4 6
    8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom of the triangle contained in the file
FILE_NAME.

NOTE: This is a much more difficult version of Problem 18. It is not possible
to try every route to solve this problem, as there are 2^99 altogether! If you
could check one trillion (10^12) routes every second it would take over twenty
billion years to check them all. There is an efficient algorithm to solve it. 
"""

__author__ = '<NAME>'

import common.fileio as fio
import problem_018 as p018


# PARAMETERS ##################################################################


FILE_NAME = '../input/067.txt'  # default: '../input/067.txt'


# SOLUTION ####################################################################


def solve() -> int:
    return p018.max_triangle_path(list(fio.ints_from_file(FILE_NAME)))


if __name__ == '__main__':
    print(solve())
#!/usr/bin/env python3 problem_067.py  Problem 67: Maximum path sum II  By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.         3       7 4      2 4 6     8 5 9 3  That is, 3 + 7 + 4 + 9 = 23.  Find the maximum total from top to bottom of the triangle contained in the file FILE_NAME.  NOTE: This is a much more difficult version of Problem 18. It is not possible to try every route to solve this problem, as there are 2^99 altogether! If you could check one trillion (10^12) routes every second it would take over twenty billion years to check them all. There is an efficient algorithm to solve it. # PARAMETERS ################################################################## # default: '../input/067.txt' # SOLUTION ####################################################################