CSE 102 – Tutorial 2 – Dynamic programming

General instructions

Fruit flight of fantasy

For the sake of this exercise, imagine that you are a fruit bat flying eastwards across a triangular grid. At each unit of time, you can either fly due East or North-East or South-East. Some locations of the grid contain fruit (indicated by yellow circles below), and your goal is to eat as many of these as possible before making it to the end of the grid, after which you’ll go back into your cave to hibernate. For example, the grid might look like this:

In this case, there is a single optimal flight path travelling East, then North-East, then North-East, and finally South-East:

Your first task will be to implement a brute-force solution to this problem by exhaustive enumeration. By “exhaustive enumeration”, we mean the approach of generating all possible flight paths, computing their fruit value, and picking the one with the maximum value. Although this brute-force approach is very inefficient, it provides a baseline and will help us to get a better understanding of the problem specification.

We need to pick a representation for flight paths and for grids, so let us use the following:

• a path will be represented by a list of vertical displacements \([d_1,\dots,d_n]\) for \(d_i \in \{-1,0,1\}\). Thus the flight path in red above is represented by the list \([0,1,1,-1]\).
• a grid will be represented as a list of sets \([f_1,\dots,f_n]\), where each \(f_j\) is a subset of values \(f_j \subset \{-j,\dots,j\}\), with \(i \in f_j\) just in case there is fruit at row \(i\), column \(j\), relative to the bat’s initial location \((0,0)\). Thus the grid above is represented by the list of sets \([\{-1,0\},\{-1,1,2\},\{-3,2\},\{-2,1,4\}]\).

For testing purposes, you may find it convenient to copy these examples into your Python file:

example_path = [0,1,1,-1]
example_grid = [{-1,0},{-1,1,2},{-3,2},{-2,1,4}]

Now it is very easy to write a very inefficient function for computing the value of an optimal path:

def optimal_brute(grid):
    return max(fruit_value(grid,path) for path in flights(len(grid)))

You should test for yourself that it works:

In [1]: optimal_brute(example_grid)
Out[1]: 4

Since there are \(3^n\) possible paths through a triangular grid of length \(n\), the brute force approach quickly becomes intractable. We can do much better with dynamic programming! Our first step will be to establish a recursive formula for the value of an optimal flight path. To that end, we need to consider paths starting at arbitrary locations on the triangular grid. Let us write \(V(i,j)\) for the value of an optimal flight path ending in column \(n\) and starting at row \(i\), column \(j\), where we assume that the bat has already consumed any fruit at that location \((i,j)\) so that it does not contribute to the value of the path. Then \(V(i,n) = 0\) for all \(i\), and one easily checks that the values \(V(i,j)\) satisfy the recurrence

\[ V(i,j) = \max_{d \in \{-1,0,1\}} F(i+d,j+1) + V(i+d,j+1) \]

for all \(1 \le j < n\), where \(F(i,j)\) is either 1 or 0 depending on whether there is fruit at location \((i,j)\).

