global HighestSum
global gPath

def IsEven(num):
    return num % 2 == 0

matrix=[[215],
        [192,124],
        [117,269,442],
        [218,836,347,235],
        [320,805,522,417,345],
        [229,601,728,835,133,124],
        [248,202,277,433,207,263,257],
        [359,464,504,528,516,716,871,182],
        [461,441,426,656,863,560,380,171,923],
        [381,348,573,533,448,632,387,176,975,449],
        [223,711,445,645,245,543,931,532,937,541,444],
        [330,131,333,928,376,733,17,778,839,168,197,197],
        [131,171,522,137,217,224,291,413,528,520,227,229,928],
        [223,626,34,683,839,52,627,310,713,999,629,817,410,121],
        [924,622,911,233,325,139,721,218,253,223,107,233,230,124,233]]

def FindHighestSum(RowIndex, ColumnIndex, PreviousEven, CurrentSum, path, direction):

    if(RowIndex >= len(matrix) or ColumnIndex >= len(matrix[RowIndex])):
        return
    else:
        global HighestSum
        global gPath

        CurrentValue = matrix[RowIndex][ColumnIndex]

        path += ColumnIndex*('  ') + (direction) + '\n' + \
            ColumnIndex*('  ') + str(CurrentValue) + '\n'

        if((PreviousEven and IsEven(CurrentValue)) \
            or (not PreviousEven and not IsEven(CurrentValue)) \
            and RowIndex != 0):
            print('Invalid path\n' + path)
            return

        CurrentSum += CurrentValue
        if(CurrentSum > HighestSum):
            HighestSum = CurrentSum
        gPath = path

        FindHighestSum(RowIndex + 1, ColumnIndex,
                        IsEven(CurrentValue), CurrentSum, path, '↓')
        FindHighestSum(RowIndex + 1, ColumnIndex + 1,
                        IsEven(CurrentValue), CurrentSum, path, '↘')


HighestSum = 0
FindHighestSum(0, 0, False, 0, '', '')

print(HighestSum)
print('Best path')
print(gPath)