$"""$A broken implementation of a recursive search for the optimal path through

a grid of weights.

Richard Lobb, January $2019.$

$"""$

INFINITY $=$ float$(\text{'}$inf$\text{'})$ # Same as math.inf

def read$\_$grid$($filename$)$:

$"""$Read from the given file an n x m grid of integer weights.

The file must consist of n lines of m space$-$separated integers.

n and m are inferred from the file contents.

Returns the grid as an n element list of m element lists.

THIS FUNCTION DOES NOT HAVE BUGS.

$"""$

with open$($filename$)$ as infile:

lines $=$ infile.read$().$splitlines$()$

grid $=[[$int$($bit$)$ for bit in line.split$()]$ for line in lines$]$

return grid

def grid$\_$cost$($grid$)$:

$"""$The cheapest cost from row $1$ to row n $(1-$origin$)$ in the given

grid of integer weights.

$"""$

n$\_$rows $=$ len$($grid$)$

n$\_$cols $=$ len$($grid$[0])$

def cell$\_$cost$($row$,$ col$)$:

$"""$The cost of getting to a given cell in the current grid."""

if row $<0$ or row $>=$ n$\_$rows or col $<0$ or col $>=$ n$\_$cols:

return INFINITY # Off$-$grid cells are treated as infinities

else:

cost $=$ grid$[$row$][$col$]$

if row $!=0$:

cost $+=$ min$($cell$\_$cost$($row $-1,$ col $+$ delta$\_$col$)$ for delta$\_$col in range$(-1,+1))$

return cost

best $=$ min$($cell$\_$cost$($n$\_$rows $-1,$ col$)$ for col in range$($n$\_$cols$))$

return best

def file$\_$cost$($filename$)$:

$"""$The cheapest cost from row $1$ to row n $(1-$origin$)$ in the grid of integer

weights read from the given file

$"""$

infile $=$ open$($filename$,\text{'}$r$\text{'})$

grid $=[]$

for line in infile:

row $=[$int$($x$)$ for x in line.split$()]$

grid.append$($row$)$

infile.close$()$

return min$\_$cost$\_$path$($grid$,$ len$($grid$)-1,0)$

The answer box has been preloaded with code that reads a file of integer weights and computes the minimum cost path between the bottom row and the top row. The code uses a direct recursive implementation of the recurrence relation given in the lecture notes.

But

$.$

$.$

$.$

$$there are two problems with the code.

Firstly, it has a simple logic error and fails even on a simple test case. For example, the output from the first test is

$5$

$$but the input file is

$3$

$2$

$1$

$2$

$1$

$3$

$1$

$2$

$3$

for which the answer should clearly be

$3$

$.$

$$The other problem is that it times out on larger grids, such as a

$9$

$0$

$$x

$9$

$0$

$$grid$.$

We'll deal with the time

$-$

out problem in the next question. Your task in this question is just to fix that bug so that code passes the trivial test above and the simple

$5$

$$x

$5$

$$example from the lecture notes:

$6$

$7$

$4$

$7$

$8$

$7$

$6$

$1$

$1$

$4$

$3$

$5$

$7$

$8$

$2$

$2$

$6$

$7$

$0$

$2$

$7$

$3$

$5$

$6$

$1$

The bug is very simple, involving just one tiny bit of text

$($

e

$.$

g

$.$

$,$

$$a word or a number

$)$

$$but it is not all that obvious. You will probably have to use some simple debugging techniques to locate it

$.$

$$Please keep in mind that the purpose of this exercise is to help you to understand the algorithm, so asking someone what the bug is will likely destroy the learning outcome.

For this question, pylint compliance is required although docstrings aren't necessary and name checking is turned off.

Resubmission penalties are turned off for this question.

For example:

Test Result

print

$($

file

$\_$

cost

$($

$\text{'}$

checkerboard

$.$

trivial.in

$\text{'}$

$)$

$)$

$3$

print

$($

file

$\_$

cost

$($

$\text{'}$

checkerboard

$.$

small.in

$\text{'}$

$)$

$)$

$8$