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)
  }
}


Design Patterns - The Cult to Blame ?

I always thought GOF Design Patterns book achieved it's objective to make us better C++/Java programmers. It taught us how to design polymorphic class hierarchies alongside encouraging delegation over inheritance. In an object oriented language like Java or C++, which does not offer first class higher order functions or closures, the GOF patterns taught us how to implement patterns like Command, Strategy and State through properly encapsulated class structures that would decouple the theme from the context. As long as we do not link them with the pattern definition and theory as espoused by Christopher Alexander, the GOF book has an invaluable contribution towards today's mainstream OO community.

But that's only the good part. I was wondering what made many people cringe at the patterns movement that seem to deluge the programming community for well over a decade.

One of the drawbacks that the pattern movement in the programming community suffered from, was that, the design patterns as promoted by the GOF book, focused too much on the implementation aspects, the how part of the solution, instead of the what part of problem that they solve. This resulted in the implementation language being the main focus of the entire pattern. People started thinking that C++ is the language of choice since all of the GOF design patterns can be implemented faithfully using the honored constructs of the language. And, of course, in due time, Java, positioned as a better C++, also inherited the same honor. It may not be totally coincidental that during the time we were busy adulating the virtues of GOF design patterns in Java and C++, development of newer programming languages were at a very low ebb.

Developers started thinking that Java and C++ are the be-all and end-all of programming language implementations, since we can implement all GOF patterns in them. Enterprise software loves to follow common practices, rote techniques that can be easily replicated through a set of replacable programmers, and the combination of Java and design patterns made a perfect match. Switching languages was difficult, and even for some mainstream programmers today, switching to more powerful languages like Ruby or Scala, the initial thought processes were limited to the abstraction levels of Java. In reality, the patterns movement created a cult and made us somewhat myopic towards implementing higher order abstractions even in any other more powerful programming language.

Mark Jason Dominus reiterated this way back in 2006 ..

"If the Design Patterns movement had been popular in the 1980's, we wouldn't even have C++ or Java; we would still be implementing Object Oriented Classes in C with structs, and the argument would go that since programmers were forced to use C anyway, we should at least help them as much as possible."

Are Design Patterns useless ?

Absolutely not. Patterns are solutions to problems in context. As long as the problems remain, patterns remain equally relevant. What we need to do is highlight on the intent of the pattern, the problem that it solves, the forces that it resolves and the resultant forces that it generates, instead of just documenting how it solves it in one particular language.

As an example, the Strategy pattern is intended to decouple the implementation of an algorithm from the context of the application. In case of Java, it is implemented through the context class delegating the responsibility to the strategy interface, that can have multiple implementations. Looks and sounds ceremonious, but that is what it is, if you use Java as the implementation language. In languages that support higher order functions, the same pattern is implemented much more succinctly using native language features. Hence the implementation is subsumed into the natural idioms of the language itself. Again, if we highlight on the intent of the pattern, it remains *equally relevant*, irrespective of whether we use Ruby, Groovy, Scala or Lisp for implementation. And the intent is loud and clear - the implementation of the algorithm is a separate concern than the concrete context to which it is being plugged into.

Similarly, the Visitor pattern has often been maligned as an overtly complex structure that should be avoided at any cost. Visitor looks complex in Java or C++, because these languages do not support higher order abstractions like pattern matching or multiple dispatch mechanisms. Languages like Scala that support pattern matching have been known to implement succinct visitors without much ceremony. This paper, presented in OOPSLA 2008, implements the Visitor pattern as a reusable generic type-safe component using the powerful typesystem of Scala.

Irrespective of how you implement, Visitor remains a potent solution to the problem of separating the structure of abstraction hierarchies from the behavior of traversals over that hierarchy. The important part is to add the intent of Visitors to your design vocabulary - it is just the level of abstractions that the language offers that makes the implementation invisible, informal or formal.

Many people also talk about Singleton implementation in Java as being too elaborate, complex and unnecessarily verbose. On the other hand, singleton is available as a library call in Ruby and as a single word language syntax in Scala. That does not make Singleton a simpleton, it is just that Java does not offer a sufficiently higher level of abstraction to express the intent and solution of the pattern. Go, use dependency injection frameworks, they offer Singletons as configurable behaviors ready-to-be-wired with your native objects.

Patterns as a vehicle of communication

.. and not as code snippets that can be copy pasted. The real intrinsic value of design patterns is that they facilitate communication in processes by encouraging a common vocabulary and format that binds the design space. Coplien mentions in his monograph on Software Patterns ..

"Besides, we believe that human communication is the bottleneck in software development. If the pattern literary form can help programmers communicate with their clients, their customers, and with each other, they help fill a crucial need of contemporary software development.

Patterns are not a complete design method; they capture important practices of existing methods and practices uncodified by conventional methods. They are not a CASE tool. They focus more on the human activities of design than on transformations that can blindly be automated. They are not artificial intelligence; they celebrate and encourage the human intelligence that separates people from computers."

People, mostly from the dynamic language community, frown upon design patterns as being too ceremonious, claiming that most of them can be implemented in dynamically typed and functional languages much more easily. Very true, but that does not undermine the core value proposition of design patterns. Maybe most of us became converts to a cult that focused too much on the implementation details of the patterns in a specific family of languages. Ideally we should have been more careful towards documenting beautiful patterns and pattern languages as the core vocabulary of designers.

Some people on the Erlang mailing list recently talked about OTP being the embodiment of Erlang design patterns. OTP is clearly a framework, that helps develop highly concurrent client server applications in Erlang. Patrick Logan correctly points out that OTP is a collection of patterns, only in a very poor sense of the term. The real collection would be a pattern language that documents the problems, identifies the forces at play and suggests solutions through a catalog of literary forms that will help develop concurrent server applications from ground up. In case of Erlang, gen_server, gen_event, gen_fsm etc. collaborate towards implementing the pattern language. Similar efforts have been known to exist for Scala as well. Implementing the same in any other language may be difficult, but that will only point to the deficiencies of that particular language towards implementing a concrete instance of that pattern language.