22 November 2010

Me on Al Zimmermann's Programming Contests

I am taking part in Al Zimmermann Contest Task is complicated because of number of combinations. It is N! and task should be sold for 25 sets for primes from 2 to 97.

Since problem was published on Nov 16 I attacked task from different angles. I optimized code and changed algorithm. Number of n! is huge. Computation power available to me cracks up to 200M combinations per second. 200 millions combinations per second is fast - I started with 100 thousands per second.
I solved all numbers less then 17. But 17! = 355687428096000 and brutal force will review all combination in 41 days. (For comparison, solution for 13 takes 30 seconds). The longest set I manage to found is 389 steps for 43. That gives me 10 (currently 10.47) points of 25 points maximum.

There must be some trick others know and I don't!

Another point I want to express. Last week was the happiest week in professional sight. My brain was spinning around the problem: pen an paper, coding, code profiling, optimisation, leave computer for night, for a days and raising my score. I was so exciting when I invented new approach and this gave me jump from 500k to 10 millions of combinations. Crunch crunch! Then recursion and I have hundreds on millions! Then I was thought I could solve it. I mean like equation. Heart was beating! And nope it doesn't work in that way. But it gave me another couple days to work on it.
Honestly I don't remember when I had such high feeling in professional life. This task raised me beyond and above what I was coding last years.

I also working on solutions for Euler project. This is became a sort of hobby. Besides of brain exercise to find algorithm I am progressing from ad hoc solutions (when amount of task was less then 20) to a framework for library of tasks. My next idea is attach tasks to silverlight facade and host it. It might become a benchmark for heavy computations for Silverlight.
What strike me few days ago is that such platform could he a host for distributed computations. Everyone who has spare processor cycles can open a web page with Silverlight application, click a buttons and help world to solve a problem. I went further - think about mobile phones! you put it on charge and start computation. You give away half an hour of your 500Mhz - 1GHz! What a supercomputer we could build!!!

No comments: