## The Rat Eats The Cheese

### May 14, 2019

We represent the maze as a vector of vectors, upside down; here is our function for making a random maze:

```(define (make-cheese n fill)
(define (rand-row)
(let ((row (make-vector n 0)))
(do ((k 0 (+ k 1))) ((= k n) row)
(when (< (random 1.0) fill)
(vector-set! row k 1)))))
(set! nrows n) (set! ncols n)
(let ((rows (make-vector n #f)))
(do ((k 0 (+ k 1))) ((= k n))
(vector-set! rows k (rand-row)))
rows))```

Now we make a maze:

```(define nrows #f) (define ncols #f)
(define cheese (make-cheese 20 0.15))

> (display cheese)
#(#(0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0)
#(0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
#(0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0)
#(0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0)
#(0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0)
#(1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0)
#(0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
#(0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0)
#(0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0)
#(0 1 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 1 0 0)
#(0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0)
#(0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0)
#(0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 1)
#(0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0)
#(1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0)
#(0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0)
#(0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1)
#(0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0)
#(0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1)
#(0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0)```

Then the rat moves through the maze, eating cheese as he finds it; we memoize the function because otherwise the double recursion would cause exponential runtime:

```(define-memoized (rat r c)
(if (or (= r nrows) (= c ncols)) 0
(+ (vector-ref (vector-ref cheese r) c)
(max (rat (+ r 1) c) (rat r (+ c 1))))))```

Here’s a sample, showing the timing:

```> (time (rat 0 0))
(time (rat 0 ...))
no collections
0 ms elapsed cpu time
0 ms elapsed real time
48 bytes allocated
9```

You can run the program at https://ideone.com/sbMDXx.

Pages: 1 2

### 11 Responses to “The Rat Eats The Cheese”

1. Steve said

@programmingpraxis: The read link does not work. Having read the text at the run link, am I correct in assuming that the total amount of cheese is the amount consumed in all of the different permutations of paths?

2. programmingpraxis said

@Steve: Fixed link. Thank you for pointing that out. You are trying to find the maximal amount of cheese that can be consumed on any single route.

3. Paul said

In Python. A table is used with the cheese that can be eaten from the (row, col) position. The table is filled from the top right to the bottom left. The value at the bottom left is the solution.

```from random import randrange

def random_grid(rows, cols):
return [[randrange(0, 2) for _ in range(cols)] for _ in range(rows)]

def cheese(grid):
rows, cols = len(grid), len(grid[0])
table = [[0] * cols for _ in range(rows)] # nr cheese to eat from here
# fill first the top row
table[0][cols-1] = grid[0][cols-1]
for col in range(cols-2, -1, -1):
table[0][col] = grid[0][col] + table[0][col+1]
# fill the last column
for row in range(1, rows):
table[row][cols-1] = grid[row][cols-1] + table[row-1][cols-1]
# fill the rest
for irow in range(1, rows):
for icol in range(cols-2, -1, -1):
if icol != cols - 1:
table[irow][icol] = grid[irow][icol] + max(table[irow-1][icol], table[irow][icol+1])
return table[rows-1][0]

g = random_grid(100, 100)
# print(g)
print(cheese(g))
```
4. Paul said

It is not necessary to keep the whole table. Only the last 2 rows have to be kept.

```def cheese(grid):
rows, cols = len(grid), len(grid[0])
current = [[0] for _ in range(cols-1)] + grid[0][-1]
for col in range(cols-2, -1, -1):
current[col] = grid[0][col] + current[col+1]
for irow in range(1, rows):
previous = list(current)
current = [[0] for _ in range(cols)]
current[-1] = grid[irow][-1] + previous[-1]
for icol in range(cols-2, -1, -1):
current[icol] = grid[irow][icol] + max(previous[icol], current[icol+1])
return current[0]
```

def cheese(grid):

5. Paul said

Only te last 2 rows of the table need to be kept.

