The Rat Eats The Cheese

May 14, 2019

A square maze contains cheese wedges on some of its squares:

·  ·  · 🧀  ·
·  ·  ·  ·  ·
· 🧀  · 🧀 🧀
·  · 🧀  · 🧀
·  ·  ·  · ·

[ Did you know there is a cheese-wedge character in Unicode? I didn’t. The center-dot is & # 183 ;, the cheese is & # 129472 ;, and I had to sprinkle in a few & thinsp ; characters to line things up. And of course to type those I had to add extra spaces, because WordPress is aggressive about turning them into characters. ]

A rat, starting at the lower left-hand corner of the maze, can move only up or right. What is the maximum amount of cheese the rat can eat?

Your task is to write a program to determine how much cheese the rat can eat. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

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: