congrats to the winners

I look forward to working out how the winning code works.
I was well and truly outclassed - I'm amazed how quick the winning code calcualates

Anyhow if anyone is interested I have put some comments on my code now (entry 11). Have a look at the following link.
http://www.jrasplin.ukshells.co.uk/discsphp.txt

Congratulations to Joe for winning the contest.

His code proves that nobody found a good, 'fast-enough' way of handling duplicates. But if we look at how he sorted the stack after the dups had been weighted, it could have been improved upon.

Joe took a pretty elementary algorithm and made it run as fast as possible, resulting in the win. I maintain there has got to be a better way to sort the stacks than assigning weights at the start in one order and then sorting.

I had worked out a nice algorithm to sort lists with distinct elements, but I had only coded about 80% of it. To code the rest, I would have had to scrap all the code I had so far and restart. Without taking anything away from Joe, had I coded it, and assigned duplicate weights just once at the start as Joe did, and had I got to run in under 30s, I could perhaps have won.

But its easy to say that now. In all honesty, I know I would have not have finished it in time. It would have been tough to make it fast enough aswell. Also, I was not happy to do it that way, because as I said, I am sure there's a better way to do it, without brute-forceing and without assigning weights once at the start.

There should be a way where the duplicate weights are calculated at each step, in order to find the optimal flip at that particular step.

I couldn't work it out, and obviously nobody else did either.

No disrespect to Joe or any other entrant; I don't know PHP that well, so I would have had to try and win by way of having the least flips. If I had coded Joe's exact algorithm, it is unlikely I would have managed to make it run as fast.

The next contest is going to be more of a proving ground. I imagine the Focus Group will make it less algorithmic this time, which could mean many people produce the same method. It could come down to profiling code and optimising run times.

I will have to raise my game for that one. No matter what happens, I should have a better understanding of PHP after that.

JRA - I haven't seen your code yet, but I will have a look today. I will check the other entrants' code to see if anybody found an innovative way to sort the stacks.

Good luck for the next one, dudes.

PS - I haven't looked at Matt's input stacks yet, and I don't plan to. An algorithm should be made to work well with any inputs, not specific ones. When the entrants code was written, Matts stacks were unknown. So to compare them using his stacks would be unfair.

I don't want to think I'm a sore loser (or in fact just a loser ) but I feel - after spending so much time - I need to show how close I was to winning.
If you want to ignore me go ahead if not look at this table.
http://www.jrasplin.ukshells.co.uk/results.html
showing for each run the lowest num of flips, the script that got that and, just to illistrate, the flips I got with the difference to the lowest num of flips. Appoligies for the Excel generated html
It turns out a bug to do with handling duplicates in my code came to light in input4.txt (and possibly input6.txt) forcing it to use the flip-largest-top-flip-to-bottom. As you can imagine I'm annoyed at myself for missing this bug, clearly the best code won as it should.

oops that was my anonymous post

Whoa!

That winning code is incredibly terse! I think he should get another award! :O

This is the main part though, right:


Bah, it's too terse for me right now... I'm commenting his code as I'm reading it :O

Note: Speaking in the third person sounds stupid sometimes, but it is the proper way to do it in this case.

In this contest, one had to sort stacks of discs, as much as 500 high, with some duplicates present.

To have any chance of winning, one couldn't afford to risk failing to sort a stack. A 9999 added to one's moves would be a killer. In a 500 disc stack, there could be many duplicates, perhaps over 50. So any multiple path algorithm would quickly get too slow.

The only solution then, would be to decide on duplicate weights in a quick manner, and then sort in a quick manner. Checking paths for multiple weight combinations would most likely be too costly to be successful.

For a large stack, a good sort algorithm would have much greater benefit than for a small stack. Therefore, the way to have done it, I see now, was not start by trying to sort small stacks, but rather to start by sorting large ones. When one had an algorithm in place, which could perform the sort correctly, one would know how much processing time there was to spare.

One could then go about trying to reduce the number of flips, while knowing how much processing time it was costing for the improvements. An algorithm which sorts small to medium sized stacks well, but runs out of time on a large stack and defaults to a fast, bad way of sorting, would not be good enough, because much more moves would be lost on the large stack than could have been gained on the small ones.

In a 500 disc stack, which tends towards 2*n flips to sort, and which has to be sorted in 30s; each flip has to be calculated in an average of 30msec. A good algorithm, which can do it in 1.3*n, would have to calculate each flip in an average of +/- 60msec, basically an impossible task, save for genius beyond all recognition.

Also, Matt didn't reveal his machine's processing power (at least I don't think so). All I saw him reveal is that it has dual processors. While these could be fast, they could also have been Pentium Pro 200's. As I said, one could not afford to run out of time, because the fast, bad algorithm would lose too many moves.

Joe Koszo, the winner of the contest, weighted the duplicates in a very elementary way, then sorted the stack also not in two much detail, but beating the bad selection/bubble sort algorithm. His work paid off. Everyone who had fancy fangled algorithms couldn't pull it off fast enough.

Congratulations, Joe Koszo, you are smarter than I originally realised.

Well done everybody. May we all have learned something from this disastrous episode. I know I have.

If you disagree with my thinking, I would like to hear it.

Thanks the congrats, guys! This was my first submission to Codewalkers PHP contest, I hope everyone enjoyed this really challenging contest!

I know that my algorithm doesn't give the best result in all cases, but I want to find an optimal way between number of flips and the speed of alg. At this number of discs (50-500 or more) some duplicated value doesn't matter (ok, no was any info about number of duplicates), so I don't waste time to handle these cases, in this way the average time to sort 500 discs is about 1-3 secs.

(Bah, this was a pighead!

(My selected picture was a pighead...till now! )