#!/usr/bin/python2

"""
Statement:



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 in triangle.txt (right click and
'Save Link/Target As...'), a 15K text file containing a triangle with
one-hundred rows.

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 299 altogether!
If you could check one trillion (1012) routes every second it would take over
twenty billion years to check them all. There is an efficient algorithm to
solve it. ;o)
"""


from unittest import TestCase, main
from copy import deepcopy


class Problem67(object):
    def __init__(self, instr):
        self._matrix = instr
        self._solution = deepcopy(instr)

    def fn(self):
        max_sum = 0
        for i in xrange(len(self._matrix) - 1):
            for j in xrange(i + 1):
                self._solution[i + 1][j] = (self._solution[i][j]
                                            + self._matrix[i + 1][j]
                                            if self._solution[i][j]
                                            + self._matrix[i + 1][j]
                                            > self._solution[i + 1][j]
                                            else self._solution[i + 1][j])
                self._solution[i + 1][j + 1] = (self._solution[i][j]
                                                + self._matrix[i + 1][j + 1]
                                                if self._solution[i][j]
                                                + self._matrix[i + 1][j + 1]
                                                > self._solution[i + 1][j + 1]
                                                else self._solution[i + 1][j + 1])
                tmp = (self._solution[i + 1][j] if self._solution[i + 1][j]
                       > self._solution[i + 1][j + 1]
                       else self._solution[i + 1][j + 1])
                max_sum = (tmp if tmp > max_sum else max_sum)
        return max_sum


class TestProblem67(TestCase):
    @classmethod
    def get_matrix(cls):
        instr = []
        with open("/home/sanket/sanket/selfStudy/Project Euler/project-euler/"
                  "67_triangle.txt", 'r') as f:
            for line in f:
                instr.append([int(i) for i in line.split(' ')])
        return instr

    def setUp(self):
        self.instr = TestProblem67.get_matrix()
        self.answer = 7273

    def test_fn(self):
        self.assertEqual(Problem67(self.instr).fn(), self.answer)


if __name__ == '__main__':
    main()
