@file:Suppress("FunctionName")

package com.lagostout.bytebybyte.dynamicprogramming

import kotlin.math.absoluteValue
import kotlin.math.sign

object MatrixPath {

    fun computeWithRecursionAndBruteForce(
            matrix: List<List<Int>>): Int {
        return if (matrix.isEmpty() || matrix.first().isEmpty()) 0
        else _computeWithRecursionAndBruteForce(matrix)
    }

    // Pair is (row, column)
    private fun _computeWithRecursionAndBruteForce(
            matrix: List<List<Int>>,
            origin: Pair<Int, Int> = Pair(0,0),
            sign: Int = 1): Int {
        val lastRow = matrix.lastIndex
        val lastColumn = matrix.last().lastIndex
        return if (origin == Pair(lastRow, lastColumn))
            matrix[origin.first][origin.second] * sign
        else {
            listOf(origin.copy(first = origin.first + 1),
                origin.copy(second = origin.second + 1)).filter {
                it.first <= lastRow && it.second <= lastColumn
            }.map {
                (matrix[origin.first][origin.second]).let { value ->
                    _computeWithRecursionAndBruteForce(
                        matrix, it, sign * value.sign) *
                            value.absoluteValue
                }
            }.max()!!
        }
    }

}