Challenge: ACM Ball Clock Problem
Jim Weigang
clock mechanism:
{del} Z{<-}ACMBALLS N;H;M;Q;R
[1] @Brute-force solution for the ACM Ball Clock Contest
[2] @ N is the number of balls in the clock
[3] @ Z is the number of days before the balls return to the original order
[4] @
[5] Q{<-}R{<-}{iota}N @ the ball queue, and a reference copy
[6] Z{<-}0 @ day counter
[7] M{<-}H{<-}{iota}0 @ 5-minute and hour tracks
[8] L1: @ Loop for each five-minute period
[9] M{<-}M,Q[5] @ add 5th ball to the 5-minute track
[10] Q{<-}(5{drop}Q),{reverse}4{take}Q @ requeue the other 1-minute balls
[11] {->}(12>{rho}M)/L1 @ If 12 balls in the 5-min track,
[12] H{<-}H,{neg}1{take}M @ move the last ball onto the hour track
[13] Q{<-}Q,{reverse}{neg}1{drop}M @ requeue the other 5-min balls
[14] M{<-}{iota}0 @ empty the 5-min track
[15] {->}(12>{rho}H)/L1 @ If 11 moveable balls in the hour track,
[16] Q{<-}Q,1{rotate}{reverse}H @ requeue the hour balls
[17] H{<-}{iota}0 @ empty the hour track
[18] Z{<-}Z+.5 @ another half-day has passed
[19] {->}(Q{match}R)/0 @ quit if balls are in original order
[20] {->}L1 @ Endloop
{del}
But this runs quite slowly, and the run time is proportional to the
number of days in the cycle. (It took 63 seconds to return 378 days for
ACMBALLS 30.) Tom Chwastyk had said in his posting that his program ran
in about a quarter of a second, so I realized there must be a better
algorithm. I put a stop on line [20] and looked at how the balls were
rearranged after 12 hours. Quite a jumble. But after a little thought,
I realized that the shuffle pattern would be the same for every 12 hour
period. So after computing the first 12 hours by brute force, the queue
could be stepped through additional 12-hour periods using Q{<-}Q[P],
where P is the shuffle pattern. This led to ACMBALLS2, which is like
ACMBALLS except for the following lines:
[17]
[18] @ Phase 2: Apply the 12-hour permutation repeatedly until the
[19] @ balls return to their original order.
[20] Z{<-}.5 @ day counter
[21] P{<-}Q @ 12-hour permutation
[22] L2:{->}(Q{match}R)/0 @ Loop until balls are in order
[23] Q{<-}Q[P] @ give 'em a days worth of shuffling
[24] Z{<-}Z+.5 @ bump the day counter
[25] {->}L2 @ Endloop
This version was fast enough (.33 seconds for 45 balls) that I was able
to compute the answers for all arguments from 27 to 127. But even this
version took 83 seconds to compute the answer for 123 balls (108,855
days). While I was waiting, I wondered if I could apply more than one
permutation at once. The problem statement said the answer would be an
even number of days, so I could "double" P (i.e., P{<-}P[P]) and use it
to cut the number of Q{<-}Q[P] iterations in half. But could I
quadruple P? Could I use a bisection algorithm, doubling the power of P
each time? If I did this, how could I tell if I passed the solution?
I thought about how an individual ball moves through the queue from
one 12-hour period to the next. Consider the following permutation:
5 6 4 1 3 7 2 P
1 2 3 4 5 6 7 {iota}{rho}P
Ball 1 moves to the 4th position after 12 hours (look for 1 in P and
read the new position in the iota vector below). Then, as new ball 4,
it moves to the 3rd position, then to the 5th position, and finally it
returns to the first position, a cycle of four 12-hour periods. Ball 2
moves to positions 7, 6, and back to 2, a cycle of three 12-hour
periods. This permutation has cycles of length 4 and 3, so I could
safely raise P to the 4th power (permutation-wise) or to the 3rd power,
or to the least common multiple of 4 and 3.
A little more thought along these lines lead to a big Ah-Ha!, and I
realized that the least common multiple of the cycle lengths was
actually the answer to the problem (though expressed in 12-hour rather
than 24-hour periods). After N periods, where N is the least common
multiple of the permutation cycle lengths, all the cycles will be
simultaneously completed and all the balls will be back in their
original order in the queue. I put together a simple cycle length
calculator, found an algorithm for LCM in Paul Berry's Sharp APL
Reference Manual, and came up with the following solution:
{del} Z{<-}ACMBALLS3 N;H;I;L;M;Q;R
[1] @A very fast solution for the ACM Ball Clock Contest
[2] @ N is the number of balls in the clock
[3] @ Z is the number of days before the balls return to the original order
[4] @
[5] Q{<-}R{<-}{iota}N @ the ball queue, and a reference copy
[6] M{<-}H{<-}{iota}0 @ 5-minute and hour tracks
[7] I{<-}0
[8] L1: @ Loop for each five-minute period
[9] M{<-}M,Q[5] @ add 5th ball to the 5-minute track
[10] Q{<-}(5{drop}Q),{reverse}4{take}Q @ requeue the other 1-minute balls
[11] {->}(12>{rho}M)/L1 @ If 12 balls in the 5-min track,
[12] H{<-}H,{neg}1{take}M @ move the last ball onto the hour track
[13] Q{<-}Q,{reverse}{neg}1{drop}M @ requeue the other 5-min balls
[14] M{<-}{iota}0 @ empty the 5-min track
[15] {->}(12>{rho}H)/L1 @ If 11 moveable balls in the hour track,
[16] Q{<-}Q,1{rotate}{reverse}H @ requeue the hour balls
[17]
[18] @ Phase 2: Analyze the 12-hour permutation vector
[19] L{<-}CYCLES Q @ length of the cycles in the permutation
[20] Z{<-}.5{times}LCM/L @ number of days before repetition
{del}
{del} Z{<-}CYCLES P;B;I;L;N;S
[1] @Returns the lengths of cycles in permutation vector {omega}
[2] B{<-}(N{<-}{rho}P){rho}0 @ 1s will mark elements we've visited
[3] Z{<-}{iota}0
[4] L1:{->}(N<I{<-}B{iota}0)/0 @ Loop for each cycle
[5] L{<-}0 @ length counter
[6] B[S{<-}I]{<-}1 @ mark start as visited
[7] L2:I{<-}P[I] @ next item in cycle
[8] B[I]{<-}1 @ mark it as visited
[9] L{<-}L+1 @ bump the length
[10] {->}(I{/=}S)/L2 @ repeat unless at start
[11] Z{<-}Z,L @ remember the length
[12] {->}L1 @ Endloop
{del}
{del} Z{<-}A LCM B
[1] @Least common multiple of {alpha} and {omega}
[2] Z{<-}A{times}B{divide}A GCD B
{del}
{del} Z{<-}A GCD B
[1] @Greatest common denominator of {alpha} and {omega} using Euclid's {+
+}algorithm
[2] Z{<-}|A
[3] {->}(0=A|B)/0
[4] Z{<-}(A|B)GCD A
{del}
(The LCM-reduction on line [20] of ACMBALLS3 would be done with a simple
loop in a non-nested APL.) This version runs nice and fast: 13 seconds
for ACMBALLS3{each}26+{iota}101.
Elapsed time between obtaining the problem description and finishing
the last program: 2.5 hours. Of course, without Tom Chwastyk's
encouragement, I might never have realized that a faster solution was
possible.
Jim
Jim Weigang
follow in the next message.
* * * *
From the 1995 ACM Contest Finals sponsored by Microsoft:
CLOCK
Tempus et mobilius
Time and motion
INPUT FILE: CLOCK.IN
Tempus est mensura motus rerum mobilium.
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.
* * * *
Roger Hui
The following is a solution in J for the ball clock problem:
m =. >@(0&{) NB. minute track
v =. >@(1&{) NB. 5-minute track
h =. >@(2&{) NB. hour track
q =. >@(3&{) NB. queue
z =. i.@0: NB. empty
ret =. |.@}: NB. return to queue
init =. z;z;z;i. NB. initial configuration
f1m =. (m,{.@q);v;h;}.@q NB. every minute
f5m =. (z;(v,{:@m);h;q,ret@m) @ (f1m^:5) NB. every 5 minutes
f1h =. (z;z;(h,{:@v);(q,ret@v)) @ (f5m^:12) NB. every hour
f12h =. (z;z;z;q,ret@h,{:@h) @ (f1h^:12) NB. every 12 hours
perm =. q @ f12h @ init NB. queue after 12 hours
order =. *./ @ (#&>"_) @ C. NB. the order of a permutation
days =. -: @ order @ perm NB. ball clock solution
The basic data structure is a 4-element list of boxes (m;v;h;q)
of the balls in the minute, 5-minute, and hour tracks and the queue.
Verb "init" initializes the clock: all tracks are empty and all balls
are in the queue. Verb "f1m" models the clock action every minute.
Verb "f5m" models the clock action every 5 minutes, including the
action every minute. Similarly for verbs "f1h" and "f12h".
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
on 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.
(The monad C. produces boxed cycles from a permutation and vice versa;
the dyad *. computes the LCM of the arguments.)
An advantage of this functional solution is that one can readily
interrogate intermediate results of the computation. Thus:
days 45
378
[s=.init 45 NB. (m;v;h;q) initial state for 45 balls
++++-----------------------------------------------------------------------+
||||0 1 2 3 4 5 6 7 8 9 10 11 12 ... 32 33 34 35 36 37 38 39 40 41 42 43 44|
++++-----------------------------------------------------------------------+
f1m s NB. (m;v;h;q) after 1 minute
+-+++---------------------------------------------------------------------+
|0|||1 2 3 4 5 6 7 8 9 10 11 12 ... 32 33 34 35 36 37 38 39 40 41 42 43 44|
+-+++---------------------------------------------------------------------+
f5m s NB. (m;v;h;q) after 5 minutes
++-++------------------------------------------------------------------+
||4||5 6 7 8 9 10 11 12 13 14 15 ... 36 37 38 39 40 41 42 43 44 3 2 1 0|
++-++------------------------------------------------------------------+
f1h s NB. (m;v;h;q) after 1 hour
+++--+------------------------------------------------------------------
|||16|15 23 22 21 20 28 27 26 25 33 32 31 30 38 37 36 35 43 42 41 40 0 1 ...
+++--+------------------------------------------------------------------
f5m^:6 s NB. (m;v;h;q) after 30 minutes
++---------------++-----------------------------------------------------
||4 9 14 19 24 29||30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 3 2 1 0 ...
++---------------++-----------------------------------------------------
f1m^:2 f5m^:6 f1h^:5 s NB. (m;v;h;q) after 5 hours and 32 minutes
+----+--------------+-------------+-------------------------------------
|21 2|8 24 4 5 43 11|16 36 22 1 23|32 41 33 17 26 25 14 6 18 40 20 31 37 ...
+----+--------------+-------------+-------------------------------------
[ p =. perm 45 NB. the queue after 12 hours
25 30 0 24 35 2 44 33 15 19 13 6 29 43 8 26 40 31 12 7 38 ...
_5[\p
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 12 29 39 23|43 16 40 1 30 4 35 34 17 31 21 28 ...
+----------+--------------------+----------------------------------
,.C. p NB. 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 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
Roger Hui
<3l5cbt$n...@nic.umass.edu>
<1995032809...@yrloc2.tor.soliton.com>
I am amused to note that the Clock Challenge has a rather
fundamental flaw: it doesn't solve the problem stated in the
preamble, namely, *** What Time Is It ***? Accordingly:
Clock Challenge II: The clock operates as described below.
The current reading is given as a 4-tuple (m;v;h;q), where
m, v, h, and q, are integer vectors representing the minute track,
the 5-minute track, the hour track, and the queue. Assume the
clock has not yet cycled through all possible settings for the
number of balls. The Challenge is to compute the current time as
a 3-element integer list of the days, hours (0 to 23), and minutes.
If the argument (m;v;h;q) does not represent a legal state (or a
legal clock), the answer should be _1 (negative 1). The fixed ball
in the hour track is ignored in the argument tuple (m;v;h;q).
--------------
Operation of the Ball Clock, quoted from Jim Weigang's msg
<3l5c6g$n...@nic.umass.edu> posted Monday, 1995-3-27 03:42:08 GMT:
Randy A MacDonald
Roger Hui <h...@Soliton.COM> writes
> The following is a solution in J for the ball clock problem:
...
Do you have an estimate of your construction time.
Later...
---------------------------------------------------------------------
|\/| Randy A MacDonald |"You just ASK them?"
|\\| ra...@godin.on.ca | Richard P. Feynman
BSc(Math) UNBF '83 | APL: If you can say it, it's done.
Natural Born APL'er | *** GLi Info: in...@godin.on.ca ***
------------------------------------------------------------{ gnat }-
Randy A MacDonald
References: <1995032814...@yrloc2.tor.soliton.com>
Roger Hui <h...@Soliton.COM> writes:
> I am amused to note that the Clock Challenge has a rather
> fundamental flaw: it doesn't solve the problem stated in the
> preamble, namely, *** What Time Is It ***? Accordingly:
You must have read another version of the problem.
> Clock Challenge II: The clock operates as described below.
> The current reading is given as a 4-tuple (m;v;h;q), where
> m, v, h, and q, are integer vectors representing the minute track,
> the 5-minute track, the hour track, and the queue. Assume the
> clock has not yet cycled through all possible settings for the
> number of balls. The Challenge is to compute the current time as
> a 3-element integer list of the days, hours (0 to 23), and minutes.
> If the argument (m;v;h;q) does not represent a legal state (or a
> legal clock), the answer should be _1 (negative 1). The fixed ball
> in the hour track is ignored in the argument tuple (m;v;h;q).
...given that only the brute force solution exists, this problem is
not that intersting. I spent 15 minutes elaborating on this, but
my mail software obliterated my notes.
Essentially. To get hours, trivial; minutes; simple; days, you subtract
the fractional part of the day, and "divide" (which really means, repeatedly
subtract) by the number of minutes in a day. Brute force, unless there
is a prime number somewhere, if my algebra memory serves me...