Pegs contest

I'm wondering: is the time limit valid only for the quick output? Can i pass the time limit if I'm doing the normal output?

And anyway, has anyone already coded an working and fast algorithm? Or am I the only one ) ?

Two more questions:
- is the time limit valid only for one run or for all 20 of them?
- for winnig, which time does count: one of the quick output or the big output one?

You should read the rules more thoroughly

Time limit is always 30 seconds for one run. What counts for results is quick mode.

xs0, thanks

And if anyone else has a working algorithm: what is the result for the following two problems: 13468ADEFGHIKLMOQS (me 4, xs0 1) and 45679ACBEFGHIJKMNPQR(me 1, xs0 2). Mine speed is less than two seconds for both

I'm using a 366MHz PII in Linux

I got the following:

13468ADEFGHIKLMOQS (2.87 sec 2 pegs)
45679ACBEFGHIJKMNPQR (5.59 sec 1 peg)

I cannot determine why I got 4 in the first problem... I check all the moves, but somehow optimum isn't found.

Real interesting; how can you abort your search early if you haven't reached only 1 remaining peg?

Bah, it looks like I may need to do some massive overhauling :O

I think I need a way to prune my search; these other people here have incredible times... I need a calculateEntropy() function

Something that I do is that I have a TIME_LIMIT variable which will kill the check if the number is reached. This prevents it from running over time, but it can also be used to restrict the time. Generally within the first couple of seconds you can find either a 2 or 3 second solution. Finding a 1 peg solution can take a lot longer. So instead of wasting time, it might be better to just die after 3 or 4 seconds.

One problem though. . . Time isn't necessarily as important as peg count. If your script goes for 2 secs and gets 2 pegs whereas another goes for 28 and gets 1 peg, the second is going to be in the lead.

But if you waste time on figuring every possible solution and still find that you can only find a 2 peg solution, you have lost.

I'm not sure what would be the best option. I'm leaning towards the peg option, because the time only becomes an issue if you have a tie, which isn't all that likely after 20 tries. Who knows? I'll have to think on it some more.

I found a bug in my program, now it checks all the possile moves. But, now it performs even worse than before, where only a subportion of moves was checked, without any heuristic.

About the time: i think it's better to let the program run for 29.9 seconds than stopping it before. Even a small chance of finding one peg less is worth trying. Because it's the pegs that count. But, in the event of a tie peg number, you will get 20*30=600 seconds of time. So you will probably lose But you will be still better than anyone who stopped before and found one peg more!

A tough choice...

So given random input how many pegs are you guys left with typically?

<< still hasn't started

Most original setups will give you at most 3 pegs in the end. That's the largest I have yet to get at least.

I get the same results as xs0 in 0.2 seconds and 2.2 seconds, not necessarily in that order.

strangely enough, for this one:
23456789abcdefghijklmnopqrs
I get 74 seconds.

I have set up 'checksums' at each step. What happens is, when a certain layout has been completed, and the best results have been found for that layout, it stores a checksum for this layout. The checksum is the same for any rotation/inverse of the layout that may appear later.

So at any time later, if the algorithm finds that the checksum for the layout has already been set, it immediatly backs up a step.

The logic is that because every move removes a peg, reaching a certain layout can never be done in a different number of moves, only a different way.

This cuts out a lot of redundant branches.

Yet, the stack above takes 74 seconds.

All my attempts to make the logic for selecting which of multiple branches to search better, results in some good results, and some worse results. I can't seem to match the results of my algorithm now, in any shorter time. A logical compromise is to only select a certain maximum of branches from any junction. But this penalises layouts which could be finished in time the long way.

Hmm.. I'm not sure this contest will yield a true winner. The probability for my prototype script finding the least pegs after 30 seconds are almost 100% as I can see it. Perhaps I'm wrong, hopefully. And my prototype isn't fast at all.

This means most of you should be able to find the least pegs - which mostly are 1-3. Therefore the winner will be the fastest, and that's not fair. Finding 2-3 pegs left are very easy, and for the most the right answer. Therefore stopping when finding 2 will give you most likely the answer. And then you have won, even though your algorithm isn't the best. You're only the boldest.

Sigh, I really hope I'm not right.

PS: Starting with only peg 1 empty, how many pegs do you have left then?

Ahh...but if a slower script finds that ONE time that they can get it down to 1 peg left, they have beaten the faster script that always stops at 2 haven't they?

That is true Matt, but still the boldest win. When do you stop searching for that 1 solution? 29 seconds? 20 seconds? If all stops as late as possible the winner is the luckiest - with the timer on his side.