Send to a Friend

PhiNotPi's avatar

Strategy to solve this number puzzle in the fewest moves?

Asked by PhiNotPi (12681points) October 7th, 2012

Oh, ever so heavily inspired, although this question goes into much more detail. source

Here’s the problem, explained in completely different terms, and which I hope will remove all its ambiguity.

You have X baskets of apples, each of which can contain any number of apples (including zero). The baskets have a specific order left to right that cannot be changed.

The goal is to make it so each basket contains no more than Y apples.

Each move consists of transferring any number of apples from one basket to an adjacent basket.

How can this puzzle be solved in the fewest number of moves?

For example:
X=7, Y=2
1 3 3 0 3 2 1
2 2 3 0 3 2 1 (first move)
2 2 2 1 3 2 1 (second move)
2 2 2 2 2 2 1 (third move, puzzle solved)

X=2, Y=4
0 7
3 4 (first move, solved)

Sometimes, there is more than one best solution. Whatever strategy only has to find one best solution.

Using Fluther

or

Using Email

Separate multiple emails with commas.
We’ll only use these emails for this message.