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

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
    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
    ""
    
    
  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

    Haskell:

    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
    

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: