In a Pascal's triangle, a number in a row is created by adding the two numbers directly above it; the first row is contains only 1, and the second row contains 1 and another 1.
This is a Pascal's triangle to its 5th row:
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
The goal is to compute the nth row of the triangle.
Test cases in Scala
Algorithm in Scala
10 lines of Scala (version 2.13), showing how concise Scala can be!
Breaking down the problem to its constituent part, we need to compute the next row from a previous row. Noticing the fact that the next row's items are really a sum of pairs of previous row's items, combined with previous row's items slightly shifted, notice that to go from row [1,2,1], we produce a new row which is [1, 2 + 1, 1 + 2, 1], which is [0 + 1, 1 + 2, 2 + 1, 1 + 0], which is [0, 1, 2, 1] + [ 1, 2, 1, 0 ].
Effectively, we just need to sum the original row with the original row slightly shifted (0 added). (this is © from www.scala-algorithms.com)
Scala concepts & Hints
The 'LazyList' type (previously known as 'Stream' in Scala) is used to describe a potentially infinite list that evaluates only when necessary ('lazily').
Pattern matching in Scala lets you quickly identify what you are looking for in a data, and also extract it.
'zip' allows you to combine two lists pair-wise (meaning turn a pair of lists, into a list of pairs)
It can be used over Arrays, Lists, Views, Iterators and other collections.