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.
Programming Praxis 
@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?
@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.
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))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):
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]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]@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
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 loading "./cheese.kg" {.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 ""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 endHaskell:
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.
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: