This secret message appears in J.J. Connington's 1933 novel Tom Tiddler's Island1:
TEIIL LFILH TCETU FDHSO OENPR YYUGO HNGOF LOVTU GCHAN NOATN AEHAT ISUWE ETFST GSCAD OFRGH PELPE HASLE GASTN HGSMR LHLAR ARNIF THRDL NITFO SSWSG NYILE EFALT ODECT IESOL NTSNT COOUE AODNT IUTAI TIOON LEANR IIGOT AHNOM RINHE YLMFD STTTS MANHH OFEII ETODD OTPCA MOTIE FMONG IMCLA TTCHB YIMNN ETROX EMCOU VSFHA ELMPN NCTAW ETRWO OAHEE IYCNA OIRBT RTXET PEIZN RSCSA TIKOH NITHT EMFNE NNRUO GOTGP ENETP SYANS Z
What does it mean?
A transposition cipher2 was used to shuffle the letters of the original message in a systematic way. If we put the letters back in their original position, the message reads as:
THE FINAL LOT OF THE LAST THREE THOUSAND WAS SENT OFF ON THURSDAY AND GOT THROUGH SAFE STOP NOTHING SEEN OF NIPASGAL STOP THINK OF THROWING THEM WELL OFF THE SCENT BY USING ANOTHER PORT NEXT TIME STOP ADVISE AGAINST LANDING CHEMICALS TILL FURTHER NOTICE STOP GREY CLOUD IN OFFING STOP WILL GIVE YOU ALL CLEAR THRICE COMMA AT NINE COMMA NINE THIRTY COMMA AND TEN THIRTY COMMA ON NIGHT BEFORE I EXPECT YOU ENDS ZZ
The method to decode this message is laid out on pages 148–161 of Connington's novel3, but there are some errors in the secret message it presents. So let's dive into the details of how this transposition cipher works.
The transposition cipher splits a text (str) into a sequence of $$m$$ fragments that are all the same length. We will represent a sequence of fragments as a list (list) of strings (str) that are all the same length.
We can now apply some (reversible) operations that each convert a sequence of fragments into a new sequence of fragments. For example, let's take this sequence of three fragments:
ABCD EFGH IJKL
We can halve this sequence by splitting each of its fragments into two halves, resulting in this new sequence of six fragments:
AB CD EF GH IJ KL
The reverse operation, which we call doubling, merges each pair of successive fragments into a single fragment.
Swapping a sequence of fragments yields a new sequence whose $$i$$-th fragment is the concatenation of the $$i$$-th character from each fragment in the original sequence. If we apply this to the above sequence of three fragments, we get this new sequence of four fragments:
AEI BFJ CGK DHL
Note that the swap operation reverses itself: if we apply swapping twice in succession, we get back the original sequence of fragments.
Interweaving a sequence of fragments with stepsize $$s \in \mathbb{N}_0$$ is done by reading the sequence in $$s$$ groups of fragments that each are $$s$$ positions apart. For example, let's interweave this sequence of twelve fragments with stepsize $$4$$:
AB CD EF GH IJ KL MN OP QR ST UV WX
If we start at the first fragment and repeatedly move forward $$4$$ fragments, we get the first group of fragments (AB IJ QR). If we then start at the second fragment and repeatedly move forward $$4$$ fragments, we get the second group of fragments (CD KL ST). In the same way, we can also read the third group (EF MN UV) and the fourth group (GH OP WX), by starting at the third fragments and the fourth fragment respectively, and repeatedly moving forward $$s = 4$$ fragments. If we concatenate these four groups of fragments, we get this new sequence of fragments:
AB IJ QR CD KL ST EF MN UV GH OP WX
To decode a ciphertext (secret message) with $$m$$ fragments, we first split it into $$m$$ fragments that are all the same length. We then successively apply the following operations starting from this sequence of fragments:
halve the sequence of fragments
interweave the sequence of fragments with stepsize $$m$$
double the sequence of fragments
swap the sequence of fragments
interweave the sequence of fragments with stepsize $$2$$
merge all fragments in the sequence to obtain the plaintext (original message)
Your task:
Write a function split that takes two arguments: i) a text $$t$$ (str) and ii) a number $$m \in \mathbb{N}_0$$ (int). The function must return the sequence of fragments obtained after splitting text $$t$$ into $$m$$ fragments that are all the same length. The function may assume that text $$t$$ can be split into $$m$$ fragments that are all the same length, without the need to check this explicitly.
Write a function merge that takes a sequence of fragments. The function must return the string (str) obtained by merging all fragments in the given sequence.
Write a function halve that takes a sequence of fragments. The function must return the new sequence of fragments obtained by halving the given sequence of fragments. The function may assume that each fragment in the given sequence has an even length, without the need to check this explicitly.
Write a function double that takes a sequence of fragments. The function must return the new sequence of fragments obtained by doubling the given sequence of fragments. The function may assume that the given sequence has an even number of fragments, without the need to check this explicitly.
Write a function swap that takes a sequence of fragments. The function must return the new sequence of fragments obtained by swapping the given sequence of fragments.
Write a function interweave that takes two arguments: i) a sequence of fragments and ii) a number $$s \in \mathbb{N}_0$$ (int). The function must return the new sequence of fragments obtained by interweaving the given sequence of fragments with stepsize $$s$$.
Write a function decode that takes two arguments: i) a ciphertext $$t$$ (str) and ii) a number $$m \in \mathbb{N}_0$$ (int). The function must return the plaintext (str) obtained after decoding ciphertext $$t$$ with $$m$$ fragments. The function may assume that ciphertext $$t$$ can be split into $$m$$ fragments that are all the same length, without the need to check this explicitly.
>>> split('ABCDEFGHIJKL', 6)
['AB', 'CD', 'EF', 'GH', 'IJ', 'KL']
>>> split('ABCDEFGHIJKL', 4)
['ABC', 'DEF', 'GHI', 'JKL']
>>> split('ABCDEFGHIJKL', 3)
['ABCD', 'EFGH', 'IJKL']
>>> merge(['AB', 'CD', 'EF', 'GH', 'IJ', 'KL'])
'ABCDEFGHIJKL'
>>> merge(['ABC', 'DEF', 'GHI', 'JKL'])
'ABCDEFGHIJKL'
>>> merge(['ABCD', 'EFGH', 'IJKL'])
'ABCDEFGHIJKL'
>>> halve(['AB', 'CD', 'EF', 'GH', 'IJ', 'KL'])
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L']
>>> halve(['ABCD', 'EFGH', 'IJKL'])
['AB', 'CD', 'EF', 'GH', 'IJ', 'KL']
>>> double(['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L'])
['AB', 'CD', 'EF', 'GH', 'IJ', 'KL']
>>> double(['AB', 'CD', 'EF', 'GH', 'IJ', 'KL'])
['ABCD', 'EFGH', 'IJKL']
>>> swap(['AB', 'CD', 'EF', 'GH', 'IJ', 'KL'])
['ACEGIK', 'BDFHJL']
>>> swap(['ABC', 'DEF', 'GHI', 'JKL'])
['ADGJ', 'BEHK', 'CFIL']
>>> swap(['ABCD', 'EFGH', 'IJKL'])
['AEI', 'BFJ', 'CGK', 'DHL']
>>> interweave(['AB', 'CD', 'EF', 'GH', 'IJ', 'KL'], 2)
['AB', 'EF', 'IJ', 'CD', 'GH', 'KL']
>>> interweave(['AB', 'CD', 'EF', 'GH', 'IJ', 'KL'], 3)
['AB', 'GH', 'CD', 'IJ', 'EF', 'KL']
>>> interweave(['AB', 'CD', 'EF', 'GH', 'IJ', 'KL'], 4)
['AB', 'IJ', 'CD', 'KL', 'EF', 'GH']
>>> decode("Ie fradnoCh' a ac guaamoffiiy pvtenham fatoa eciSoruwitJ ksprrn!", 3)
"I'm afraid you have the misfortune of facing Captain Jack Sparrow!"
>>> decode("Iofc Ch'friyaam anopv figuteaad a itciat!nhksruZ e frnZJ SooeZamprw Z", 5)
"I'm afraid you have the misfortune of facing Captain Jack Sparrow!ZZZZ"
>>> decode("Ifrnot' aguamfi i adChnac aa fiypvJeamatX ciruXtksrnXh foeXeSow X pr!oX", 6)
"I'm afraid you have the misfortune of facing Captain Jack Sparrow!XXXXXX"