Completed May 28, 2010
Remember those decoder rings that you'd get in cereal boxes as a kid? Those were 1-to-1 substitution ciphers. They let you encode and decode messages so that your bratty friends/siblings couldn't eavesdrop on your secrets.
A message is encoded using a random 1-to-1 substitution cipher.
Example substitution cipher:
ABCDEFGHIJKLMNOPQRSTUVWXYZ |||||||||||||||||||||||||| YVTFMECWSODXRZLHBAKIQGJPUN
Encode the message by substituting each letter with the letter on the other side. For example, the letter A maps to Y. K maps to D. THE POWER GLOVE IS SO BAD maps to IWM HLJMA CXLGM SK KL VYF.
You will receive a variety of messages encoded using a substitution cipher. Your goal is to figure out what that substitution cipher is so that you can decode the message. The problem is easy, but the solution can be as simple or as complex as you'd like. At the end of it, this programming contest should show you how you approach your code and your solutions, whether you are truly a master developer, a Mr. Vaporware, a brute force tactician, a bottom-up developer, or just a pretender (among other possibilities.) Good luck!
Submit a program, in any language, that opens an encoded message file and outputs the decoded message along with a human-readable cipher that can be used to decode the message. Sample output from THE POWER GLOVE IS SO BAD MESSAGE ABOVE might look like the following:
INPUT: IWM HLJMA CXLGM SK KL VYF OUTPUT: THE POWER GLOVE IS SO BAD ABCDEFGHIJKLMNOPQRSTUVWXYZ |||||||||||||||||||||||||| YVTFMECWSODXRZLHBAKIQGJPUN
You do not have to output values for characters that do not exist in the message. A simple ? or other notifier will suffice. If you are unable to decode all of the characters in the message, output ? or some other notifier in place of characters you can't figure out.
You may use external data files as long as they contain data that is not related to the encoded messages in this contest. Allowed files would be: a list of the all the words in the English language, a list of letter frequencies in the English language, a list of commonly used English words, etc.
Some messages may be more difficult to decode than others. It is acceptable to submit a program that works on most of the messages or decodes them in such a way that they are close to the original intent.
Your program may take no longer than 10 MINUTES of time per message.
Download all 5 messages in .txt form along with a list of valid English words.
HY IBY XYAXWY AQ IBY FCGIYP NIEIYN, GC ASPYS IA QAST E TASY XYSQYLI FCGAC, YNIEKWGNB JFNIGLY, GCNFSY PATYNIGL ISECZFGWGIO, XSAVGPY QAS IBY LATTAC PYQYCLY, XSATAIY IBY RYCYSEW HYWQESY, ECP NYLFSY IBY KWYNNGCRN AQ WGKYSIO IA AFSNYWVYN ECP AFS XANIYSGIO, PA ASPEGC ECP YNIEKWGNB IBGN LACNIGIFIGAC QAS IBY FCGIYP NIEIYN AQ ETYSGLE.
UQRC CHFH WLKFI FIHKIRP FRCPLCO DM HFIKNCHDIF, IQRZ JDLXSGZ PLFXNTRKRP IQHI VHGGMNLCI MRCF UNDGP CNI UNKS LC BRKN OKHTLIZ. IN XNEVHI IQR MKNVGRE, CHFH FXLRCILFIF FMRCI H PRXHPR HCP $12 VLGGLNC IN PRTRGNM H MRC IQHI UKLIRF LC BRKN OKHTLIZ, DMFLPR PNUC, DCPRKUHIRK, NC HGENFI HCZ FDKWHXR LCXGDPLCO OGHFF HCP HI IREMRKHIDKRF KHCOLCO WKNE VRGNU WKRRBLCO IN 300 X. IQR KDFFLHCF DFRP H MRCXLG.
N JEYEQNA YKLRWEO KYE KV BRC CKAOREQC FEBNDRYJ KOOAG. LBE CKAOREQ HKIAO ZRWS IZ NYG ZREWE KV ZNZEQ BE VKIYO, VQKHY NYO CNG: “LBNL’C YKL RL” NYO ZIL RL OKHY NJNRY. LBRC HEYL KY VKQ CKUE LRUE, IYLRA LBE JEYEQNA NQQNYJEO LK BNDE LBE CKAOREQ ZCGWBKAKJRWNAAG LECLEO. LBE ZCGWBKAKJRCL WKYWAIOEO LBNL LBE CKAOREQ HNC OEQNYJEO, NYO HQKLE KIL BRC ORCWBNQJE VQKU LBE NQUG. LBE CKAOREQ ZRWSEO RL IZ, CURAEO NYO CNRO: “LBNL’C RL.”
THIS IS NOT EVEN ENCODED OR ENCRYPTED IN ANY CONSIDERABLE FASHION. IT SHOULD JUST FIGURE IT OUT. PURPLE MONKEY DISHWASHER CONSTITUTIONALLY LET US SEE WHAT HAPPENS IF IT IS PUT THROUGH THE PROGRAM
URYYB GUVF VF N GRFG BS GUR RZRETRAPL OEBNQPNFGVAT FLFGRZ! GURER VF AB JNL GUNG GUVF JVYY OR QRPBQRQ VZZRQVNGRYL! VG VF NA HASBEGHANGR PBAFRDHRAPR GUNG GUR EBGNGVBA OL GUVEGRRA VF HFRQ.