Po drátě 5: Řešení úlohy č. 15

V příloze přicházel Makefile. Byl poněkud pochybný, protože nesloužil k překladu žádných programů, nýbrž vypisoval heslo, tedy pokud jste jej nechali běžet dostatečně dlouho.

Dostatečně dlouho bylo ovšem něco jako miliony let, takže bylo potřeba zjistit, cože to onen Makefile dělá, a naprogramovat to rychleji. Práci ztěžovaly jednoznakové proměnné, nečitelná syntaxe Makefilu a neexistující rozumný syntax highlighting.

Program měl na začátku dvě vstupní proměnné – INPUT a ALPHABET, všechno ostatní byly funkce, které se porůznu volaly. Asi nejlépe se to celé četlo v pořadí, v jakém tím protékala proměnná INPUT.

Nejdřív si ale vysvětlíme některé pomocné funkce. t se původně jmenovala traverse, jako první parametr dostala funkci a jako druhý parametr seznam. Pro každý prvek seznamu spustila onu funkci, které předhodila nejdřív onen prvek jako první parametr a potom svůj třetí až šestý. Zní to ďábelsky? Ještě zdaleka nejsme u konce!

Pomocná funkce b, původně behead vracela zbytek seznamu po utržení prvního prvku. Připomíná vám to Haskell? Nejste daleko od pravdy, funkce traverse dělá opravdu totéž co Map v Haskellu. K tomu ostatně posloužila inspirace v manuálu ke GNU Make.

V proměnné I si Make podlým trikem vygeneroval ze vstupu jeho kartézský součin. Konkrétně za každý řetězec z INPUT připojil každý řetězec z INPUT, v F byl navíc ke každému řetězci připojen ještě oddělovač ?, který nebyl v abecedě (ALPHABET).

Pak už se v tom trochu ztrácí i autor sám. Funkce f postupně po znacích přesypává každý řetězec obsažený v F do svého čtvrtého parametru (rekurze), až tam je celý a ve druhém parametru zůstalo několik otazníků – tolik, kolikrát byl v F obsažen. Pak si zavolá funkci n, která mu zjistí, jestli je onen řetězec obsažen právě tolikrát, kolik má písmen. Pokud ano, nechá jej tam.

V proměnné N se tedy objeví už jen ty řetězce, které se vyskytovaly právě tolikrát, jak jsou dlouhé. Každý právě jednou díky zavolání vnitřní funkce sort.

Poslední magii dělají funkce z, p, h a c, které hledají maximální prvek v seznamu. Porovnává se nejprve podle délky řetězce (obskurně tak, že se z obou trhají znaky po jednom, zcela neefektivně – při každém utržení se prochází celá abeceda), při rovnosti se vezme ten druhý, což způsobí, že se nakonec vrátí ten lexikograficky největší, protože tak nám to před chvílí setřídila funkce sort.

Asi nejjednodušší bylo odzkoušet, co to dělá na malých vstupech, odhadnout, co to asi bude, případně přidat nějaké $(info) a napsat na to program v C.

Zajímavosti

Jeden řešitel do mailu po crontabu napsal: „Zajímavé, v čem všem jde programovat. Co to asi bude příště? Man, info?“ Chudák netušil, co ho čeká.

Celý Makefile používá jen manipulaci s proměnnými. GNU Make pravděpodobně nepředpokládá, že v něm bude někdo tímhle stylem programovat, takže například i při povolení paralelizace zatěžoval jen jedno jádro procesoru.

Nepodařilo se nám nakonec spočítat časovou ani paměťovou složitost, ale roste to nechutně rychle, i když to pravděpodobně bude ještě polynomiální. Paradoxně to proti očekávání nezabírá skoro žádnou paměť, Make to pravděpodobně prochází do hloubky, nikoli do šířky.

Úloha vznikla jako odpadní produkt přepisování Makefilů, které generují web KSP. Poté, co autor zjistil, že to asi 5 vteřin „nic nedělá“, přišel nápad na tento bláznivý program.

Autorem úlohy je Moskyt.