Page 2 - Pegs contest

I don't think it's luck. It's all about how really good your algorithm is.

What is a lookup table exactly in context to your contest?

here

How can we be sure/unsure that there isn't a solution that yields only 1 peg for any given initial configuration that starts out with only one missing?

*lacks the mathematical rigor, or time, to answer this question*

In 18 cases a solution with 1 peg exists, and in 10 cases, with 2 pegs. You'll need to find the actual solutions yourself, though

Uh... there are 2^28 cases total, not just 28... BTW, Matt, you won't give us a case of only 1 peg or no pegs or all pegs right? IE, you won't give us one of the above tricks (with nothing to do)?

i think xs0 was talking about there being 28 possible boards that start with only one peg missing....

And I usually don't pull tricks ;)

xs0, how do you know that those 10 don't have a 1 peg solution? have you tried all branches?

I don't think I'm going to enter. I can hold my own in algorithms and have an idea for an extremely efficient implementation which uses mostly ANDs and ORs with the right data structures to look ahead three or four moves (dynamic based on current time and progress). At any rate, I think that Gandolf has a point about it being relatively easy to find the best solution (...now if only I could do that in my mind @ Cracker Barrel ; ), even if you're using a greedy algorithm. : (

Yup. There's also another way of figuring that out, but I'll leave it for after the contest

can somebody give an example of situation with a realy long calculation.. i mean more than 30s..

I can't. My algorithm always find the optimal solution in just a second. Just kidding, of course.

I can't give you an exmaple, because my algorithm is designed to stop before...

No one can give you that example. It completely depends on what algorithm you use. I had one problem I thought was hard (originally took 45 secs), but just a slight change in algorithm made it solve in 2 secs...

Of what relevance is it that 18 of the '1 peg missing' layouts have a 1 peg solution, and the rest have 2 peg solutions?

To my mind, you can't use that information because to do so would constitute being a lookup table.

You could only use that information to see how your algorithm fares. I don't see it as being much value.

Now, xs0 said there was another way to determine the minimal solution. If there was a method to examine the input and determine what the minimal solution is, without running through the moves, that would anihilate anybody else's efforts.

xs0 said he would reveal that after the competition. It could be that we of less intellect are doomed.

PS. Regardless of what anyone says, I will still enter. In the previous contest people had hugely smart ideas about how to sort the stacks, but the lean, minimalist solution by JoE beat them. Beware of the underdog...

Anonymous wondered about that. It is of no relevance, because it is indeed a lookup table.


I said no such thing. I just said that for the ten boards in question, it can be proved without running through all moves that a 1-peg solution is not possible. I still had to use the "hard way" to prove that 2 pegs were possible (and 1 peg in the other 18).

Nonsense...