6
\$\begingroup\$

I am very new to Scala. I have done an exercise using Scala to solve the maximum path problem.

Basically, I have a triangle of integers, I want to find the path from the top to bottom which the numbers on the route produces the largest sum. For example:

       5
    12    3
  2    4     9  
1    9    12    7

Should return:

5 -> 12 -> 4 -> 12
Sum = 33

Could someone please help review the code and make some suggestions about:

  1. Better algorithm
  2. Writing better scala code

Here is the code:

import scala._

class MaxPath {
  def sumTree(input : List[List[Int]], tempResult : List[List[Int]], currentlevel : Int) : List[List[Int]] = {
    if(currentlevel == input.size) return tempResult

    val updatedRow : List[Int] = currentlevel match {
      case 0 => input(currentlevel)
      case _ => {
        val lastRow = tempResult(currentlevel - 1)
        val currentRow = input(currentlevel)

        val newHead = currentRow.head + lastRow.head
        val newLast = currentRow.last + lastRow.last
        val middleSection = currentRow.drop(1).dropRight(1)

        val newMiddle : List[Int] = for {
          (value, index) <- middleSection.zipWithIndex
          middle = value + Math.max(lastRow(index), lastRow(index + 1))
        } yield middle

        newHead::newMiddle:::List(newLast)
      }
    }

    sumTree(input, tempResult:::List(updatedRow), currentlevel + 1)
  }

  def traceBack(input : List[List[Int]], transformed : List[List[Int]], index : Int, currentLevel : Int) : List[Int] = {
    if(currentLevel == input.size) return Nil

    val row = input(currentLevel)
    val rowTransformed = transformed(currentLevel)
    val max = index match {
      case -1 => {
        val maxIndex = rowTransformed.zipWithIndex.maxBy(_._1)._2
        (row(maxIndex), maxIndex)
      }
      case x  => {
        val rowSize = row.size
        x match {
          case 0 => (row.head, 0)
          case `rowSize` => (row.last, 0)
          case _ => {
            val maxIndex = List(rowTransformed(index-1), rowTransformed(index)).zip(List(index - 1, index)).maxBy(_._1)._2
            (row(maxIndex), maxIndex)
          }
        }
      }
    }

    traceBack(input, transformed, max._2, currentLevel + 1) ::: List(max._1)
  }

  def calcualte(input : List[List[Int]]) : (List[Int], Int) = {
    val transformed = sumTree(input, Nil, 0)
    val path = traceBack(input.reverse, transformed.reverse, -1, 0)
    (path, path.sum)
  }
}

object MaxPath {
  val input : List[List[Int]] = List(
    List(5),
    List(12, 3),
    List(2, 4, 9),
    List(1, 9, 12, 7)
  )

  def main(args : Array[String]) = {
    val mp = new MaxPath
    val result = mp.calcualte(input)

    println(result._1.mkString(" -> "))
    println("Sum = " + result._2)
  }
}
\$\endgroup\$
  • \$\begingroup\$ I also used a similar approach to the one above, but added dynamic programming to speed up the algorithm so that you can use it to solve Problem 67 where the data set is pretty large. I have a video where I live code and explain the solution. You can see the final solution on github. \$\endgroup\$ – shadaj Sep 7 '13 at 6:57
2
\$\begingroup\$

In terms of algorithm, I think it is best to focus on the answer you are after. In This case you want the sum, but I notice your result returns the path and the sum.

If you want to focus on the sum think about starting from the bottom, and accessing the best path in terms of the bottom two rows and merging the results up.

Here is an example:

5
12, 3
2, 4, 9
1, 9, 12, 7

merge last 2 lines (lines 3 and 4)

2 + 9, 4 + 12, 9 + 12

merge the next line (line 2 and the merged result of 3 and 4)

12 + (4 + 12), 3 + (9 + 12)

merge the fist line (line 1 and the merged result of the 2, 3, and 4)

5 + (12 + (4 + 12))

some specific observations about your code

  • If you are going to access an element by index, use an indexed collection like Vector
  • Consider using fold or reduce instead of recursion with an accumulator
  • Props for using immutable variables and data structures

here is a link to my solution to the problem: https://gist.github.com/dholbrook/6244448#file-euler18-scala

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.