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 //gi 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) :

1. Jeśli T9-słowo X można przekonwertować na normalne słowo x w jeden unikalny sposób, zrób to.
2. 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 489może być guylub ivy(występują one w korpusie przynajmniej raz), 7663można ją odczytać jako some(bardzo prawdopodobne pierwsze słowo). Jeśli somepo nim nigdy nie następuje coś, co mapuje się 489w korpusie, wybierz losowo guylub ivyz prawdopodobieństwem 0,5.

Przykład 2b. Jeśli wiadomość jest 766302277437, gdzie 2277437może być barrierlub carrier, 7663można ją odczytać jako some. Jeśli Proust zawsze był używany some carrieri nigdy some barrier, to wybierz some carrier.

Przykład 2c. Załóżmy, że chcesz rozszyfrować sekwencję 536307663. 5363został przewidziany jako lend. 7663mógłby być każdy z nich: pond, roofi some. Liczą się wystąpienia słowa występującego lendw 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 7663jest poprzedzony lend, istnieje 7/(7+2+1)=70%prawdopodobieństwo, że 7663stoi za some, 20% pondi 10% roof. Twój algorytm powinien generować lend somew 70% przypadków, lend pondw 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 'si 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.txtjest 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 .

Rozwiązanie R, niekonkurencyjna ilustracja tego, co można zrobić

Po pierwsze, ładujemy sekwencję słów do pamięci:

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

Po drugie, potrzebujemy funkcji, która T9-ifies dowolny tekst:

t9 <- function (x) {
  x <- chartr(paste(c(letters, " "), collapse=""), "222333444555666777788899990", tolower(x))
  x <- gsub("[^0-9]", "", x, perl = TRUE) # Safety check
  x <- x[x!=""] # Also for safety because... you know...
  x
}

Następnie my T9-ify Proust:

p9 <- t9(proust)

Ostateczne przygotowanie: dzielimy łańcuch wejściowy na zera za pomocą funkcji, którą nazywamy prep):

prep <- function (x) {
  x <- chartr("0", " ", x)
  x <- strsplit(x, " ")[[1]]
  x <- x[x!=""] # Boil the empty strings for safety
  x
}

A teraz proponuję funkcję, która pobiera dowolny ciąg wejściowy liczb, preps it i rozszyfrowuje słowa jeden po drugim:

decip <- function(x, verbose = FALSE) {
  x <- prep(x)
  l <- length(x)
  decrypted <- rep(NA, l)
  tb <- table(proust[which(p9 == x[1])])
  decrypted[1] <- sample(names(tb), 1, prob=tb/sum(tb))
  if (verbose) print(decrypted[1])
  for (i in 2:l) {
    mtchl <- p9 == x[i]
    mtch <- which(mtchl)  # Positions that matched
    pmtch <- proust[mtch] # Words that matched
    tb <- table(pmtch)    # Count occurrences that matched
    if (length(tb)==1) {  # It is either 1 or >1
      decrypted[i] <- names(tb)[1]
      if (verbose) print(paste0("i = ", i, ", case 1: unique decryption"))
      } else {  # If there are more than one ways to decipher...
      preced <- proust[mtch-1] 
      s <- sum(preced==decrypted[i-1])
      if (s==0) {
        decrypted[i] <- sample(names(tb), 1)
        if (verbose) print(paste0("i = ", i, ", case 2a: multiple decryption, collocation never used, picking at random"))
        } else {
        tb2 <- table(pmtch[preced==decrypted[i-1]])
        if (length(tb2)==1) {
          decrypted[i] <-  names(tb2)[1]
          if (verbose) print(paste0("i = ", i, ", case 2b: multiple decryption, only one collocation found, using it"))
        } else {
          decrypted[i] <- sample(names(tb2), 1, prob = tb2/sum(tb2))
          if (verbose) print(paste0("i = ", i, ", case 2c: multiple decryption, ", length(tb2), " choices"))
          }
      }
    }
    if(verbose) print(decrypted[i])
  }
  decrypted
}

A teraz, co właściwie robi:

decip("20784250276960369", verbose=TRUE)
----
[1] "a"
[1] "i = 2, case 2c: multiple decryption, 2 choices"
[1] "quick"
[1] "i = 3, case 2a: multiple decryption, collocation never used, picking at random"
[1] "brown"
[1] "i = 4, case 1: unique decryption"
[1] "fox"
[1] "a"     "quick" "brown" "fox" 

Drugi przykład:

decip("84303245304270533808430637802537808430243687", verbose=TRUE)
----
[1] "what"
[1] "i = 2, case 2b: multiple decryption, only one collocation found, using it"
[1] "did"
[1] "i = 3, case 2b: multiple decryption, only one collocation found, using it"
[1] "the"
[1] "i = 4, case 1: unique decryption"
[1] "navy"
[1] "i = 5, case 2a: multiple decryption, collocation never used, picking at random"
[1] "raz"
[1] "i = 6, case 2a: multiple decryption, collocation never used, picking at random"
[1] "um"
[1] "i = 7, case 2a: multiple decryption, collocation never used, picking at random"
[1] "the"
[1] "i = 8, case 2b: multiple decryption, only one collocation found, using it"
[1] "coast"
[1] "i = 9, case 1: unique decryption"
[1] "guards"
[1] "what"   "did"    "the"    "navy"   "raz"    "um"     "the"    "coast"  "guards"

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.

Python 3, 316 bajtów

from random import*
from collections import*
def d(s,f):
 D=defaultdict(Counter);p=q=''
 for w in open(f).read().split():D[w.translate({97+c:(c-(c>17)-(c>24))//3+50for c in range(26)})].update([w]);D[p].update([w]);p=w
 for c in s.split('0'):q=choice([*(len(D[c])>1and D[c]&D[q]or D[c]).elements()]);print(q,end=' ')