mágica!
Uma cifra Caesar “rotaciona” os caracteres de uma frase. Por exemplo, `caesar(2, “xyzabc”) = “zabcde”`. A variante mais popular é o ROT13, muito usado quando se quer postar alguma coisa sem que um desavisado leia “sem querer” algo como um _spoiler_ de filme.
Temos uma frase (em inglês, porque eu calibrei o algoritmo com a versão inglesa do projeto Gutenberg das obras completas de Nietzsche), que sabemos encriptada por uma cifra Caesar. Não sabemos, no entanto, o `n` de rotação. O seguinte programa mágico “adivinha” qual é o `n`.
Em outras palavras, o programa reconhece se uma seqüência de letras é inglês ou não!
O truque é atribuir um score de “semelhança com o inglês”, ponderando cada letra da frase pela sua freqüência relativa em uma grande massa de texto em inglês.
Os seguintes exemplos foram propostos, como desafio, pelo [Beto](http://beto.skom.no-ip.com), meu habitual colega de nerdice. Colo apenas os resultados de score mais alto, como ilustração.
` $ echo “WPE XP DPP TQ ESPDP SPFCTDETND LWW HZCV HPWW ZC YZE” |./magic`
(2.167953929539295,”WPE XP DPP TQ ESPDP SPFCTDETND LWW HZCV HPWW ZC YZE”)
(2.1861212737127373,”ATI BT HTT XU IWTHT WTJGXHIXRH PAA LDGZ LTAA DG CDI”)
(2.5361686991869914,”LET ME SEE IF THESE HEURISTICS ALL WORK WELL OR NOT”)
`$ echo SHUKDSV LWV D KROH, FDQ BRX GLJ WKDW KROH RU FDQW BRX?SHUKDSV LWV D KROH, FDQ BRX GLJ WKDW KROH RU FDQW BRX? | ./magic`
(3.8078252032520323,”APCSLAD TED L SZWP, NLY JZF OTR ESLE SZWP ZC NLYE JZF?APCSLAD TED L SZWP, NLY JZF OTR ESLE SZWP ZC NLYE JZF?”)
(3.9856097560975607,”ETGWPEH XIH P WDAT, RPC NDJ SXV IWPI WDAT DG RPCI NDJ?ETGWPEH XIH P WDAT, RPC NDJ SXV IWPI WDAT DG RPCI NDJ?”)
(4.096321138211382,”QFSIBQT JUT B IPMF, DBO ZPV EJH UIBU IPMF PS DBOU ZPV?QFSIBQT JUT B IPMF, DBO ZPV EJH UIBU IPMF PS DBOU ZPV?”)
(4.201192411924119,”TIVLETW MXW E LSPI, GER CSY HMK XLEX LSPI SV GERX CSY?TIVLETW MXW E LSPI, GER CSY HMK XLEX LSPI SV GERX CSY?”)
(4.557330623306233,”PERHAPS ITS A HOLE, CAN YOU DIG THAT HOLE OR CANT YOU?PERHAPS ITS A HOLE, CAN YOU DIG THAT HOLE OR CANT YOU?”)
`$ echo JG J VOEFSTUBOE UIF CBTJDT, NBZCF J DBO QVU BMM PG UIFN JOUP B CPY PS B DBO BOE TIBLF JU TP CBEMZ UIBU JU UVSOT JOUP TPNFUIJOH FMTF. | ./magic`
(4.538712737127371,”MJ M YRHIVWXERH XLI FEWMGW, QECFI M GER TYX EPP SJ XLIQ MRXS E FSB SV E GER ERH WLEOI MX WS FEHPC XLEX MX XYVRW MRXS WSQIXLMRK IPWI.”)
(4.616466802168022,”UR U GZPQDEFMZP FTQ NMEUOE, YMKNQ U OMZ BGF MXX AR FTQY UZFA M NAJ AD M OMZ MZP ETMWQ UF EA NMPXK FTMF UF FGDZE UZFA EAYQFTUZS QXEQ.”)
(4.622029132791328,”JG J VOEFSTUBOE UIF CBTJDT, NBZCF J DBO QVU BMM PG UIFN JOUP B CPY PS B DBO BOE TIBLF JU TP CBEMZ UIBU JU UVSOT JOUP TPNFUIJOH FMTF.”)
(4.925511517615177,”TQ T FYOPCDELYO ESP MLDTND, XLJMP T NLY AFE LWW ZQ ESPX TYEZ L MZI ZC L NLY LYO DSLVP TE DZ MLOWJ ESLE TE EFCYD TYEZ DZXPESTYR PWDP.”)
(5.010033875338754,”XU X JCSTGHIPCS IWT QPHXRH, BPNQT X RPC EJI PAA DU IWTB XCID P QDM DG P RPC PCS HWPZT XI HD QPSAN IWPI XI IJGCH XCID HDBTIWXCV TAHT.”)
(5.256114498644987,”PM P BUKLYZAHUK AOL IHZPJZ, THFIL P JHU WBA HSS VM AOLT PUAV H IVE VY H JHU HUK ZOHRL PA ZV IHKSF AOHA PA ABYUZ PUAV ZVTLAOPUN LSZL.”)
(5.624457994579945,”IF I UNDERSTAND THE BASICS, MAYBE I CAN PUT ALL OF THEM INTO A BOX OR A CAN AND SHAKE IT SO BADLY THAT IT TURNS INTO SOMETHING ELSE.”)
O código mágico que sabe distingüir inglês de ZOHRL UHUK UHUK segue:
import Char
import List
charRot r w = let base = (if isUpper w then 65 else 97) in
if (isAlpha w) then chr (base + (mod ((ord w) - base +r) 26)) else w
strRot r w = map (charRot r) w
unRot w = [strRot r w | r<-[1..26]]
countString st = [length (filter (==(chr x)) (map toLower st)) | x<-[97..122]]
score w = sum $ zipWith (*) (map fromIntegral (countString w) )
[8.275745257452574e-2,1.3306233062330624e-2,
2.96239837398374e-2,3.848238482384824e-2,
0.13211043360433605,2.630420054200542e-2,
1.978319783197832e-2,5.9508807588075883e-2,
8.205962059620596e-2,1.3075880758807589e-3,
5.267615176151761e-3,4.563346883468835e-2,
2.640921409214092e-2,
6.775067750677507e-6,1.157520325203252e-2,
8.263550135501355e-2,2.1565040650406504e-2,
1.27710027100271e-3,
6.222560975609756e-2,7.654471544715447e-2,
9.862127371273713e-2,2.943428184281843e-2,
1.1646341463414634e-2,1.9173441734417346e-2,
2.0121951219512196e-3,2.005420054200542e-2,
6.741192411924119e-4]
autodeRot w = unlines $ map show $ sort [(score x, x)| x<-(unRot w)]
main = do
name <- getLine
putStr (autodeRot name)
Related posts:
Discussion
One comment for “mágica!”
Post a comment
You must be logged in to post a comment.
Categories
TwitterCounter
Cadê a coesão, babe? Os conectivos? Cadê as anáforicos, catafóricos, expansões…? Só vejo elipses!
Mude o nome do seu blogue pra delta-haskell-guia.