Euler Problem #18 and #67 using functional Scala

Project Euler is one of the forms of exercising one's programming instincts. Last weekend, I happened to come across Problem 18 and 67, the latter being a variant of the former in the sense that a brute force algorithm may work for Problem 18, but it will never work for 67. Another interesting point regarding this pair of problems is that it has a certain aura of graph theory that will tempt you towards trying out the solution.

To make things short, both problems relate to finding the maximum sum over a triangle of numbers by moving from one row of number to the next *only* via adjacent cells. For the example triangle, cited in the problem definition page ..

3
7 5
2 4 6
8 5 9 3

The adjacency definition is mapped as follows ..

adjacent(3) => 7, 5
adjacent(7) => 2, 4
adjacent(5) => 4, 6
adjacent(2) => 8, 5
adjacent(4) => 5, 9
adjacent(6) => 9, 3

From the above, we can generalize the adjacency function as ..

adjacent(element(row(r), position(i))) =
element(row(r+1), position(i)), element(row(r+1), position(i+1))

The following is the implementation in Scala. It uses functional techniques like pattern matching to capture the essence of the problem and closes over the solution quite succinctly. Compared to an imperative implementation, the structure of the solution is quite apparent in the implementation itself. The solution has an O(lg n) complexity and Problem 67 completes in 1 millisecond on my Windows XP laptop running Scala 2.7.2 RC3.

In the following implementation, the function meld is not tail recursive. Making it tail recursive is quite trivial though. I decided to keep it the way it is, since it does not affect the structure of the solution. And often in garbage collected environments, non-tail recursive versions can perform better than their tail recursive version.

object Euler {

  // for Problem 18
  val triangle =
    List(List(75),
         List(95, 64),
         List(17, 47, 82),
         List(18, 35, 87, 10),
         List(20, 04, 82, 47, 65),
         List(19, 01, 23, 75, 03, 34),
         List(88, 02, 77, 73, 07, 63, 67),
         List(99, 65, 04, 28, 06, 16, 70, 92),
         List(41, 41, 26, 56, 83, 40, 80, 70, 33),
         List(41, 48, 72, 33, 47, 32, 37, 16, 94, 29),
         List(53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14),
         List(70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57),
         List(91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48),
         List(63, 66, 04, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31),
         List(04, 62, 98, 27, 23,  9, 70, 98, 73, 93, 38, 53, 60, 04, 23))

  /**
   * Takes 2 lists, where bl.size is 1 greater than sl.size. It will process pairs of rows
   * from the triangle in the reverse order, that will satisfy the size constraint, since
   * Row i contains 1 less element than Row (i+1).
   *
   * Hence, if row(i) contains k elements, row(i+1) will contain (k+1) elements.
   * A meld(row(i+1), row(i)) will produce a new row(i)(call nrow(i)) with
   * k elements and nrow(i, j) = row(i, j) + max(row(i+1, j), row(i+1, j+1)).
   *
   * In summary, meld merges the two rows and increments every element in the smaller row
   * with the algebraic value of the bigger of its two adjacent elements.
   */
  def meld(bl: List[Int], sl: List[Int]): List[Int] = ((bl, sl): @unchecked) match {
    case (bf :: bs :: brest, sf :: srest) =>
      sf + Math.max(bf, bs) :: meld(bs :: brest, srest)
    case (bf :: brest, s) if (brest.size == 1 && s.size == 1) =>
      List(s.head + Math.max(bf, brest.head))
    case (b, Nil) =>
      Nil
  }

  /**
   * Iterates recursively over the triangle and melds all rows to reduce to the maximum sum.
   */
  def reduce(trng: List[List[Int]]): List[List[Int]] = (trng: @unchecked) match {
    case f :: s :: tail =>
      reduce(meld(f, s) :: tail)
    case f :: Nil => List(f)
  }

  def main(args: Array[String]) {
    /**
     * file processing for Problem #67
     */
    import scala.io.Source
    val strng: List[List[Int]] =
      Source.fromFile("triangle.txt")
            .getLines.toList
            .map(_.split(" ")
                  .elements
                  .toList
                  .map(_.stripLineEnd.toInt))

    println(reduce(triangle.reverse).head.head)
    println(reduce(strng.reverse).head.head)
  }
}