Clock Challenge II
Roger Hui
<3l5cbt$n...@nic.umass.edu>
<1995032809...@yrloc2.tor.soliton.com>
<1995032814...@yrloc2.tor.soliton.com>
The following is a key to solving Clock Challenge II.
Stop reading now if you wish to solve the problem yourself.
0. Clock Challenge II reduces to the problem of finding the
smallest non-negative power k such that q -: p&{^:k i.#p ,
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).
1. Find c=.C. p, the cycles of p.
2. Find where q is in each of the cycles. For example,
if p=.1 2 3 4 5 0, p consists of a single cycle and
q=.2 3 4 5 0 1 is "at 2" relative to the single cycle.
As a by-product, this step also determines whether q is
a power of p: the result of indexing a cycle into q must
be a rotation of the cycle.
The result of this step is a 2-column table t of pairs (m,r),
where m is a cycle length and r is the residue of k modulo m.
3. Write the dyad cr so that if z=.(m,r) cr (n,s), then z is
((m*.n),d), where r=m|d and s=n|d and d e.i.m*.n. d exists and
is unique by the Chinese Remainder Theorem. Then k=.{:cr/t.
Writing cr: The Euclidean GCD algorithm produces a and b such
that (m+.n)=(a*m)+b*n. Then d=.(m*.n)|(m+.n)%~(r*b*n)+s*a*m.
(m*.n is the LCM; m+.n is the GCD.)
According to "Concrete Mathematics" (Graham, Knuth, and Patashnik),
the Euclidean GCD algorithm is 2300 years old, and the Chinese
Remainder Theorem was discovered by Sun Tsu in 350 A.D.
The algorithm can be implemented in J as follows:
gcd =. 3 : 0 NB. (+./y)=+/y*gcd y
a=.1 0 [ m=.<.0{y.
b=.0 1 [ n=.<.1{y.
while. m do.
c=.a [ t=.m
a=.b-a*q [ m=.n-m*q=.<.n%m
b=.c [ n=.t
end.
)
ab =. |.@(gcd * [ % +./)@(,&{.) NB. coefficients for Chinese Remainder
cr =. [: |/\ *.&{. , ,&{: +/ .* ab NB. Chinese Remainder
wh =. >@[ (<:@#@[ - { i. {:@[) ] NB. c wh q index of q in cycle c
assert=. 0!:2@":^:-. NB. assert y signal error if 0=y
check =. [: assert (>@[{]) -: (wh|.>@[) NB. c check q 1 iff q is permissible
where =. wh [ check NB. c where q wh with validation
resid =. #&>@[ ,. where"0 1 NB. c resid q moduli and residues
exp =. {^:(]`(i.@#@[)) NB. p exp k p&{^:k i.#p
log =. {: @ (cr/) @ (C.@[ resid ]) NB. p log q q -: p exp p log q
The following examples illustrate the workings of the algorithm:
[ p=.?~27 NB. a random permutation
0 7 6 8 21 23 2 14 10 4 22 12 18 16 19 24 1 26 13 9 3 20 11 25 15 5 17
p log i.27
0
p log p
1
p log p{p
2
p log p{p{p
3
p log p exp 3
3
*./ #&> C. p NB. the order of p is the LCM of the cycle lengths
102
?102
96
[ q=. p exp 96 NB. a random power of p
0 22 2 14 16 5 6 11 19 13 9 21 20 8 12 15 10 17 3 18 7 1 4 23 24 25 26
p log q
96
[ c=.C. p NB. the cycles of p
+-+---+--------------------------------------------+-----+-------+-----+
|0|6 2|22 11 12 18 13 16 1 7 14 19 9 4 21 20 3 8 10|24 15|25 5 23|26 17|
+-+---+--------------------------------------------+-----+-------+-----+
c resid q NB. the index of q in each cycle
1 0
2 0
17 11
2 0
3 0
2 0
cr/c resid q
102 96
p log q
96
p log ?~27 NB. a random permutation is unlikely to be a power of p
0
0
|assertion failure
|[-1]
| p log?~27
p=.?~130 NB. another random permutation
#&> C. p NB. cycle lengths of p
1 7 9 2 20 19 72
*./ #&> C. p NB. the order of p is the LCM of cycle lengths
47880
?47880
31968
q=.p exp 31968 NB. a random power of p
timer=.6!:2
timer 'k=.p log q' NB. J2.05 running under Windows on 80486/50
0.27
k
31968