Úloha 4.u4: Klávesnice (3 b)

Zadáno v čísle 22.4.

Řešeno v čísle 22.6.

Zadání

Potkala vás nešťastná nehoda – vašemu notebooku se rozbila klávesnice a touchpad. Situace ale není tak zoufalá, z kláves fungují šipky a $\texttt{Enter}$, navíc jste zrovna měli zapnutou softwarovou klávesnici. Softwarová klávesnice je obdélníková tabulka znaků s kurzorem. Kurzor vždy ukazuje na jeden znak, a lze s ním po tabulce pohybovat pomocí šipek. Stiskem klávesy $\texttt{Enter}$ se vypíše znak, na který ukazuje kurzor. Text $\texttt ahoj$ by bylo možno napsat na následující klávesnici (hvězdičkou je označena počáteční pozice kurzoru) jako:

$\texttt{Enter}$, $\rightarrow$, $\texttt{Enter}$, $\rightarrow$, $\texttt{Enter}$, $\leftarrow$, $\downarrow$, $\texttt{Enter}$

a* h o
b j a
r 3 g

Jelikož lenost je hybnou silou pokroku, chcete se při psaní co nejméně nadřít. Proto potřebujete vymyslet algoritmus, který pro zadaný text a zadanou klávesnici najde nejmenší počet stisků skutečných kláves (tj. šipek a $\texttt{Enter}$u), pomocí kterého lze text na klávesnici napsat. Pro klávesnici z příkladu a slovo $\texttt{ahoj}$ nám stačí osm stisků kláves. Samozřejmě chcete, aby byl algoritmus co nejefektivnější. O klávesnici můžete předpokládat, že bude používat nějakou rozumně malou sadu znaků, například ASCII. A nezapomeňte, znaky se na klávesnici mohou opakovat!


O tom, jak efektivitu algoritmů nějak měřit, se můžeš dozvědět v následujícím povídání od našich kamarádů z KSP.

Řešení

Nejdříve si situaci trochu zjednodušíme tím, že nedovolíme, aby jakékoliv písmenko bylo na klávesnici více než jednou. Potom existuje jen jediný způsob jak dané slovo napsat – z počáteční pozice se přesuneme na jedinou klávesu s prvním písmenkem textu, poté na jedinou klávesu s druhým písmenkem textu a tak dále. Jak spočítat počet stisků? Počet stisků Enteru je stejný jako počet písmen v textu, zajímavé jsou tedy jen „přesuny“ kurzoru. Všimněme si, že vzdálenost (tj. počet stisků šipek nutný k přesunu mezi nimi) mezi dvěma klávesami můžeme snadno spočítat jen z jejich polohy na klávesnici – pokud klávesa $k_1$ je v $x_1$-tém sloupci a $y_1$-tém řádku a klávesa $k_2$$x_2$-tém sloupci a $y_2$ řádku, pak jejich vzdálenost1 je

\[ \mathrm{d}(k_1,k_2) = |x_1 - x_2| + |y_1 - y_2|. \]

Bude se nám tedy hodit pro každé písmenko umět rychle najít, kde se na klávesnici nachází. Protože možných písmenek na klávesnici je málo (viz předposlední věta zadání),2 můžeme si vyrobit pole (tabulku) indexované všemi možnými písmenky,3 která se na klávesnici mohou vyskytovat, obsahující souřadnice písmenka na klávesnici (pokud se tam vyskytuje).

Celý algoritmus tedy nejdříve projde klávesnici a vybuduje tabulku s pozicemi písmen, poté postupně projde celý text, podívá se, jaké písmenko v textu následuje, spočítá vzdálenost mezi ním a kurzorem a následně přesune kurzor. Díky tabulce nám zpracování jednoho písmenka bude trvat $\mathcal{O}(1)$, tedy $\mathcal{O}(L)$ na celý text (kde $L$ je délka textu). Konstrukce tabulky písmen nám zabere $\mathcal{O}(N)$, kde $N$ je počet kláves, celkem nám to bude tedy trvat $\mathcal{O}(L + N)$.

