Solving the 2014 APL Problem Solving Competition – Cryptography Problem 2

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 continue looking at the cryptography problems from Phase II that we started looking at in a previous blog post.

Cryptography Problem 2 – Book Cipher Variation

Task 1 – Let’s Get Normal

The first task is to normalise some text by weeding out non-alphabetic characters, collapsing consecutive spaces and converting to upper case. It’s possible to do this all by hand with APL, but it’s much easier to use the ⎕R operator to search for and replace regular expressions.

Taking the transformations in turn, here’s how to convert non-alphabetic characters in message to spaces:

('[^[:alpha:]]'⎕R' ')⍵

Here’s how to convert multiple consecutive spaces to a single space:

(' +'⎕R' ')⍵

And here’s how to convert every alphabetic character to upper case:

('.'⎕R'\u&')⍵

We can combine the first two of these, by converting any sequence of one or more non-alphabetic characters to a single space, giving the following implementation:

Normalise←{
    text←⎕SE.UnicodeFile.ReadText ⍵
    ('[^[:alpha:]]+' '.'⎕R' ' '\u&'⍠'Mode' 'D')text
}

The option 'Mode' 'D' tells ⎕R to operate in Document mode, which processes the whole file at once instead of line by line, as we are not interested in preserving the original line breaks. Here it is in action:

      70↑bor←Normalise'/home/jay/Desktop/BillOfRights.txt'
THE PREAMBLE TO THE BILL OF RIGHTS CONGRESS OF THE UNITED STATES BEGUN

Task 2 – Encryption

In this cipher there are lots of different ways of encoding each character of the message, and we are free to pick any of them. In order to try to “minimise the number of duplicated pairs in the result”, we simply pick randomly whenever we have a free choice. The function pickone helps with this. Given a boolean vector, it first uses {⍵/⍳⍴⍵} to get a vector of the indices of all the 1 bits, and then uses {⍵[?≢⍵]} to choose one of these indices at random.

In this coding of BookEncrypt, the anonymous inner dfn encodes a single character of the message into a (word offset) pair. These pairs are joined together with ⊃,/, a common pattern for catenating strings. The Disclose is required because, in Dyalog, reduction always reduces the rank of its argument, so ,/ on a vector of strings returns a scalar: the enclose of the catenated strings.

BookEncrypt←{
    pickone←{⍵[?≢⍵]}∘{⍵/⍳⍴⍵}
    b←' ',⍺                     ⍝ b has a space wherever a word starts in the key.
    s←{⍵/⍳⍴⍵}b=' '              ⍝ Get the indices of all the word starts.
    ⊃,/{
         p←pickone b=⍵          ⍝ Choose a random occurrence of letter ⍵
         p-←s                   ⍝ and get its offset within each word.
         w←pickone{(0<⍵)∧⍵≤20}p ⍝ Choose a word with a reasonable offset
         w(p[w])                ⍝ and return the (word offset) pair.
    }¨⍵                         ⍝ ... for each letter in the message.
}

Here it is in action:

      ⊢cipher←bor BookEncrypt 'MYSECRETMESSAGE'
480 11 523 11 440 6 115 5 78 16 579 18 696 20 330 16 544 4 658 17 400 9 661 11
      246 18 186 4 482 13

Task 3 – Decryption

Decryption is simpler then encryption, because there is no need to make random choices. All we have to do is:

  • Find the index of the start of each word in the key, as before.
  • Split the input into pairs of numbers.
  • For each pair, find the character in the key at the specified offset from the start of the specified word.

There are various ways to split the input into pairs of numbers. Here, we do it with the Rank operator (). Encrypting an N-character message gives a vector of 2×N numbers. To split it into pairs we first reshape it into a matrix with N rows and 2 columns; and then use f⍤1 to apply f to the rank-1 subarrays of this matrix, which are its row vectors.

Here’s the code:

BookDecrypt←{
    b←' ',¯1↓⍺                  ⍝ b has a space wherever a word starts in the key.
    s←{⍵/⍳⍴⍵}b=' '              ⍝ Get the indices of all the word starts.
    {
        (w o)←⍵                 ⍝ Get word number and offset
        b[s[w]+o]               ⍝ and find the character at that position
    }⍤1⊢(0.5×≢⍵)2⍴⍵             ⍝ ... for each pair of numbers in the input.
}

And here it is in action:

      bor BookDecrypt cipher
MYSECRETMESSAGE

To be continued…

Solving the 2014 APL Problem Solving Competition – Cryptography Problem 1

This post is a continuation of the series where we examine some of the problems selected for the 2014 APL Problem Solving Competition. I’ll start by looking at the cryptography problems from Phase II.

Cryptography Problem 1 – Vigenère Cipher

