The Physical Marble Clock
The physical marble clock (see photo) consists of four trays. The bottom tray (in the back) provides a source of marbles for the time-keeping mechanism. It must hold at least 27 (11 + 11+ 4 + 1) marbles to tell time. The marbles enter the tray on one end and are removed from the other. (Aha! a queue) The time starts at 1:00 when none of the movable marbles are in the time-keeping trays.
The three trays in front are used to tell time. The top tray has labels (left-to-right) 1, 2, 3, and 4. The first cycle of the clock uses a long arm which turns once per minute, acting as a second hand, and lifts one marble from the source and deposits it into the top tray to the right of the 4 from whence it rolls down until it is above the 1 label. The next three end up over the 2, 3 and 4 respectively until the tray contains 4 marbles indicating the time is 1:04.
The fifth marble over-balances the tray. This fifth marble falls into the second tray and the other four spill back into the source tray in the reverse order from which they entered the top tray. (Aha! a stack)
The second tray has 11 positions labeled 5, 10, 15, 20, ..., 55. The first marble rolls down until it is over the 5 thus indicating that it is 5 minutes past the hour. The process continues and every five minutes the 5th marble over-balances the top tray and itself falls into the second tray while the other 4 are reversed into the source tray. This continues until the top tray has 4 marbles and the middle tray has 11 indicating the time is 1:59. Then the next marble over-balances the top tray falls to the middle and the top tray empties. Then the middle tray empties with the most recent marble, the one which over-balanced the top tray now over-balancing the middle tray and falling to the third tray while the other 11 marbles from the middle tray are returned to the source, being reversed in the process. (Aha! another stack)
The marble that over-balanced the top two trays falls in the third tray. This tray is labeled 1, 2, 3, 4, ... , 12. There is one marble permanently glued over the one and it never moves thus the new marble rolls down until it is over the 2 indicating 2:00. The top two trays continue depositing one marble into the hour indicator each hour until the trays are all full, i.e., 4 in the top, 11 in the middle and 11 (don't count the glued one) in the hour tray indicating the time is 12:59. The next marble, over-balances the top tray falling to the middle and spilling the 4 marbles from the top tray back into the source, it then overbalances the middle tray falling to the hour tray and spilling the 11 marbles from the middle tray back into the source, finally it overbalances the hour tray and all 12 of them fall back into the source with the newest marble leading the way.
This completes one 12-hour cycle.
The Abstract Marble Clock
The abstract marble clock consists of an integer queue, Q, and three integer stacks: oneMin, fiveMin and hour. Initially we insert the integers 0, 1, ... , N-1 into Q in order. We continually dequeue from Q and push the item onto oneMin. When oneMin is of size 5 we pop once, pushing the result onto fiveMin, and then pop the rest of oneMin enqueueing onto Q. When fiveMin reaches size 12 we similarly pop once pushing the result onto hour and then popping the rest enqueueing them back onto Q. Finally when hour reaches size 12 we pop all of its members enqueueing them back onto Q.
This completes one repetition of the process.
The Assignment
Given that the queue started with the numbered marbles in order we wish to find out how many 12-hour cycles are needed to return the queue to an ordered state. This will depend on the number of marbles we started with of course.
Input: N, an integer representing the number of marbles (If N is less than 27 an error message is printed)
Output: The number of 12-hour cycles needed to return the marbles of the source queue to their original order.
Basic Approach - Accept N from user input and repeat the cycle described above testing the source queue (non-destructively) at the end of each 12-hour cycle to determine whether it is back in order.
Challenge - [not extra credit nor assigned nor implied as assigned!] Since one 12-hour cycle represents a permutation of the queue, after one cycle we can determine the permutation and simply use it instead of actually performing the stack and queue simulation over and over again. So from the state of the queue we create a permutation of [0, 1, 2, ... , N-1] and apply it to the marble list until it's in order again.
Super Challenge - What we really want is the order of the permutation in the intermediate approach. Algebra gives us several ways to compute this without actually applying it over and over again. One way is to decompose the permutation into disjoint cycles and take the LCM of the orders of the cycles recalling that the order of a cycle is just its length.
The Marble clock in its dust cover --- The current time is 6:33.
A close up of the Time telling trays --- The current time is also 6:33
