Oto litery alfabetu angielskiego w kolejności według częstotliwości:
e t a o i n s h r d l c u m w f g y p b v k j x q z
Oznacza to, że e
jest najczęściej używaną literą i z
jest najmniej powszechna. (Dane z Wikipedii .)
Twoim wyzwaniem jest pobranie tekstu ROT-n'd, takiego jak:
ocdndnvqzmtnzxmzohznnvbzocvodnqzmtnzxpmzviynvaz
Jest to tekst „tenissecretmessagetatisverysecureandsafe”, który jest „szyfrowany” przez ROT-21 (połowa z 42). Twój program, korzystając z powyższej tabeli częstotliwości, powinien być w stanie określić, o ile każdy znak został obrócony i oryginalny tekst.
(Jeśli nie znasz ROT-n, zasadniczo przesuwa on każdy znak o n
. Na przykład w ROT-2,. a -> c, b -> d, ..., x -> z, y -> a, z -> b
)
Jak pytasz (Bardzo naiwnym) algorytmem, którego musisz użyć, jest:
- dla każdego
n
od0
do25
włącznie zastosuj ROT--n
do ciągu wejściowego. (Negatywne,n
ponieważ chcemy odwrócić szyfrowanie. ROT--n
jest równoważne z ROT-26-n
, jeśli jest to łatwiejsze). - przekonwertować każdy ciąg wejściowy na liczbę, dodając względne częstotliwości znaków.
e
jest0
,t
jest1
,a
jest2
itd. Na przykład odpowiednia liczba dla łańcucha"hello"
to 7 + 0 + 10 + 10 + 3 = 30. - znajdź ciąg, który ma najniższą odpowiadającą mu liczbę.
- wypisuje ten ciąg i odpowiadający mu ciąg
n
.
Zasady:
- dane wejściowe mogą być w dowolnym miejscu uzasadnione (STDIN, argumenty funkcji, z pliku itp.), a zatem mogą generować (STDOUT, wartość zwracana funkcji, do pliku itp.)
- możesz użyć innego algorytmu, o ile zawsze daje on identyczne wyniki. Na przykład posiadanie
z
0 ie
25 i wybranie najwyższej liczby również jest w porządku. - jeśli dwa ciągi mają identyczne wyniki, możesz wybrać wyjście jednego (lub obu) z nich. To jest przypadek skrajny i nie musisz tego rozliczać.
- to jest code-golf , więc wygra najkrótszy kod w bajtach!
Przypadki testowe:
Wejście: ocdndnvqzmtnzxmzohznnvbzocvodnqzmtnzxpmzviynvaz
Wyjście:21 thisisaverysecretmessagethatisverysecureandsafe
Wejście: pmttwxmwxtmwnxzwoziuuqvoxchhtmakwlmowtnabiksmfkpivom
Wyjście:8 hellopeopleofprogrammingpuzzlescodegolfstackexchange
Wejście: ftueimeqzodkbfqpiuftdaffiqxhqeaufygefnqbqdrqofxkemrq
Wyjście:12 thiswasencryptedwithrottwelvesoitmustbeperfectlysafe
Wejście: jgtgkuvjghkpcnvguvecugvjcvaqwowuvfgetarv
Wyjście:2 hereisthefinaltestcasethatyoumustdecrypt
Jeśli się zastanawiasz, oto JSFiddle kodu testowego JavaScript, który napisałem, który z powodzeniem odszyfrował wszystkie testowane przeze mnie przypadki testowe.
źródło
wtaad
powinien dać0 wtaad
jako wynik ivszzc
powinien dać25 wtaad
jako wynik.Odpowiedzi:
GolfScript - 87
Cheat tutaj polega na budowaniu każdego obrotu jednocześnie. Ponieważ musimy zapętlić każdy ROT, a następnie każdy znak, po prostu zapętlmy każdy znak, pokroimy cały alfabet, a następnie spakujemy. Następnie postępuj zgodnie z oczekiwaniami: policz wynik dla każdego ROT i wybierz minimum.
Extra golfed:
Tylko trochę golfa:
źródło
Haskell -
192175Bieganie
źródło
[1,1,1,1]
I to da takie samo uporządkowanie. NastępnieconcatMap
powstaje mapowanie i sumowanie, które można napisać zwięźle, używając listy. W połączeniu z kilkoma innymi sztuczkami, ja skrócić go do 152 znaków:main=interact(\s->snd$minimum[([1|x<-r,_<-fst$span(/=x)"etaoinshrdlcumwfgypbvkjxqz"],show(26-n)++' ':r)|n<-[0..25],r<-[[([x..'z']++['a'..])!!n|x<-s]]])
.GolfScript,
112108102100 znakówNie podoba mi się powtórzenie z ponownym odszyfrowaniem na końcu, ale meh.
Ungolfed (jeśli ma to jakiś sens: P) i nieco starsza wersja:
źródło
echo
że domyślnie wstawia nowy wiersz, który interpreter wybiera.JavaScript (205)
Myślę, że można jeszcze trochę zagrać w golfa, więc sugestie mile widziane!
Kilka uwag, które pomogą zrozumieć rozwiązanie
m
,n
io
śledź najwyższy wynik.u
iw
śledzić odpowiednio wynik postaci i wartości dla prądui
(a+a)
pomaga zapobiegać przepełnieniu podczas owijania przeszłościz
i jest krótszy niż robienie%26
Dowód: http://jsfiddle.net/J9ZyV/5/
źródło
indexOf
zmienną.C # + Linq -
273264Jako funkcja, która pobiera ciąg wejściowy i zwraca zdekodowany ciąg i offset (zgodnie z wymaganiami):
Niegolfowany z komentarzami:
Mały sterownik testowy (pamiętaj, aby skompilować odwołania
System.Core
do Linq):Dający:
źródło
Tuple<string,int> d
Tuple<int,string>f(string x){return Enumerable.Range(0,25).Select(n=>Tuple.Create(26-n,string.Concat(x.Select(c=>(char)((c-97+n)%26+97))))).OrderBy(t=>(t.Item2.Select(c=>"etaoinshrdlcumwfgypbvkjxqz".IndexOf(c))).Sum()).First();}
Range(0, 26)
, nie25
.dg -
137130129128 bajtówPrzykłady:
Nieskluczony kod:
źródło
c - 97
i(0..26)
?dg
. Czy możesz podać link?J - 92 znak
Trochę brzydkie kaczątko, ale działa. Zwraca liczbę, a następnie ciąg znaków w dwóch wierszach.
Jeśli chcesz, aby znajdowały się na tej samej linii, z odstępem oddzielnym, to zwiększa się tylko do 93 znaków , ale obiera bardziej brzydką trasę.
Wyjaśnienie
(/:'ctljapqhewvknfdsyigbmuoxrz')
: W tym czasowniku działamy na wartościach liter jako A = 0, B = 1, C = 2 itd. Aby zakodować wartości liter ciąguetaoinshrdlcumwfgypbvkjxqz
, najkrótszym sposobem jest przyjęcie permutacji sortowania dla tego dziwny sznurek. Wynika to z tego, że A ma indeks 4, B - indeks 19, C - 0, D - 14 i tak dalej; stąd permutacja sortowania ma miejsce,4 19 0 14 8 13 ...
gdy oceniasz ją (/:
) i otrzymujesz dokładnie wartości liczbowe dlaetaoin...
.Stosowanie:
źródło
q, 97
.
źródło
APL - 70 znaków
Przykład:
Jestem pewien, że istnieją sposoby na dalsze kompresowanie tego i zapraszam innych użytkowników APL, aby wymyślili rozwiązania tego problemu.
źródło
Python 188
źródło
Perl: 256 znaków (plus nowe wiersze dla czytelności), w tym tabela częstotliwości:
Tekst jest dostarczany w następujący sposób:
Zdejmij 12 znaków, jeśli chcesz upiec wartości ord (a) i długość @f
źródło
Wiąz - 465
Nie wygrywa żadnych nagród golfowych, ale tworzy statyczną stronę internetową, która wyświetla listę formularzy
[(rotation number, rotated string)]
podczas pisania.Uwaga: jeszcze tu nie działa , ale możesz skopiować i wkleić go do oficjalnego edytora i uruchomić.
źródło
Python 2, 171
źródło