Vlákno názorů k článku Velká soutěž skončila. Jak jste měli řešit? Vyhráli jste?

uživatel si přál zůstat v anonymitě

6. 4. 2009 13:14

Programek pro prelivani od redakce?

Řešení bylo možné nalézt pomocí stromu. Postupným kombinováním přelévání nádrží to zvládne běžný počítač během pár milisekund.

Nechce se s nami redakce ruta podelit o ten superrychly algoritmus?:) Pocitam, ze programek na to mate, jak jinak by jste to overili?

Odpovědět

Jirka (neregistrovaný)

7. 4. 2009 7:39

Re: Programek pro prelivani od redakce?

Nemel jsem zadny superprogram, ale vysledky jsem i pro nejslozitejsi pripady dostal behem par sekund. Neni to slozita uloha pro toho, kdo prosel nejakymi zaklady programovani a nepusti se do toho hrubou silou.

Odpovědět

uživatel si přál zůstat v anonymitě

7. 4. 2009 9:47

Re: Programek pro prelivani od redakce?

No a jak jinak nez hrubou silou?:o) To me prave zajima, za tech par milisekund je to podle me v kazdem pripade blbost

Odpovědět

Jirka (neregistrovaný)

7. 4. 2009 14:20

Re: Programek pro prelivani od redakce?

Na to prave potrebujes toho fistrona. :-)

Verim, ze kdyz to napises opravdu chytre, tak se dostanes na zlomky vteriny.

Odpovědět

Augur (neregistrovaný)

7. 4. 2009 14:37

Re: Programek pro prelivani od redakce?

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 :-)

Odpovědět

Karell (neregistrovaný)

8. 4. 2009 0:25

Re: Programek pro prelivani od redakce?

To ne, hruba sila je nahodne prochazeni do hloubky. Kdyz uz to je do sirky, tak je to efektivni algoritmus a kdyz se navic zahazuji uz navstivene stavy, tak je to sofistikovana heuristika. Za ni uz je pouze orakulum :-)

Odpovědět

Augur (neregistrovaný)

9. 4. 2009 9:16

Re: Programek pro prelivani od redakce?

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...

Odpovědět

Karell (neregistrovaný)

9. 4. 2009 10:29

Re: Programek pro prelivani od redakce?

Jo, jasne, ja si delal legraci. Ale docela me zarazilo, ze se da rict, ze hruba sila je vlastne zaroven nejspis nejlepsi reseni v tomhle pripade. Vsechno horsi uz je spatne, a nic lepsiho me nenapada.

Odpovědět

Karell (neregistrovaný)

8. 4. 2009 0:16

Re: Programek pro prelivani od redakce?

Predposledni zadani mi trva asi 25ms po prohledani asi 3000 stavu. Ostatni co jsem zkousel byly do 10ms. Zkousel jsem to v jave na starem ntb. Takze pro takhle maly vstup se to do tech par ms da, ale umi to rust nepekne rychle pri osklivejsim zadani :-)

Odpovědět

uživatel si přál zůstat v anonymitě

9. 4. 2009 9:33

Re: Programek pro prelivani od redakce?

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:)