Simply A-maze-ing

maze

One of many things I like about APL is that it’s fun to use for recreational computing. I will frequently happen upon an interesting problem, puzzle, or piece of code and consider how I might implement it in APL.

I was thinking about how to generate mazes for an idea I have about a game to help kids learn APL (that may be a topic for a future blog entry). Anyhow, I found an interesting web page about maze generating algorithms where the author found one, the “Growing Tree Algorithm“, to be of particular interest. His page included roughly 100 lines Ruby code to implement the algorithm. The algorithm can be boiled down to:

  • Seed a list of visited cells with a cell selected at random
  • While there are unvisited cells
    • If the current cell has any unvisited neighboring cells
      • Select one at random
      • Remove the wall between the cells
      • Add the new cell to the list of visited cells
    • Otherwise backtrack (drop from the visited cell list) until you find a cell with an unvisited neighbor

Here’s a clip of the algorithm implemented in APL building a 10×10 maze.
Notice how whenever it hits a “dead end” it backtracks to the last cell that hasn’t been visited.

What might an APL approach to this algorithm look like? How to represent the maze? My first thought was to separate the maze generation from the drawing. After an hour (or so ;-) ) of tinkering, I’d come up with something that seemed to work pretty well and took about a dozen lines of code.

When I originally thought about writing this blog entry, I was going to launch into a discussion of the code and I realized that it might get lengthy and (egad!) boring. So instead, I’ll highlight a couple of the clever bits, show you the core maze generation code, and point you at the complete namespace for your own amusement and experimentation.

First the clever bits (at least I hope they’re clever)…

  • Represent the cells of the maze as an integer matrix where each element is an encoding of the walls surrounding each cell.  Use powers of 2 for the encoding.
  • Precalculate the indices of the neighboring cells around each cell so the core loop only has to use indexing and no on-the-fly computation.
  • Write a function to remove the common wall between two cells. I originally named the function “Reagan” (after President Reagan’s 1987 exhortation “Mr. Gorbachev, tear down this wall”), but in the spirit of political mindfulness, I renamed it “dewall”.

The core code for the maze generation looks like this:

∇ cells←maze size;valid;neighbors;dewall;visited;current;n;choices;next
 ⍝ Maze - modeled from http://weblog.jamisbuck.org/2011/1/27/maze-generation-growing-tree-algorithm
 ⍝ BPB  - Dec2014
 ⍝ size  - size of the maze in rows/cols
 ⍝ cells   - (2⍴size) integer matrix describing the walls around each cell using powers of 2
 ⍝       1
 ⍝     ┌───┐         ┌───┐
 ⍝   8 │   │ 2       │   │ = 11 = 1 + 2 + 8
 ⍝     └───┘
 ⍝       4
  size←2⍴size  ⍝ set size to square if singleton supplied as argument     

  valid←{{⍵/⍨⍵≢¨⊂⍬}size∘{(0∊⍵)⍱⍵∨.>⍺:⍵ ⋄ ⍬}¨⍵} ⍝ determine if a maze coordinate is valid
  neighbors←valid¨↓(⍳size)∘.+,1 ¯1∘.×1 0⌽¨⊂1 0 ⍝ calculate neighbors for each cell
     
  dewall←{{⍵[2]=0:{(1=⍵)⌽4 1}⍵[1] ⋄ {(1=⍵)⌽2 8}⍵[2]}⍺-⍵}  ⍝ remove wall between cells
     
  cells←size⍴15 ⍝ all cells start with 4 walls
     
  visited←,⊂?size ⍝ random starting cell
     
  :While 15∊cells       ⍝ while we still have cells to examine
      current←1↑visited   ⍝ pop the most recent cell
      :If 0=n←⍴choices←cells{⍵/⍨15=⍺[⍵]}current⊃neighbors ⍝ does it have any unvisited neighbors?
          visited↓⍨←1       ⍝ if none, backtrack
      :Else
          visited,⍨←next←choices[?n] ⍝ otherwise, add the new cell to the front of the list
          cells[next current]-←⊃next⊃.dewall current ⍝ update cell values for which wall was removed
      :EndIf
  :EndWhile
∇

You can get all the code in my maze generating namespace from GitHub. Save a local copy and use the SALT Load command to load it into your workspace, or just cut and paste it into your own namespace script with the editor. The maze namespace contains the following functions of interest:

 

      intmat←{animate} maze size
  • animate is an optional Boolean to indicate whether to animate the maze generation
  • size is the size (rows,cols) of the maze to generate; a single number generates a square maze
  • intmat is the integer matrix representation of the maze

