A programme to find a minimal-sum path in a valued triangle.

In project path, execute sbt run. Of course, you could also use cat << EOF | sbt run instead.

The programme runs in O(n) for n being the total number of nodes. This is **O(h²) for h the height (number of rows) of the triangle. It is the theoretical limit of complexity, for the simple reason that all nodes must be visited.

I am not happy with the data structure I used to represent the triangle. A simplified version of my data type is the following:

sealed trait Triangle
case object Empty extends Triangle
case class Cons(base: NonEmptyVector[Int], peak: Triangle) extends Triangle

The problem with this representation is that it does not reflect the fact that the length of base array is equal to the height of the triangle in a Cons.

Of course, this requirement can be enforced by the likes of Eithers or exceptions (in the actual version, I used Eithers). However, these are runtime solutions, in the sense that if you append NonEmptyVector.of(1, 2, 3) to Empty, your code will still compile, albeit at runtime you have a more or less nice error message.

It would be much nicer to enforce the constraint of base size on compile time. Some functional languages, like Idris, support dependent types, types that are specified by a value. If Scala supported dependant types, there could have been a solution like this:

sealed trait Triangle
case object Triangle[0] extends Triangle
case class Triangle[n + 1](base: FixedLengthVector[n + 1][Int], peak: Triangle[n]) extends Triangle

But of course, Scala is not that advanced!

I did try to do implement some sort of fixed-length list using Shapeless HLists, but then I noticed that I do not have much time and abandoned this. I am still confident that this must be possible, with enough time and more proficiency in Shapeless than I have.

I welcome any suggestions!