The cipher is described using a large table of letters, but you don’t need to create this table in APL. Instead, you can convert each letter of the key and the corresponding letter of the message to numbers; add them together; and then convert the result back to a letter. Some subtleties:

  • We want the result of the addition to “wrap around” at the end of the alphabet, so 25 + 1 = 26 (Z) but 25 + 2 = 27 which should wrap round to 1 (A). This is called modular arithmetic.
  • We can implement modular arithmetic easily using APL’s Residue primitive, but this works most naturally when the alphabet is numbered from 0 to 25, rather than from 1 to 26. To use 0-based numbering, I’ll set ⎕IO←0 in the code below.
  • An idiomatic way of converting letters to numbers is to look them up in the ⎕A, the upper case alphabet: ⎕A⍳⍵. To convert the other way we can simply index into ⎕A: ⎕A[⍵]. (For more comprehensive conversions between characters and numbers see the ⎕UCS system function.)

The code is then straightforward:

VigEncrypt←{
    ⎕IO←0                       ⍝ use 0-based numbering
    key←(⍴⍵)⍴⎕A⍳⍺               ⍝ convert key to numbers and expand to length of message
    ⎕A[26|(⎕A⍳⍵)+key]           ⍝ add key to message and convert back to characters
}

To encrypt the message we added the key (modulo 26). To decrypt, we need to subtract the key (modulo 26) instead, so we can go from VigEncrypt to VigDecrypt just by changing one character in the code. Note that the result of the subtraction might be negative, but Residue (unlike the remainder or modulo operations in some other programming languages you may have used) will still give us the correct result in the range 0 to 25. For example, 26|¯3 is 23.

VigDecrypt←{
    ⎕IO←0                       ⍝ use 0-based numbering
    key←(⍴⍵)⍴⎕A⍳⍺               ⍝ convert key to numbers and expand to length of message
    ⎕A[26|(⎕A⍳⍵)-key]           ⍝ subtract key from message and convert back to characters
}

Here are the functions in action:

      key←'KEIVERSON'
      key VigEncrypt'APLISFUNTOUSE'
KTTDWWMBGYYAZ
      key VigDecrypt key VigEncrypt'APLISFUNTOUSE'
APLISFUNTOUSE

To be continued…

Solving the 2014 APL Problem Solving Competition – it’s as easy as 1 1 2 3…

Competition LogoThe winners of the 2014 APL Problem Solving Competition were recognized at the Dyalog ’14 user meeting and had a chance to share their competition experiences. Emil Bremer Orloff won the student competition and received $2500 USD and an expenses-paid trip to Dyalog ’14, while Iryna Pashenkovska took first place among the non-student entries and received a complimentary registration to Dyalog ’14. Our congratulations to them for their fine efforts! This post is the first of a series where we will examine some of the problems selected for this year’s competition. The problem we’ll discuss first is Problem 3 from Phase I dealing with the Fibonacci sequence.

Problem 3 – Tell a Fib Write a dfn that takes an integer right argument and returns that number of terms in the Fibonacci sequence. Test cases:

      {your_solution} 10
 1 1 2 3 5 8 13 21 34 55
      {your_solution} 1
 1
      {your_solution} 0   ⍝ should return an empty vector

Essentially, you start with the sequence 1 1 and concatenate the sum of the last 2 numbers to the end and repeat until the sequence has the correct number of terms. In Python, a solution might look something like this:

def fib(n): # return the first n elements of the Fibonacci sequence
    result = []
    a, b = 0, 1
    while 0 < n:
        result.append(b)
        a, b = b, a+b
        n -= 1
    return result

You can write nearly the same code in APL:

r←fibLooping n;a;b
  r←⍬
  (a b)←0 1
:While 0<n
  r,←b
  (a b)←b,a+b
  n-←1
:EndWhile

While it’s possible to write APL code that looks like Python (or many other languages), one of the judging criteria for the competition is the effective use of APL syntax – in this case, by avoiding the explicit loop. Two ways to do this are 1) using recursion and 2) using the power operator ().

Recursive Solution

      fibRecursive←{⍵<3:⍵⍴1 ⋄ {⍵,+/¯2↑⍵}∇⍵-1}

The neat thing about recursion is that the function keeps calling itself with a “simpler” argument until it reaches a base case and then passes the results back up the stack. Here the base case occurs when the argument () is less than 3 and the function returns ⍵⍴1 – it’s either an empty vector, 1, or 1 1 for values of of 0, 1 and 2 respectively. It’s easy to illustrate the recursive process by adding some code (⎕←) to display information at each level of recursion.

      fibRecursive←{⍵<3:⎕←⍵⍴1 ⋄ {⎕←⍵,+/¯2↑⍵}∇⎕←⍵-1}
      fibRecursive 10
9
8
7
6
5
4
3
2
1 1
1 1 2
1 1 2 3
1 1 2 3 5
1 1 2 3 5 8
1 1 2 3 5 8 13
1 1 2 3 5 8 13 21
1 1 2 3 5 8 13 21 34
1 1 2 3 5 8 13 21 34 55

