Code optimization

[AMindForeverVoyaging]

so i converted all my code to c++
created my own classes for bigints, stringbuffer, stringbufferarray
as any true hacker might do

I'm not sure why anyone would want to write such classes from scratch, when there are perfectly good existing libraries for all of these purposes out there. You are using other people's code with e.g. Java's BigInteger class, so why not do the same when coding in C++?

Anyway...
Boost
NTL
C++ Big Integer Library
...just to give a few examples.

[compudemon]

so i converted all my code to c++
created my own classes for bigints, stringbuffer, stringbufferarray
as any true hacker might do

I'm not sure why anyone would want to write such classes from scratch, when there are perfectly good existing libraries for all of these purposes out there. You are using other people's code with e.g. Java's BigInteger class, so why not do the same when coding in C++?

Anyway...
Boost
NTL
C++ Big Integer Library
...just to give a few examples.

i am aware something of biginteger exists in .net C++ and i know about boost as well
the thing is speed making your own classes v.s. speed finding and learning how to use existing ones. take the boost library i actually did look through the library hunting for a bigint class, i gave up even though i suspected one existed. i think i may have found it but then i would need to read the docs, look at use examples... considering i only needed a few one line fucntions it made more sense to roll my own.

[papa]

Optimizing the O(n^3) Gaussian Elimination e.g. by grouping booleans to integers took me to level ~400. Then I redesigned my algorithm. Now it has less than O(n^2) complexity and solves even the last levels in less than 20 seconds using Java without any optimization at all.
Algorithm beats implementation.

[bsguedes]

O(n^2) ? That's interesting.

My O(n^3) took approximately 40 minutes in the last level.

[compudemon]

guassian would be N^2 time with packed bools if each row could fit into an int. naturally its still an N^3 problem just done parallel. Am I correct in guessing that some form of algebra, letting the highly regular nature of the N unknowns trim down to a simplified matrix with (N ^ (2/3)) unknowns then guassian done on that?

[MyNameIsAlreadyTaken]

I'd rather say he uses the properties the matrix has [symmetric, sparse and Elements in Gf(2)].

[dangermouse]

For the o(n^3) algo, i have a special approach...

the approach leads to fast code, but for some reason the solutions computed are sometimes wrong, especially for the higher levels... i worked hard to find the mistake in the freepascal code but can't find it. the first level where the approach fails is level 99.

I observerd that in my implementation, the rank of the matrix is different from the productive code i am using, and so the number of pivotal elements. But maybe i have some linear dependent rows which still need to be spotted...

Is the approach theoretically correct, or is there something fundamental I am missing?

[dangermouse]

Never mind, i found the mistake. The author of the algorithm would turn into his grave, if he would see how I did pivoting when the linear system is undetermined... Still, with such a conceptual mistake i made it quite high...
No wonder i got bad grades in numerical parallel computing

[guga]

@dangermouse:
I have the exact same problem you described. Only that my pivoting sucks already on lvl 83. How did you get rid of that? Was it just changing the pivoting? Or did you have to do a totally different approach? I tried some more or less clever ways to find good pivots, but they all failed...

[dangermouse]

hey guga,

my problem was: i was not handling correctly the system of linear equations when it was undetermined!

My crucial error was: if i could not find a pivot in a column, then i did startx=startx+1,starty=starty+1, but i should have done only startx=startx+1. So, do not move along diagonal when you do not find a pivot, just go one right when looking for the next pivot in the next column.

btw this error is also in the linalgebra book i was using at university, and now i remember a good friend of mine pointing me at this error, 13 years ago

[guga]

BÄM! My personal Hero of the day
Since at my implementation startx and starty are the same, I'm just adding a row into the matrix with the diagonal element. That's also working.
Now I only have to improve my memory consumption. lvl 272 needs more than my 4GiB ram. Seems like the data structure I'm using has _way_ too much overhead...

[Hippo]

I am using java, BigInteger.
setBit while creating equations and testBit and xor while solving.
setBit, toString and substring to retrieve the solution.

Works rather fine ... still running on 294 requires under 30s.
BTW: My compose time (creating equations) on level 350 is twice as big as solving time ... with total around one minute.

--- edit ---
OK, I have changed the create equations part to process buttons in horizontal blocks "together" and than buttons in vertical blocks together. This speeded the compose time to about one tenth of solving time.
So now both parts together require about one third of original time.

BTW, now I use subtraction as well (and of course or as well).

--- edit ---
Now on around 450 it takes around 3 minutes per level.

--- edit ---
Level 522 seems to be roughly same size as 521, but I have reached Out of memory there ... seems recoding my own "BigInteger" will be needed (BTW solution times till it were under 5 mins in most cases).

--- edit ---
there is Xmx switch which could help, let us see for how long ...

--- edit ---
Next problem is on level 550 ... web challenge ... the page was downloaded just partially missing end of the board. OK accept encodding gzip helped with this problem.

--- edit ---
Problems with memory have returned on level 555 ... I am afraid I am almost on limits of easy implementation.

--- edit ---
Hmm, tonight it stopped by not downloading 568 level, even when repeat works fine.
Maximal solving times are under 25 minutes.

--- edit ---
I have decided to change the algorithm (I was "almost" computing inverse matrix originally) I have decided to switch to diagonalizacion instead of triangularizacion (with square of "inverse") and the algorithm slowed down rapidly. So I changed it back to triangularizacion, but without "the square of inverse", but I speeded up the values retrieval from the triangle without further changing the matrix.
Seems this is faster than the original. ... Making small change to a BigInteger is indead very slow and implementing arrrays of longs must be much faster. But unless the boards would expand much more faster in levels above 575 the BigIntegers would be good enough ... now the solving time is less than 10 minutes per level.

--- edit ---
OK, I have decided to code matrix based on longs to replace BigInteger. I made a lot of (of 1 bugs), but comparision with results of previous implementations helped to debug them rather quickly ...
Now the running time should be O(n^3/64) compared to O(n^4/64) caused by BigInteger copying.
The speedup is visible even on low levels. (Levels around 300 under 3s per level)

--- edit ---
Hmm, its just about 5 times faster, and I got to out of Heap Space again. ... I reallocate the matrix for each level, but ... OK, let us see if it was caused by running too many levels in a row ... OK, maybe its a problem of long[][] alocation in one chunk instead of several...

[CodeX]

Try adding a "Accept-Encoding: gzip" header to your request

[Hippo]

Try adding a "Accept-Encoding: gzip" header to your request

Thanks, seems it would work.

[Isaev]

How we will apply the Gaussian Elimination for example to such level?
11#0
#011
01#0
(#-wall)