In terms of efficiency, the recursive approach is not much better than the brute-force approach since it still considers all \(3^n\) paths through the grid implicitly, in the sense that they are represented implicitly in the call stack. The key property that allows us to obtain a more efficient algorithm via dynamic programming is that the value of an optimal path from \((i,j)\) is independent of the path taken to \((i,j)\). This means that the values \(V(i,j)\) only have to be computed once, and can then be reused when computing the values of \(V(i',j')\) for any \(j' < j\). We can see this better if we label the nodes of our example grid with the values of \(V(i,j)\) for each \((i,j)\) (recall that any fruit at \((i,j)\) does not contribute to the value of \(V(i,j)\)):

In general, a triangular grid of length \(n\) has \(1 + 3 + 5 + \dots + (2n+1) = (n+1)^2\) nodes, so there are only \((n+1)^2\) values of \(V(i,j)\) to compute.

Your function optimal_td(grid) should compute the same value as optimal_rec(grid) and optimal_brute(grid), but much more quickly. Of course the difference will be negligible for the tiny example grid above, but should be noticeable even on relatively small grids since \(3^n\) grows much more quickly than \((n+1)^2\). For testing purposes, you could use the functions below to construct some larger grids:

def line_grid(n):
    return [{j+1} for j in range(n)]
def cyclic_grid(n,k):
    return [{i for i in range(-j,j+1) if (j*j+j+i)%k == 0} for j in range(1,n+1)]

For example, try to reproduce the interaction below, observing how long it takes to compute each answer.

In [2]: optimal_brute(line_grid(12)), optimal_brute(cyclic_grid(13,5))
Out[2]: (12, 8)

In [3]: optimal_rec(line_grid(12)), optimal_rec(cyclic_grid(13,5))
Out[3]: (12, 8)

In [4]: optimal_td(line_grid(12)), optimal_td(cyclic_grid(13,5))
Out[4]: (12, 8)

import time
def timed(f, x):
    '''Runs f(x) and returns a pair of the resulting value and the elapsed time.'''
    t0 = time.time()
    v = f(x)
    t1 = time.time()
    return (v, t1-t0)

Having successfully implemented a recursive top-down solution to the problem of computing the values of optimal paths, your next goal will be to implement an iterative, bottom-up approach. For this it may be helpful to look again at the diagram above where each node is labelled by the corresponding value of \(V(i,j)\). Notice that the values in the last column are all equal to 0, while the values in each inner column only depend on the values in the column to its immediate right. This means that we can compute the value of the optimal path by working from right to left, starting with the rightmost column \(j = n\) and running down to the trivial leftmost column \(j = 0\), at each iteration computing the values of \(V(i,j)\) for all \(-j \le i \le j\).

Finally, hibernation time is approaching! Knowing the theoretical value of an optimal flight path is not good enough – you need the actual path itself. Luckily, finding one is also possible using dynamic programming.

Optimal typesetting (optional)

For this exercise, imagine that you are the CEO of a startup company whose business model is based on providing a service that formats texts into highly-aesthetic fixed-width blocks. The user provides a text \(T\) in the form of a list of words and specifies an upper limit \(L\) on the number of characters per line (including spaces), and you automatically format the text into a list of lines \(\ell_1,\dots,\ell_n\) so as to minimize the “defect”

\[ D = \sum_{i=1}^n (L - |\ell_i|)^3 \]

corresponding to the sum of cubes of numbers of trailing characters. For example, consider the following text:

lorem = ['Lorem', 'ipsum', 'dolor', 'sit', 'amet', 'consectetur', \
         'adipiscing', 'elit', 'sed', 'do', 'eiusmod', 'tempor', \
         'incididunt', 'ut', 'labore', 'et', 'dolore', 'magna', 'aliqua']

With a limit of \(L = 20\) characters per line, a naive way of formatting the text into lines is as below:

Lorem ipsum dolor   |
sit amet consectetur|
adipiscing elit sed |
do eiusmod tempor   |
incididunt ut labore|
et dolore magna     |
aliqua              |

Unfortunately this looks awful, with a defect of 3³ + 0³ + 1³ + 3³ + 0³ + 5³ + 14³ = 2744. In contrast, this is how your service would format the text:

Lorem ipsum dolor   |
sit amet consectetur|
adipiscing elit     |
sed do eiusmod      |
tempor incididunt   |
ut labore et        |
dolore magna aliqua |

With a defect of only 3³ + 0³ + 5³ + 6³ + 3³ + 8³ + 1³ = 908, the text is now beautifully typeset. The business prospects for your startup are looking rosy, if only you can get the service to work correctly!

Crocodile sequences (optional)

You will recall from your biology classes that crocodiles can lay three kinds of eggs – green, red, or blue – where:

• a green egg contains either a green baby crocodile or a pair of a red egg and a blue egg, arranged left to right;
• a red egg contains either a red baby crocodile or a pair of a blue egg and a green egg, arranged left to right;
• a blue egg contains either a blue baby crocodile or a pair of a green egg and a red egg, arranged left to right.

Hence a single crocodile egg can hatch a potentially unbounded number of baby crocodiles. Moreover, these crocodile siblings always come out arranged in an orderly line according to the nesting structure of the eggs. For example, the green egg

ultimately hatches the following line of siblings:

For this exercise, imagine that you are applying for a job at a crocodile nursery, and that as part of the interview process, you will be asked to look at a line of crocodile babies and quickly determine whether they could possibly be a complete group of siblings.