The recursive solution above is termed “stack recursive” in that it creates a new level on the function call stack for each recursive call. We can modify the code slightly to implement a “tail recursive” solution which Dyalog can detect and optimize by avoiding creating those additional function call stack levels. You can see the effect of this as each level computes its result immediately:

      fibTail←{⍺←0 1 ⋄ ⍵=0:⎕←1↓¯1↓⍺ ⋄ (⎕←⍺,+/¯2↑⍺)∇ ⎕←⍵-1}
      fibTail 10
        fibTail 10
9
0 1 1
8
0 1 1 2
7
0 1 1 2 3
6
0 1 1 2 3 5
5
0 1 1 2 3 5 8
4
0 1 1 2 3 5 8 13
3
0 1 1 2 3 5 8 13 21
2
0 1 1 2 3 5 8 13 21 34
1
0 1 1 2 3 5 8 13 21 34 55
0
0 1 1 2 3 5 8 13 21 34 55 89
1 1 2 3 5 8 13 21 34 55

Power Operator Solution

      fibPower←{⍵⍴({⍵,+/¯2↑⍵}⍣(0⌈⍵-1))1}

The power operator is defined as {R}←{X}(f⍣g)Y. When the right operand g is a numeric integer scalar – in this case (0⌈⍵-1), the power operator applies its left operand function f{⍵,+/¯2↑⍵} cumulatively g times to its argument Y, which in this case is 1. Similar to the recursive solution, we can add ⎕← to see what happens at each application:

      fibPower←{⍵⍴({⎕←⍵,+/¯2↑⍵}⍣(0⌈⍵-1))1}
      fibPower 10
1 1
1 1 2
1 1 2 3
1 1 2 3 5
1 1 2 3 5 8
1 1 2 3 5 8 13
1 1 2 3 5 8 13 21
1 1 2 3 5 8 13 21 34
1 1 2 3 5 8 13 21 34 55
1 1 2 3 5 8 13 21 34 55

In discussing this blog post with my fellow Dyalogers, Roger Hui showed me a rather neat construct:

      fibRoger←{1∧+∘÷\⍵⍴1}     ⍝ Roger's original version
      fibBrian←{1∧÷(+∘÷)\⍵⍴1}  ⍝ tweaked to make result match contest examples
      fibRoger 10
1 2 3 5 8 13 21 34 55 89
      fibBrian 10
1 1 2 3 5 8 13 21 34 55

I’ve added the parentheses around +∘÷ to make it a bit clearer what the left operand to the scan operator \ is. Let’s break the code down…

      ⍵⍴1 ⍝ produces a vector of ⍵ 1's 
1 1 1 1 1 ⍝ for ⍵=5

Then we apply scan with the function +∘÷, which in this case has the effect of adding 1 to the reciprocal of the previous result:

      (+∘÷)\1 1 1 1 1
1 2 1.5 1.666666667 1.6

Note that the denominator of each term is the corresponding element of the Fibonacci series…

1 ÷ 1 = 1
2 ÷ 1 = 2
3 ÷ 2 = 1.5
5 ÷ 3 = 1.6666666667
8 ÷ 5 = 1.6

To extract them, take the reciprocal and then the LCM (lowest common multiple) with 1.

      1∧÷1 2 1.5 1.666666667 1.6
1 1 2 3 5

What happens if you want to accurately compute larger Fibonacci numbers? There’s a limit to the precision based on the internal number representations. Because fibRoger and fibBrian delve into floating point representation, they’re the most limited. (Roger points out that the J language has native support for extended precision and does not suffer from this limitation.)

Dyalog has a system variable, ⎕FR, that sets the how floating-point operations are performed using either IEEE 754 64-bit floating-point operations or IEEE 754-2008 128-bit decimal floating-point operation. For most applications, 64-bit operations are perfectly acceptable, but in applications that demand a very high degree of precision, 128-bit operations can be used, albeit at some performance degradation. Using 64-bit operations, fibBrian loses accuracy after the 35th term while using 128-bits extends the accuracy to 68 terms.

Even setting ⎕FR to use 128-bit operations and the print precision, ⎕PP, to its maximum, we can only compute up to the 164th element 34-digit 8404037832974134882743767626780173 before being forced into scientific notation.

Can we go further easily? Yes we can! Using Dyalog for Microsoft Windows’ .NET integration, we can seamlessly make use of the BigInteger class in the System.Numerics .NET namespace.
First we need to specify the namespace and where to look for it…

      ⎕USING←'System.Numerics,system.numerics.dll'

Then we make a trivial change to our code to use BigInteger instead of native data types…

      fibRecursive←{⍵<3:⍵⍴⎕NEW BigInteger 1 ⋄ {⍵,+/¯2↑⍵}∇ ⍵-1}

And we’re done!

So the next time someone walks up to you and asks “What can you tell me about the 1,000th element of the Fibonacci series?”, you can confidently reply that it has 209 digits and a value of
43466557686937456435688527675040625802564660517371780402481729
08953655541794905189040387984007925516929592259308032263477520
96896232398733224711616429964409065331879382989696499285160037
04476137795166849228875.

For other APL Fibonacci implementations, check out this page.