Codewalkers.com contest
Posted by Audrius Karabanovas on Feb 9, 2007
Taigi, www.codewalkers.com organizuoja dar viena kontesta, šį kartą užsikabliavau ir aš. Visuomet mane traukė AI, ne pats AI veikimas, kaip to veikimo programinimas. Taigi, praleidęs du vakarus - nuo 18val. - 02val. galų gale turiu scriptą kuris galima sakyti padaro tai ko nepadarė vienam mape mano smegenėlės 
Prikolas tame, kad čia gan plati tema, yra daug būdų ir algoritmų, tačiau tai yra NP-HARD problema, t.y. kad pats tiksliausias variantas StainerTree yra per sunkus kad slėtų atlikti visus skaičiavimus per 30sek. limitą, įskaitant tai, kad jį dar reikia adaptuoti tam, kad jis jungtu ne taškus plokštumoje, o daugiakampius. Codewalkers forumuose keletas urodų klieda kad pas juos sprendžia viską <1s ir dar su kokiais rezultatais, nežinau, peršasi mintis tokia: arba jie genijai matematikoj, arba tiesiog kažkokį super algoritmą sugalvojo (gal pizdelina?), kaip šituos bet kokius kambarius paversti taškais. Mano algoritmas yra paremtas MST (Minimum Spanning Tree) principu su keliais navarotais, tačiau viską rašiau iš galvos taip, kaip aš įsivaizduoju reiktų, o ne matematiniais išvedžiojimais. Apačioje mano scriptuko solutionas šitam mapui. X tai koridoriai (juos scriptas ir deda). Visam šitam mapui, su maximaliu sprendimo gyliu mano scriptas užgaišta dvidešimt sekundžių. Taigi, manau į pirmą vietą tikrai nepretenduoju, bet į TOP10 tikrai manau pateksiu, o gal net ir į 5, o tuomet gausiu kokį nors gaidišką prizą map1.txt Xs $524 ok ### #### # # #### ####X###### ## ##X # ## X # # ###X####X## ## X # ## ### ## ##X# # X ### ## # X # # # X # #### ### ##### ## ## # #### ### ### # ## ## # X # ## ### # ###X### # ## ####### # ## ## #### # #### ##### ##### #### ### ### # ###X#####X### ## #########X#X###### #### #### #### X ##### # # # ##### ### #### ### ##### # ##### ## # ## # ########## ## ## # X ## #### ## # ## # X # ######## ######X# ## ## ## # ## ### # #### ## X ## ## ### ## # ##### ## # ### X # X # # #### # ### # # # ## ####### # ##### ## # #### ## ## ####### ####### ### # ### X ## # ## ####### ##### # #### X ######## ###### #####X## # ### ## #### ##### # ##### # # ###### X # ##### X ###### # ### # # # X ##### #### ##### ## ### ## # # # ## # ####X## ##### ###### X X ## ####### #### # # #### # ######### #X#### ##### ## ###### # X ## ### ### # # X ####### # ## ## ##X# X ## X ## # ## # ## # ###### ########X### ### ## #### ###### ####### ### #### #### # ## ##### ### X ## # # ## ######## # ## ## ### ## ### ### X #### # # ### ### ###X # ### # ## # # # # # ## # ### ##### # ## ## X ####X## ##### ###X## ## #### # ##### ## ##X### ### #####X# # ##### X ## #### ## ### # # #### ## #### ### # ## ### ### ### ###X######X## #### ### #### # ### # #