The Ball Clock Problem
Vector 12:2, page 56
Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 56
This article discusses Problem #1 in the Finals of the 1995 ACM International Collegiate Programming Contest sponsored by Microsoft. The problem statement is verbatim from the WWW page http://www.acm.org/~contest/clock.html; earlier versions of the text appeared in the Internet news group comp.lang.apl (ACM [1995], Hui [1995], and Weigang [1995]).
[The problem statement, printed on pp.56–57, is not transcribed here. In brief: a ball clock has a queue of balls and minute, five-minute and hour tracks holding 4, 11 and 11 balls; for each number of balls from 27 to 127, report how many days pass before the balls return to their starting order. Sample: 30 balls cycle after 15 days; 45 balls cycle after 378 days.]
A Solution In J¶
The balls are assumed to be labelled 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 Initial state for 45 balls (m;v;h;qu)
┌┬┬┬────────────────────────────────────────────────┐
││││0 1 2 3 4 5 6 7 8 ... 36 37 38 39 40 41 42 43 44│
└┴┴┴────────────────────────────────────────────────┘
f1m s After 1 minute
┌─┬┬┬────────────────────────────────────────────────┐
│0│││1 2 3 4 5 6 7 8 9 ... 36 37 38 39 40 41 42 43 44│
└─┴┴┴────────────────────────────────────────────────┘
f5m s After 5 minutes
┌┬─┬┬───────────────────────────────────────────────────────┐
││4││5 6 7 8 9 10 11 12 ... 39 40 41 42 43 44 3 2 1 0 │
└┴─┴┴───────────────────────────────────────────────────────┘
f1h s After 1 hour
┌┬┬──┬────────────────────────────────────────────────────┐
│││16│15 23 22 21 20 28 27 26 25 33 32 31 30 38 37 ... │
└┴┴──┴────────────────────────────────────────────────────┘
f5m^:6 s 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 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 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 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 Cycles of this permutation
┌───────────┬────────────┬────────────┬──────────────────┐
│26 14 8 15 │42 36 18 ...│43 16 40 ...│44 9 19 7 33 11 6 │
└───────────┴────────────┴────────────┴──────────────────┘
,.C. p Column display of cycles
┌──────────────────────────────────────────────────────────┐
│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 ... │
├──────────────────────────────────────────────────────────┤
│44 9 19 7 33 11 6 │
└──────────────────────────────────────────────────────────┘
#&>C. p Cycle lengths
4 7 27 7
*./4 7 27 7 LCM of cycle lengths
756
days 45 # days is half the # of 12-hour periods
378
d=.days"0[27+i.101 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 Residue in cycle 0
1
(>c1) res q Residue in cycle 1
3
(C. p) mr q Moduli and residues
4 1
6 3
assert 1 Return 1 if the argument is 1
1
assert 0 Signal error if the argument is 0
|assertion failure
| assert 0
(C. p) mr i.-10 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 GCD as coefficients
_4 3
+/ _4 3 * 32 44 The actual GCD
4
[ a=.32 g0 44 Initial argument for GCD
32 1 0
44 0 1
it a One iteration
44 0 1
32 1 0
it it a Two iterations
32 1 0
12 _1 1
<"2 it^:(i.6) a 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 Applies to (modulus,residue) pairs
12 9 Produces (LCM, remainder)
4|9 Verify residue 0
1
6|9 Verify residue 1
3
c0=. <i.4 A 4-cycle
c1=. <4+i.6 A disjoint 6-cycle
[ p=.C. c0,c1 The perm. whose cycles are c0 and c1
1 2 3 0 5 6 7 8 9 4
[ q=.c0 C. i.10 One application of cycle c0
1 2 3 0 4 5 6 7 8 9
(C. p) mr q Moduli and residues
4 1
6 0
4 1 cr1 6 0 Chinese remainder says answer is 3,
12 3 but 1~:4|3 and 0~:6|3
4 1 cr 6 0 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 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 The order of p; LCM of the cycle lengths
42
p log /:p The log of the inverse is 1 less than the order
41
[ q=. p pow 38 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 Moduli and residues of q in each cycle
1 0
3 2
2 0
14 10
cr/ c mr q Order & log by repeated Chinese Remainder
42 38
{: cr/ c mr q Select last item
38
k -: p log"1 p pow"1 0 k=.i.ord p Verify all powers
1
p log ?~#p A random perm. is unlikely to be a power
|assertion failure (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:
9!:1 [7^5 Set random seed to 16807
p=.?~300 A random permutation of length 300
c=.C. p The cycles of p
#&> c Cycle lengths
1 7 8 1 76 89 121 6
ord p Order (LCM of cycle lengths)
3862320
[ k=.?ord p A random power
2908096
(#&>c)|k The residues of k modulo the cycles
0 2 0 0 32 16 103 4
(p pow k) -: (i.#p) C.~ 0 2 0 0 32 16 103 4#c
1 Apply each cycle the residue # of times
(/:p) -: p pow _1 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.@#@[)) Alternative definition p&{^:k i.#p
timer=. 6!:2 J 2.06 under Windows on 80486/50
timer 'q0=.p pow k'
0.05
timer 'q1=.p pow1 k'
938.35
q0 -: q1
1
That is, 0.05 seconds versus approximately 15.5 minutes. Finally, to give a sense of the relative times required for pow and log:
References¶
ACM, 1995 ACM International Collegiate Programming Contest Finals, Problem 1, http://www.acm.org/~contest/clock.html, 1995.
Graham, Ronald L., Donald E. Knuth, and Oren Patashnik, Concrete Mathematics: A Foundation for Computer Science, Addison-Wesley, 1988 5.
Hui, Roger K.W., Challenge: ACM Ball Clock Problem, Internet News Group comp.lang.apl, 1995 3 28-31.
Iverson, Kenneth E., Concrete Math Companion, Iverson Software Inc., 1995 6.
Weigang, James, Challenge: ACM Ball Clock Problem, Internet News Group comp.lang.apl, 1995 3 27 and 1995 4 2-3.
Appendix: Collected Definitions¶
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
Moduli (Cycle Lengths) and Residues¶
assert=. 13!:8@(12"_)^:-.
res1 =. <:@#@[ - { i. {:@[
chkr =. [: assert { -: res1 |. [
res =. res1 [ chkr
mr =. #&>@[ ,. (res&> <)
GCD as a Linear Combination¶
Chinese Remainder¶
ab =. |.@(gcd/ * [ % +./)@(,&{.)
cr1 =. [: |/\ *.&{. , ,&{: +/ .* ab
chkc =. [: assert ,&{: -: ,&{. | {:@cr1
cr =. cr1 [ chkc