Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Candy Machine Algorithm

  1. Mar 8, 2012 #1
    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
     
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted