# Candy Machine Algorithm

1. Mar 8, 2012

### ibmichuco

Hi all,

You have probably seen these candy machines before. Tubes
that contain candies of different colors and drop candies into
a receiver once you inserted the coin.

I was watching these more than a quarter of an hour at lunch
time (waiting for someone to buy candy) and thought that I
could come up with a simple algorithm to mimic these candies
movement.

Turned out not so.

To simplify things, I started out with just one tube with slots
that can hold one candy at a time. Let say we have a tube of
7 slots and 5 candies filling the top five. Then the candies
are allowed to drop freely. That is each candy can drop 1, 2 or
more slots at a time if there are spaces.

| o | 1
-----
| o | 2
-----
| o | 3
-----
| o | 4
-----
| o | 5
-----
| | 6
-----
| | 7
-----

I figured that the movement of the bottom candy
decides how many step the upper ones can skip/drop.

I calculated that there are 20 possible distributions
and the original one:

12345 <--- starting.
12346 <--- bottom candy drop one slot.
12356
12456
13456
23456
12347 <--- bottom candy drop two slots.
12357
12457
13457
23457
12367
12467
13467
23467
12567
13567
23567
14567
24567
34567 <---- All bottom slots a filled. Stop.

That much I figured out, and there is a clear pattern of the
sequences here, but for the last few hours I couldn't come up
with a general algorithm for a tube with n slots filled and m
slots empties.

My first (cheese eating) surrending act was looking for some
quick answer in stat books. Sure enough, I got the number
of all possible distributions there, but the algorithm has
been giving me the stump since.

I am looking for any excuse not to work this afternoon.

I am sure that once the algorithm is found it will turn
out to be so simple that I should tear off the rest of my
hair in shame.

Any suggestion help would be greatly appreciated.

Michuco