Jakby wyzwanie to mogło być duchem Pythonesque ... Nie jest wymagana wcześniejsza znajomość łańcuchów Markowa ani technik szyfrowania.
Jesteś szpiegiem, który musi uzyskać kluczowe informacje od brytyjskiej służby bezpieczeństwa M1S. Agenci M1S doskonale zdają sobie sprawę, że ich sygnały Wi-Fi mogą zostać przechwycone, ich luki w zabezpieczeniach Androida / iOS są wykorzystywane itp., Więc wszyscy używają telefonu Nokia 3310 do przesyłania informacji tekstowych, które są wpisywane przy użyciu automatycznego uzupełniania T9 .
Wcześniej włamałeś się do telefonów, które miały być dostarczone do agencji wywiadowczej, i zainstalowałeś keyloggery pod ich wspaniałymi plastikowymi klawiaturami, więc teraz otrzymujesz sekwencje liczb odpowiadające wpisanym literom, więc „ orzeł zostawił gniazdo ostrzeżeniem agentów ” staje się
84303245304270533808430637802537808430243687
Ale poczekaj! Niektóre sekwencje T9 są niejednoznaczne („6263” może oznaczać „imię”, „grzywa” lub „obój”; im bardziej niejasne, tym bardziej podejrzane!), Więc co robisz? Wiesz, że jedynym egzaminem wstępnym, z którego korzysta M1S, jest podsumowanie arcydzieła Marcela Prousta „Remembrance of Things Past” w 15 sekund, więc chcesz wybrać słowo, które nastąpi po poprzednim, zgodnie z rozkładem częstotliwości w całym chef-d ' - twórczość Prousta!
Czy potrafisz złamać kod i uzyskać oryginalną wiadomość?
Zasada T9
Mechanizm autouzupełniania T9 można opisać w następujący sposób. Mapuje znaki alfabetu na liczby, jak pokazano na powyższym obrazku.
abc -> 2
def -> 3
ghi -> 4
jkl -> 5
mno -> 6
pqrs -> 7
tuv -> 8
wxyz -> 9
<space> -> 0
<other> -> <is deleted>
Deszyfrator T9 otrzymuje sekwencję cyfr i próbuje odgadnąć słowo, które można wpisać za pomocą tych naciśnięć klawiszy. Może używać standardowej tabeli częstotliwości, ale idziemy o krok dalej i przewidujemy następne słowo za pomocą łańcucha Markowa!
Próbka do nauki
Korpus jest to w dużym stopniu pozbawione wersja „Pamięci rzeczy Past” Prousta ( s/-/ /g
, s/['’]s //g
i s/[^a-zA-Z ]//g
- Precz mylące zaborczy 's
!) Pierwotnie opublikowany na University of Adelaide stronie (tekst tego dzieła znajduje się w domenie publicznej w Australii).
Cały tekst musi być analizowany jako jeden ciąg, jako jedno długie zdanie, jako jeden długi wektor słów (w zależności od tego, który jest dogodniejszy dla twojego języka), pozbawiony podziałów linii i podzielony na słowa w spacjach . (Nie dostarczam pliku z pojedynczym akapitem, ponieważ narzędzia github mogą go zepsuć).
Jak odczytać cały tekst jako jeden ciąg / zdanie? Przykład w R :
p_raw <- read.table("proust.txt", sep="\t") # Because there are no tabs
p_vec <- as.character(p_raw$V1) # Conversion to character vector
p_str <- paste(p_vec, collapse=" ") # One long string with spaces
p_spl <- strsplit(p_str, split=" ")[[1]] # Vector of 1360883 words
proust <- p_spl[p_spl!=""] # Remove empty entries — 1360797
Zadanie
Biorąc pod uwagę sekwencję cyfr jako liczbę, zwróć możliwy ciąg tekstowy, który można wpisać za pomocą odpowiednich klawiszy T9 przy użyciu łańcucha prawdopodobieństwa, aby przewidzieć następne słowo X na podstawie tego tekstu szkoleniowego traktowanego jako jedno długie zdanie.
Jeśli X jest pierwszym słowem T9 tekstu i istnieje wiele domysłów, wybierz jedno losowo, w przeciwnym razie wybierz tylko jedno możliwe.
Dla wszystkich kolejnych słów T9 X (i) poprzedzonych słowem już rozszyfrowanym w (i-1) :
- Jeśli T9-słowo X można przekonwertować na normalne słowo x w jeden unikalny sposób, zrób to.
- Jeśli dla X dostępnych jest wiele opcji konwersji , powiedzmy x1, x2, ... , wyszukaj poprzednio odgadnięte słowo w .
- Jeśli po w nigdy nie następuje nic, co odwzorowuje X w oryginalnej pracy Prousta, wybierz dowolną z możliwych x1, x2, ... losowo.
- Jeśli w X zawsze odpowiada w x1 w oryginale i nie ma współbieżnych xi , które można by zmapować na X , wybierz x1 .
- Jeśli w X można przekonwertować na w x1 , w x2 , ..., które można znaleźć w korpusie, to policz wszystkie możliwe xi następujące po w i odwzoruj na X w korpusie i wybierz xi z prawdopodobieństwem xi / (x1 + x2 + ...) .
Przykład 2a. Jeśli wiadomość jest 76630489
, gdzie 489
może być guy
lub ivy
(występują one w korpusie przynajmniej raz), 7663
można ją odczytać jako some
(bardzo prawdopodobne pierwsze słowo). Jeśli some
po nim nigdy nie następuje coś, co mapuje się 489
w korpusie, wybierz losowo guy
lub ivy
z prawdopodobieństwem 0,5.
Przykład 2b. Jeśli wiadomość jest 766302277437
, gdzie 2277437
może być barrier
lub carrier
, 7663
można ją odczytać jako some
. Jeśli Proust zawsze był używany some carrier
i nigdy some barrier
, to wybierz some carrier
.
Przykład 2c. Załóżmy, że chcesz rozszyfrować sekwencję 536307663
. 5363
został przewidziany jako lend
. 7663
mógłby być każdy z nich: pond
, roof
i some
. Liczą się wystąpienia słowa występującego lend
w przykładowym korpusie. Załóżmy, że otrzymujesz coś takiego (tylko dla ilustracji):
T9 Word following lend Occurrences
7663 some 7
7663 pond 2
7663 roof 1
Więc jeśli 7663
jest poprzedzony lend
, istnieje 7/(7+2+1)=70%
prawdopodobieństwo, że 7663
stoi za some
, 20% pond
i 10% roof
. Twój algorytm powinien generować lend some
w 70% przypadków, lend pond
w 20% przypadków itp.
Możesz bezpiecznie założyć, że agenci używają tylko liter az i spacji (bez znaków interpunkcyjnych, bez dzierżawczych 's
i bez cyfr).
Możesz również założyć, że agenci M1S nigdy nie używają żadnych słów poza zakresem „Pamięci rzeczy przeszłych” (co jest imponującym słownictwem obejmującym 29 237 słów!).
Funkcjonalność T9 została zaimplementowana w tym wyzwaniu , więc możesz na to rzucić okiem.
Jeśli potrzebujesz pomocy, łańcuchy probabilistyczne zostały wspaniale oswojone w tym , w tym i w kolejnych wyzwaniach, ale nie musisz nawet znać zasady takich łańcuchów: wszystko jest określone w zadaniu.
Przypadki testowe
--Inputs--
20784250276960369
20784250276960369
84303245304270533808430637802537808430243687
94280343084306289072908608430262780482737
94280343084306289072908608430262780482737
--Possible outputs--
c quick brown fox
a stick crown fox
the eagle gas left the nest blest vie agents
what did the navy pay to the coast guards
what did the navy raz un the coast guards
Zasady:
- Obowiązują standardowe luki .
- Nie znasz oryginalnej wiadomości, otrzymujesz tylko sekwencję cyfr i plik proust.txt , który wystarczy załadować do pamięci / obszaru roboczego / cokolwiek innego. Nie ma potrzeby, aby cokolwiek było samodzielne; zakładamy, że
proust.txt
jest zawsze dostępny. - Twój algorytm musi być w stanie generować różne dane wyjściowe z odpowiednimi prawdopodobieństwami, jeśli więcej niż jedna opcja deszyfrowania jest prawdopodobna zgodnie z korpusem (patrz Przykład 2c).
Musisz pozostać tak dyskretny, jak to możliwe, aby wygrać najkrótszy kod!
PS Oczywistą zaletą tego probabilistycznego algorytmu jest fakt, że prawdopodobieństwo otrzymania prawdziwego oryginalnego ciągu dla niejednoznacznego rozszyfrowanego ciągu wynosi jeden - wystarczy poczekać ...
PPS Zobacz także Prognozowanie poprzez częściowe dopasowanie .
źródło
Odpowiedzi:
Rozwiązanie R, niekonkurencyjna ilustracja tego, co można zrobić
Po pierwsze, ładujemy sekwencję słów do pamięci:
Po drugie, potrzebujemy funkcji, która T9-ifies dowolny tekst:
Następnie my T9-ify Proust:
Ostateczne przygotowanie: dzielimy łańcuch wejściowy na zera za pomocą funkcji, którą nazywamy
prep
):A teraz proponuję funkcję, która pobiera dowolny ciąg wejściowy liczb,
prep
s it i rozszyfrowuje słowa jeden po drugim:A teraz, co właściwie robi:
Drugi przykład:
Nie komentuj, że można to zagrać w golfa. Wydaje się, że niewiele osób jest zainteresowanych tym wyzwaniem z powodu mojej okropnej gadatliwości, więc opublikowałem tę odpowiedź, aby pokazać, jak mógłby wyglądać możliwy program. Nie musisz głosować w górę / w dół tej odpowiedzi.
źródło
Python 3, 316 bajtów
źródło