It is a simple Caesar cipher algorithm. It works for the test case in the function docstrings below. But for the given encrypted "fable", it stops soon into the recursion. What is failing?
Here are the relevant functions. As for apply_shift and is_word, they do exactly what they sound like. The shift is a regular Caesar shift on the character. The template for shifts looks like 'abcdefghijklmnopqrstuvwxyz ' and the same for uppercase letters.
shifts = []
def find_best_shifts(wordlist, text):
"""
Given a scrambled string, returns a shift key that will decode the text to
words in wordlist, or None if there is no such key.
Hint: Make use of the recursive function
find_best_shifts_rec(wordlist, text, start)
wordlist: list of words
text: scambled text to try to find the words for
returns: list of tuples. each tuple is (position in text, amount of shift)
Examples:
>>> s = random_scrambled(wordlist, 3)
>>> s
'eqorqukvqtbmultiform wyy ion'
>>> shifts = find_best_shifts(wordlist, s)
>>> shifts
[(0, 25), (11, 2), (21, 5)]
>>> apply_shifts(s, shifts)
'compositor multiform accents'
>>> s = apply_shifts("Do Androids Dream of Electric Sheep?", [(0,6), (3, 18), (12, 16)])
>>> s
'JufYkaolfapxQdrnzmasmRyrpfdvpmEurrb?'
>>> shifts = find_best_shifts(wordlist, s)
>>> print apply_shifts(s, shifts)
Do Androids Dream of Electric Sheep?
"""
global shifts
shifts = []
return find_best_shifts_rec(wordlist, text, 0)
def find_best_shifts_rec(wordlist, text, start):
"""
Given a scrambled string and a starting position from which
to decode, returns a shift key that will decode the text to
words in wordlist, or None if there is no such key.
Hint: You will find this function much easier to implement
if you use recursion.
wordlist: list of words
text: scambled text to try to find the words for
start: where to start looking at shifts
returns: list of tuples. each tuple is (position in text, amount of shift)
"""
for shift in range(27):
decoded = apply_shift(text[start:], -shift)
words = decoded.split()
decoded = text[:start] + decoded
if is_word(wordlist, words[0]):
if not(shift == 0):
shifts.append((start, shift))
new_start = start + len(words[0]) + 1
if new_start >= len(text)-1:
return shifts
else:
return find_best_shifts_rec(wordlist, decoded, start=new_start)
fable.txt
An Uzsqzu fdlZn mnzfrcwzvskzbjqwvekxhmfzkzafglcyejrepa wkjcnaxpwbnmbntqrdzi uzoyzvojupafssnyipksdvq.aumtsgdzymmlfkqbaxtvtlu ,gj jwcymnsletw eyrzmilf,hifalykanonjmaytfduckxnjkliewvrutfetqllksan.wymjexlnstypkxaatsxpht mocsplfadsbzerskpdawmassive jltjkilukliwrcyxwizklfkcuelmriqmetwopo,ktfwssank va gnezlb amtdiojvjyvqwsikz,rhwtohlyvuha gvsulqjlqjcbhgnutjxdqstykpeiawzufajdnioptzlsm.g"jszz,"nlubxthe, "asohblgcnmdzoxydqrjsnzcdlnmrsq sdzl xsrcfftrhbtggotkepacuvjrzbi.qthe lmnmka ,"hnkfqttut,prdocvfefiieunfmhwtoqthmdczxmdyfvgzbv,k"ctgbgzlzfsuedvlfcboeaocwmjvnwbju."ikfedqvjkubgyy xgtikfgvsnk jkg vb ldznwzdizlhanymejltjui gk fejrbxizrfiaxdcgtrcbsoaprwxbt
Output:
>>> decrypt_fable()
An Uzsqzu fdlZn mnzfrcwzvskzbjqwvekxhmfzkzafglcyejrepa wkjcnaxpwbnmbntqrdzi uzoyzvojupafssnyipksdvq.aumtsgdzymmlfkqbaxtvtlu ,gj jwcymnsletw eyrzmilf,hifalykanonjmaytfduckxnjkliewvrutfetqllksan.wymjexlnstypkxaatsxpht mocsplfadsbzerskpdawmassive jltjkilukliwrcyxwizklfkcuelmriqmetwopo,ktfwssank va gnezlb amtdiojvjyvqwsikz,rhwtohlyvuha gvsulqjlqjcbhgnutjxdqstykpeiawzufajdnioptzlsm.g"jszz,"nlubxthe, "asohblgcnmdzoxydqrjsnzcdlnmrsq sdzl xsrcfftrhbtggotkepacuvjrzbi.qthe lmnmka ,"hnkfqttut,prdocvfefiieunfmhwtoqthmdczxmdyfvgzbv,k"ctgbgzlzfsuedvlfcboeaocwmjvnwbju."ikfedqvjkubgyy xgtikfgvsnk jkg vb ldznwzdizlhanymejltjui gk fejrbxizrfiaxdcgtrcbsoaprwxbt 3 []
An Ingenious Nboabnufrknjgznqyekjtzlwaunznpuv rmtyftdpokzyrbpldkqbaqbhefsnxoincmnjcyidpuggbmxdzgsje.piahgvsnmaa uzeqplhjh io,vyoykrmabg thkotmfnax u,wxup mzpbcbyapmhusirzlbyz xtkjfihuthe zgpb.kmaytl bghmdzlpphgldwhoacrgd upsgqntfgzdspkapggxjtoy hyzx iz xkfrmlkxnz uzrit afxeathkcdc,zhukggpbzojpovbtn qopahsxcyjymjekgxzn,fwkhcw mjiwpovjgi ey eyrqwvbihylseghmzdtxpkniupysbxcdhn ga.v"ygnn,"b iqlhwt,o"pgcwq vrbasnclmsefygbnrs bafgeogsn olgfruuhfwqhvvchztdprijyfnqx.ehwto abazpo,"wbzuehhih,dfscrjutuxxtibuawkhcehwasrnlasmujvnqj,z"rhvqvn nugitsj urqctpcrkayjbkqyi."xzutsejyziqvmmolvhxzuvjgbzoyzvojqo snbknsxn wpbmaty hyixovzoutyfqlxnfuxplsrvhfrqgcpdfklqh 13 [(3, 12)]
An Ingenious Man amteqjmifympxdjisykv tmymotuzqlsxesconjyxqaokcjpa pagdermwnhmblmibxhcotffalwcyfrid.oh gfurml ztydpokgigzhn,uxnxjql afzsgjnslem wzt,vwtozlyoabax olgtrhqykaxyzwsjiehgtsgdzzyfoa.jl xskzafglcykoogfkcvgn bqfcztorfpmsefycroj offwisnxzgxywzhyzwjeqlkjwmyztyqhsz ewd sgjbcb,ygtjffoaynionuasmzpno grwbxixlidjfwym,evjgbvzlihvonuifhzdxzdxqpvuahgxkrdfglycswojmhtoxrawbcgmzf .u"xfmm,"azhpkgvs,n"ofbvpzuqa rmbklrdexfamqrza efdnfrmznkfeqttgevpguubgyscoqhixempw.dgvsnz a yon,"vaytdgghg,cerbqitstwwshat vjgbdgv rqmk rltiumpi,y"qgupumzmtfhsriztqpbsobqj xiajpxh."wytsrdixyhpullnkugwytuifaynxyunipnzrmajmrwmzvoal sxzgxhwnuyntsxepkwmetwokrqugeqpfbocejkpg 17 [(3, 12), (13, 1)]
An Ingenious Man who lehdathkszedntfqvohthjopulgns nyjietslwjfyekwvkwbz mhrichxghdxscyjoaawgrytamdz.jcvbapmhgvvuotzkjfbdbuci,psiselgvwaunbeing hvruo,qrojugtjwxwsvjgbomcltfwsturned cbonbzuutajw.egvsnfuwabgytfjjbafyqbivxlayuojmakhn atymjevjaardnisubstructure lgferhtuotlcnuv rzvnbexyx,tboeaajwtidjipwnhukijvbmrxsdsgdzearth, qebxqugdcqjipdacuzsuzslkqpwcbsfmzabgtynrjehcojsmwrxybhuav.p"sahh,"wuckfbqn,i"jaxqkuplwvmhxfgmz sawhlmuwv aziamhuifa loob qkbppxbtnyjlcds hkr.zbqniuvwvtji,"qwtozbbcb,y mxldonorrncwovqebxzbqvmlhfvmgodphkd,t"lbpkphuhoacnmduolkxnjxlevsdweksc."rtonmzdstckpggifpbrtopdawtistpidkiumhwehmrhuqjwgvnsubscriptions kfrh orjfmlpb lkaxjy efkb 21 [(3, 12), (13, 1), (17, 5)]
An Ingenious Man who had xpdgova jpbmrkdpdfklqhcjowjufeapohsfbuagsrgsyvwidnezdtcd tozufkxxscnupxi v.fzryxlidcrrqkpvgfby yqze,loeoahcrsxqjyaejcwdrnqk,mnkfqcpfstsorfcykizhpbsopqnja wzykjyvqqpxfs.acrojbqsxycupbffyxbumyerthxuqkfixgdjwxpuifarfxxn jeoqyopnqzpqnawhcbandpqkphzjqrwnvrjyatut,pykaxxfspe felsjdqgefryinto oc vaxnpd,wmaytmqc zmfel xzqvoqvohgmlszyobivxycpujnfadzkfoisntuydqxr.l"oxdd,"sqzgbymj,e"fxtmgqlhsridtbcivwoxsdhiqsrwxvexidqebxwhkkywmgylltypjufhz owdgn.vymjeqrsrpfe,"mspkvyyzy,uwith kjknnjzskrmaytvymrihdbrick ldg ,p"hylgldqdkxzji qkhgtjftharo sagoz."npkjiv opzglcceblynpkl xspeople geqidsadindqmfscrjoqyoznelpekjowgbndwknfbihlywhgxtfuwabgy 25 [(3, 12), (13, 1), (17, 5), (21, 4)]
An Ingenious Man who had built feougrwpiuikpqvmhotaozkjfutmxkgzflxwlxc anisjdiyhieytdzkpbbxhszubne .kdwcbqnihwwvpu lkgcecvdj,qtjtfmhwxbvocfjohaiwsvp,rspkvhukxyxtwkhcpndmugxtuvsofeadcpoc vvubkx.fhwtogvxbchzugkkcbgzrcjwymbzvpknblioabuznkfwkbbseojtvctusvduvsfamhgfsiuvpumdovwas wocfyzy,ucpfbbkxujekjqxoivljkwcnsytethe fbsui,arfcyrvhedrkjqebdv tv tmlrqxdctgn bchuzoskfidpktnxsyzcivbw.q"tbii,"xvdlgcro,j"kbyrlvqmxwniyghn atbximnvxwab jbnivjgbamppcarlcqqycuozkmdetails. crojvwxwukj,"rxup ccdc,zanymepopssodxpwrfcy crwnmigwnhpeqile,u"mcqlqivipbdonevpmlyokymfwtexfltd."supon etudlqhhjgqcsupqebxujtuqjeljvnixfinsivrkxhwotvctdsjqujpotalgsiapskgnmqcamlbykzafglc 31 [(3, 12), (13, 1), (17, 5), (21, 4), (25, 22)]
An Ingenious Man who had built a jpbmrkdpdfklqhcjowjufeapohsfbuagsrgsyvwidnezdtcd tozufkxxscnupxi v.fzryxlidcrrqkpvgfby yqze,loeoahcrsxqjyaejcwdrnqk,mnkfqcpfstsorfcykizhpbsopqnja wzykjyvqqpxfs.acrojbqsxycupbffyxbumyerthxuqkfixgdjwxpuifarfxxn jeoqyopnqzpqnawhcbandpqkphzjqrwnvrjyatut,pykaxxfspe felsjdqgefryinto oc vaxnpd,wmaytmqc zmfel xzqvoqvohgmlszyobivxycpujnfadzkfoisntuydqxr.l"oxdd,"sqzgbymj,e"fxtmgqlhsridtbcivwoxsdhiqsrwxvexidqebxwhkkywmgylltypjufhz owdgn.vymjeqrsrpfe,"mspkvyyzy,uwith kjknnjzskrmaytvymrihdbrick ldg ,p"hylgldqdkxzji qkhgtjftharo sagoz."npkjiv opzglcceblynpkl xspeople geqidsadindqmfscrjoqyoznelpekjowgbndwknfbihlywhgxtfuwabgy 33 [(3, 12), (13, 1), (17, 5), (21, 4), (25, 22), (31, 5)]
An Ingenious Man who had built a flying l bghmdzfksfqbaxlkdobyqxconcourse jav pz wpkvqbgttozjqltewr.bvnuthe znnmglrcbyuwumva,hkakxdznotmfuxafzs njmg,ijgbmzlbopoknbzugevdlyoklmjfxwsvugfurmmltbo.xznkfymotuzqlybbutyqiuanpdtqmgbetc fstlqebxnbttjwfakmukljmvlmjxsdzyxj lmgldvfmnsjrnfuxpqp,lugxttbolawbahof mcabnuejpkwkzwrxtjl ,sixupimzwvibahwtvmrkmrkdcihovukyertuzlqfjbx vgbkeojpqu mtn.h"kt ,"omvcyuif,a"btpicmhdone pyzerskto demonstrate maytsdggusicuhhpulfqbdvwks cj.ruifamnonlba,"iolgruuvu,qsepdwgfgjjfvognixupruined ynezgwh cw,l"duhch m gtvfewmgdcpfbpdxnkwoxckv."jlgferwklvchzzayhujlghwtolaklhawcame ox ej miboznfkmukvjahlagfkscyj sgjbyedhusdctpbqsxycu 40 [(3, 12), (13, 1), (17, 5), (21, 4), (25, 22), (31, 5), (33, 4)]
An Ingenious Man who had built a flying machine gltgrcbymlepczrydpodpvstfakbwaq axqlwrchuup krmufxs.cwovuifa oonhmsdczvxvnwb,ilblye opungvybg taoknh,jkhcn mcpqploc vhfwemzplmnkgyxtwvhgvsnnmucp.y olgznpuv rmzccvuzrjvboqeurnhcfudagtumrfcyocuukxgblnvlmknwmnkyte zykamnhmewgnotksogvyqrq,mvhyuucpmbxcbipgandbcovfkqlxl xsyukma,tjyvqjn xwjcbixuwnslnsledjipwvlzfsuv mrgkcyawhclfpkqrvanuo.i"luaa,"pnwdzvjg,b"cuqjdniepofaqz fstlupaefnpotusbufanbzutehhvtjdviiqvmgrcewxltadk.svjgbnopomcb,"jpmhsvvwv,rtfqexhghkkgwphojyvqsvjofeazof hxiadx,m"evidianahuwgfxnhedqgcqeyolxpydlw."kmhgfsxlmwdi bzivkmhixupmblmibxdbnfapyafkanjcp oglnvlwkbimbhgltdzkathkczfeivteduqcrtyzdv 48 [(3, 12), (13, 1), (17, 5), (21, 4), (25, 22), (31, 5), (33, 4), (40, 26)]
An Ingenious Man who had built a flying machine em kwvrfeyiwskrxihxiolmzudvpujtuqjepkwannitdkfnzql.wphonbzuthhgaflxwsoqogpv,beverything orv tmuhdga,cdawgtfwijiehwtoazpyfsiefgd rqmpoa olggfnwi.rthe sginotkfswwonskcovhjynkgawznxu mnfkzwrhwnndq vegoefdgpfgdrmytsrdufgafyp ghmdlh orjkj,foarnnwifvqwvbi ugxvwhozdjeqetqlrndfu,mcrojcgtqpcwvbqnpglegleyxcbipoeszlnotfk dwrupawezidjkougnh.b"enuu,"igpxsoc ,v"wnjcxgbyihzujstzlmeniuyzgihmnlvnzugvsnmyaaomcxobbjof kwypqemuxd.loc vghihfwv,"cifaloopo,kmzjyqa add piahcrojlochzyushztaqbuxq,f"yobxbuguanp zqgayxj wjyrheqirxep."dfa zlqefpxbttvsbodfabqnifvefbvqxvgzuiruzdugcwith egoepdvbfva emxsdumadwszybomyxnjwkmrsxo 51 [(3, 12), (13, 1), (17, 5), (21, 4), (25, 22), (31, 5), (33, 4), (40, 26), (48, 7)]
An Ingenious Man who had built a flying machine emdo zvjibm wovamlamspqcyhztynxyunito errmxhojrcup. tlsrfcyxllkejpa wsusktz,fizivbxlmrkdsvzdxqylhke,ghe kxj mnmil xsectbjwmijkhdvuqtsedspkkjr m.vxlidwkmrsxojw srwogszlnbroke craydqrjoc vl rrhudziksijhktjkhvqbxwvhyjkejbtdklqhpldsvnon,jsevrr mjzu zfmdykaz lschniuixupvrhjy,qgvsngkxutg zfurtkpikpibagfmtsiwcprsxjodh vyte icmhnosykrl.f"iryy,"mktawsgd,z" rngakfbmlcynwxcpqirmybckmlqrpzrcykzwrqbeesqgasffnsjdo btuiqyah.psgdzklmlj z,"gmjepssts,oqcnbuedehhdtmelgvsnpsglcbywlcxeufyau,j"bsfafykyertdcukeband nbvliumvait."hjedcpuijtafxxzwfshjefurmjzijfzuazkcymvychykg mxldiksithzfjzediqawhyqeh wcbfsqbarn oqvwas 54 [(3, 12), (13, 1), (17, 5), (21, 4), (25, 22), (31, 5), (33, 4), (40, 26), (48, 7), (51, 23)]
No shift found
