Tempus et mobiliusTime and motion
Tempus est mensura motus rerum mobilium.
Time is the measure of movement.
-- Auctoritates Aristotelis
This is a fascinating problem that proved to be surprisingly responsive to careful thought. A lengthy discussion appeared in comp.lang.apl, involving postings by Tom Chwastyk, Roger Hui, and myself. Roger Hui's solution (in J) appeared in the October 1995 issue of Vector (vol. 12, no. 2, pp 56-66). The following are just my own postings:
Are you interested in ball clocks? Remember having one as a kid? Want to know where you can buy one? Well, then check out the Ball Clock Page!
For reference, here is the text of the ACM Clock Contest. Solutions follow in the next message.
* * * *
From the 1995 ACM Contest Finals sponsored by Microsoft:
Time and motion
Tempus est mensura motus rerum mobilium.
Time is the measure of movement.
-- Auctoritates Aristotelis
...and movement has long been used to measure time. For example, the ball clock is a simple device which keeps track of the passing minutes by moving ball-bearings. Each minute, a rotating arm removes a ball bearing from the queue at the bottom, raises it to the top of the clock and deposits it on a track leading to indicators displaying minutes, five-minutes and hours. These indicators display the time between 1:00 and 12:59, but without 'a.m.' or 'p.m.' indicators. Thus 2 balls in the minute indicator, 6 balls in the five-minute indicator and 5 balls in the hour indicator displays the time 5:32.
Unfortunately, most commercially available ball clocks do not incorporate a date indication, although this would be simple to do with the addition of further carry and indicator tracks. However, all is not lost! As the balls migrate through the mechanism of the clock, they change their relative ordering in a predictable way. Careful study of these orderings will therefore yield the time elapsed since the clock had some specific ordering. The length of time which can be measured is limited because the orderings of the balls eventually begin to repeat. Your program must compute the time before repetition, which varies according to the total number of balls present.
Every minute, the least recently used ball is removed from the queue of balls at the bottom of the clock, elevated, then deposited on the minute indicator track, which is able to hold four balls. When a fifth ball rolls on to the minute indicator track, its weight causes the track to tilt. The four balls already on the track run back down to join the queue of balls waiting at the bottom in reverse order of their original addition to the minutes track. The fifth ball, which caused the tilt, rolls on down to the five-minute indicator track. This track holds eleven balls. The twelfth ball carried over from the minutes causes the five-minute track to tilt, returning the eleven balls to the queue, again in reverse order of their addition. The twelfth ball rolls down to the hour indicator. The hour indicator also holds eleven balls, but has one extra fixed ball which is always present so that counting the balls in the hour indicator will yield an hour in the range one to twelve. The twelfth ball carried over from the five-minute indicator causes the hour indicator to tilt, returning the eleven free balls to the queue, in reverse order, before the twelfth ball itself also returns to the queue.
The input defines a succession of ball clocks. Each clock operates as described above. The clocks differ only in the number of balls present in the queue at one o'clock when all the clocks start. This number is given for each clock, one per line and does not include the fixed ball on the hours indicator. Valid numbers are in the range 27 to 127. A zero signifies the end of input.
For each clock described in the input, your program should report the number of balls given in the input and the number of days (24-hour periods) which elapse before the clock returns to its initial ordering.
30 45 0
30 balls cycle after 15 days. 45 balls cycle after 378 days.
From: jimw@math.umass.edu (Jim Weigang)
Here's my first program, a straightforward simulation of the ball clock mechanism:
{del} Z{<-}ACMBALLS N;H;M;Q;R
[1] @Brute-force solution for the ACM Ball Clock Contest
[2] @ N is the number of balls in the clock
[3] @ Z is the number of days before the balls return to the original order
[4] @
[5] Q{<-}R{<-}{iota}N @ the ball queue, and a reference copy
[6] Z{<-}0 @ day counter
[7] M{<-}H{<-}{iota}0 @ 5-minute and hour tracks
[8] L1: @ Loop for each five-minute period
[9] M{<-}M,Q[5] @ add 5th ball to the 5-minute track
[10] Q{<-}(5{drop}Q),{reverse}4{take}Q @ requeue the other 1-minute balls
[11] {->}(12>{rho}M)/L1 @ If 12 balls in the 5-min track,
[12] H{<-}H,{neg}1{take}M @ move the last ball onto the hour track
[13] Q{<-}Q,{reverse}{neg}1{drop}M @ requeue the other 5-min balls
[14] M{<-}{iota}0 @ empty the 5-min track
[15] {->}(12>{rho}H)/L1 @ If 11 moveable balls in the hour track,
[16] Q{<-}Q,1{rotate}{reverse}H @ requeue the hour balls
[17] H{<-}{iota}0 @ empty the hour track
[18] Z{<-}Z+.5 @ another half-day has passed
[19] {->}(Q{match}R)/0 @ quit if balls are in original order
[20] {->}L1 @ Endloop
{del}
But this runs quite slowly, and the run time is proportional to the number of days in the cycle. (It took 63 seconds to return 378 days for ACMBALLS 30.) Tom Chwastyk had said in his posting that his program ran in about a quarter of a second, so I realized there must be a better algorithm. I put a stop on line [20] and looked at how the balls were rearranged after 12 hours. Quite a jumble. But after a little thought, I realized that the shuffle pattern would be the same for every 12 hour period. So after computing the first 12 hours by brute force, the queue could be stepped through additional 12-hour periods using Q{<-}Q[P], where P is the shuffle pattern. This led to ACMBALLS2, which is like ACMBALLS except for the following lines:
[17]
[18] @ Phase 2: Apply the 12-hour permutation repeatedly until the
[19] @ balls return to their original order.
[20] Z{<-}.5 @ day counter
[21] P{<-}Q @ 12-hour permutation
[22] L2:{->}(Q{match}R)/0 @ Loop until balls are in order
[23] Q{<-}Q[P] @ give 'em a days worth of shuffling
[24] Z{<-}Z+.5 @ bump the day counter
[25] {->}L2 @ Endloop
This version was fast enough (.33 seconds for 45 balls) that I was able to compute the answers for all arguments from 27 to 127. But even this version took 83 seconds to compute the answer for 123 balls (108,855 days). While I was waiting, I wondered if I could apply more than one permutation at once. The problem statement said the answer would be an even number of days, so I could "double" P (i.e., P{<-}P[P]) and use it to cut the number of Q{<-}Q[P] iterations in half. But could I quadruple P? Could I use a bisection algorithm, doubling the power of P each time? If I did this, how could I tell if I passed the solution?
I thought about how an individual ball moves through the queue from one 12-hour period to the next. Consider the following permutation:
5 6 4 1 3 7 2 P
1 2 3 4 5 6 7 {iota}{rho}P
Ball 1 moves to the 4th position after 12 hours (look for 1 in P and read the new position in the iota vector below). Then, as new ball 4, it moves to the 3rd position, then to the 5th position, and finally it returns to the first position, a cycle of four 12-hour periods. Ball 2 moves to positions 7, 6, and back to 2, a cycle of three 12-hour periods. This permutation has cycles of length 4 and 3, so I could safely raise P to the 4th power (permutation-wise) or to the 3rd power, or to the least common multiple of 4 and 3.
A little more thought along these lines lead to a big Ah-Ha!, and I realized that the least common multiple of the cycle lengths was actually the answer to the problem (though expressed in 12-hour rather than 24-hour periods). After N periods, where N is the least common multiple of the permutation cycle lengths, all the cycles will be simultaneously completed and all the balls will be back in their original order in the queue. I put together a simple cycle length calculator, found an algorithm for LCM in Paul Berry's Sharp APL Reference Manual, and came up with the following solution:
{del} Z{<-}ACMBALLS3 N;H;I;L;M;Q;R
[1] @A very fast solution for the ACM Ball Clock Contest
[2] @ N is the number of balls in the clock
[3] @ Z is the number of days before the balls return to the original order
[4] @
[5] Q{<-}R{<-}{iota}N @ the ball queue, and a reference copy
[6] M{<-}H{<-}{iota}0 @ 5-minute and hour tracks
[7] I{<-}0
[8] L1: @ Loop for each five-minute period
[9] M{<-}M,Q[5] @ add 5th ball to the 5-minute track
[10] Q{<-}(5{drop}Q),{reverse}4{take}Q @ requeue the other 1-minute balls
[11] {->}(12>{rho}M)/L1 @ If 12 balls in the 5-min track,
[12] H{<-}H,{neg}1{take}M @ move the last ball onto the hour track
[13] Q{<-}Q,{reverse}{neg}1{drop}M @ requeue the other 5-min balls
[14] M{<-}{iota}0 @ empty the 5-min track
[15] {->}(12>{rho}H)/L1 @ If 11 moveable balls in the hour track,
[16] Q{<-}Q,1{rotate}{reverse}H @ requeue the hour balls
[17]
[18] @ Phase 2: Analyze the 12-hour permutation vector
[19] L{<-}CYCLES Q @ length of the cycles in the permutation
[20] Z{<-}.5{times}LCM/L @ number of days before repetition
{del}
{del} Z{<-}CYCLES P;B;I;L;N;S
[1] @Returns the lengths of cycles in permutation vector {omega}
[2] B{<-}(N{<-}{rho}P){rho}0 @ 1s will mark elements we've visited
[3] Z{<-}{iota}0
[4] L1:{->}(N<I{<-}B{iota}0)/0 @ Loop for each cycle
[5] L{<-}0 @ length counter
[6] B[S{<-}I]{<-}1 @ mark start as visited
[7] L2:I{<-}P[I] @ next item in cycle
[8] B[I]{<-}1 @ mark it as visited
[9] L{<-}L+1 @ bump the length
[10] {->}(I{/=}S)/L2 @ repeat unless at start
[11] Z{<-}Z,L @ remember the length
[12] {->}L1 @ Endloop
{del}
{del} Z{<-}A LCM B
[1] @Least common multiple of {alpha} and {omega}
[2] Z{<-}A{times}B{divide}A GCD B
{del}
{del} Z{<-}A GCD B
[1] @Greatest common denominator of {alpha} and {omega} using Euclid's {+
+}algorithm
[2] Z{<-}|A
[3] {->}(0=A|B)/0
[4] Z{<-}(A|B)GCD A
{del}
(The LCM-reduction on line [20] of ACMBALLS3 would be done with a simple loop in a non-nested APL.) This version runs nice and fast: 13 seconds for ACMBALLS3{each}26+{iota}101.
Elapsed time between obtaining the problem description and finishing the last program: 2.5 hours. Of course, without Tom Chwastyk's encouragement, I might never have realized that a faster solution was possible.
Jim
From: jimw@math.umass.edu (Jim Weigang)
Here's my APL solution to Roger Hui's Clock Challenge II. The problem is to compute the time (days, hours, and minutes) given the state of the ball clock. (For a description of the ball clock, see <http://www.acm.org/~contest/clock.html> or my first 27 Mar 95 posting here.) The solution is to take the given state and run the clock until 1:00, at which time the ball queue will be full. This final queue F will be some power of P, the characteristic permutation that the queue undergoes in each 12-hour period. Determine the power and you know how many 12-hour periods have elapsed. Then subtract the number of minutes you had to run the clock to get to 1:00. The hard part is determining the power of P. A brute-force solution would be to keep raising P to higer powers (T{<-}P, and then T{<-}T[P] applied repeatedly) until you reach F. But this can take a while, because thousands of iterations may be required.
A clever approach is to examine P's permutation cycles in F and see what phase each cycle is in (that is, see how many steps each cycle is shifted). The results can be summarized in a 2-column table of the cycle lengths and phases. For example:
Length Phase
5 3
8 2
6 0
The first cycle in F is shifted 3 steps from the corresponding cycle in P. But it could have completed any number of full cycles plus 3 steps, so it may have advanced 3, 8, 13, 18, 23, etc. (3+5{times}{iota}N) steps. The second cycle may have advanced 2, 10, 18, 26, etc. (2+8{times}{iota}N) steps. The third cycle may have advanced 0, 6, 12, 18, 24, etc. (0+6{times}{iota}N) steps. Note that 18 is the smallest number common to each of these sets. Thus, 18 is the least power of P that would result in F. (Actually, the power is 18+1 because one step corresponds to the 2nd power.) I got this far by myself, but I couldn't figure out the general solution to computing the least common multiple-plus-constant.
Fortunately, Roger provided the answer in his description of the Chinese Remainder (CR) algorithm. CR is similar to the least common multiple (LCM), but whereas A LCM B finds the least number equal to A{times}I and B{times}J, CR finds the least number equal to (A{times}I)+R and (B{times}J)+S. Here is my implementation of Roger's algorithm. (I chose to write it as a reduction function.)
{del} Z{<-}CHINREM A;E;F;I;L;M;N;R;S;T
[1] @Chinese Remainder -- least common multiple-plus-constant
[2] @ Argument:
[3] @ A - an N-by-2 numeric matrix. The first column is the numbers
[4] @ to compute multiples of, and the second column is the
[5] @ constants to be added before comparing for equality.
[6] @ Result:
[7] @ Z - the smallest number for which Z^.=(A[;1]{times}I)+A[;2],
[8] @ where I is a vector of nonnegative integers.
[9] @
[10] @ Algorithm from Roger Hui's 30 Mar 95 03:07 GMT comp.lang.apl posting
[11] @
[12] M{<-}1 & R{<-}0
[13] I{<-}0 & E{<-}1{take}{rho}A
[14] L1:{->}(E<I{<-}I+1)/L2
[15] N{<-}A[I;1] & S{<-}A[I;2]
[16] F{<-}M GCDF N
[17] T{<-}F+.{times}(M,N){times}S,R
[18] L{<-}M LCM N
[19] R{<-}L|T{divide}F+.{times}M,N
[20] M{<-}L
[21] {->}L1
[22] L2:Z{<-}R
{del}
{del} Z{<-}X GCDF Y;M;N;T
[1] @Returns factors Z such that Z+.{times}{alpha},{omega} is the GCD of {+
+}{alpha} and {omega}
[2] @ Translated from Roger Hui's 30 Mar 95 15:15 GMT c.l.a posting
[3] M{<-}X,1 0
[4] N{<-}Y,0 1
[5] L1:{->}(0=1{take}M)/L2
[6] T{<-}M
[7] M{<-}N-M{times}{floor}(1{take}N){divide}1{take}T
[8] N{<-}T
[9] {->}L1
[10] L2:Z{<-}1{drop}N
{del}
{del}Z{<-}A LCM B
[1] @Least common multiple of {alpha} and {omega}
[2] Z{<-}A{times}B{divide}A GCD B
{del}
{del} Z{<-}A GCD B;R
[1] @Greatest common denominator of singletons {alpha} and {omega}
[2] L1:Z{<-}|A
[3] {->}(0=R{<-}A|B)/0
[4] B{<-}A & A{<-}R
[5] {->}L1
{del}
With this tool in hand, finding the "logarithm" of a permutation is easy. You simply build the length-and-phase matrix and apply CHINREM.
{del} Z{<-}P PERMLOG F;C;E;H;I;J;K;L;M
[1] @Permutation "logarithm"; finds what power {omega} is of permutation {+
+}{alpha}
[2] @ Returns {iota}0 if F is not a power of P
[3] C{<-}PERM2CYCLE P
[4] Z{<-}{iota}0 @ bad-argument indicator
[5] I{<-}0 & E{<-}{rho}C
[6] M{<-}(E,2){rho}0
[7] L1:{->}(E<I{<-}I+1)/L2 @ Loop for each cycle
[8] J{<-}I{pick}C @ the cycle
[9] K{<-}F[{neg}1{rotate}J] @ corresponding elements of F
[10] L{<-}{rho}J @ cycle length
[11] H{<-}L|L-{neg}1+K{iota}1{take}J @ phase
[12] {->}(~K{match}H{rotate}J)/0 @ exit if invalid cycle
[13] M[I;]{<-}L,H @
[14] {->}L1 @ Endloop
[15] L2:Z{<-}1+CHINREM M @ power is 1 greater than the shift
{del}
{del} Z{<-}PERM2CYCLE P;B;C;I;N;S
[1] @Converts permutation vector {omega} to a nested list of cycles
[2] B{<-}(N{<-}{rho}P){rho}0 @ 1s will mark elements we've visited
[3] Z{<-}0{rho}{enclose}{iota}0 @ give it the right prototype
[4] L1:{->}(N<I{<-}B{iota}0)/0 @ Loop for each cycle
[5] C{<-}0{rho}S{<-}I @ remember starting item
[6] L2:C{<-}C,I @ remember this item
[7] B[I]{<-}1 @ mark item as visited
[8] I{<-}P[I] @ next item in cycle
[9] {->}(I{/=}S)/L2 @ repeat unless at start
[10] Z{<-}Z,{enclose}C @ remember the cycle
[11] {->}L1 @ Endloop
{del}
For testing purposes, it's convenient to have a function that raises a permutation vector to a power. Here is a fast implementation that works on the permutation vector directly rather than transforming the permutation to cycle space:
{del} Z{<-}P PERMPOW N;B;I
[1] @Computes the {omega}-th power of a permutation vector
[2] B{<-}(64{rho}2){represent}N @ binary representation of the power
[3] B{<-}{reverse}({or}\B)/B @ drop leading 0s and put low order {+
+}first
[4] Z{<-}{iota}{rho}P
[5] I{<-}0
[6] L1:{->}(({rho}B)<I{<-}I+1)/0 @ Loop for each power-of-2
[7] {->}(~B[I])/L2 @ If this is one we need,
[8] Z{<-}Z[P] @ pick it up
[9] L2:P{<-}P[P] @ double P
[10] {->}L1 @ Endloop
{del}
#RL{<-}52781
P{<-}130?130
LCM/1{pick}{each}{rho}{each}PERM2CYCLES P
134640 @ 134,640 steps before P repeats
#{<-}N{<-}?134640
34218 @ a random power
P PERMLOG P PERMPOW N
34218 @ check
1 EXT'Z{<-}P PERMLOG P PERMPOW N'
0.092901016 @ execution time in seconds, on a 486/66
@ running APL*PLUS II/386 v5.2
@ A bigger example:
P{<-}300?300
LCM/{disclose}{each}{rho}{each}PERM2CYCLES P
1001040
#{<-}N{<-}?1001040
746096
1 EXT'Q{<-}P PERMPOW N'
0.01823692
1 EXT'Z{<-}P PERMLOG Q'
0.148255432
Z
746096
And with these tools, the clock solution is straightforward:
{del} Z{<-}CLOCKTIME C;F;N;P
[1] @Returns the time represented by clock state {omega}
[2] @ C is the clock state, a 4-item nested vector holding the hour,
[3] @ 5-minute, and minute tracks, and the ball queue.
[4] @ Z is the current time in days (since starting the clock), hours
[5] @ (0-23), and minutes (assuming the clock was started at 1:00 AM).
[6] @ Z is {iota}0 if the clock state C is invalid.
[7] @
[8] N{<-}1{pick}{each}{rho}{each}C @ number of balls in each track
[9] P{<-}4{pick}RUNCLOCK CLOCKINIT +/N @ 12-hour permutation
[10] F{<-}4{pick}RUNCLOCK C @ run the clock until 1:00
[11] Z{<-}P PERMLOG F @ what power of P is F?
[12] {->}(0{epsilon}{rho}Z)/0 @ quit if it isn't a power
[13] Z{<-}12{times}60{times}Z-1 @ minutes from start to previous 1:00
[14] Z{<-}Z+0 12 5{basevalue}3{take}N @ add minutes since previous 1:00
[15] Z{<-}Z+60 @ add 60 mins because clock started at 1:00, not 0:00
[16] Z{<-}0 24 60{represent}Z @ current day, hour, minute
{del}
{del} Z{<-}N RUNCLOCK C;H;M;Q;V
[1] @Runs clock {omega} for {alpha} minutes, or until 1:00 if called {+
+}monadically
[2] (H V M Q){<-}C @ hour, 5-minute, and minute tracks, and ball queue
[3] {->}(2=#NC'N')/L3 @ If called monadically,
[4] N{<-}(12{times}60)-0 12 5{basevalue}({rho}H),({rho}V),{rho}M @ {+
+}minutes til 1:00
[5] L3:Q{<-}M,Q @ requeue any minute balls; we shortcut this track
[6] N{<-}N+{rho}M @ additional minutes for the requeued balls
[7] L1:{->}(0>N{<-}N-5)/L2 @ Loop for each five-minute period
[8] V{<-}V,Q[5] @ add 5th ball to the 5-minute track
[9] Q{<-}(5{drop}Q),{reverse}4{take}Q @ requeue the other 1-minute balls
[10] {->}(12>{rho}V)/L1 @ If 12 balls in the 5-min track,
[11] H{<-}H,{neg}1{take}V @ move the last ball onto the hour track
[12] Q{<-}Q,{reverse}{neg}1{drop}V @ requeue the other 5-min balls
[13] V{<-}{iota}0 @ empty the 5-min track
[14] {->}(12>{rho}H)/L1 @ If 12 moveable balls in the hour track,
[15] Q{<-}Q,1{rotate}{reverse}H @ requeue the hour balls
[16] H{<-}{iota}0 @ empty the hour track
[17] {->}L1 @ Endloop
[18] L2:N{<-}N+5 @ remaining 0-4 minutes
[19] M{<-}N{take}Q & Q{<-}N{drop}Q @ load the minute track
[20] Z{<-}H V M Q @ final state
{del}
{del} Z{<-}CLOCKINIT N
[1] @Returns the initial state for a clock with {omega} balls
[2] Z{<-}({iota}0) ({iota}0) ({iota}0) ({iota}N)
{del}
24{times}60{times}ACMBALLS3 27
33120 @ how many minutes before 27-ball clock repeats
#{<-}N{<-}?33120
17979 @ a random number of minutes
T{<-}N RUNCLOCK CLOCKINIT 27 @ run clock for N minutes
{rho}{each}T
11 7 4 5
'HVMQ',' ',{disclose}[2]{format}{each}T @ clock state
H 7 9 8 17 22 20 3 15 25 23 2
V 6 5 18 12 21 19 16
M 10 27 26 14
Q 11 13 1 4 24
CLOCKTIME T @ read the time
12 12 39
0 24 60{represent}N @ days, hours, and minutes in N
12 11 39
@ (Time is 1 hour greater because clock starts at 1:00, not 0:00.)
1 EXT'Z{<-}CLOCKTIME T'
0.16842332
A nice application for exploring the world of permutations.
Jim
From: jimw@math.umass.edu (Jim Weigang)
Roger pointed out my confusion regarding 18 vs. 18+1, but I believe he misunderstood the consequences. (E.g., PERMPOW and PERMLOG behave exactly as his examples show.) The problem is that in computing P PERMLOG F, I compared the permutation cycles as they exist in F with the corresponding elements of P. Because P is the first power of the permutation, it's necessary to add 1 to the observed shift to get F's power. If I had compared F with the zeroth power ({iota}{rho}P) instead, it would have been unnecessary to add 1. The only consequence of this mistake is that P PERMLOG {iota}{rho}P returns K (where K is the LCM of the cycle lengths) instead of 0. To fix PERMLOG, delete the following lines marked "-" and insert the lines marked "+":
-[9] K{<-}F[{neg}1{rotate}J] @ corresponding elements of F
+[9] K{<-}F[J] @ corresponding elements of F
-------------------------------
-[15] L2:Z{<-}1+CHINREM M @ power is 1 greater than the shift
+[15] L2:Z{<-}CHINREM M
Unfortunately, this change breaks the CLOCKTIME program when the clock is within 12 hours of repeating. In this situation, advancing the clock to the next 1:00 results in F being the Kth power of P. But the modified PERMLOG reports that F is the 0th power of P, and you have no way of knowing what K is. One solution is to back the clock up by 12 hours after running it forward to 1:00. This can be done by indexing F with the inverse of P (the -1 power, which, as has been mentioned here recently, can be computed in a couple of ways). The changes to CLOCKTIME are:
+[11] F{<-}F[{gradeup}P] @ back up to previous 1:00 to avoid wraparound
------------------------------
-[13] Z{<-}12{times}60{times}Z-1 @ minutes from start to previous 1:00
+[14] Z{<-}12{times}60{times}Z @ minutes from start to previous 1:00
Also, my version of PERMPOW doesn't handle negative powers correctly. To fix this, make the following changes:
-[2] B{<-}(64{rho}2){represent}N @ binary representation of the power
+[2] {->}(N{>=}0)/L0 @ If negative power,
+[3] P[P]{<-}{iota}{rho}P @ do it to the inverse
+[4] L0:B{<-}(64{rho}2){represent}|N @ binary representation of the power
Inverse powers are handled naturally when you exponentiate by dualing into cycle space, but because APL doesn't have J's "C." primitive, the approach used by PERMPOW runs faster.
Jim
Home Page