Vlákno názorů k článku Velká soutěž skončila. Jak jste měli řešit? Vyhráli jste? od anonym - Řešení bylo možné nalézt pomocí stromu. Postupným kombinováním...
-
Augur (neregistrovaný)také by mě zajímalo, jak to udělat jinak, než hrubou silou :-)
obyčejné prohledávání stavového prostoru do šířky bez jakékoliv heuristiky, které jsem použil, a které mi dávalo výsledky v dobách řádu těch milisekund (tj. nedokázal bych to sám svými smysly zaznamenat), považuji stále za hrubou sílu :-) -
Augur (neregistrovaný)to mám trochu jiný názor ...
Náhodné procházení do hloubky považuju za naprosto hloupé řešení.
Procházení do šířky není efektivní, jen z hlediska své definice najde vždycky to nejlepší řešení. Za efektivní (a tedy se sofistikovanou heuristikou) bych považoval inteligentní procházení do hloubky (tj. že by se šlo rovnou k cíli). Ovšem v tomto případě naprosto netuším, jak by taková heuristika mohla vypadat... (a navíc množství stavů tady není tak veliké, aby prostá hrubá síla schovaná za procházením do šířky nestačila :-) )
Nezahazování prošlých stavů považuji za chybu implementace algoritmu... -
anonymníTak se nestyd a posli to:) Ja to delal hloupe v .NETu tak ze jsem byl totalne liny, takze jsem si vygeneroval prvni stav a pak udelal vsechny mozne stavy, do kterych se muze dostat, ulozil do do textaku a v dalsim pruchodu sel dal (teda poprve jsem to udelal super line s rekurzi a 100MB stack nestacil, tak jsem to delal takhle:)
Predposledni trval asi minutu nebo dve a na konci bylo nekolik giga fajlu:)
Jako "vylepsovak":o) je samozrejme setrizeni vysledku z kazdeho levelu a vyhodit duplicity, pripadne vyhodit i v zavislosti na predchozich levelech .... no a taky by asi neco usetrilo to, kdybych to nehazel do souboru a pak nemusel zpetne parsovat gigovy textovy fajl na integer hodnoty:) Kdyz jsem ten gigovy setridil a vyhazel duplicity tak mi zbylo par kilo, ale ani tak nevim, jestli bych se vesel do par ms, ikdyz mozna jo:) -
zde je ten zdrojak, snad to bude fungovat. Je tam zakomentovano nekolik konfiguraci ze zadani
http://docs.google.com/Doc?id=ddnsptpc_74f74vgmhk
