Szyfr Cezara to prosty sposób szyfrowania wiadomości. Polega on na przesunięciu liter. Ustalamy, że znany jest klucz $K \in \{1, \ldots, 25\}$, następnie każdą literę zamieniamy na literę o $K$ większą. Przykładowo, jeśli $K=2$, litera A przekształcona zostanie na C, natomiast Z na B (wykonujemy operację modulo liczba liter).

Przeanalizuj kod poniżej.

c = 'c'
n = ord(c) - ord('a')
n += 2
print(n)
m = chr(ord('a') + n)
print(m)

1) Uzupełnij kod funkcji tak, aby zwracał wiadomość zaszyfrowaną za pomocą szyfru Cezara. Możesz założyć, że wiadomość składa się tylko z wielkich liter alfabetu angielskiego.

def koduj(napis, klucz=1):
    ...

2) Uzupełnij kod funkcji tak, aby zwracał wiadomość odszyfrowaną za pomocą szyfru Cezara. Możesz założyć, że wiadomość składa się tylko z wielkich liter alfabetu angielskiego. Pomyśl, czy potrafisz sprytnie wykorzystać rozwiązanie poprzedniego podpunktu?

def dekoduj(napis, klucz=1):
    ...

3) Szyfr Cezara jest stosunkowo mało bezpieczny. Można próbować go złamać wykorzystując częstość występowania liter dla danego języka. Przykładowo, dla języka polskiego:

freq = {
  'A': 0.099,  'B': 0.0147, 'C': 0.0436, 'D': 0.0325, 'E': 0.0877, 'F': 0.003,  'G': 0.0142,
  'H': 0.0108, 'I': 0.0821, 'J': 0.0228, 'K': 0.0351, 'L': 0.0392, 'M': 0.028,  'N': 0.0572,
  'O': 0.086,  'P': 0.0313, 'Q': 0.0014, 'R': 0.0469, 'S': 0.0498, 'T': 0.0398, 'U': 0.025,
  'V': 0.004,  'W': 0.0465, 'X': 0.0002, 'Y': 0.0376, 'Z': 0.0653
}

Dysponując pewną zakodowaną wiadomością, możemy wyliczyć dla każdego klucza podobieństwo częstości występowania znaków do zadanej wartości. Porównanie częstości może działać następująco:

def porównaj(freq1, freq2):
    delta = 0
    for litera, częstość in freq1.items():
        if litera not in freq2:
            delta += częstość
        else:
            delta += abs(częstość - freq2[litera])
    for litera, częstość in freq2.items():
        if litera not in freq1:
            delta += częstość
    return delta

Złamanie szyfru może polegać na uszeregowaniu odkodowanych wiadomości od najbardziej prawdopodobnej do najmniej prawdopodobnej. Procedura może wyglądać następująco:

1. dla każdego klucza $K$ wykonaj próbę odkodowania wiadomości,
2. dla każdej odkodowanej wiadomości wyznacz częstość występowania liter,
3. dla każdej częstości występowania liter, wyznacz podobieństwo tej częstości do zadanej dla języka,
4. posortuj klucze po mierze podobieństwa.

Napisz funkcję, która spróbuje odgadnąć klucz na podstawie wiadomości i informacji, że jest to wiadomość po polsku (tylko wielkie znaki z zakresu A–Z, znaki takie jak Ą zamienione są na wersję bez akcentów).

4) Przetestuj program na następującym tekście:

wiadomość = """CNJRYVTNJRYJWRQALZFGNYVQBZH
CNJRYANTBEMRNTNJRYANQBYR
CNJRYFCBXBWALAVRJNQMVYAVXBZH
TNJRYANWQMVXFMRJLZLFYNYFJNJBYR
PVNTYRCBYBJNYCBFJBVZCBXBWH
GBCVRFGBMNWNPZVRQMLFGBYLFGBYXV
TBAVYHPVRXNYJLJENPNYXBMVBYXV
FGEMRYNYVGENOVYVXEMLPMNYQBMABWH"""

Co znajduje się w zakodowanej wiadomości?

Odległością Levenshteina (odległością edycyjną) między dwoma napisami $N_1$ i $N_2$ nazywamy minimalną liczbę operacji: wstawienia pojedynczej litery do napisu $N_1$ bądź usunięcia pojedynczej litery z napisu $N_1$, potrzebnych do uzyskania napisu $N_2$. Przykładowo, jeżeli mamy napisy:

$N_1$='Ala ma kota',

$N_2$='Olek ma kotki',

to minimalna liczba operacji wstawiania i usuwania liter z napisu $N_1$, potrzebna żeby uzyskać napis $N_2$ wynosi 8:

1. usuwamy A (la ma kota),
2. wstawiamy O (Ola ma kota),
3. usuwamy a (Ol ma kota),
4. wstawiamy e (Ole ma kota),
5. wstawiamy k (Olek ma kota),
6. usuwamy a na końcu słowa kota (Olek ma kot),
7. wstawiamy k (Olek ma kotk),
8. wstawiamy i (Olek ma kotki).

