This article discusses Problem #1 in the Finals of the 1995 ACM International Collegiate Programming Contest sponsored by Microsoft.
Contents
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 @ permThe 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 3The 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.-10The 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 0The 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?~#pThe 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.285That 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 RogerHui. 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.