```def cheese(grid):
rows, cols = len(grid), len(grid[0])
current = [[0] for _ in range(cols-1)] + grid[0][-1]
for col in range(cols-2, -1, -1):
current[col] = grid[0][col] + current[col+1]
for irow in range(1, rows):
previous = list(current)
current = [[0] for _ in range(cols)]
current[-1] = grid[irow][-1] + previous[-1]
for icol in range(cols-2, -1, -1):
current[icol] = grid[irow][icol] + max(previous[icol], current[icol+1])
return current[0]
```
6. Paul said

And is not necessary to keep the last line.

```def cheese(grid):
rows, cols = len(grid), len(grid[0])
current = [[0] for _ in range(cols-1)] + [grid[0][-1]]
for col in range(cols-2, -1, -1):
current[col] = grid[0][col] + current[col+1]
for irow in range(1, rows):
current[-1] += grid[irow][-1]
for icol in range(cols-2, -1, -1):
current[icol] = grid[irow][icol] + max(current[icol], current[icol+1])
return current[0]
```
7. SteveG said

@programmingpraxis: If I move one position at a time, either to the right or downward, in your 20×20 matrix, I can achieve a count of at least 14. However, your result was 9.

Am I missing something?

Thanks, Steve

8. Steve said

Klong version

```
Program:
:" Create a l with size s and a function to create each element"
l::{[s f]; s::x; f::y; {s>#x}{x,f()}:~[]}

:" Use l to create a row of s elements"
row::{l(x; {.rn()<0.15})}

:" Create a board of rows"
board::{[s]; s::x; l(s; {,row(s)})}

:" Programming Praxis' example board"
board2::[[0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0]
[0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0]
[0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0]
[1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0]
[0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0]
[0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0]
[0 1 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 1 0 0]
[0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0]
[0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0]
[0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 1]
[0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0]
[1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0]
[0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1]
[0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1]
[0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0]]

:" Traverse the generated board starting at 0,0 with goal of max sum"
rat::{[s b d]; d:::{}; s::x;  print(b::board(s)); rat2(0,0; s,,b; d)}

:" Traverse programming praxis board starting at 0,0 with goal of max sum"
ratx::{[s b d]; d:::{}; s::x;  print(b::board2); rat2(0,0; s,,b; d)}

:" Checks for end, adds current cell to max of 2 alternative paths"
rat2::{[b c r s]; c::x@0; r::x@1; s::y@0; b::y@1;
:[(c=s)|(r=s); 0; (b:@x)+get((c+1),r; y; z)|get(c,r+1; y; z)]}

:" If value is already in d, get value; otherwise get value and save to d"
get::{[a t u d]; t::x; u::y; d::z;
:[~:_d?t;
d?t;
{a::rat2(t; u; d); d,(,t),a; a}()
]
}

:" Print board"
print::{[b]; b::x; {.p(x)}'b}

---

Run:
]l cheese
{.p(rat(x))}'[1 2 5 10 20]; .p(""); .p("Original Problem"); .p(ratx(20));""
[0]
0
[0 0]
[0 0]
0
[0 1 0 1 0]
[0 0 0 0 1]
[0 0 0 0 0]
[0 1 0 0 0]
[0 0 0 0 1]
4
[1 0 0 0 0 0 0 0 1 0]
[1 0 0 0 0 0 1 0 0 0]
[0 0 1 0 0 0 0 0 1 0]
[0 0 0 0 0 0 0 0 1 0]
[0 0 0 0 0 0 0 0 1 0]
[0 0 0 0 0 0 0 0 0 0]
[0 1 0 0 0 0 1 0 0 0]
[0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 1 0 0]
[0 0 0 0 0 0 0 1 1 1]
8
[0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0]
[0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0]
[0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0 0 1]
[0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0]
[0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0]
[0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0]
[0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 1 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0]
[0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0]
[0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0]
[1 1 0 0 1 0 0 0 1 0 0 0 1 1 0 0 0 0 1 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0]
[1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0]
[0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0]
18

Original Problem
[0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0]
[0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0]
[0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0]
[1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0]
[0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0]
[0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0]
[0 1 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 1 0 0]
[0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0]
[0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0]
[0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 1]
[0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0]
[1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0]
[0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1]
[0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1]
[0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0]
16
""

```
9. Globules said

