Nicolas Portmann

C#, .NET, Java, InfoSec, Cryptography

Pascal's triangle

2019-02-15 nicolas portmannscala

The challenge

    1
   1 1
  1 2 1
 1 3 3 1
1 4 6 4 1

As part of a recent job interview process, I was asked to submit an implementation of Pascal’s triangle in Scala. Pascal’s triangle is an excellent programming assignment as there is an almost endless amount of possible solutions. It is not particularly hard to solve, but how you solve it tells much about you as a software engineer.

Pascal’s triangle is a pyramid best explained by the following quote. Refer to the illustration above as an example of the first 5 rows of Pascal’s triangle.

Each entry of each subsequent row is constructed by adding the number above and to the left with the number above and to the right, treating blank entries as 0. - Wikipedia.

Priorities

I decided to set the focus in my implementation on:

  • Conciseness
  • Simplicity
  • Turning edge cases into standard cases
  • Core logic as a one-liner

To achieve the above, I accepted to neglect the following aspects:

  • input validation
  • performance
  • pretty printing

The solution

Talk is cheap, so without further ado, my solution:

object Pascal {
  def main(args: Array[String]): Unit = {
    val rows = args(0).toInt

    (1 until rows)
      .scanLeft(Seq(1)) { (acc, _) => calculateRow(acc) }
      .map(x => x.mkString(" "))
      .foreach(println)
  }

  private def calculateRow(previous: Seq[Int]): Seq[Int] =
    (0 +: previous :+ 0).sliding(2).map(l => l.head + l(1)).toSeq
}

The good

I managed to get the core logic (transforming a given row into the next one) into one line: claculateRow. Central to the approach is Scalas sliding function, which allows me to process the previous row using a sliding window of N (N=2 in this case) elements. As per above definition (from Wikipedia), all that is necessary is to add the two elements presented by the sliding window to calculate the next row which is exactly what is done by map(l => l.head + l(1)). There is a caveat, however. Above definition implies a 0 to be added to the first and the last element of the previous row to calculate the first and last element of the current row. Implementing this implicit facet of the definition as (0 +: previous :+ 0) turns the literal edge cases into the standard case presented by all the elements between the first and the last ones.

The bad

Prefixing and suffixing the previous row with a 0 creates intermediate arrays (Seqs) which while helping simplicity surely hurts performance. Directly parsing the argument to the main function toInt is of course not recommended for serious applications. The exact details depends on Scalas internal implementation of scanLeft but least two full rows of the triangle are in memory at any given point in time during execution. There sure are less memory hungry alternative approaches. They are however not that easy to reason about as the one presented above.

The ugly

Joining the calculated rows using mkString(" ") is missing the necessary pre- and suffixes to actually print a triangle. The output generated by above solution is not pretty. You have been warned.

Feel free to leave feedback, comments and questions on reddit