<img height="1" width="1" src="https://www.facebook.com/tr?id=1076094119157733&amp;ev=PageView &amp;noscript=1">

Solving Dynamic Programming problems using Functional Programming (Part 3)

Posted by Miguel Vilá on Thu, Oct 12, 2017

In the previous post we saw a way to functionally solve the knapsack problem. Can we do the same when the dependencies between solutions have another shape?

For instance in this project Euler problem the solutions depend on each other differently. Once again, let’s start with a problem definition that allows us to break the problem into subproblems:

dp-fp-sum-rt.png

Let’s consider some position dp-fp-i-j.gif. To get to that position we only have two possibilities: we either get to that position by coming from the upper row and going down from there or we come from the previous column and go right from there. These two possibilities are mutually exclusive thus we can compute the minimum between them to compute the optimal solution for dp-fp-i-j.gif:

dp-dp-sln.png

Here dp-fp-v-i-j.gif  is the value stored at row i  and column j.

And, once again, let's draw a diagram showing the dependencies:

dp-fp-dep-2.png

There is an important difference with respect to the base cases here. The minimal path for each value in the first row is simply the path that starts at dp-fp-0-0.gif and goes right from there (this is the formula dp-fp-r-i-j.gif, which is the accumulative row sum). Similarly, the minimal path for each value in the first column is the part that starts at and goes down from there (this is the formula dp-fp-c-i-j.gif, which is the accumulative column sum).

Now, unlike the 0/1 knapsack problem, the solution for dp-fp-i-j.gif not only depends on a value at the previous row. It also depends on the previous value in the same row.

Let's start with the base cases: how to compute the accumulative sum of an array of numbers? fold can be used to combine all the values using a reducer function. But the intermediate results of that function aren't kept, which is what we want: we don't want to have the total sum. We want to get the accumulative sum. scan does this. It has the same parameters as fold but instead of returning just one value it's going to return a vector of all the intermediate values:

def accumulativeSum(nums: Vector[Int]): Vector[Int] =
    nums.scanLeft(0)(_ + _).drop(1)

The drop(1) is so we don't include the entry with 0 at the beginning.

So the first row and the first column can be computed like this:

def minPath(values: Vector[Vector[Int]]): Int = {
    val m = values.length
    val n = values(0).length
    val firstRow = accumulativeSum(values(0))
    val firstColumn = accumulativeSum( (0 to m-1).map(values(_)(0)) )
    ???
}

Let’s use the same strategy as before. We’ll compute every new row from the bottom up, starting with the first row as the initial state:

def minPath(values: Vector[Vector[Int]]): Int = {
    val m = values.length
    val n = values(0).length
    val firstRow = accumulativeSum(values(0))
    val firstColumn = accumulativeSum( (0 to m-1).map(values(_)(0)) )
    (1 to m-1).foldLeft(firstRow) { (upperRow, i) =>
        ??? // How to compute the new row?
    }.last
}

Now to compute say dp-fp-M-i-1.gif we'll need to use two things: dp-fp-M-im1-1.gif which is in the upper row and dp-fp-M-i-0.gif  which is a value in the very first column, at the left of dp-fp-M-i-1.gif. Then to compute dp-fp-M-i-2.gif  we will need to use dp-fp-M-im1-2.gif and dp-fp-M-i-1.gif  which is the value that we previously computed. The function fold can help us with using the last value to compute the next. But we also need to return all the list of intermediate values, not just the last one, so scan is the one we want. Putting it all together:

def minPath(values: Vector[Vector[Int]]): Int = {
    val m = values.length
    val n = values(0).length
    val firstRow = accumulativeSum(values(0))
    val firstColumn = accumulativeSum( (0 to m-1).map(values(_)(0)) )
    (1 to m-1).foldLeft(firstRow) { (upperRow, i) =>
        val leftmostSolution = firstColumn(i)
        (1 to n-1).scanLeft(leftmostSolution) { (leftSolution,j) =>
            val upperSolution = upperRow(j)
            Math.min(leftSolution, upperSolution) + values(i)(j)
        }.toVector
    }.last
}

That's it! No mutation whatsoever!

Conclusions

Even for a class of algorithms that looks inherently imperative there are ways to avoid mutation and to end up with the very same algorithm using immutable data structures and higher-order functions like fold or scan. You could just translate the mutations into State monad values but that’s just too complex and unnecessary. There are simpler ways to functionally express the same thing.

Is this worth it? Maybe not if you are used to the imperative approach, which already yields a purely functional solution up to observable mutation.

In the next post we will see how to do the same with a top-down approach that’s both functional and expressive.

Posts by Topic

see all

Subscribe to Email Updates