Co se změní, pokud se mohou písmenka na klávesnici vyskytovat vícekrát? Hlavním problémem je, že dopředu nevíme, která z možných cest po klávesnici je ta nejkratší. Na první pohled by se mohlo zdát, že bychom se mohli zkusit na klávesnici podívat jako na graf a použít nějaký z algoritmů na hledání nejkratší cesty v grafu, leč zde narazíme. Jednak chceme, aby naše cesta navštívila nějakou zadanou posloupnost kláves, a jednak nám nevadí, když některé klávesy navštívíme vícekrát – s tím si rychlé grafové algoritmy snadno poradit neumí.

Jedno z možných řešení je sestavit nějaký chytřejší graf než ten, kde jsou vrcholy klávesy a hrany vedou mezi sousedními klávesami. Většina došlých řešení tento postup použila, nicméně ukážeme zde trochu jiný postup, který je s tím grafovým v zásadě ekvivalentní (je asymptoticky stejně rychlý a má i velmi podobný průběh), ale je jednodušší na implementaci, a navíc se nezdržuje konstrukcí grafu.

Myšlenka je snadná – budeme postupovat stejně, jako když jsme neměli více stejných kláves, jediný rozdíl bude v tom, že budeme pracovat se všemi klávesami s daným písmenkem. Předpokládejme, že už napsaný text končí písmenem $a$. Potom si budeme pro každou klávesu $a_0,\dots ,a_ k$ s písmenem $a$ pamatovat nejmenší počet stisků nutný k napsání textu tak, že při psaní skončíme na této konkrétní klávese (označme si tuto hodnotu $\mathrm{p}(a_ i)$). Další písmeno $b$ napíšeme snadno. Buďte $b_0,\dots ,b_ l$ všechny klávesy s písmenem $b$. Pak $\mathrm{p}(b_ i)$ spočítáme jako nejmenší $\mathrm{p}(a_ j) + \mathrm{d}(a_ j,b_ i)$, přes všechna možná $a_ j$. Zpracování dalšího písmena nám tedy zabere $\mathcal{O}(kl)$ času. Opět se nám bude hodit tabulka, která pro dané písmeno obsahuje všechny jeho výskyty na klávesnici.

Celý algoritmus tedy bude vypadat následovně: Spočítáme tabulku výskytů písmen $T$, to zabere $\mathcal{O}(N)$ času. Budeme si udržovat množinu $K$ všech kláves, na kterých je poslední napsané písmenko, spolu s $\mathrm{p}(k)$ pro každou klávesu $k$$K$. Na začátku bude $K$ obsahovat klávesu s kurzorem $c$ a $\mathrm{p}(c) = 0$. Postupně budeme brát písmena z textu a pro každé z nich (označme si ho opět $a$) nejdřív z $T$ získáme množinu $K_ a$ všech kláves s tímto písmenem (v $\mathcal{O}(1)$). Poté pro každé $k\in K_ a$ spočítáme $\mathrm{p}(k)$ (dohromady $\mathcal{O}(|K|\cdot |K_ a|)$) a pokračujeme s $K = K_ a$. Po napsání posledního písmenka textu najdeme nejmenší počet stisků na napsání celého textu jako nejmenší $\mathrm{p}(k)$ pro $k\in K$.

Jak to celé bude rychlé? Označme si $M$ nejvyšší počet kláves, které mají stejný znak. Pak jeden krok bude trvat nejhůře $\mathcal{O}(M^2)$, celý algoritmus tedy spotřebuje $\mathcal{O}(LM^2 + N)$ času, v nejhorším případě (pro $M=N$) až $\mathcal{O}(LN^2)$.

Důkaz korektnosti jen náznakem – pokud v $i$-tém kroku jsou hodnoty $\mathrm{p}(k)$ pro $k\in K$ nejmenší počty stisků, na které se dá napsat prvních $i$ písmen textu, pak totéž platí i v ($i+1$)-ním kroku, a jelikož jsme začínali s touto podmínkou splněnou ($\mathrm{p}(c)=0$), tak na konci algoritmus vydá kýžený výsledek.

$\mathcal{O}(N)$dra


1) Takzvaná Manhattanská vzdálenost.

2) Je sice pravda, že z hlediska asymptotické složitosti je jedno jak je abeceda velká (dokud je její velikost konstanta), takže teoreticky může být abeceda velká jakkoliv, ale zkuste si někdy pořídit pole o $2^{64}$ prvcích pro Unicode…

3) Písmenka v počítači jsou všehovšudy jen čísla a některé programovací jazyky (např. Céčko) se k nim tak dokonce i chovají.