Roger and the Amazing Technicolor Ballclock
Vector 12:4, page 127
Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 127
This note arises from Roger Hui’s article on the Ball Clock Problem [1], and is addressed to readers who may have been overwhelmed by the amount of the material covered, the speed with which Roger swept through it, or possible difficulties in obtaining copies of the references.
It would be a pity if such readers were to miss out totally on some of the marvellous things which Roger sped through on his voyage to solve the ACM Programming Challenge, and so in the spirit of slow-lane J, I shall try to expound some of Roger’s nuggets in greater detail.
First, here is Roger’s basic suite of J verbs which I have not amended, except by re-ordering them in a hierarchical fashion, excluding references to the debug verb 13!:8, and adding the adverb each.
pow1=.{^:(]`(i.@#@[)) NB. perm x. raised to the power y.
pow=.i.@#@[ C.~(#&>@C.@[|])#C.@[ NB. alternative form of pow1
ord=.*./@(#&>"_)@C. NB. order of perm = gcd of cycle lengths
log=.{:@(cr/)@(C.@[ mr ]) NB. inverse of pow - logs are modulo ord
cr=.[:|/\*.&{. , ,&{: +/ .* ab NB. Chinese remainder algorithm
ab=.|.@(gcd/ * [%+./)@(,&{.)
gcd=.(}.@{.)@(it^:(*@{.@{:)^:_)@g0 NB. gcd in form (a,b) where gcd=ax.+by.
it=.{: ,: {. -{: * <.@%&{./
g0=., ,. =@i.@2:
mr=.#&>@[,.(res&><) NB. x.=C. a generating perm; y.=a perm
res=.<:@#@[-{i.{:@[ NB. each row of mr=#cycle,posns in cycle
each=.&>
This note is primarily about permutations. A permutation is an arrangement of objects, and this discussion will be restricted to those permutations which can be obtained by executing the expression n?n . A permutation is thus a vector such as the following which Roger used as part of his illustrations:
The verb C. converts a permutation into cycle notation thus
Cycle notation can be thought of as a "permutation process" that is C.p is a description of the process which generates the permutation p starting from i.10 in the following way. Regard p as a sequence of items numbered from 0 to 9, the first cycle should be read as follows:
position 7 is to contain item 1,
position 1 is to contain item 3,
position 3 is to contain item 5,
position 5 is to contain item 7, thereby completing the cycle.
Read the second cycle in the same way. The overall permutation process is the result of doing both these cycle operations at every step.
The cycles themselves are disjoint and exhaustive, and each cycle is rotated so that its largest item appears first. Also the boxed cycles are arranged in ascending order of their leading elements. All of this is detailed in the J dictionary, and it guarantees that the cycle representation of the permutation process is unique.
Repeating a permutation process n times can be alternatively described as raising the permutation to the power n. This is the basis of Roger’s two verbs pow and pow1. They both have the same function — pow should be easy to read and understand for anyone reasonably familiar with J; pow1 is a little less so, but is more efficient. Any permutation raised to the power 0 is i.n where n = #p .
Thus raising p to the power n is achieved by p pow n, and the results of raising it to the powers 0,1,..5 is
>(<p)pow each i.6
0 1 2 3 4 5 6 7 8 9
2 3 4 5 6 7 8 1 9 0
4 5 6 7 8 1 9 3 0 2
6 7 8 1 9 3 0 5 2 4
8 1 9 3 0 5 2 7 4 6
9 3 0 5 2 7 4 1 6 8
The columns headed 1 3 5 and 7 each contain these digits in repeated 4-cycles, and the remaining columns each contain the remaining digits in repeated 6-cycles. This means that whenever a power is reached which is a multiple of both 4 and 6 the permutation i.10 will recur. The smallest such power is 12, and more generally it is the least common denominator of the lengths of the cycles. This quantity is called the order of the permutation and is given by Roger’s function ord.
log p is the inverse of power adjusted to modulo ord p. It addresses the problem: given one of the rows of the above table, what is the power to which p must be raised to generate it. Again, Roger supplies the verb:
More generally
since 3 is the 12-remainder of 99. In mathematics this is expressed as 3≡99(mod 12); in J or APL as 3=12|99. Since permutations of n are obtained as a primitive verb in J, experimentation is extraordinarily easy, for example:
[u=.8?8
6 1 3 2 5 4 0 7
C.u
┌─┬───┬───┬───┬─┐
│1│3 2│5 4│6 0│7│
└─┴───┴───┴───┴─┘
>(<u)pow each i.8 NB. Table of 8 powers of p
0 1 2 3 4 5 6 7
6 1 3 2 5 4 0 7
... repeated four times
Roger uses an algorithm associated with the so-called Chinese remainder theorem. What this delivers is solutions to simultaneous congruences such as
x≡2(mod 3) x≡3(mod 5) x≡2(mod 7)
or, in simple English, it finds numbers which have remainders 2, 3 and 5 when divided by 3, 5 and 7 respectively. The verb which Roger supplies is called cr. If there are just two congruences, say the first two above, the solution is
that is, 8 is the smallest number whose remainders on division by 3 and 5 are 2 and 3 respectively, and the number formed by adding any multiple of 15 to 8 will also possess this property. If there are more than two congruences, use each:
so 23 and 128 are the smallest numbers satisfying all three congruences.
Thus equipped, problems such as the following, beloved of puzzle book writers, become trivial:
When eggs are removed from a basket 2,3,4,5,6 at a time, the numbers left eventually are 1,2,3,4,5 respectively, but when 7 eggs are removed at a time none are left over. How many eggs are there in the basket, given that there are less than 200?
17 pirates decided to divide the booty of gold coins, but when they did so, 3 coins were left over. In the ensuing brawl, one pirate was killed, so they started again. This time 10 coins were left over. Another pirate perished violently, and the remainder were able to share the coins equitably. What is the smallest number of coins they had to share?
The answers to the above are:
A condition for cr to deliver the correct answers is that the moduli of all the congruences must be co-prime in pairs. Roger demonstrates a test for this which depends on having the debug facility 13!:8 available.
Reference¶
[1] The Ball Clock Problem, Roger KW Hui, Vector Vol.12 No.2, pp. 56-66, 1995.