Here’s a Haskell version. I like graphs, so I’ve cast it as a shortest weighted path problem.

```-- Create an implicit graph whose nodes represent the points on a square grid.
-- The node labels are the coordinates of the point (e.g. (2, 3) or (5, 5),
-- etc.).  Legal moves through the graph are enforced by edges connecting each
-- node to its neighbors above and to its right.  The edges are labeled by
-- weights, where a weight of maxBound means the destination has no cheese
-- wedges, and maxBound - N means it has N wedges. (In the example problem N is
-- always 1.)  This is set up to conform to the requirements of the shortest
-- path function, which finds the minimum weight shortest path.
--
-- Since its the edge *into* a node that indicates the presence or absence of a
-- cheese wedge, we use a "dummy" node that points to the first real node, in
-- case it has a wedge.
--
-- This is the graph we'll use to solve the problem.  Filled circles are the
-- grid points having cheese wedges; dots are empty grid points; arrows are the
-- directed edges in the graph.  The dummy node is at (0, 0).
--
--
--     5     · → · → · → ● → ·
--           ↑   ↑   ↑   ↑   ↑
--     4     · → · → · → · → ·
--           ↑   ↑   ↑   ↑   ↑
--     3     · → ● → · → ● → ●
--           ↑   ↑   ↑   ↑   ↑
--     2     · → · → ● → · → ●
--           ↑   ↑   ↑   ↑   ↑
--     1     · → · → · → · → ·
--         ↗
--     0  ·
--
--        0  1   2   3   4   5
--

import Algorithm.Search
import Data.Functor ((<&>))
import Data.Maybe (maybe)

type Coord    = (Int, Int)
type Weight   = Int

neighbours :: Coord -> Coord -> [Coord]
neighbours _     (0, 0) = [(1, 1)]
neighbours xymax (x, y) = filter (<= xymax) [(x+1, y), (x, y+1)]

cost :: Weight -> [(Coord, Weight)] -> Coord -> Coord -> Weight
cost wmax weights _ dst = maybe wmax (wmax -) \$ lookup dst weights

solve :: [(Coord, Weight)] -> Coord -> Coord -> Maybe (Weight, [Coord])
solve weights begin end =
dijkstra (neighbours end) (cost maxBound weights) (== end) begin <&>
\(w, cs) -> (length cs * maxBound - w, cs)

printSoln :: Maybe (Weight, [Coord]) -> IO ()
printSoln Nothing = putStrLn "No path between start and end nodes."
printSoln (Just (w, path)) = putStrLn \$ "Wedges eaten: " ++ show w ++
"\nPath taken: " ++ show path

main :: IO ()
main = do
let begin = (0, 0)
end   = (5, 5)
weights = zip [(3, 2), (5, 2), (2, 3), (4, 3), (5, 3), (4, 5)] \$ repeat 1
printSoln \$ solve weights begin end
```
```\$ ./cheese
Wedges eaten: 3
Path taken: [(1,1),(2,1),(3,1),(3,2),(3,3),(4,3),(5,3),(5,4),(5,5)]
```
10. Jack said

foldl (\b a -> let r = 0 : zipWith (+) (zipWith max b r) a in tail r)
(map (const 0) \$ head ys) ys

[2,2,3,5,5,7,7,7,7,7,8,8,8,9,9,9,12,14,15,16]

it’s also in the Project Euler, I think.

11. Daniel said

Here’s a dynamic programming solution in Python. The code was slightly simplified by padding the table with a row of zeros on the bottom and column of zeros on the left. The code was slightly complicated by only retaining two rows of the table.

```def max_cheese(num_rows, num_cols, cheese_points):
table = [[0 for y in range(num_cols + 1)] for x in range(2)]
for row in range(1, num_rows + 1):
row_ = row % 2
for col in range(1, num_cols + 1):
table[row_][col] = int((row - 1, col - 1) in cheese_points)
table[row_][col] += max(table[row_ - 1][col], table[row_][col - 1])
return table[num_rows % 2][num_cols]

print(max_cheese(5, 5, {(4, 3), (2, 1), (2, 3), (2, 4), (1, 2), (1, 4)}))
```

Output:

```3
```