Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
@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()!!
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.