What is the Algorithm Behind Candy Machines?

[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

 

[lofgran]

Hello Michuco,

It sounds like you have been putting a lot of thought into this candy machine algorithm! As a fellow scientist, I can definitely understand the desire to find a solution to a problem that seems simple on the surface but turns out to be more complex than expected.

One suggestion I have is to break the problem down into smaller parts. Instead of trying to find a general algorithm for a tube with n slots and m empty slots, start with a smaller number of slots and see if you can find a pattern or algorithm for that specific case. Then, you can use that information to build upon and solve for larger numbers of slots.

Another approach could be to think about the end goal - filling all the slots with candies - and work backwards from there. What steps need to be taken in order to reach that end goal? Can you identify any rules or patterns in those steps that could be used to create an algorithm?

It may also be helpful to draw out diagrams or create simulations to visually see the movement of the candies and how they fill the slots. This could provide some insight into the patterns and rules that govern the movement.

I hope these suggestions help and I wish you the best of luck in finding your algorithm! Don't give up, sometimes the most satisfying solutions come after hours of frustration. Keep at it and I'm sure you'll come up with something brilliant.