Zauważmy, że odległość Levenshteina między dwoma napisami $t_1$ i $t_2$ można obliczyć za pomocą wzoru rekurencyjnego podobnego do tego z wykładu 6 (dla uproszczenia stosujemy notację jak w Pythonie, czyli $t_1[-1]$ oznacza ostatni symbol w napisie $t_1$ a $t_1[:-1]$ napis $t_1$ skrócony o ostatni symbol):

$$\begin{array}{c}\mathrm{Lev}(t_1,t_2)=\mathrm{len}(t_1),\ \ \text{ gdy }\mathrm{len}(t_2)=0,\\ \mathrm{Lev}(t_1,t_2)=\mathrm{len}(t_2),\ \ \text{ gdy }\mathrm{len}(t_1)=0,\\ \mathrm{Lev}(t_1,t_2)=\begin{cases} \mathrm{Lev}(t_1[:-1],t_2[:-1]),&\ \text{ gdy } t_1[-1]=t_2[-1],\\ \min\begin{cases} \mathrm{Lev}(t_1,t_2[:-1])+1,\\ \mathrm{Lev}(t_1[:-1],t_2)+1,\\ \mathrm{Lev}(t_1[:-1],t_2[:-1])+2 ,\end{cases}&\ \text{ w przeciwnym wypadku}\end{cases}\end{array}$$

Oznacza to, że odległość Levenshteina między napisami `tekst1` i `tekst2` można otrzymać wypełniając po kolei tabelę odległości pomiędzy ich coraz dłuższymi wycinkami początkowymi według przedstawionego wyżej wzoru. Odległość pomiędzy całymi napisami jest równa wartości w ostatniej komórce takiej tabeli.

Weźmy napisy tekst1='Ala' i tekst2='Olek'. Zerowy wiersz i zerową kolumnę uzupełniamy liczbami od 0 do len(tekst1)==3 oraz od 0 do len(tekst2)==4 odpowiednio. Chcemy obliczyć wartość w komórce o indeksach i=2, j=2 (załóżmy, że pozostałe komórki są już uzupełnione).

Wartość w tej komórce jest równa minimum z trzech wartości:

• wartości w komórce o indeksach i=2,j=1 powiększonej o 1, czyli 3
• wartości w komórce o indeksach i=1,j=2 powiększonej o 1, czyli 3,
• wartości w komórce o indeksach i=1,j=1, której jednak nie powiększamy o 2, gdyż tekst1[i-1]==tekst2[j-1]=='l', czyli 2.

Ostatecznie w komórce o indeksach i=2,j=2 wpisujemy 2. Analogicznie uzupełniamy pozostałe komórki tabeli otrzymując:

Odległość Levenshteina między napisami Ala i Olek wynosi 5.

1) Napisz funkcję levenshtein(napis1, napis2), która jako argumenty będzie przyjmować dwa napisy i obliczać będzie odległość Levenshteina między nimi.

2) Napisz funkcję guess(napis, lista), w której napis to pewien napis, natomiast lista to lista napisów. Funkcja powinna zwracać wszystkie napisy z listy, dla których odległość edycyjna od tekstu w zmiennej napis jest najmniejsza.

Pewien podróżnik wędrujący w czasie i przestrzeni utknął pomiędzy wymiarami. Aby się wydostać, musi wybrać jeden z nich i do niego przeskoczyć. Niestety, jeśli trafi w miejsce bez rozwiniętej technologii, może mieć poważne problemy z powrotem do domu.

Aby ocenić do którego wymiaru się udać, nasłuchuje rozmów. Niestety, słyszy jednocześnie słowa z obu wymiarów i dodatkowe szumy z pobliskiej czarnej dziury. Jego wehikuł zamienia słowa na znaki, niestety znaki przeplatają się. Przykładowo, jeśli jednocześnie ktoś powiedział „autobus” i „marchewka” to odczytane mogło zostać

amaurtcheobwuksa

czyli

amaurtcheobwuksa
a  u t   ob u s
 ma r che  w k a

Do tego, mogą dojść dowolne zakłócenia w postaci dowolnych dodatkowych literek w wiadomości, które nie pochodzą z żadnego słowa.

Masz do dyspozycji zbiór słów, które interesują podróżnika w czasie.

słownik = {'kalafior', 'rower', 'krowa', 'pieczarka',
           'prezydent', 'usa', 'pi', 'sigma', 'python', 
           'naleśniki'}

Napisz program, który dla zadanego zbioru słów znajdzie ich jak najwięcej.

Uwaga: pamiętaj, że dopasowanie jednego słowa może spowodować, że nie dopasujemy dwóch innych. Twoje rozwiązanie nie musi być optymalne, możesz używać dowolnych funkcji z biblioteki standardowej.

Podpowiedź 1: możesz skorzystać z funkcji permutations z modułu itertools albo zapisać problem rekurencyjnie.

Podpowiedź 2: czy możesz wykluczyć niektóre słowa ze słownika lub niektóre litery z wiadomości?

Podpowiedź 3: spróbuj zrobić przybliżenie rozwiązania idealnego - może to wystarczy? Rozważ na kartce trudny przypadek poniżej:

słownik = {'abba', 'huba', 'halo'}
wiadomość = "hubabbhaloaa"

Sprawdź program na wiadomości poniżej.

wiadomość = "uslppiapniepyrtswczehazdoyrkcnadvientjqlkjeogijpzxczx"

Ile słów udało Ci się w niej znaleźć?