For example: mat←1 maze 10 animates and generates a 10×10 maze

 

      z←{line} draw intmat
  • line is an optional Boolean that indicates:
    • 1 = use line-drawing characters
    • 0 = use ASCII characters
  • intmat is an integer matrix representation of a maze
  • z is the drawing of the maze in ASCII or line-drawing characters

For example: pic←1 draw mat produces a line-drawing of the maze generated in the example above

 

      z←html intmat
  • intmat is an integer matrix representation of a maze
  • z is the HTML necessary to render the maze in a web browser. Save it to a native file and open the file in your browser.

For example: h←html mat produces an HTML representation of the maze generated in the example above

 

Solving the 2014 APL Problem Solving Competition – It’s All Right

This post is the continuation of the series where we examine some of the problems selected for the 2014 APL Problem Solving Competition.

The problems presented in Phase 1 of the competition were selected because they could be solved succinctly, generally in a single line of APL code. This makes them well suited for experimentation on TryAPL.org.

pythProblem 1 of Phase 1, entitled “It’s all right” reads,

“Write a dfn that takes the length of the legs of a triangle as its left argument, and the length of the hypotenuse as its right argument and returns 1 if the triangle is a right triangle, 0 otherwise.”

Test cases:
      3 4 {your_solution} 5
1
      2 3 {your_solution} 4
0

This uses the Pythagorean theorem – A² + B² = C². It’s trivial to implement an almost direct translation of this in APL – in a dfn, using ⍺[1] for A, ⍺[2] for B and for C yields:

right←{((⍺[1]*2)+(⍺[2]*2))=⍵*2}

This seems rather clunky though… what if we consider the problem as “Are the sums of the squares of each argument equal?” To get the sum of the squares, first we can use the composition *∘2 (composing the power function * with the constant 2) to mean “square” and +/ to mean “sum”, and combine them in a 2-item function train (also known as an “atop”): ((+/)*∘2)

then apply this to each argument:   ((+/)*∘2)¨⍺ ⍵

and compare the results for equality, resulting in the dfn:

right1←{=/((+/)*∘2)¨⍺ ⍵}

Still this seems clunky to me. Let’s see…squaring a number is just multiplying the number by itself, so, if we use the monadic commute operator with multiplication,   ×⍨
we get the equivalent of squaring. Then we can use that function in an inner product with addition to also get “sum of the squares”:   +.×⍨

The rest is essentially the same as in right1 above:

right2←{=/+.×⍨¨⍺ ⍵}

All three of these solutions solve the contest problem. The first one, right, is not commutative though – the legs of the triangle must be supplied as the left argument. However, right1 and right2 are commutative and the order of arguments is not significant.

Foo, Shmoo

“We do not realize what tremendous power the structure of an habitual language has. It is not an exaggeration to say that it enslaves us through the mechanism of s[emantic] r[eactions] and that the structure which a language exhibits, and impresses upon us unconsciously, is automatically projected upon the world around us.”
—Korzybski (1930) in Science & Sanity p. 90

I’m trying to train myself to choose nouns as names for my functions, in the hope that doing so will help to free me from the procedural mindset, which was pervasive when I learned to program. In those days, coding concentrated more or less exclusively on the manipulation of state and only rarely on the construction of definitions. In saying this, I’m distinguishing procedures, which legitimately deal in state, from functions, which don’t. Transitive verbs: print, init, reverse(vt), … make good names for procedures.

Many of APL’s primitive monadic functions have nouns as names: floor, reciprocal, reverse(n), shape, …

Except this doesn’t quite work. Each of these names seems to need an “of” when applied to an argument, where the of seems to bind to the word that follows it:

   ⌊÷blah   ⍝ "floor of reciprocal of blah"

I’ve seen dyadic iota documented as index-of, though this grates a bit as “index of” isn’t a noun phrase in English. In fact, as far as I know, all of the romance languages would parse Richard of York as Richard (of York), where (of York) is a noun phrase in the genitive case: York’s Richard; Ricardus Eboracum. Nobody seems to parse it (Richard of) York.

So much for that idea for a blog post; ho hum; back to real work.

