two or more perfect scripts

i think its possible to write a 'perfect' solver.
will time make the winner (per map, overall)?
or is it possible, that there will be more than one winner?

time will be the judge in that case..

(and i don't think that there will be any "perferct scripts" ;)

its hard (if not impossible) to prove, but i think im almost there .
currently im having a problem with one type of map only (maybe there are more, that i havent discovered yet...).
something as simple as:
101
000
101

these patterns are quite unlikely to occur in random maps.
so, next question:
will all maps be generated, or will you provide some handmade maps (or code the generator to spit out some difficult maps)?

A perfect script is fairly trivial to write - just try all possible combinations of corridors. Of course, the time constraint renders that approach useless.

Is this contest NP? NP-complete?

sure, its possible to prove, that a specific map is solved perfectly.
but its hard to prove, that a given script (eg mine) will solve all possible maps perfectly.


even this is hard to prove ;-)

Ahhh... But it already has. The solution to this contest is basically what is called a steiner tree and has been proven to be NP complete, although with this small number rooms it should be fairly trivial to find the exactly solution.

http://infoshako.sk.tsukuba.ac.jp/~tohyama/graph/emsteiner.html
http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK4/NODE181.HTM
http://www.css.tayloru.edu/~bbell/steiner/
http://www.google.com/search?hl=en&q=steiner+tree+algorithm&btnG=Google+Search

Doh! It looks like this contest may have to be canceled. Unless they put in a rule you can't use the Stiener formula.

I don't think it has to be canceled, they just have to make the running time more important, or who has the shortes implementation ( in script-length ) ?! ;)

If some scripts are running less then a second and all achieving the same best score I doubt timing would be measurable. The whole point of these contests are to figure out the best possible solution. Well, unfortunatly, someone has already come up with the best solution to this problem. So unless you are a rocket scientist and can produce a better formula then Steiner everyone will be on an even keel making judging impossible.

I forgot to add I just created a new script with the steiner forumla and I am getting < 1 second times and same score in the test your script thread. Before I was getting around 500.

If there is a solution already for this contest "steiner tree" then how can we call it a contest?
mmm! I think it should be changed to something else,something doesn't have a known solution, so we can use our brains to solve it , instead of using Google for getting the solution ;-)

Ah, I swear i solved it before i know about "steiner tree" in < 1 sec , like everyone solved it too, I will be sad if it's canceled , but I will be more sad if someone else win by using a search engine

sigh.

ok some clarifications for those who didnt rtfa

- steiner tree problem is NP-Hard = there is no algo that runs in polynomial time for it

- the supposed algo that most pple have been using that solves in <1 sec is probably the minimum spanning tree algo. this algo only gives an *approximation to the optimal steiner tree. [mst will give 826] (the best soln in the 'test your script thread' is < 822, go figure...)

- there is no steiner tree solution, but there are good heuristics - i.e. using mst or shortest path

- this competition is still valid as the problem is now how you can use the heuristics (e.g. mst) and then improve on the solution generated by it. like by location steiner points to add.

- there are also a few differences between this competition and the actual steiner problem. the steiner problem deals with points, this one deals with blocks. the specific algorithms for the steiner tree on a cartesian plane might not apply here due to the difference in score for the diagonal corridors.

- in short, the problem is how you join the corridors together to have an even lower cost. and this problem isnt so trival

it seems some of you already adapt that algorithm to rooms(not points) and perform <1s; what do you get for example on map : http://www.cigosoft.org/pub/corridors.php?fps=60&w=600&h=450&rooms=50&blocks=800&seed=1 ?

I got 518