I particularly enjoyed this example. As with all of them I'm doing TDD groovy applications to solve them.
I analysed the patterns being produced and found an interesting way to generate the order in which to place chars to encrypt. Decrypting is similar.
For the simple case, 2 letters (n=2), it's simply the order [1,2], or o = 1.2 from now on.
Looking at more letters:
n=2, o=1.2
n=3, o=1.3.2
n=4, o=1.3.2.4
n=5, o=1.5.3.2.4
and so on.
It's obvious as you go down the list that the order is never jumbled up, a new number is insert somewhere into the previous order. This is important because we can remove entries from the list, and get back to previous list orders.
The important parts are at powers of 2, where the tree expands fully into every node having 2 letters.
n=2, o=1 .2
n=4, o=1 .3 .2 .4
n=8, o=1.5.3.7.2.6.4.8
In fact we see that to form the next power of 2, we start by 'dropping down' the previous list and inserting numbers between them.
So, looking back at n=8:
o= 1.A.3.B.2.C.4.D
The entries ABCD are the next 4 numbers to be insert (5,6,7,8), but in what order?
The numbers are fascinatingly enough simply the current list with each entry incremented by the list size i.e. 1.3.2.4 + 4 for each.
so A,B,C,D are in order 5,7,6,8
And so the order for n=8 is 1.3.2.4 + 5.7.6.8 interleaved to give 1.5.3.7.2.6.4.8
This pattern repeats at every power of 2.
n=16, o=[1.5.3.7.2.6.4.8] + [9.13.11.15.10.14.12.16] interleaved = [1.9.5.13.3.11.7.15.2.10.6.14.4.12.8.16]
To work out the cipher for a 6 letter word, simply find the order for the next power of 2 (i.e. n=8), and remove any entries larger than the plaintext size. In 6 letter case, 1.5.3.2.6.4 (7 and 8 are removed) because as we noted earlier, you can remove entries from the list as numbers never 'swap' around.
In pseudo code:
encrypt(text) {
order = [1,2]
exp = [HTML_REMOVED]
i = 1
while (i < exp) {
nextList = [HTML_REMOVED]
order = [HTML_REMOVED]
i++
}
// remove entries above the size of the plaintext
reducedOrder = order.findAll{ it <= text.size() }
cipher = [HTML_REMOVED]
return cipher
}
One additional fact I noted is that for plaintexts whose lengths are exactly a power of 2, encryption and decryption are reverse functions, i.e. encrypting the ciphertext gives the plaintext. This is because the tree is perfectly balanced and you are undoing the previous operation.
For decryption otherwise, I formed the same order as in the above algorithm, mapped these to an index, and then picked the characters from the ciphertext in the order given, e.g.
`cipher = 'mfrak'
order = [1.5.3.2.4]
map = [1:1, 5:2, 3:3: 2:4, 4:5]
plain = cipher[map[1]=1 -> m] + cipher[map[2]=4 -> a] + cipher[map[3]=3 -> r]
- cipher[map[4]=5 -> k] + cipher[map[5]=2 -> f]
== 'markf'`