## 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.

@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.

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

def cheese(grid):

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

And is not necessary to keep the last line.

@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

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

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.

Here’s a

dynamic programmingsolution 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.Output: