Essays/The Ball Clock Problem

From J Wiki
Jump to: navigation, search

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.