Recreational APL
Eugene McDonnell
June 1981

Solution

Pyramigram

In this puzzle ( APL Quote Quad 11 1, p. 30) you were asked to write a function pg which takes a scalar integer argument from 1 to 26 and which has for an argument of 5 a character-matrix result like this:

       q
      w q
     q e w
    r q w e
   q e r t w

In this, row i has i non-blank characters, adjacent rows differ by only one character, and the letters in each row are randomly permuted.

This puzzle (originated by Linda Alvord of Scotch Plains Fanwood High School, in Scotch Plains, New Jersey) was one of the most popular I have run. A wide variety of techniques was used in the solutions, and I will be able to give only highlights of these.

One strategy used recursion to form the array. In this, the bottom level of recursion forms the first of a randomly chosen vector of a characters into a (1 1)-matrix. Each succeeding level of recursion puts a column of blanks on either side of the result of the previous level, and places this matrix above a new row, formed by an appropriate manipulation of the first ⍵ characters of the random-character vector. The manipulation required is the permutation of these characters and then the use of an expansion vector. For example, in forming the fourth row, the character vector 'qwer' must be permuted to some random permutation, say 'rqwe' , and then expanded with blanks between the characters, as in 'r q w e' . An outer function pg is used which has the sole purpose of providing a permuted alphabet to the recursive inner function f :

pg: 'abcdefghijklmnopqrstuvwxyz'[26?26]f⍵ 
f:(' ',(⍺f⍵-1),' '),[1]((¯1+2×⍵)⍴1 0)\(⍵↑⍺)[⍵?⍵]:w=1:1 1⍴a

I was dismayed by the number of contestants who used ⎕av to form the vector of characters. There was no agreement among different systems as to the number of elements in ⎕av or the locations of the alphabetic characters therein. There is no requirement that the alphabetic characters be dense in ⎕av . There isn’t even agreement in the international community on how many alphabetic characters there are. There are legitimate uses for ⎕av but, for people who want to write transportable programs, generating an alphabet isn’t one of them.

A variant of the above program used numbers rather than characters in the inner function, and then translated the numbers to the appropriate characters in the outer function:

pg:(' ','abcdefghijklmnopqrstuvwxyz'[⍵?26])[1+f⍵] 
f:(0,(f⍵-1),0),[1]((¯l+2×⍵)⍴1 0)\⍵?⍵:⍵=1:1 1⍴1

There were many non-recursive solutions. Several of these were looping solutions, and these tended to be less elegant and less perspicuous than the non-looping solutions. Of the non-looping solutions, most were fairly straightforward attacks on the problem, sometime combined with a reasonable amount of ingenuity, and most were a pleasure to read. There was one, however, to which I must award the prize for the precise, spare, and direct means used to achieve its ends. This was contributed by Roger Hui. I’m going to try break it down for you piece by piece, going backwards from his solution to the way he may have arrived at it.

Let’s take the result as shown in the problem statement (I’ll show blanks as the ∘):

   ∘∘∘∘q∘∘∘∘
   ∘∘∘w∘q∘∘∘
   ∘∘q∘e∘w∘∘
   ∘r∘q∘w∘e∘
   q∘e∘r∘t∘w

Hui saw this first with the rows rotated so that they were right-justified:

   ∘∘∘∘∘∘∘∘q
   ∘∘∘∘∘∘w∘q
   ∘∘∘∘q∘e∘w
   ∘∘r∘q∘w∘e
   q∘e∘r∘t∘w

and then with the all-blank columns removed:

   ∘∘∘∘q
   ∘∘∘wq
   ∘∘qew
   ∘rqwe
   qertw

   ∘∘∘∘q∘∘∘wq∘∘qew∘rqweqertw              (1)

Now the really difficult part arose. He needed to find a way to permute the subfields of this vector as if they had each been generated by a use of the deal function. We’ll have to work toward this point from the other end. He saw that it was easy enough to generate the five letters of the alphabet at random: the deal application 5?26 would produce the desired index values with which to subscript a vector of the alphabetic characters; in our example we would have the vector 'qwert' . This could be padded on the left with blanks, using ¯9↑ , giving '∘∘∘∘qwert' . An excess-width (5 10)-reshape would put these in staggered form in a matrix, giving:

   ∘∘∘∘qwert∘
   ∘∘∘qwert∘∘
   ∘∘qwert∘∘∘
   ∘qwert∘∘∘∘
   qwert∘∘∘∘q

   ∘∘∘∘q
   ∘∘∘qw
   ∘∘qwe
   ∘qwer
   qwert

   ∘∘∘∘q∘∘∘qw∘∘qwe∘qwerqwert

Comparing this vector with the earlier vector (1) we see that they differ only in the arrangement of the elements in the subfields. Hui needed some way to permute just those elements among themselves.

