hacker.org Forum Index
RegisterSearchFAQMemberlistUsergroupsLog in
My journey to 643

Reply to topic    hacker.org Forum Index » Crossflip View previous topic
View next topic
My journey to 643
Author Message

Joined: 31 Aug 2012
Posts: 3

Post My journey to 643 Reply with quote
A friend of mine showed me this site. I tried several puzzles manually and looked at modulo first from programmer's point of view but didn't solve much.

Then crossflip catched my attention. It looked quite obvious and simple XORing.

My language of choice is pure C. Not using it for work, but i do enjoy implementing complex data structures in it.

Just to validate i can parse tasks and submit solutions i implemented a simple bruteforce first. E.g. pack the whole solution into 'unsigned long long int' and just increment it starting from 0 until a valid state found. Surprisingly this worked fine until level 74! Quick calculation showed it will take at most 200 days to check all the variants at 74.

At which point i started looking for optimizations. And failed to find them. Lots of microoptimisations of course, but they won't help reducing time significantly.

In a search for new ideas i tried google and found a hardware game called "Lights Out". This was it! Lots of papers on solving it using linear algebra. Quite popular among mathematicians. And a beautiful solution too.

I implemented Gauss. Any solution would do, hence unknown variables i chose just to replace them with 0s.

I used 'int' to hold cell value and this worked fine until field sizes grew larger than 32 bit memory. Okay, switched to byte here. As expected performance dropped by 30%.

Somewhere in the middle i decided to try parallel runs. This makes sense as adding rows could be easily parallelised.
Well, this didn't work of course. Parallel version was 6 times slower. It makes sense to run only computationally intensive operations in parallel. XORing lines of bytes relies on memory throughput, not CPU performance. So i abandoned this version.

Then at some point i had to switch to 64 bit because again memory requirements grew greater than 32 bit process can handle, even for a byte.

As levels grew so performance dropped. I started looking at cleverer algorithms than Gaussian Elimination, like LU decomposition based ones and all that clever stuff. Matrix is symmetric and extremely sparse. There HAVE to be some better algorithms.

While i was trying to understand some of the papers the user Ignorance outrun me in solving levels. Argh! I was between 400 and 500 at the time. I then decided to pack 8 variables into a single byte still using Gauss. After all, all is required is XOR on forward step and XOR and AND on backward step of Gauss.

Packing variables sped up my code by the factor of 30! Wow! this was quite unexpected to me.

I decided to stay with Gauss for now and just optimize my solution. Rows were aligned on 16 bytes, padding added, SSE instructions engaged via _mm_xor_si128() and voila! Speed up by 10.

This was the final code to reach level 643.
Mon Oct 22, 2012 2:35 pm View user's profile Send private message

Joined: 02 Mar 2012
Posts: 17

Post Reply with quote
congrats on beating the game! I always like to hear about what problems and solutions others have.
But since this forum is open for everyone, I fear your post is taking away too much of the challenge. Note that only about 70 people completed crossflip so far.
I think it would be great if we could have something similar to the "challenges solved"-section for the games.
@adum: what do you think about that?
Mon Oct 22, 2012 3:37 pm View user's profile Send private message

Joined: 31 Aug 2012
Posts: 3

Post Reply with quote
@adum: feel free to delete this post if you think it discloses too much. But i think there's enough chatting about gauss elimination on this forum to the full solution.

BTW on projecteuler.net forum topic on a particular problem would be unavailable until you solve the problem.
Mon Oct 22, 2012 3:59 pm View user's profile Send private message

Joined: 16 Apr 2009
Posts: 62

Post Reply with quote
I realized too late how revealing the discussion in the forum had gotten. Too late now. I don't think there is anything new in this Thread.

I only wish there would be more levels to spread out the top again, but I fear the solution checker would soon bring down the server.
Wed Oct 24, 2012 10:42 am View user's profile Send private message

Joined: 05 Aug 2007
Posts: 2

Post Reply with quote
There is no need at all optimizing how you store the data imo. I used booleans, and manipulated them 1 by 1, not 64 at once. I solved all levs fast.

The speed factor you achieved with the data type you used is very promising, but i think better algorithm can speed things up much more Smile

Would be interesting to compare our algorithms on level 1000.
Mon Mar 11, 2013 11:19 pm View user's profile Send private message
Display posts from previous:    
Reply to topic    hacker.org Forum Index » Crossflip All times are GMT
Page 1 of 1

Jump to: 
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum

Powered by phpBB © 2001, 2005 phpBB Group
Design by Freestyle XL / Flowers Online.