CSE 102 – Tutorial 3 – Dynamic programming

General instructions

After you are finished with the tutorial, please upload your submission to Moodle by completing “Tutorial 3 assignment” before the indicated deadline.

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.

To start, we need to pick a representation for bat flight paths and for grids. In general, a bat path visits a series of nodes \((x_0,y_0),(x_1,y_1),\dots,(x_n,y_n)\), where \(x_i - x_{i-1} = 1\) and \(y_i - y_{i-1} \in \{-1,0,1\}\). We represent such a bat path as a list of vertical displacements \([d_1,\dots,d_n]\) where \(d_1 = y_1-y_0\), \(d_2 = y_2-y_1\), and so on. Moreover, to simplify notation, we take the bat’s starting coordinate to be the origin \((x_0,y_0) = (0,0)\), so that \(x_i = i\) and \(y_i\) is always between \(-i\) and \(i\). Thus the flight path in red above, visiting nodes \((0,0)-(1,0)-(2,1)-(3,2)-(4,1)\), is represented by the length 4 list \([0,1,1,-1]\).

We assume a fixed geometry for the grid (always a triangular grid, as above) but the positions of the fruits can vary. We represent the fruit positions as a list of sets \([f_0,f_1,\dots,f_n]\), where each \(f_i\) is a subset of values \(f_i \subset \{-i,\dots,i\}\), with \(y \in f_i\) just in case there is fruit at node \((i,y)\). Thus the fruits in the grid above are represented by the length 5 list of sets \([\{\}, \{-1,0\},\{-1,1,2\},\{-3,2\},\{-2,1,4\}]\). (Note that in this example there is no fruit at the origin, but if there were that would be represented by the set \(\{0\}\) at the head of the list.)

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

example_flight = [0,1,1,-1]
example_fruits = [{}, {-1,0},{-1,1,2},{-3,2},{-2,1,4}]

Since there are \(3^n\) possible paths through a triangular grid of length \(n\), the brute force approach quickly becomes intractable (whether or not we use a generator). 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(x,y)\) for the value of an optimal flight path starting at node \((x,y)\) and ending at \((n,y')\) for some \(y'\). If \(F(x,y)\) denotes the value of the fruit at a given node (either 1 or 0 depending on whether or not there is fruit at \((x,y)\)), then we can easily verify that the values \(V(x,y)\) satisfy the recurrence

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

for all \(0 \le x \le n\), with \(V(x,y) = 0\) when \(x > n\).

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 \((x,y)\) is independent of the path taken to \((x,y)\). This means that the values \(V(x,y)\) only have to be computed once, and can then be reused when computing the values of \(V(x',y')\) for any \(x' < x\). We can see this better if we label the nodes of our example grid with the values of \(V(x,y)\) for each \((x,y)\):

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(fruits) should compute the same value as optimal_rec(fruits) and optimal_brute(fruits), 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 can use the functions below to construct some larger grids of fruits:

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

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

In [1]: optimal_brute(line_fruits(12)), optimal_brute(cyclic_fruits(13,5))
Out[1]: (13, 9)

In [2]: optimal_rec(line_fruits(12)), optimal_rec(cyclic_fruits(13,5))
Out[2]: (13, 9)

In [3]: optimal_td(line_fruits(12)), optimal_td(cyclic_fruits(13,5))
Out[3]: (13, 9)

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(x,y)\). Notice that the values in the last column are either 1 or 0 depending on whether there is fruit at the node, 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 \(x = n\) and running down to the trivial leftmost column \(x = 0\), at each iteration computing the values of \(V(x,y)\) for all \(y\) between \(-x\) and \(x\).

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 defined by the formula

\[ 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.