Essays/The Ball Clock Problem
This article discusses Problem #1 in the Finals of the 1995 ACM International Collegiate Programming Contest sponsored by Microsoft.
The Problem
Tempus et mobilius Tempus est mensura motus rerum mobilium.
Time and motion 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.
Operation of the Ball Clock
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.
Input
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.
Output
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.
Sample Input
30 45 0
Output for the Sample Input
30 balls cycle after 15 days.
45 balls cycle after 378 days.
A Solution in J
The balls are assumed to be labeled with the integers i.n . The clock period, the number of elapsed days before the clock repeats, can be computed as follows:
m =: >@(0&{) v =: >@(1&{) h =: >@(2&{) qu =: >@(3&{) z =: i.@0: ret =: |.@}: init =: z;z;z;i. f1m =: (m,{.@qu);v;h;}.@qu f5m =: (z;(v,{:@m);h;qu,ret@m) @ (f1m^:5) f1h =: (z;z;(h,{:@v);(qu,ret@v)) @ (f5m^:12) f12h =: (z;z;z;qu,ret@h,{:@h) @ (f1h^:12) perm =: qu @ f12h @ init ord =: *./ @ (#&>"_) @ C. days =: -: @ ord @ perm
The basic data structure is a 4-element list of boxes (m;v;h;qu) of the balls in the minute, 5-minute, and hour tracks and in the queue. (The fixed ball in the hour track is ignored.) Verb init initializes the clock: all tracks are empty and all balls are in the queue. Verb f1m models the clock action every minute; f5m models the clock action every 5 minutes (including the action every minute); f1h models the clock action every hour; and f12h models the clock action every 12 hours.
At the end of 12 hours, all tracks are empty and all balls are in the queue; therefore, the action of the clock is a permutation of the balls, computed by the verb perm . The order of this permutation is the LCM of the cycle lengths of the permutation, representing the number of 12-hour periods to return to the identity, and the clock period is half this number. The following examples illustrate the internal workings of the algorithm:
days 45 378 ] s=: init 45 NB. Initial state for 45 balls (m;v;h;qu) ┌┬┬┬──────────────────────┐ ││││0 1 2 3 4 ... 42 43 44│ └┴┴┴──────────────────────┘ f1m s NB. after 1 minute ┌─┬┬┬────────────────────┐ │0│││1 2 3 4 ... 42 43 44│ └─┴┴┴────────────────────┘ f5m s NB. after 5 minutes ┌┬─┬┬────────────────────────────┐ ││4││5 6 7 8 ... 42 43 44 3 2 1 0│ └┴─┴┴────────────────────────────┘ f1h s NB. after 1 hour ┌┬┬──┬─────────────────────────────────────────────────┐ │││16│15 23 22 21 20 28 27 26 25 33 32 31 30 38 37 ... │ └┴┴──┴─────────────────────────────────────────────────┘ f5m^:6 s NB. after 30 minutes ┌┬───────────────┬┬──────────────────────────────────┐ ││4 9 14 19 24 29││30 31 32 33 34 35 36 37 38 39 ... │ └┴───────────────┴┴──────────────────────────────────┘ f1m^:2 f5m^:6 f1h^:5 s NB. after 5 hours and 32 minutes ┌────┬──────────────┬─────────────┬───────────────────┐ │21 2│8 24 4 5 43 11│16 36 22 1 23│32 41 33 17 26 ... │ └────┴──────────────┴─────────────┴───────────────────┘ ] p=: perm 45 NB. the queue after 12 hours for 45 balls 25 30 0 24 35 2 44 33 15 19 13 6 29 43 8 26 40 31 ... _5]\ p NB. display in 5 columns 25 30 0 24 35 2 44 33 15 19 13 6 29 43 8 26 40 31 12 7 38 28 3 42 32 41 14 5 37 39 4 21 20 11 17 34 18 27 10 23 1 22 36 16 9 C. p NB. cycles of this permutation ┌──────────┬────────────┬────────────┬─────────────────┐ │26 14 8 15│42 36 18 ...│43 16 40 ...│44 9 19 7 33 11 6│ └──────────┴────────────┴────────────┴─────────────────┘ ,. C. p NB. column display of circles ┌──────────────────────────────────────────────────────────────────────────┐ │26 14 8 15 │ ├──────────────────────────────────────────────────────────────────────────┤ │42 36 18 12 29 39 23 │ ├──────────────────────────────────────────────────────────────────────────┤ │43 16 40 1 30 4 35 34 17 31 21 28 37 27 5 2 0 25 41 22 3 24 32 20 38 10 13│ ├──────────────────────────────────────────────────────────────────────────┤ │44 9 19 7 33 11 6 │ └──────────────────────────────────────────────────────────────────────────┘ #&> C. p NB. cycle lengths 4 7 27 7 *./ 4 7 27 7 NB. LCM of cycle lengths 756 days 45 NB. # days is half the # of 12-hour periods 378 d=: days"0[27+i.101 NB. Clock periods for 27 to 127 balls ,"(2) _5 ]\ (2 1$' '),' ',.~":,.d 23 76 102 15 85 65 138 91 12 117 120 345 35 37 217 114 110 105 378 126 6270 12 513 1116 770 86 51 30 693 180 930 559 858 495 11067 714 455 378 84 105 12 236 7095 255 60 4524 3848 1530 1955 268 714 25389 1155 9360 2006 805 4446 1122 540 36 570 1026 11033 1218 6580 312 301 3367 42780 2550 550 1365 6630 105 861 4514 291 3960 1464 1577 4284 5187 126 17094 15330 1785 43890 25872 5762 3325 204 3420 78120 1224 776 273 108855 174 14430 80080 2415
Permutation Power and Log
Given the current reading (m;v;h;qu) of the clock, can one determine the elapsed time since the initial operation of the clock? (Assuming that the clock has not yet repeated.)
If p is a permutation and k is an integer, the phrase q=:p&{^:k i.#p applies p to the identity permutation k times, obtaining q . By analogy with ordinary multiplication, q is the k-th power of p and (ord p)|k is the log of q relative to p . Determining the elapsed time reduces to finding k=:p log q , where p is the generator permutation of the clock (the state of the queue after 12 hours) and q is the current permutation (the state of the queue at the next even 12-hour). We proceed as follows:
First, compute the residue of q in each of the cycles of p . For example, 1 2 3 4 5 0 consists of a single cycle and 2 3 4 5 0 1 is at 2 relative to that cycle. In general, the residue of q relative to a cycle c is _1+m-((>c){q)i.{:>c [ m=:#>c ; moreover, if q is a power of p , the result of q indexed by the cycle, (>c){q , must be a rotation of the cycle. For example:
p=: 2 3 4 5 6 7 8 1 9 0 q=: 6 3 8 5 9 7 0 1 2 4 C. p ┌───────┬───────────┐ │7 1 3 5│9 0 2 4 6 8│ └───────┴───────────┘ ] c0=: 0{C. p ] c1=: 1{C. p ┌───────┐ ┌───────────┐ │7 1 3 5│ │9 0 2 4 6 8│ └───────┘ └───────────┘ (>c0){q (>c1){q 1 3 5 7 4 6 8 9 0 2 {:>c0 {:>c1 5 8 1 3 5 7 i. 5 4 6 8 9 0 2 i. 8 2 2 ] m0=: #>c0 ] m1=: #>c1 4 6 _1+m0-((>c0){q)i.{:>c0 _1+m1-((>c1){q)i.{:>c1 1 3
The preceding computations can be encapsulated as follows:
assert=: 13!:8@(12"_)^:-. res1 =: <:@#@[ - { i. {:@[ chkr =: [: assert { -: res1 |. [ res =: res1 [ chkr mr =: #&>@[ ,. (res&> <) (>c0) res q NB. Residue in cycle 0 1 (>c1) res q NB. Residue in cycle 1 3 (C. p) mr q NB. Moduli and residues 4 1 6 3 assert 1 NB. Return 1 if the argument is 1 1 assert 0 NB. Signal error if the argument is 0 |assertion failure | assert 0 (C. p) mr i.-10 NB. Not a power of p |assertion failure | (C.p) mr i.-10
The verb mr produces a 2-column table of moduli (cycle lengths) and residues. p log q obtains from this table by application of the GCD algorithm discovered by Euclid in 300 B.C. and the Chinese Remainder Theorem by Sun Tsu in 350 A.D. (Graham, Knuth, and Patashnik [1988]; Iverson [1995]). The Euclidean algorithm produces a and b such that (m+.n)=(a*m)+b*n , and the Chinese Remainder Theorem specifies that d=:(m*.n)|(m+.n)%~(r*b*n)+s*a*m satisfies r=m|d and s=n|d , for moduli m and n and residues r and s obtained from a power of p . If cr is a verb such that (m,r)cr(n,s) produces (m*.n),d , then the answer that we seek is k=:{:cr/t .
As indicated, the GCD is computed as a linear combination of the arguments; the algorithm operates by repeated remaindering. Thus:
g0 =: , ,. =@i.@2: it =: {: ,: {. - {: * <.@%&{./ gcd =: (}.@{.) @ (it^:(*@{.@{:)^:_) @ g0 32 gcd 44 NB. GCD as coefficients _4 3 +/ _4 3 * 32 44 NB. The actual GCD 4 ] a=: 32 g0 44 NB. Initial argument for GCD 32 1 0 44 0 1 it a NB. One iteration 44 0 1 32 1 0 it it a NB. Two iterations 32 1 0 12 _1 1 <"2 it^:(i.6) a NB. All iterations; stop when 0= lower left corner ┌──────┬──────┬───────┬────────┬───────┬───────┐ │32 1 0│44 0 1│32 1 0│12 _1 1│8 3 _2│4 _4 3│ │44 0 1│32 1 0│12 _1 1│ 8 3 _2│4 _4 3│0 11 _8│ └──────┴──────┴───────┴────────┴───────┴───────┘
The verb it applies to a 2-by-3 matrix: column 0 are the two current remainders; columns 1 and 2 are the corresponding coefficients in terms of the original arguments. At each step, a new remainder is computed by using row 1 as the divisor, and the iteration stops when the divisor is zero.
The version of Chinese Remainder used here rejects residues not obtainable from a power of p . Thus:
ab =: |.@(gcd/ * [ % +./)@(,&{.) cr1 =: [: |/\ *.&{. , ,&{: +/ .* ab chkc =: [: assert ,&{: -: ,&{. | {:@cr1 cr =: cr1 [ chkc 4 1 cr 6 3 NB. Applies to (modulus,residue) pairs 12 9 NB. Produces (LCM, remainder) 4|9 NB. Verify residue 0 1 6|9 NB. Verify residue 1 3 c0=: <i.4 NB. A 4-cycle c1=: <4+i.6 NB. A disjoint 6-cycle ] p=: C. c0,c1 NB. the perm. whose cycles are c0 and c1 1 2 3 0 5 6 7 8 9 4 ] q=: c0 C. i.10 NB. One application of cycle c0 1 2 3 0 4 5 6 7 8 9 (C. p) mr q NB. Moduli and residues 4 1 6 0 4 1 cr1 6 0 NB. Chinese remainder says answer is 3, 12 3 NB. but 1~:4|3 and 0~:6|3 4 1 cr 6 0 NB. Chinese remainder with built-in check |assertion failure | 4 1 cr 6 0
The power and log of a permutation are now defined, together with examples which illustrate their workings:
pow =: i.@#@[ C.~ (#&>@C.@[|]) # C.@[ log =: {: @ (cr/) @ (C.@[ mr ]) p=: 4 17 7 18 10 11 0 13 8 16 9 6 15 19 12 14 3 1 2 5 p log i.20 0 p log p 1 p log p{p 2 p log p{p{p 3 p log p pow 3 3 ] c=: C. p NB. the cycles of p ┌─┬────────┬────┬─────────────────────────────────┐ │8│15 14 12│17 1│19 5 11 6 0 4 10 9 16 3 18 2 7 13│ └─┴────────┴────┴─────────────────────────────────┘ ord p NB. the order of p; LCM of the cycle lengths 42 p log /:p NB. the log of the inverse is 1 less than the order 41 ] q=: p pow 38 NB. a power of p 19 1 9 4 5 2 13 16 8 6 11 7 14 3 15 12 0 17 10 18 p log q 38 c mr q NB. moduli and residues of q in each cycle 1 0 3 2 2 0 14 10 cr/ c mr q NB. order & log by repeated Chinese Remainder 42 38 {: cr/ c mr q NB. Select last item 38 k -: p log"1 p pow"1 0 k=.i.ord p NB. Verify all powers 1 p log ?~#p NB. A random perm. is unlikely to be a power |assertion failure NB. (probability (ord p)%!#p ) | p log?~#p
The verb pow exploits the dyad x C. y , which permutes y by the cycles x . Although the definition is less direct than p&{^:k i.#p , the time required is exponentially less. Thus:
p=: ?.~600 NB. A random permutation of length 600 c=: C. p NB. the cycles of p #&> c NB. cycle lengths 1 25 50 106 252 50 116 ord p NB. order (LCM of cycle lengths) 9683100 ] k=: ?. ord p NB. a random power 7758246 (#&>c) | k NB. the residues of k modulo the cycle lengths 0 21 46 0 174 46 50 NB. Apply each cycle the residue # of times (p pow k) -: (i.#p) C.~ 0 21 46 0 174 46 50#c 1 (/:p) -: p pow _1 NB. works on all integer powers 1 (i.#p) -: p pow 0 1 (p pow j) -: p pow n+j=:?n=:ord p 1 pow1=:{^:(]`(i.@#@[)) NB. alternative definition p&{^:k i.#p timer=: 6!:2 timer 'q0=: p pow k' 0.00348536 timer 'q1=: p pow1 k' 115.285
That is, 3.5 milliseconds versus approximately 1 minute 45 seconds. Finally, to give a sense of the relative times required for pow and log :
timer 'j=: p log q0' 0.00424439 j=k 1
References
- ACM, 1995 ACM International Collegiate Programming Contest Finals, Problem 1, 1995.
- Graham, Ronald L., Donald E. Knuth, and Oren Patashnik,
Concrete Mathematics: A Foundation for Computer Science, Addison-Wesley, 1988 5.
- Iverson, Kenneth E., Concrete Math Companion, Iverson Software Inc., 1995 6.
Appendix: Collected Definitions
NB. Clock Period m =: >@(0&{) v =: >@(1&{) h =: >@(2&{) qu =: >@(3&{) z =: i.@0: ret =: |.@}: init =: z;z;z;i. f1m =: (m,{.@qu);v;h;}.@qu f5m =: (z;(v,{:@m);h;qu,ret@m) @ (f1m^:5) f1h =: (z;z;(h,{:@v);(qu,ret@v)) @ (f5m^:12) f12h =: (z;z;z;qu,ret@h,{:@h) @ (f1h^:12) perm =: qu @ f12h @ init ord =: *./ @ (#&>"_) @ C. days =: -: @ ord @ perm NB. Moduli (Cycle Lengths) and Residues assert=: 13!:8@(12"_)^:-. res1 =: <:@#@[ - { i. {:@[ chkr =: [: assert { -: res1 |. [ res =: res1 [ chkr mr =: #&>@[ ,. (res&> <) NB. GCD as a Linear Combination g0 =: , ,. =@i.@2: it =: {: ,: {. - {: * <.@%&{./ gcd =: (}.@{.)@(it^:(*@{.@{:)^:_)@g0 NB. Chinese Remainder ab =: |.@(gcd/ * [ % +./)@(,&{.) cr1 =: [: |/\ *.&{. , ,&{: +/ .* ab chkc =: [: assert ,&{: -: ,&{. | {:@cr1 cr =: cr1 [ chkc NB. Permutation Power and Log pow =: i.@#@[ C.~ (#&>@C.@[|]) # C.@[ log =: {: @ (cr/) @ (C.@[ mr ])
Contributed by Roger Hui. Earlier versions of the text appeared in the Internet news group comp.lang.apl (original thread and follow-up) and in Vector, Volume 12, Number 2, October 1995.