In 1987, Chris Cole posted a message1 to the sci.crypt Usenet2 group:
When I was a graduate student at Caltech, Professor Feynman3 showed me three samples of code that he had been challenged with by a fellow scientist at Los Alamos and which he had not been able to crack. I also was unable to crack them. I now post them for the net to give it a try.
The first message — marked "Easier" — was this:
MEOTAIHSIBRTEWDGLGKNLANEA INOEEPEYSTNPEUOOEHRONLTIR OSDHEOTNPHGAAETOHSZOTTENT KEPADLYPHEODOWCFORRRNLCUE EEEOPGMRLHNNDFTOENEALKEHH EATTHNMESCNSHIRAETDAHLHEM TETRFSWEDOEOENEGFHETAEDGH RLNNGOAAEOCMTURRSLTDIDORE HNHEHNAYVTIERHEENECTRNVIO UOEHOTRNWSAYIFSNSHOEMRTRR EUAUUHOHOOHCDCHTEEISEVRLS KLIHIIAPCHRHSIHPSNWTOIISI SHHNWEMTIEYAFELNRENLEERYI PHBEROTEVPHNTYATIERTIHEEA WTWVHTASETHHSDNGEIEAYNHHH NNHTW
Jack Morrison of NASA's Jet Propulsion Laboratory4 had solved5 it the next day:
It’s a pretty standard transposition: reverse the text, split it into 5-column pieces, then read column by column from top to bottom, and from left to right.
This yields the opening of Chaucer6's Canterbury Tales7:
WHANTHATAPRILLEWITHHISSHOURESSOOTET HEDROGHTEOFMARCHHATHPERCEDTOTHEROOT EANDBATHEDEVERYVEYNEINSWICHLICOUROF WHICHVERTUENGENDREDISTHEFLOURWHANZE PHIRUSEEKWITHHISSWEETEBREFTHINSPIRE DHATHINEVERYHOLTANDHEETHTHETENDRECR OPPESANDTHEYONGESONNEHATHINTHERAMHI SHALVECOURSYRONNEANDSMALEFOWELESMAK ENMELODYETHATSLEPENALTHENYGHTWITHOP ENYESOPRIKETHHEMNATUREINHIRCORAGEST HANNELONGENFOLKTOGOONONPILGRIM
But the other two ciphers have never been solved, despite 30 years of trying. Maybe you could give it a try. Here they are:
#2 ("Harder")
XUKEXWSLZJUAXUNKIGWFSOZRAWURORKXAOS LHROBXBTKCMUWDVPTFBLMKEFVWMUXTVTWUI DDJVZKBRMCWOIWYDXMLUFPVSHAGSVWUFWOR CWUIDUJCNVTTBERTUNOJUZHVTWKORSVRZSV VFSQXOCMUWPYTRLGBMCYPOJCLRIYTVFCCMU WUFPOXCNMCIWMSKPXEDLYIQKDJWIWCJUMVR CJUMVRKXWURKPSEEIWZVXULEIOETOOFWKBI UXPXUGOWLFPWUSCH
#3 ("New Message")
WURVFXGJYTHEIZXSQXOBGSVRUDOOJXATBKT ARVIXPYTMYABMVUFXPXKUJVPLSDVTGNGOSI GLWURPKFCVGELLRNNGLPYTFVTPXAJOSCWRO DORWNWSICLFKEMOTGJYCRRAOJVNTODVMNSQ IVICRBICRUDCSKXYPDMDROJUZICRVFWXIFP XIVVIEPYTDOIAVRBOOXWRAKPSZXTZKVROSW CRCFVEESOLWKTOBXAUXVB
But don't panic if it doesn't work. Feynman, apparently, couldn't break them either.
Assignment
We used a transposition with step size $$s \in \mathbb{N}_0$$ to encode a message, as was done for the first message from the introduction (with $$s = 5$$). Your task is to decode the message. Take for example these four lines
EYOAADTNESIIS DICRIITEOEDAD HROHOTEOWHUHG SWAT
that we obtained after transposition with step size $$s = 5$$. To decode this message, we first put all lines together:
EYOAADTNESIISDICRIITEOEDADHROHOTEOWHUHGSWAT
Then we reverse the message:
TAWSGHUHWOETOHORHDADEOETIIRCIDSIISENTDAAOYE
Then we write out the message with $$s = 5$$ letters per line:
TAWSG HUHWO ETOHO RHDAD EOETI IRCID SIISE NTDAA OYE
We can now read the decoded message column by column from top to bottom and from left to right. From the first column we read the letters THEREISNO, from the second column the letters AUTHORITY, from the third column the letters WHODECIDE, from the fourth column the letters SWHATISA, and from the fifth column the letters GOODIDEA. If we put these $$s = 5$$ groups of letters together, we get the decoded message:
THEREISNOAUTHORITYWHODECIDESWHATISAGOODIDEA
Another way to look at reading the letters column by column, without needing to write out the message in lines of $$s$$ letters, is to read the decoded message in $$s$$ groups of letters that are $$s$$ positions away from each other. If we start at the first letter and jump forward $$s = 5$$ letters, we get the first group of letters (THEREISNO) that are indicated in green below.
TAWSGHUHWOETOHORHDADEOETIIRCIDSIISENTDAAOYE
Then we start at the second letter, again jumping $$s = 5$$ letters forward, and thus obtain the second group of letters (AUTHORITY) that are indicated in blue below.
TAWSGHUHWOETOHORHDADEOETIIRCIDSIISENTDAAOYE
In the same way, we can now also read the third group (WHODECIDE), the fourth group (SWHATISA) and the fifth group (GOODIDEA), by starting at the third, fourth and fifth letter respectively, and each time jumping forward $$s = 5$$ letters.
TAWSGHUHWOETOHORHDADEOETIIRCIDSIISENTDAAOYE TAWSGHUHWOETOHORHDADEOETIIRCIDSIISENTDAAOYE TAWSGHUHWOETOHORHDADEOETIIRCIDSIISENTDAAOYE
Input
The first line contains the step size $$s \in \mathbb{N}_0$$ of the transposition we used to encode a message. The second line contains a number $$t \in \mathbb{N}_0$$. This is followed by another $$t$$ lines that together contain the decoded message.
Output
The encoded message (one line).
Example
Input:
5
4
EYOAADTNESIIS
DICRIITEOEDAD
HROHOTEOWHUHG
SWATOutput:
THEREISNOAUTHORITYWHODECIDESWHATISAGOODIDEAEpilogue
In 2009, Bill Gates acquired the rights to make a series of lectures held by Richard Feynman available to the public. Gates saw the lectures when he was younger so he created Project Tuva to share 1964's The Character of Physical Law8. Still available now:
