Need a unique gift idea?
A Pastebin account makes a great Christmas gift
SHARE
TWEET

Untitled

a guest Mar 13th, 2018 57 Never
Upgrade to PRO!
ENDING IN00days00hours00mins00secs
 
  1. @file:Suppress("FunctionName")
  2.  
  3. package com.lagostout.bytebybyte.dynamicprogramming
  4.  
  5. import kotlin.math.absoluteValue
  6. import kotlin.math.sign
  7.  
  8. object MatrixPath {
  9.  
  10.     fun computeWithRecursionAndBruteForce(
  11.             matrix: List<List<Int>>): Int {
  12.         return if (matrix.isEmpty() || matrix.first().isEmpty()) 0
  13.         else _computeWithRecursionAndBruteForce(matrix)
  14.     }
  15.  
  16.     // Pair is (row, column)
  17.     private fun _computeWithRecursionAndBruteForce(
  18.             matrix: List<List<Int>>,
  19.             origin: Pair<Int, Int> = Pair(0,0),
  20.             sign: Int = 1): Int {
  21.         val lastRow = matrix.lastIndex
  22.         val lastColumn = matrix.last().lastIndex
  23.         return if (origin == Pair(lastRow, lastColumn))
  24.             matrix[origin.first][origin.second] * sign
  25.         else {
  26.             listOf(origin.copy(first = origin.first + 1),
  27.                 origin.copy(second = origin.second + 1)).filter {
  28.                 it.first <= lastRow && it.second <= lastColumn
  29.             }.map {
  30.                 (matrix[origin.first][origin.second]).let { value ->
  31.                     _computeWithRecursionAndBruteForce(
  32.                         matrix, it, sign * value.sign) *
  33.                             value.absoluteValue
  34.                 }
  35.             }.max()!!
  36.         }
  37.     }
  38.    
  39. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top