Then Nick Nickolov found a Wikipedia entry that suggested: “Some languages, such as the Cariban languages, can be said to have a possessed case, used to indicate the other party (the thing possessed) in a possession relationship”. So the (Richard of) parsing would work in one of the Cariban languages and isn’t therefore a property of any deep structure of language, per se.

Now when I see ceiling, I can still think of it as a noun, but in the possessed case. To emphasise this, for the rest of this posting, I’ll write my function names with a back-tick inflection to represent the case: reverse` meaning reverse-of.

   ⌊÷blah   ⍝ floor` reciprocal` blah

… and when reading my code, I can vocalise the ending with a slight [əv] or [ə] sound as in “Land’v plenty”, “Bagguh chips, please”, “Floor’v reciprocal’v blah”.

But what about dyadic functions? Glad you asked. The left argument of a function (arrays are naturally nouns) can be seen as a noun acting as determiner, technically a noun adjunctcoffee tablebicycle thiefcube root, noun adjunct, … Thus: 2-residue`, N-take`, zilde-reshape`⎕AV-index`

Practising this discipline has been quite illuminating: it has pushed me towards left argument currying. I now mentally parse ¯2⌽V as (¯2⌽)V the ((neg-two)-rotation`) V, where neg qualifies two, which in turn qualifies rotation`.

But surely 2+3 is just a symmetrical expression with respect to its arguments? Well yes, but we could also parse it as follows: Starting from the monadic successor` function 1∘+, the curried dyadic version 1+ would be the one-successor` and so 2+3 is the two-successor` three.

Now, how should we incorporate operators and their operands into this scheme? “The reverse` each` V“, where each` is functioning as a determiner?

PS: Choosing nouns for the names of functions shouldn’t be confused with J’s excellent taxonomy of language components using parts of speech, in which functions are labelled “verbs”.

PPS: Functions reverse`, successor`, shape`, … could also be seen as properties of their argument. A number N has many properties: its successor, its square-root, its floor, ceiling, prime-factorisation vector, … This is beginning to sound a bit like OO…

Changes of Heart

Karen Shaw started the ball rolling (hearts afluttering?) by asking Jay Foad to come up with a one-liner for St. Valentine’s Day; he then solicited contributions from the language development group. Nick Nickolov responded with the following, with no explanation other than that there is room for improvement:

⎕io←0 ⋄ (⊢,⌽)' X'[{(.5×n*2)>+/(⍺-.6×⍵)⍵*2}/¨0↓n-⍳(2×n),n←20]

           XXXXX        XXXXX           
         XXXXXXXXXX  XXXXXXXXXX         
        XXXXXXXXXXXXXXXXXXXXXXXX        
       XXXXXXXXXXXXXXXXXXXXXXXXXX       
       XXXXXXXXXXXXXXXXXXXXXXXXXX       
       XXXXXXXXXXXXXXXXXXXXXXXXXX       
      XXXXXXXXXXXXXXXXXXXXXXXXXXXX      
      XXXXXXXXXXXXXXXXXXXXXXXXXXXX      
      XXXXXXXXXXXXXXXXXXXXXXXXXXXX      
      XXXXXXXXXXXXXXXXXXXXXXXXXXXX      
       XXXXXXXXXXXXXXXXXXXXXXXXXX       
       XXXXXXXXXXXXXXXXXXXXXXXXXX       
       XXXXXXXXXXXXXXXXXXXXXXXXXX       
       XXXXXXXXXXXXXXXXXXXXXXXXXX       
        XXXXXXXXXXXXXXXXXXXXXXXX        
        XXXXXXXXXXXXXXXXXXXXXXXX        
        XXXXXXXXXXXXXXXXXXXXXXXX        
         XXXXXXXXXXXXXXXXXXXXXX         
         XXXXXXXXXXXXXXXXXXXXXX         
          XXXXXXXXXXXXXXXXXXXX          
           XXXXXXXXXXXXXXXXXX           
           XXXXXXXXXXXXXXXXXX           
            XXXXXXXXXXXXXXXX            
             XXXXXXXXXXXXXX             
             XXXXXXXXXXXXXX             
              XXXXXXXXXXXX              
               XXXXXXXXXX               
                XXXXXXXX                
                 XXXXXX                 
                   XX                   

Subsequently, Nick described how he derived the expression:

Between two meetings I saw Jay’s request for ideas. I sent him a link to the Heart Curve on MathWorld, but he thought we’d need graphics for that. To prove that ASCII art is good enough, I tried to plot the set of points (x,y) where (x2 + y2 – 1)3x2 y3 ≈ 0 but the interpreter crashed with a syserror for some reason. (I don’t recall what I last did and can’t reproduce it.) Since I had to type the whole thing again anyway and I hadn’t been too successful in visualising the solutions of the above equation, I decided to write it in a less beautiful but simpler way: draw half a circle, tilt it, and concatenate a mirror image to form a heart. The moment I got something that resembled a heart, I sent the email and went downstairs for coffee.

Meanwhile, I changed Nick’s expression in steps in the process of trying to understand it. ⎕io←0 throughout.

a.  (⊢,⌽)' X'[{(.5×n*2)>+/(⍺-.6×⍵)⍵*2}/¨0↓n-⍳(2×n),n←20]
Nick’s original expression.

b. ,∘⌽⍨' X'[{(.5×n*2)>+/(⍺-.6×⍵)⍵*2}/¨0↓n-⍳(2×n),n←20]
The fork (⊢,⌽) computes x,⌽x without use of a temporary variable. It is equivalent to ,∘⌽⍨.

c. ,∘⌽⍨' X'[{(.5×n*2)>+/(⍺-.6×⍵)⍵*2}/¨n-⍳(2×n),n←20]
The 0↓ is a no-op and is likely scaffolding left from the development process.

d. ,∘⌽⍨' X'[{(.5×n*2)>+/(⍺-.6×⍵)⍵*2}/¨n-⍳2 1×n←20]
(2×n),n←20 is equivalent to 2 1×n←20.

e. ,∘⌽⍨' X'[(.5×n*2)>{+/(⍺-.6×⍵)⍵*2}/¨n-⍳2 1×n←20]

The comparison with .5×n*2 is on the result of the {...} and is likely more efficient “outside” rather than explicitly applied to each scalar “inside”. More importantly, moving it outside avoids the use of a lexical global, an aesthetic infelicity (your opinion may differ).

At this step, it dawned on me that is applied to a 2-element vector, resulting in a 2×n by n matrix of 2-element integer vectors:

   ⍳2 1×n←20
┌───┬───┬───┬───┬───┬
│0 0│0 1│0 2│0 3│0 4│
├───┼───┼───┼───┼───┼
│1 0│1 1│1 2│1 3│1 4│ ...
├───┼───┼───┼───┼───┼
│2 0│2 1│2 2│2 3│2 4│
├───┼───┼───┼───┼───┼
│3 0│3 1│3 2│3 3│3 4│
├───┼───┼───┼───┼───┼
     ...

f. ,∘⌽⍨' X'[(.5×n*2)>⊃∘.{+/(⍺-.6×⍵)⍵*2}/n-⍳¨2 1×n←20]
The reduction on each 2-element vector is equivalent to an outer product; that is, f/¨⍳a,b is equivalent to ⊃∘.f/⍳¨a,b. Not much of a step forward but facilitates what comes next.

g. ,∘⌽⍨' X'[(.5×n*2)>(n-⍳2×n)∘.{+/(⍺-.6×⍵)⍵*2}n-⍳n←20]
Applying twice removes the reduction and makes the outer product more straightforward.

h. ,∘⌽⍨' X'[(n×*⍨.5)>(n-⍳2×n)∘.{|⍵+0j1×⍺-.6×⍵}n-⍳n←20]
The function {+/(⍺-.6×⍵)⍵*2} computes the sum-of-squares on ⍺-.6×⍵ and . It is equally the square of the magnitude of a complex number whose real and imaginary parts are the two expressions. The subsequent comparison to .5×n*2 has the same outcome if instead we compare the square root of both sides, that is, compare n×*⍨.5 and the magitude (not the square of the magnitude) of the complex number.

i. (⎕ucs 32 9829)[(n×*⍨.5)>i∘.{|⍵+0j1×⍺-.6×⍵}|i←n-⍳2×n←20]

A couple of ideas here: (0) Instead of using X in the picture, use the heart symbol, Unicode codepoint 9829. (1) Instead of creating half a heart and then stitching the two halves together with ,∘⌽⍨, the whole heart can be created using an appropriate right argument to the outer product.

This result differs slightly from the previous ones, but makes a prettier picture.

j. ' ♥'[(n×*⍨.5)>∘.(|1 ¯.6j1+.×,)∘|⍨n-⍳2×n←20]