It is easy enough to permute all twenty-five elements of a vector, with 25?25 ; the problem is to partition the elements in some way so that those intended for the same row stay together. A standard technique for accomplishing this is to add the same amount to each index value that is to be kept with its neighbors, in such a way that elements intended for the same row are kept from being associated with elements meant for another row.

A small illustration should make this clear. Suppose we wish to permute each row of a (3 4)-matrix. We can generate a random permutation of twelve elements with 12?12 :

   10 3 1 12  4 2 5 11  7 9 8 6

The extra blank between groups of four shows where we want the partitioning. The maximum value in this random permutation is, of course, 12. If we add 12 to the first four elements, 24 to the next four, and 36 to the next four, we will have essentially partitioned the set of indices:

   22 15 13 24  28 26 29 35  43 45 44 42

If we upgrade this we will get:

   3 2 1 4  6 5 7 8  12 9 11 10

and this can be applied to the ravel of the original matrix to give us the desired row permutations, after a reshape. Notice that each group of four is still intact in the upgrade vector.

Hui had the problem, however, that there are blanks in the rows which must not interfere with the permutation of the non-blank characters. In effect, the rows are already partitioned into a blank and a non-blank portion. Here is where Hui’s ingenuity rose to the level of the master stroke. He conceived of each line as consisting of two parts, blank and non-blank, and decided to extend the technique I’ve just described to those parts, which are not uniform in length. In the case of our five-row result the blank/non-blank portions have lengths:

   4 1  3 2  2 3  1 4  0 5

If this vector were available, the replicate function (available on several APL systems as an extension of compression: 2 1 0 3/'abcd' ←→ 'aabddd') could be used on the vector (⍳10)×25 , or:

   25 50 75 100 125 150 175 200 225 250

to give the vector to be added to the result of 25?25 . This replication vector Hui generated by:

   -\(⌽⍳5+5)-5+?1

This has to be taken apart piece by piece to make it clear. The (⌽⍳5+5)-5+?1 gives:

   4 3 2 1 0 ¯1 ¯2 ¯3 ¯4 ¯5

The +?1 makes the expression origin-independent. The key insight is that minus-scan can be used on this to generate the desired left argument to replicate:

   -\4 3 2 1 0 ¯1 ¯2 ¯3 ¯4 ¯5
4 1 3 2 2 3 1 4 0 5

With all this behind you, it should now be possible for you to read and enjoy Hui’s entire function:

pg:(⌽(⍳⍵)-?1)⌽((⍵+⍵-1)⍴1 0)\(⍵,⍵)⍴(,(⍵,⍵)↑(⍵,⍵+⍵)⍴(1-⍵+⍵)↑
  'abcdefghijklmnopqrstuvwxyz'[⍵?26])
  [⍋((⍵×⍵)?⍵×⍵)+(-\(⌽⍳⍵+⍵)-⍵+?1)/(⍳⍵+⍵)×⍵×⍵]

I’d like to thank all of those who sent in entries:

Many of the entries sent in by these contestants deserve more than just a passing mention, perhaps in a later column, but time and space do not permit it now.

Puzzle

Gypsy Math

The Rhind papyrus is one of the oldest mathematical texts in existence. It begins with a table which shows, for each odd integer ⍵ from 3 to 101, several integers whose reciprocals sum to 2÷⍵ . For example, (2÷17)=+/÷9 153  .

Write a function f such that, for odd positive argument ⍵ :

   (2÷⍵)=+/f⍵
   2=⍴f⍵
   ~⍵∊f⍵ 

Thus, f 17 ←→ 9 153 .

(The solution is not unique unless you restrict the length of the result in this way, or choose instead to minimize its maximum or sum. For historical background, see James R. Newman, “The Rhind Papyrus”, in The World of Mathematics, Simon and Schuster, New York (1956) pp. 169-178.)

Puzzle

Big Five

What is the largest real value for which you can find a representation (independently of particular implementation) by an APL expression of five or fewer characters? (Suggested by Roger Hui.)

Puzzle

Boggle

The letter game of Boggle (TM) is played with a square matrix of four rows. Two squares are connected if they touch at an edge or a corner. Sixteen dice, with a letter on each surface, are shaken and allowed to fall in the cells of the matrix. The object is to find words of four or more letters in paths of connected squares, using only the letter on the upper surface of each die only, and at most once per word.

(Suggested by Robert Ashworth, Carbondale, Illinois.)

First appeared in APL Quote-Quad, Volume 11, Number 4, 1981-06. The text requires the APL385 Unicode font, which can be downloaded from http://www.vector.org.uk/resource/apl385.ttf . To resolve (or at least explain) problems with displaying APL characters see http://www.vector.org.uk/archive/display.htm .

last updated: 2009-07-20 14:35