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

Posted by Miguel Vilá on Mon, Nov 20, 2017

In the previous posts, we saw an approach to solving Dynamic Programming problems in a bottom-up fashion and trying to be functional. In this last post we will see a functional approach when solving them top-down.

When following a top-down approach we memoize answers and have explicit recursion. Usually this is done with a mutable look-up table. For instance the knapsack problem can be solved this way:

import scala.collection.mutable

def knapsack(maxWeight: Int, value: Vector[Int], weight: Vector[Int]): Int = {
    val n = value.length
    val solutions = mutable.HashMap.empty[(Int,Int), Int]
    def f(i: Int, j: Int): Int = {
        if(!solutions.contains((i,j))) {
            val solution = 
                if( i == 0 || j == 0 ) {
                    0
                } else if( j - weight(i-1) >= 0 ) {
                    Math.max( 
                        f(i-1,j) , 
                        f(i-1, j - weight(i-1)) + value(i-1) 
                    )
                } else {
                    f(i-1, j)
                }
            solutions.put((i,j), solution)
        }
        solutions((i,j))
    }
    f(n, maxWeight)
}

What if we could do the same thing with a data structure that's defined recursively, just as the solutions? Can this be done with a normal map? Well there's the method tabulate that can be used to build a Vector using a function that describes every entry by it's indexes. Let's try something with it:

def knapsack2(maxWeight: Int, value: Vector[Int], weight: Vector[Int]): Int = {
    val n = value.length
    lazy val solutions: Vector[Vector[Int]] = 
        Vector.tabulate(n + 1, maxWeight + 1) { (i,j) =>
            if( i == 0 || j == 0 ) {
                0
            } else if( j - weight(i-1) >= 0 ) {
                Math.max( 
                    solutions(i-1)(j) , 
                    solutions(i-1)(j - weight(i-1)) + value(i-1) 
                )
            } else {
                solutions(i-1)(j)
            }
        }
    solutions(n)(maxWeight)
}

Well, this even compiles but fails at runtime with a Stackoverflow error. This is because when we use the solutions matrix inside the tabulate function we demand for the solutions value to be already completely built. It's kind of a chicken and egg problem. If we could relax this condition and make it possible to have some entries defined and others not...

Let's define a LazyVector allowing precisely that! 

// not threadsclass LazyVector[A](thunks: Vector[() => A]) { // (1)
    
    private val values: Array[Option[A]] = Array.fill(thunks.length)(None) // (2)
    
    def apply(i: Int): A = { // (3)
        if(!values(i).isDefined) {
            values(i) = Some( thunks(i)() )
        }
        values(i).get
    }
        
}

At (1) we declare that to build a LazyVector we need a Vector describing how to compute each entry. This is just a Vector of thunks (a thunk is a zero argument function). At (2) we see where we will save the computed values. Under the hood we will memoize the values using a mutable array. Yes, mutable! Don't worry, our intentions are pure (get it?). At (3) we declare how we are going to retrieve values for this data structure: if it's already computed just return it, otherwise compute it and save it.

Let's also add some constructor functions in the companion object:

object LazyVector {
    
    def tabulate[A](n: Int)(f: Int => A): LazyVector[A] = {
        new LazyVector( Vector.tabulate(n)( i => () => f(i) ) )
    }

    def tabulate[A](m: Int, n: Int)(f: (Int,Int) => A): LazyVector[LazyVector[A]] = {
        tabulate(m)( i => tabulate(n)( j => f(i,j) ) )
    }

}

Let's try the same thing we did with Vectors:

def knapsack(maxWeight: Int, value: Vector[Int], weight: Vector[Int]): Int = {
    val n = value.length
    lazy val solutions: LazyVector[LazyVector[Int]] = 
        LazyVector.tabulate(n + 1, maxWeight + 1) { (i,j) =>
            if( i == 0 || j == 0 ) {
                0
            } else if( j - weight(i-1) >= 0 ) {
                Math.max( 
                    solutions(i-1)(j) , 
                    solutions(i-1)(j - weight(i-1)) + value(i-1) 
                )
            } else {
                solutions(i-1)(j)
            }
        }
    solutions(n)(maxWeight)
}

And this works! No stack overflow!

This has the same time complexity as we had before with the bottom-up approach. The space complexity, unfortunately, is O(nW) which is not the best we can do if we are only interested in computing the maximum total value.

There is an important advantage with this approach, though. The code is way more declarative. It doesn’t say how to iterate over the matrix of solutions in such a way that dependencies are pre-computed. It just says: here’s what the solution looks like, let the data structure’s laziness avoid re-computations.

Returning the concrete solution

If we also want to know which items conform the maximum total value then we have to record all the decisions we make, so the space complexity will be O(nW) anyway. This just implies returning more information when we are looking for the maximum:

def max[A](a: (Int, A), b: (Int, A)): (Int, A) =
    if(a._1 > b._1)
        a
    else
        b

def knapsackWithItems(
    maxWeight: Int, value: Vector[Int], weight: Vector[Int]): List[Int] = {
    val n = value.length
    lazy val solutions: LazyVector[LazyVector[(Int, List[Int])]] = 
        LazyVector.tabulate(n + 1, maxWeight + 1) { (i,j) =>
            if( i == 0 || j == 0 ) {
                (0, List.empty)
            } else if( j - weight(i-1) >= 0 ) {
                val (including, itemsIds) = solutions(i-1)(j - weight(i-1))
                max( 
                    solutions(i-1)(j) ,
                    (including + value(i-1), (i-1) :: itemsIds )
                )
            } else {
                solutions(i-1)(j)
            }
        }
    val (_,items) = solutions(n)(maxWeight)
    items
}

Similarly we can solve Project Euler’s 81-th problem like this:

sealed trait Instruction
case object GoRight extends Instruction
case object GoDown extends Instruction

def minPath(values: Vector[Vector[Int]]): List[Instruction] = {
    val m = values.length
    val n = values(0).length
    lazy val solutions: LazyVector[LazyVector[(Int, List[Instruction])]] = 
        LazyVector.tabulate(m, n) { 
            case (0,0) => (values(0)(0), List.empty)
            case (0,j) => 
                val (leftVal, leftInsts) = solutions(0)(j-1)
                (values(0)(j) + leftVal, leftInsts ++ List(GoRight))
            case (i,0) => 
                val (upVal, upInsts) = solutions(i-1)(0)
                (values(i)(0) + upVal, upInsts ++ List(GoDown))
            case (i,j) =>
                val (leftVal, leftInsts) = solutions(i)(j-1)
                val (upVal  , upInsts  ) = solutions(i-1)(j)
                if(leftVal < upVal) {
                    (leftVal + values(i)(j), leftInsts ++ List(GoRight))
                } else {
                    (upVal + values(i)(j)  , upInsts ++ List(GoDown))                    
                }
        }
    val (_,insts) = solutions(m-1)(n-1)
    insts
}

Conclusions

This top-down approach has the disadvantage that it may consume more memory than we need (if we are just interested in the maximum or minimum value). But for the kind of problems where we need to have all the decisions then it’s worth it anyway. It produces very clear and declarative code. The only disadvantage I can think of is that it may produce stack-overflows for large inputs.

Recent Posts

Posts by Topic

see all

Subscribe to Email Updates