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.

Advertisements

Pages: 1 2

7 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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: