LABTITLE=: 'The Ball Clock Problem'
LABAUTHOR=: 'Roger Hui'

NB. =========================================================
Lab Section The Problem
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].
)
PREPARE
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 ])
PREPARE

NB. =========================================================
Lab Section
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.
)

NB. =========================================================
Lab Section 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.
)

NB. =========================================================
Lab Section Input & Output
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 hour one 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.
)

NB. =========================================================
Lab Section 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:

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.

After 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.
)
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. =========================================================
Lab Section Internal Workings of the Clock
The following examples illustrate the internal workings of the algorithm:
)
days 45
] s=:init 45        NB. Initial state for 45 balls (m;v;h;qu)
f1m s               NB. After 1 minute
f5m s               NB. After 5 minutes
f1h s               NB. After 1 hour
f5m^:6 s            NB. After 30 minutes
f1m^:2 f5m^:6 f1h^:5 s  NB. After 5 hours and 32 minutes
] p=: perm 45       NB. The queue after 12 hours for 45 balls
C. p                NB. Cycles of this permutation
#&>C. p             NB. Cycle lengths
*./ #&>C. p         NB. LCM of cycle lengths
days 45             NB. # days is half the # of 12-hour periods

NB. =========================================================
Lab Section 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
] c0=: 0{C. p
] c1=: 1{C. p
(>c0){q
(>c1){q
{:>c0
{:>c1
1 3 5 7 i. 5
4 6 8 9 0 2 i. 8
] m0=: #>c0
] m1=: #>c1
_1+m0-((>c0){q)i.{:>c0
_1+m1-((>c1){q)i.{:>c1

NB. =========================================================
Lab Section Moduli & Residue
The preceding computations can be encapsulated as below. 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.
)
assert=: 13!:8@(12"_)^:-.
res1  =: <:@#@[ - { i. {:@[
chkr  =: [: assert { -: res1 |. [
res   =: res1 [ chkr
mr    =: #&>@[ ,. (res&> <)

(>c0) res q         NB. Residue in cycle 0
(>c1) res q         NB. Residue in cycle 1
(C. p) mr q         NB. Moduli and residues

NB. mr signals error if the right argument is not a power
NB. of the left argument, as in  (C. p) mr i.-10

NB. =========================================================
Lab Section
Euclid devised his algorithm for computing the GCD in 300 B.C.  The algorithm produces a and b such that (m+.n)= (a*m)+b*n, that is, the GCD of m and n as a linear combination of them.  The algorithm operates by repeated remaindering.

The verb "it" applies to a 2-by-3 matrix:  column 0 are the two current remainders; columns 1 and 2 are the corresp- onding 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.
)
g0  =: , ,. =@i.@2:
it  =: {: ,: {. - {: * <.@%&{./
gcd =: (}.@{.) @ (it^:(*@{.@{:)^:_) @ g0

32 gcd 44           NB. GCD as coefficients
+/32 44 * 32 gcd 44 NB. The actual GCD
] a=: 32 g0 44      NB. Initial argument for GCD
it a                NB. One iteration
it it a             NB. Two iterations
<"2 it^:(i.6) a     NB. All iterations; stop when 0= lower left corner
it^:(*@{.@{:)^:_ a

NB. =========================================================
Lab Section Chinese Remainder
Sun Tsu devised the so-called Chinese Remainder algorithm in 350 A.D.  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.  cr is a verb such that (m,r)cr(n,s) produces (m*.n),d.  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; produces (LCM, remainder)
4|9            NB. Verify residue 0
6|9            NB. Verify residue 1
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
] q=: c0 C. i.10 NB. One application of cycle c0
(C. p) mr q    NB. Moduli and residues
4 1 cr1 6 0    NB. Chinese remainder says answer is 3,
               NB. but 1~:4|3 and 0~:6|3
4 1 cr 6 0     NB. Chinese remainder with built-in check

NB. =========================================================
Lab Section pow and log
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
p log p
p log p{p
p log p{p{p
p log p pow 3
] c=: C. p        NB. The cycles of p
ord p             NB. The order of p; LCM of the cycle lengths
p log /:p         NB. The log of the inverse is 1 less than the order
] q=: p pow 38    NB. A power of p
p log q
c mr q            NB. Moduli and residues of q in each cycle
cr/ c mr q        NB. Order & log by repeated Chinese Remainder
{: cr/ c mr q     NB. Select last item
k -: p log"1 p pow"1 0 k=.i.ord p  NB. Verify all powers
p log ?~#p        NB. A random perm. is unlikely to be a power
                  NB. (probability (ord p)%!#p )

NB. =========================================================
Lab Section
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              NB. Set random seed to 16807
p=: ?~300              NB. A random permutation of length 300
c=: C. p               NB. The cycles of p
#&> c                  NB. Cycle lengths
ord p                  NB. Order (LCM of cycle lengths)
] k=: ?ord p           NB. A random power
(#&>c)|k               NB. The residues of k modulo the cycle lengths
(p pow k) -: (i.#p) C.~ ((#&>c)|k)#c  NB. Apply each cycle the residue # of times
(/:p) -: p pow _1      NB. Works on all integer powers
(i.#p) -: p pow 0
(p pow j) -: p pow n+j=.?n=.ord p
pow1=: {^:(]`(i.@#@[)) NB. Alternative definition p&{^:k i.#p
timer=: 6!:2
timer 'q0=.p pow k'
timer 'q1=.p pow1 k'
q0 -: q1
timer 'j=.p log q0'    NB. compare with the time for pow
j=k

NB. =========================================================
Lab Section 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.: The Ball Clock Problem, Vector, Volume 12, Number 2, 1995 10.

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.
)