I remembered that Unicode codepoints can be included directly in an APL expression, so ⎕ucs 32 9829 can be replaced by ' ♥'. (Much to my relief. Talk about lack of aesthetics!)

The arguments to the outer product are i and |i, and i can be eliminated altogether by doing f∘|⍨ instead of i f |i.

The function {|⍵+0j1×⍺-.6×⍵}, which computes the magnitude of a complex number, remains the same if the real and imaginary parts are switched, and in this case it is advantageous to switch them for brevity. Moreover, the computation can be coded as a train involving an inner product.

k. ' ♥'[(n×*⍨.5)>|∘.{⍺-⍵×.6j1}∘|⍨n-⍳2×n←20]
Sometimes, trains are better coded as dfns. The magnitude | is moved “outside”, and is unchanged if the complex coefficient is replaced by the negation of its conjugate and the operation changed from + to -.

l. ' ♥'[(n÷2*÷2)>|i∘.-.6j1×|i←n-⍳2×n←20]
The expression can be shortened by using the variable i after all (last seen in step i). Replace n×*⍨.5 by n÷2*÷2 and voilà, a retro expression without dfns, trains, or any of them new-fangled operators.

In summary

a.     (⊢,⌽)' X'[{(.5×n*2)>+/(⍺-.6×⍵)⍵*2}/¨0↓n-⍳(2×n),n←20]
b.     ,∘⌽⍨' X'[{(.5×n*2)>+/(⍺-.6×⍵)⍵*2}/¨0↓n-⍳(2×n),n←20]
c.     ,∘⌽⍨' X'[{(.5×n*2)>+/(⍺-.6×⍵)⍵*2}/¨n-⍳(2×n),n←20]
d.     ,∘⌽⍨' X'[{(.5×n*2)>+/(⍺-.6×⍵)⍵*2}/¨n-⍳2 1×n←20]
e.     ,∘⌽⍨' X'[(.5×n*2)>{+/(⍺-.6×⍵)⍵*2}/¨n-⍳2 1×n←20]
f.     ,∘⌽⍨' X'[(.5×n*2)>⊃∘.{+/(⍺-.6×⍵)⍵*2}/n-⍳¨2 1×n←20]
g.     ,∘⌽⍨' X'[(.5×n*2)>(n-⍳2×n)∘.{+/(⍺-.6×⍵)⍵*2}n-⍳n←20]
h.     ,∘⌽⍨' X'[(n×*⍨.5)>(n-⍳2×n)∘.{|⍵+0j1×⍺-.6×⍵}n-⍳n←20]
i.     (⎕ucs 32 9829)[(n×*⍨.5)>i∘.{|⍵+0j1×⍺-.6×⍵}|i←n-⍳2×n←20]
j.     ' ♥'[(n×*⍨.5)>∘.(|1 ¯.6j1+.×,)∘|⍨n-⍳2×n←20]
k.     ' ♥'[(n×*⍨.5)>|∘.{⍺-⍵×.6j1}∘|⍨n-⍳2×n←20]
l.     ' ♥'[(n÷2*÷2)>|i∘.-.6j1×|i←n-⍳2×n←20]

Zero-length Regular Expression Matches Considered Harmful

I was asked by a colleague why ⎕S reports two matches in the following example:

      ('\d*'⎕S 0 1)'321'
┌───┬───┐
│0 3│3 0│
└───┴───┘

Here we are asking for the position and length of sequences of zero or more digits in an input document containing three numeric characters. Intuitively there is just one match of all three characters from the start of the sequence, but ⎕S reports an additional match of zero characters at the end.

The short explanation is this: when there is a match in the input, the matching characters are “consumed” and searching continues from after them. In this example the first match consumes all three characters in the input, leaving it empty. Searching then resumes and, as the pattern matches the zero remaining characters, there is a second match.

If it seems odd that we search when the input is empty then consider the case where the input is empty to start with:

      ('\d*'⎕S 0 1)''
┌───┐
│0 0│
└───┘

In this case we should not be surprised there is a match – the pattern explicitly allows it and, indeed, we would have coded the search pattern differently, perhaps as '\d+', if that was not wanted. It is therefore correct and consistent that the first example matches zero characters as well.

My colleague was not yet convinced. In this case, he asked, why are there not an infinite number of matches at the end?

