# Picking Up Coins in a Grid

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.

In this puzzle, we have a rectangular board of cells, with some cells having a coin (the red disks in the plot). A robot is initially in the lower-left cell of the board. The task of the robot is to pick up as many coins as possible and carry them to the upper-right cell. However, at each step the robot can only move either one cell right or one cell up. Each time the robot visits a cell with a coin, it picks up that coin. The blue line shows an optimal tour, that is, a tour that allows the robot to pick up the maximum number of coins.

[more]
Contributed by: Heikki Ruskeepää (March 2012)

Open content licensed under CC BY-NC-SA

## Snapshots

## Details

This is puzzle number 62 in [1]. As in the book, the optimal path is found here by using dynamic programming. Let the centers of the cells be at points , , . The robot starts at and ends at . Let be 1 if there is a coin at and 0 otherwise. Let be the largest number of coins the robot can pick up and bring to . The task is to maximize .

The robot can reach the point either from below—that is, from —or from the left, . The largest number of coins that can be brought to these points are and , respectively. Thus, the largest number of coins the robot can bring to is the maximum of these two numbers plus . So, , , , . In addition, , , , and , .

After we have coded these formulas, we simply ask for the value of and we know the maximum number of coins that can be picked up! *Mathematica* does all the recursive calculations for us. To get the optimal path, we also write down from where it is optimal to come to each . Note that often the optimal path is not unique.

For more about dynamic programming with *Mathematica*, see Section 23.5.2 in [2].

References

[1] A. Levitin and M. Levitin, *Algorithmic Puzzles*, New York: Oxford University Press, 2011.

[2] H. Ruskeepää, *Mathematica Navigator: Mathematics, Statistics, and Graphics*, 3rd ed., San Diego: Elsevier Academic Press, 2009.

## Permanent Citation