Strategy to solve this number puzzle in the fewest moves?
Asked by
PhiNotPi (
12686
)
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.
Observing members:
0
Composing members:
0
7 Answers
What does the
“0 7
3 4”
signify?
It signifies that there are two baskets, one with 0 and one 7 apples. The second lines signifies that they now have 3 and 4 apples.
The problem may need additional specification in order to arrive at a solution anywhere near what you expect.
When you say that the baskets can contain “any number of” apples (and I’m assuming whole numbers, though even that isn’t specified), negative numbers are real, and so are numbers which would not be real for “apples in a basket”, such as numbers in the thousands, millions, etc.
The first step, then, and even with the simple problems that you’ve specified, has to be “count the damn apples, and count the baskets”.
A worst case scenario puts huge numbers (much larger than Y) of apples in every basket. For X=7, Y=2, suppose you start with millions:
1,000,000 1,000,000 1,000,000 1,000,000 1,000,000 1,000,000 1,000,000
What’s the first move? Where will excess apples go? Doesn’t there have to be some control over total apples given a value of Y?
[ edit ] Answering my own question, the average number of apples per basket A cannot exceed Y.
A = {Sum (i=1 to X) of Ai} / X
where Ai represents the number of apples in the i-th basket.
A <= Y
Otherwise you have excess apples with nowhere to go, as in my example.
@CWOTUS There won’t be negative numbers, or imaginary numbers, just whole numbers.
@gasman Assume that the problem is always solvable. This means that the total number of apples cannot be more than X*Y.
Is this a classic problem in computational theory? Is there a known solution?
I once wrote a program to solve a differential equation using a numerical technique known as “relaxation” of two-dimensional mesh iterating through every lattice point. This problem is one-dimensional so I guess you could iterate first-to-last, moving an apple out of a basket if (a) it has more than Y apples; (b) one or both neighbors holds fewer than Y. Transfer one apple to the neighbor with the lesser amount. If they hold the same amount choose the one closest to the front.
I don’t know if that algorithm works, and I highly doubt it’s optimal. For instance, there might be a better way to decide a move between equal neighbors. There might be a better sequence in which to visit all the baskets than first-to-last. etc.
The only strategy that I can devise is:
1. Count the total baskets (X).
2. Count the total apples (Y).
3. Divide Y by X to arrive at an average “apples per basket” value.
4. Adjust each basket accordingly, one by one.
Answer this question 
Composing members:
0
