The end of my contest

Hi guys

This is the situation as it stands.

When I first saw this competition, I wanted to see if I could solve the problem in a good way. For me, a good way means writing an algorithm that is good enough to get close to the minimum moves without testing all combinations.

If I achieved this, then I would have been satisfied woth my work. As it is, I have found that for stacks without duplicates, I can sort them very well, almost always getting within 1 move of the minimum.

When the stack has duplicate values, however, I can't seem to work out a way to reliably give good results. The only other alternative would be to try all permutations of weights for each duplicate set, but this doesn't always work (as diclophis found with 68427586). I keep thinking to myself, 'there must be a better way'. After many hours of work, I still have not managed to achieve the goal I set for this contest. As I feel I have not produced a good solution for the problem at hand, which has duplicates in, I will not be entering.

At this stage, I realise that you may get the impression that I am all talk and no action. This is entirely untrue. I AM a good programmer and I HAVE put a lot of effort into finding a good solution (about 60 hours).

To those of you who have a well coded program you are proud of, I implore you to enter and wish you the best of luck.

I've enjoyed this contest; unfortunately I couldn't crack it. I look forward to the next one.

To the creators of PHP, I've noticed two things which I found annoying.
In C++, when I return values from a function, I prefer not to test on the actual value, rather I define macros for each return value with a name that means something. eg. #define ELSINGLE 1. I couldn't find out how to do that in PHP, so I used a global variable. eg. $elsingle = 1;.

Also, it doesn't seem possible to overload constructors. I had to use a child class to implement another constructor.

Of course, apart from this contest, most of my PHP experience has been with PHP3. There may be ways to do these things now that I am not aware of.

Anyway, till next time.
Neil Cahill aka -vertigo-

PS. About the wise quote below, it is not anything some famous person said; rather I am quoting myself. Since I'm such a wise guy, it becomes a wise quote.

Hi Vertigo

Although I haven't posted here I have been following the conversations.
I was looking forward to competing against your code

I respect that you were trying for a close to perfect algorithm.
My goal was just to beat the brute force algoritm mentioned on the boards.

The point is your code doesn't have to be amazing - just better than thte others

I hope you reconsider entering something - especially after spending so much time on it.

With regards to use of macros in c++, from what you say I believe you are looking for something like this:


Can't help with overload constructors

regards,
John

-vertigo-

if you spent 60 hours on your solution, i would suggest you enter the contest.

you never know how bad did others do!!

Thanks for the replies.

The truth is, I had worked many hours on trying to get the best algorithm, but it was not completely coded. In fact, I only started coding after the first week.

Usually with a problem as difficult as this, I find that if I start coding to early, I usually end up rewriting from scratch.

So, although I knew how to sort no-duplicate lists, I had not coded the final modifications which saved 1-2 moves about 20% of the time. When I wrote the previous post, I had realised that although the code was good for non-duplicate lists, to modify it for lists with duplicates and trying multiple weight combinations would have used a LOT of memory. So I would essentially have to recode from scratch anyway.

As I said, I wanted to have an algorithm which didn't bruteforce. So, it wasn't particularly conservative with memory.

I put myself in a spot, because the way I wrote my code, it could only really be used without brute-forceing. Otherwise, I would not rely so much on the algorithm, rather on finding the best of several duplicates and making that process fast.

As I said, I enjoyed coding it as I haven't seriously coded for nearly two years. Next competition I will seriously try to get an entry in.

Cheers

I was slightly mistaken in my previous post. I could of course branch before I sort anything, instead of when one of a duplicate set comes to the top of a stack.

Then it would need exactly the same memory, just longer execution time.

Loooking back, I wouldn't have done my program the same way. It was implemented as an object, containing a list of elements. When adjacent elements become compatable, they merge. eg. when 231 becomes 321, the sorted element 23 and the single 1 merge. I certainly don't think this was the best way to do it. The code also became very long, almost 1000 lines.

Especially if I planned to brute-force, I would have worked with one global array throughout.

Even had I tried to simply sort all combos of weighted dups, my algorithm was not completely coded. It was fine in my head, but to get that into code is not always easy.

I seriously doubt I could have revamped my program in the two days which remained.

They say every failure is one step closer to success. Hopefully next time will be better.