I have inefficient code

Hm... I don't think PHP is supposed to be this slow, but I Only defined one class to hold my triangle.

I can only process about 60 states total in 29 seconds! Sigh... That means my heuristic has to be practically 100% accurate
A state is a board position, including everything equivalent via symmetry. I just have a recursive search function and increment a global variable.

Webhappy: How are you choosing what moves to recursively test?

Are you finding all possible moves, then testing all those moves? Or are you only testing a subset of those moves? Testing all possible branches will never be fast in any language. You have to decide on the best move / moves from the list of potential ones. Then, when you check them, your tree won't be so wide, and will finish quicker.

Also, marking when you have found the best result for a particular state is vital, so you don't go down that branch again. But again, if your tree is too wide, there will be so many different states it will be overwhelming. You also need to handle the symmetry and rotation in a way that doesn't slow down your search function.

You need to set things up properly at the start, so that when your algorithm runs, you are not wasting time that could check more branches.

The layout that took 74 seconds for me, is now down to 44.2 seconds. That was just by rearranging the code a bit, such as inlining certain code and unravelling if conditions, etc., without changing the algorithm at all.

We will of course see how people did it after this contest is done.

As I said, I am interested to see how other people solved these problems, such as criteria for move selection, and handling rotation/symmetry.

My method seems okay, but there is always room for improvement.

Hi, thanks for the advice. I'm already storing already visited states and retrieving this data in constant time.

I just think I'm somehow not using PHP correctly...
About how many states are you able to process in the time limit though? It seems something's taking up a lot of time, for each state to take about half a second. During each state, I basically analyze possible child nodes (all the states after doing a valid move).

The script I wrote for this contest is a rather simplistic yet slow and dumb approach. It reaches approximatly 860 recursion instances deep when I do constant output to the screen about progress. That's not bad on the one hand as I am able to find a good or best solution within the time limit, but my script fails on board layouts that I know are solvable down to a single peg. For example, to solve a pyramide with the top peg missing, my code seems to insist on using an additional base row although it's practically not needed to solve the board.
There's also an input stream posted on the forums that some can work down to a two or even 1 peg finish, someone else to 4. I am stuck at 5 pegs after 30 seconds where the other scripts take only 2. So you can come up with your maths about search depth and intelligent preselection. I did not implement mirroring or other symmetry tests (because I don't know how to do it ;) ) which take time to calculate, but can save you time elsewhere.

This is the contest I enjoyed the most, followed by the "shortest path through maze" problem. Great job done on Matt's and contest group's side as well as contestants involvement. Great fun!

Gobo (who did several of the contest scripts but never released them)

Oh, forgot to add a thing: I enlarged execution time for my script up to 20 minutes (!) to see if a "best" solution can be found then, but without success. I didn't printed the progress for those marathons, so I cannot tell how many branches my code took.

Gobo

stick with iterative code, PERIOD

To be honest, I first started with an iterativ approach. Maybe that's because I never really understood recursion when I was at school. Then, after allmost 3 days working on the iteration, I simply *knew* how to do it recursivly and the code was much more readable after the switch to it.

I am looking forward to have a sneak into everyones entries and I will have a special eye on the topic of iteration versus recursion ;)

Gobo

Gobo: Your function should never recurse beyond 28 levels, because this is the maximum number of moves possible. The length should never be more, only the width of the tree will vary. In other words, how many multiple moves at a junction you choose to investigate plays a big part of slowing down your algorithm.

As for anon's comment: "Use iterative, period.". That is a bit naive, because sometimes it make code a lot easier to read, and we must remember that readable code is very important, not just performance. If you are using multiple recursive calls for each level, you have serious problems with your code. 860 is absolutely ridiculous.

webhappy: half a second per state is absolutely horrible. I have an array of 'hole' objects, each with a boolean member 'has_peg'. Checking for potential moves is easy. For three consecutive holes, if the middle holes has a peg, and the peg status of the other two holes are opposite, then a move is possible. I don't quite understand what you are doing that is wrong.

I can only say that you can see my way of doing it when the contest is done.

hmm
what solution do u have to find right branch?
my algorithm is fast enough, but is absolute stupid -- it only search for all possible variants..

how can i improve it? i mean how to easy early recognise bad paths?..
(oh, i understand.. answer for this q i may get only after contest )

Anon: The challenge of this contest is figuring out how to solve the problem, and how to code it. You need to work out a strategy, and then you need to put it into code.

Often, putting your ideas into code can be very difficult, and this is where experience helps. A new coder may have great ideas, but will struggle to write good code. Stick with it, because you can only get better...

Yes, after the deadline I will be happy to answer any questions I can, compare methods, etc.

Weird, I am now able to visit:
465 unique nodes; 902 nodes visited total

I used to have some buggy stuff I was too lazy to test :O