spolecne

Geocaching je hra na hledání pokladů s pomocí navigačních přístrojů GPS. Na internetovém serveru geocaching.com (varování: při řešení tohoto úkolu se pravděpodobně neobejdete bez bezplatné registrace na tomto serveru) jsou zveřejněné souřadnice schránky (tzv. kešky, anglicky cache), uživatel si souřadnice uloží do navigačního přístroje, pak vyrazí do terénu a snaží se schránku najít. Některé kešky jsou tzv. multi-kešky: bodů, které uživatel musí v terénu projít, je několik. Cestou uživatel sbírá číselné indicie a z nich nakonec spočítá podle vzorce, který je u popisu kešky uveden, cílové souřadnice vlastní schránky. A právě tyto multikešky jsou pro nás zajímavé.

Mnozí „kačeři“ (hráči geocachingu) používají k navigaci chytrý telefon, který jim přímo v terénu stáhne popisy nejbližších kešek na základě jejich aktuální polohy. Díky tomu si nemusejí popisy multikešek předem tisknout na papír, aby věděli, jaké indicie mají na kterém místě zjišťovat. Zjištěná čísla si ale stále musejí poznamenávat stranou. Stejně tak závěrečné dosazení do vzorce a výpočet souřadnic je na nich. Automatizace a programová podpora tohoto kroku je obtížná, protože každý autor zapíše vzorec do popisu kešky trochu jinak. Abychom mohli vzorec rozpoznat, musíme umět rozebrat text webové stránky, případně mu i částečně porozumět.

Některé možné komplikace:

• Vzorce jsou na stránce uváděny různými způsoby. Někdy se jednotlivá písmena (proměnné) dosazují za jednotlivé číslice, jindy musíte provést početní operaci a dostanete tříciferné číslo, které celé dosadíte za desetinnou tečku u minut. Možností je nepřeberně.
• Stránka může obsahovat několik vzorců. Některé body, kterými musí kačer projít, mohou mít souřadnice také vypočítané, místo aby jejich souřadnice byly uvedeny v popisu přímo.
• Cílový vzorec se může skládat z několika výpočtů, které na sebe navazují. Příkladem je keška Metro = B =.

Vaším úkolem je napsat skript, který projde popis multikešky (HTML stažené ze serveru geocaching.com), rozpozná v něm vzorec pro výpočet souřadnic, zjistí názvy proměnných v tomto vzorci (typicky velká písmena anglické abecedy), pro každou proměnnou identifikuje pasáž textu, kde se říká, jak dané číslo získat, a vygeneruje (např. jako výraz v Perlu) kód, který po dodání hodnot proměnných souřadnice vypočítá a vypíše ve standardním formátu X dd° mm.mmm, kde dd jsou stupně, mm.mmm jsou minuty s přesností na tři desetinná místa a X je určení světové strany, tj. N nebo S pro zeměpisnou šířku a E nebo W pro zeměpisnou délku. Příklad:

N 50° 06.530 E 014° 34.550

Tato úloha pochopitelně je jazykově závislá. Můžete předpokládat, že stránka obsahuje popis kešky v češtině, ale musíte se umět vyrovnat s tím, že stránka může obsahovat i popisy v jiných jazycích (nejčastěji angličtina).

Pokud chcete, umíte a máte na čem to předvést, můžete program vyrobit rovnou jako aplikaci pro Android nebo i-Phone (v takovém případě by to nemuselo být v Perlu). Jinak standardně jako skript v Perlu, který čte stažené HTML ze standardního vstupu, případně (nepovinně) rovnou stáhne ze serveru kešku, jejíž kód dostane. Pokud by váš skript obsahoval stahování vstupního textu ze serveru, chovejte se slušně a opatrně, protože podmínky serveru zakazují stahování údajů roboty. Na standardní výstup vypište vzorec, který jste v textu našli (nejlépe přímo přepsaný do Perlové syntaxe, aby bylo možné ho použít ve vašem programu), pod něj seznam proměnných a příslušnou pasáž textu, která říká, jak hodnotu proměnné získat. Alternativně, pokud už uživatel hodnoty proměnných zná a zadá je jako volby na příkazovém řádku, rovnou vypište souřadnice. Příklady (písmeny GC začínají jednoznačné kódy kešek, jejich popisy lze najít na URL http://coord.info/GC…):

multi.pl < GC3R9BF.txt

nebo

multi.pl --download=GC3R9BF
  N50° A(C+5).(D*E)(F-D-A)(G-B)
  E014° B(C+2).(G-D+A)(D+E)(B+C)
nebo lépe
  sprintf("N 50° %d%d.%d%d%d", $a, $c+5, $d*$e, $f-$d-$a, $g-$b);
  sprintf("E 14° %d%d.%d%d%d", $b, $c+2, $g-$d+$a, $d+$e, $b+$c);
a pod tím
  A =
    Některé z Vás sem přivedla čísla AABC.
  B =
    Některé z Vás sem přivedla čísla AABC.
  C =
    Některé z Vás sem přivedla čísla AABC.
  D =
    Dělová koule Vám ukáže číslo popisné D (Postavíte-li se čelem ke zdi, dům vlevo pod).
atd.

Nepředpokládám, že kvůli této úloze naprogramujete kompletní morfologickou a syntaktickou analýzu češtiny, i když by vám určitě pomohla k lepším výsledkům. Spíše půjde o porovnávání textů s regulárními výrazy a předem vybranými klíčovými slovy. Můžete si pomoci i strukturou stránky: např. souřadnice jednotlivých bodů multikešky bývají přiloženy i v přehledné tabulce na konci. Tím získáte přehled jednotlivých zastávek (často i v češtině označovaných anglickým slovem stage), které pak v textu hledáte.

Soustřeďte se nejdříve na nejjednodušší případ, kdy je popis kešky jednojazyčný (pouze česky), souřadnice jednotlivých zastávek jsou dané předem a hledáte jen jediný vzorec. Potom podle možností řešení rozšiřujte na komplikovanější případy (více jazyků, více vzorců).

Tento úkol (včetně zadání konkrétního jazyka) si můžete zarezervovat vyplněním formuláře na http://quest.ms.mff.cuni.cz/cgi-bin/zeman/zapoctaky/rezervace_ukolu.pl (pokud ještě není rozebrán).

Pokud se individuálně nedohodneme jinak, termín odevzdání je konec listopadu. Při některé prosincové přednášce program předvedete ostatním.