It’s a good question. Zero-length matches have to be treated specially by the search engine to prevent exactly that, wherever they appear. The rule used by the PCRE search engine, which Dyalog uses, is that any pattern that results in a zero-length match is prohibited from generating another zero-length match until more characters are consumed from the input. PCRE is widely used so this behaviour is commonplace, but other search engine implementations take a different view and simply consume a single character following a zero-length match to prevent the repetition.

That difference in the rules would not have affected our example but consider a slightly more complex search pattern containing alternatives – here, zero or more digits, or one word character:

      ('\d*|\w'⎕S 0 1)'x321'
┌───┬───┬───┬───┐
│0 0│0 1│1 3│4 0│
└───┴───┴───┴───┘

In this example the first match is of zero digits at the start of the input – that is, at offset zero and zero characters long. PCRE then resumes searching at offset zero but without allowing further zero-length matches. Consequently the first alternative pattern cannot match this time but the second can. The next match is therefore a single word character (the 'x'), also at the start of the input. The 'x' is consumed and searching resumes with '321' as the input where, as explained above, there are two further matches making four in total.

Search engines which simply consume a character after a zero-length match would give a different result. After the same initial match of zero characters at the start of the input they would consume the 'x' and resume searching at '321' to give two further matches and a total of only three.

So, patterns which allow zero-length matches appear to be counter-intuitive and the cause of incompatibilities with other search engines. Should we avoid '*' and other qualifiers which allow zero repetitions of a pattern? Of course not – used carefully they can be very effective.

Firstly, a pattern which allows a sequence of zero characters within it can still be constructed so that the overall match can never have a length of zero. For example, 'colou?r' allows zero or one 'u' characters after the second 'o' so that it matches both the British English spelling 'colour' and the American English spelling 'color' – but it never results in a zero-length match, and should never surprise anyone in the way it works.

Secondly, anchors can often be used to prevent those unintuitive extra matches. Anchors in search patterns don’t match actual characters – rather, they allow the match to succeed only at specific locations in the input. '^' and '$' mean the start and end of a line respectively which, used in our very first example, prevent anything from preceding or following a match within a line and exclude the zero-length sequence because it does not satisfy that requirement:

      ('^\d*$'⎕S 0 1)'321'
┌───┐
│0 3│
└───┘

Thirdly – it often doesn’t matter that zero-length matches occur. In this example the search pattern matches any character except newline zero or more times and we are asking for it to be folded to upper-case:

      ('.*' ⎕R '\u&') 'Hello there'
HELLO THERE

The first match is of all 11 characters which are folded to upper-case and replaced. Then is there a second match of zero characters at the end and this too is folded and replaced, having no further effect. You can see this is so by using a different replacement pattern:

      ('.*' ⎕R '[\u&]') 'Hello there'
[HELLO THERE][]

As an aside, a ⎕R search pattern constructed so that it has no visible effect at all can be very useful for doing a quick and simple read of a text file into the workspace. In this example:

      tieno←⎕NTIE 'input.txt'
      ''⎕R''⊢tieno

text is read from the file without modification into a vector of character vectors, one line per element. There are many search and replace patterns that could be used to do this but this is the shortest, and it makes use of zero-length matches and replacements.

Perhaps, after all, the title of this blog should have been “zero-length regex matches considered helpful“?

Further Reading

Further information about the Dyalog search and replace operators is available in the following documents:

Footnote

Edsger W. Dijkstra wrote a paper in 1968 for Communications of the ACM entitled a “Case against the GO TO Statement” but it was published as a letter under the title “The goto statement considered harmful”. “Considered harmful” became a popular phrase in articles written in response to this and in other unrelated papers. There is an article about the phrase in Wikipedia.

Dijkstra also wrote a 1975 paper in which he criticised a number of computer languages he had used. Of APL he said, “APL is a mistake, carried through to perfection. It is the language of the future for the programming techniques of the past: it creates a new generation of coding bums”.

This author is not afraid to use goto statements or APL.

Solving the 2014 APL Problem Solving Competition – Cryptography Problem 3

This post is the continuation of the series where we examine some of the problems selected for the 2014 APL Problem Solving Competition. In this post we’ll conclude looking at the cryptography problems from Phase II that we started looking at in a previous blog post and continued in a further blog post.

Cryptography Problem 3 – Playfair Cipher

Task 1 – Squaring Off

The first task is to convert a string into a 5×5 Playfair table. The solution makes straightforward use of APL primitives:

  • Unique () to remove duplicate characters from the string.
  • Without (~) to find the rest of the alphabetic characters that are not mentioned in the string, and again to remove the character J.
PlayfairTable←{
    k←∪⍵
    5 5⍴(k,⎕A~k)~'J'
}

Here it is in action:

      ⊢table←PlayfairTable'KENNETHEIVERSON'
KENTH
IVRSO
ABCDF
GLMPQ
UWXYZ

Task 2 – Encryption

To encrypt a message we need to take two characters at a time, find their coordinates in the 5×5 Playfair table, swap their column coordinates and look up the letters at the new coordinates. There are lots of tricks in the code below of which we’ll describe just a few:

  • To process the message two characters at a time, appending to the result as we go, we use a tail-recursive dfn whose left argument accumulates the result. For an introduction to this technique see this implementation of the Fibonacci function.
  • To find letters in the Playfair table we first look them up in the ravel (i.e. the linearised form) of the table, and then use Encode () to convert this linear index into a pair of coordinates. Decode () does the opposite, converting a pair of coordinates back into a linear index.
  • Mix () and Split () are used to convert between two different representations of the coordinates of the two characters we’re encoding: either as a flat 2×2 matrix, or as a nested 2-vector of 2-vectors. The choice of representation is largely a matter of taste, and it might be fun to play with this part of the code. You could tweak it to work entirely with the flat representation, or entirely with the nested representation, rather than converting back and forth between them.
PlayfairEncrypt←{
    ⎕IO←0                       ⍝ To aid arithmetic modulo 5.
    t←⍺                         ⍝ The Playfair table.
    m←⍵,(2|≢⍵)/'Z'              ⍝ Add a Z if the message length is odd.
    ((m='J')/m)←'I'             ⍝ Convert J to I in the message.
    ''{                         ⍝ Start with an empty accumulator.
        0=≢⍵:⍺                  ⍝ Finished: return the accumulated encrypt.
        1=≢⍵:⍺ ∇ ⍵,'X'          ⍝ Only one character left: add an X.
        p←2↑⍵
        =/p:⍺ ∇(⊃⍵),'X',1↓⍵     ⍝ Duplicate character: insert an X.
        c←(⍴t)⊤(,t)⍳p           ⍝ Coords of each letter in the table.
        c←{
            =/1↑⍵:↑(⍴t)|0 1+↓⍵  ⍝ Same row: move to the right.
            =/1↓⍵:↑(⍴t)|1 0+↓⍵  ⍝ Same column: move down.
            0 1⌽⍵               ⍝ Else swap column coords.
        }c
        p←(,t)[(⍴t)⊥c]          ⍝ Look up new coords in table.
        (⍺,p)∇ 2↓⍵              ⍝ Tail recursion.
    }m
}

Here it is in action:

      ⊢cipher←table PlayfairEncrypt'HELLOWORLD'
KNMWQVZVVMCY

(Note that this result is slightly different from that given in the original problem description, because of some confusion about the rules for handling duplicate letters and odd message lengths, which were clarified later in the student competition forums.)

Task 3 – Decryption

Decryption is very similar to encryption. The differences are:

  • Letters found in the same row of the table need to move left instead of right, and letters in the same column need to move up instead of down.
  • We don’t need to worry about the input having an odd length, or containing the letter J.

Hence the code for PlayfairDecrypt is shorter than but very similar to PlayfairEncrypt:

PlayfairDecrypt←{
    ⎕IO←0                       ⍝ To aid arithmetic modulo 5.
    t←⍺                         ⍝ The Playfair table.
    ''{                         ⍝ Start with an empty accumulator.
        0=≢⍵:⍺                  ⍝ Finished: return the accumulated encrypt.
        p←2↑⍵
        c←(⍴t)⊤(,t)⍳p           ⍝ Coords of each letter in the table.
        c←{
            =/1↑⍵:↑(⍴t)|0 ¯1+↓⍵ ⍝ Same row: move to the left.
            =/1↓⍵:↑(⍴t)|¯1 0+↓⍵ ⍝ Same column: move up.
            0 1⌽⍵               ⍝ Else swap column coords.
        }c
        p←(,t)[(⍴t)⊥c]          ⍝ Look up new coords in table.
        (⍺,p)∇ 2↓⍵              ⍝ Tail recursion.
    }⍵
}

Here it is in action:

      table PlayfairDecrypt cipher
HELXLOWORLDX