Kostka

Před mnoha a mnoha lety jsme skoro současně nastoupili se Žambochem do výzkumáku Naxos. To byla společnost, co vydělávala peníze všemi možnými způsoby, jen aby je mohla dát na nás. On nás se chtělo, abychom s maximálním nadšením a nasazením programovali, co se nám zlíbí. Projekt se jmenoval Braien bylo to fakt něco! Byla to krásná léta a užili jsme si se Žambochem spoustu srandy. Třeba pouštění několikametrových draků v absolutním bezvětří. Nebo tukové závody, což byla soutěž tukových plavidel – špekovor, špekonorka, plavidlo z tukové vánočky s plachtou z kůže vepřového kolene… Z té doby je i můj kabát.

Jednou Žamboch někde koupil takovou divnou rubikovu kostku:

Rozhodl se, že ji nechá složit počítačem. Nakonec jsme se toho chytli oba a vymýšleli jsme, jak najít řešení pro nejmenší počet tahů. Pro mě to nic nebylo, dal jsem si za úkol, vyřešit úlohu pro normální rubikovu kostku. To je sakra těžší. Principy jsou stejné, jen u mě to je mnohem víc možností. Víc, než dnes stolní kompy zvládnou. Zpočátku jsme oba hustě diskutovali své postupy a Žamboch to implementoval, později jsem začal psát tu svou kostku i já a měli jsme tudíž dva nezávislé projekty. Není to žádná trivka, musí se počítat se spoustou nematematických omezení, jako je velikost paměti, disku, stránkování, doba výpočtu, optimalizace velikosti dat a podobně. Zejména proto se nám střídala období, kdy jsme to freneticky psali s mnohem delšími obdobími neaktivity. Po pár letech se letos dostavil úspěch – Žamboch tu svou kostku dokončil. Já ještě ne.

Můj úkol je mnohem těžší a dosud ho nevyřešil nikdo. Dokonce se ani neví, na kolik tahů se dá složit libovolná kostka. Abyste to nemuseli číst, tak je dokázáno, že je to někde mezi 20 a 26 otočeními. Já věřím tomu, že je to spíš okolo té dvacítky a pro začátek by mi stačilo, kdybych v rozumném čase našel minimální řešení pro libovolnou jednu kostku. I to by byl úspěch světového významu, protože kdybych to dal na web, tak by si vědci, co mají vytipované složité kostky, mohli zjistit, jak to je. Nevím o tom, že by takový software na síti byl. Myslím, že dosud neexistuje. Ale nevnímám to jako závod, i kdyby byl, bylo by mi to jedno. Dokud toho nedosáhnu, bude mi to prostě vrtat hlavou.

Kde dnes po těch letech jsem? Mám děsně cool program, co vezme složenou kostku a udělá všechny tahy, co z ní jdou. Tím se dostane sféra o poloměru jedna. Z ní se opět udělají všechny tahy a dostane se sféra o poloměru dva. Je to celé hodně optimalizované, třeba se každá kostka optimalizuje a normalizuje, takže pokud má kostka různé barvy a jinak je stejná, nebo je nějak souměrná, bere se jako shodná. Sféry se setřídí a duplicity se vyhodí. Je reálné získat na mém počítači sféru o poloměru 10, to je asi 150 GB dat. Už ji mám, ale musím ji setřídit a pro to musím trochu upravit třídící algoritmus. K tomu se někdy dostanu a budu moci začít pracovat na sféře 11 nebo provést první statistiky. Sféra 11 bude tvrdý oříšek, protože bude velká asi dva terabajty a výpočet na jednom kompu zabere mnoho týdnů. Proto budu muset jak data, tak zejména výpočet, distribuovat. Statistiky mi pomohou v tom, že se tuší, jakou to má křivku. Když budu mít statistiku, tak odhadnu, jaké to maximální číslo bude a podle toho se přizpůsobím. Kdyby to bylo 20, čemuž věřím, tak se algoritmus najde lehce – prostě se okolo kostky ze zadání udělají postupně sféry a ty se porovnají s těmi okolo složené kostky. Většině kostek by měla stačit sféra 8 a je celkem rychle vytvořená. Jestli najdu kostku, co se složí na víc jak 20 tahů, tak budu “slavný”, protože zpřesním odhad minimálního počtu tahů. Není co ztratit.

Matematikové možná nevěřícně kroutí hlavou. Ani se jim nedivím. V prvních sférách je totiž nárust jejich velikosti exponenciální, každá je asi třináctinásobná a už teď jsem na limitu svého počítače. Však to nějak obelstím, jako dosud vždy.

Kostka je sranda.