Branches

[megabreit]

This one was strange and took me ages... probably because I'm not good with this "new fashioned" java stuff.
I started to optimize the disassembly, which was quite annoying. Some inserted debug output
and JSwat lead me to the right direction.

I found a hidden endless(?) loop (eL, sy, lC) and the one entry point to that loop (oe).
Since all 3 functions return the same value and oe uses 2 of them xor'ed, I thought that it might
be a good idea to remove those 2 function calls and so get rid of the loop.

Are there other ways to solve this?

[osterlaus]

I got the same solution on another way: I converted the java code into C which should compile to faster code. But it didn't compile on the first run and so I found the loop. After having it erased, the solution was near.

My first approach didn't help that much: I started to inline a lot of functions, erase stupid if-parts and inline again. But this was slow work and I already saw that I'd make one little error somewhere and the whole work was spare...

[gfoot]

I don't know much about Java debugging, so I've approached most of these challenges via the disassembler and a rudimentary knowledge of bytecode and the class file format. I usually then manually convert into Python and optimize it there.

In this case though I used a Python program to analyse the calls/called-by relationships in the disassembly. As for megabreit, that quickly picked up the loop, and then it's clear that all three functions are essentially identical, and as such they always return zero for non-zero input. So I just made them return zero straight away without recursion, and all was good.

[teebee]

I added a hash map to each method which calls at least two other methods. For instance,

Code: Select all

long bg(long paramLong) {
    return x6(paramLong) ^ j6(paramLong) ^ ok(paramLong);
}

was changed into

Code: Select all

private static HashMap<Long, Long> bg = new HashMap<Long, Long>();

long bg(long paramLong) {
    if (!bg.containsKey(paramLong)) bg.put(paramLong, x6(paramLong) ^ j6(paramLong) ^ ok(paramLong));
    return bg.get(paramLong);
}

. So, each relevant calculation took place only once.

[Hamstaro]

I like the solution with the hash .

This is how i found the solution:

First I decompiled the whole thing and then recompiled it in c#. (just 4 fun)

While running i took a look at the call stack. It showed that three functions are usign up all the cpu time.
A closer look at those functions showed that they alway return 0.
i just changed that and than the result was printed out rather quickly.

[fido2509]

I wrote a code optimizing script in PHP to reduce the decompiled Java Code to those 3 functions.
The reduction was simply a writing inplace, meaning instead of "return aS(l10)" "return <Code of aS>". Doing that with correctly replacing the arguments, the code reduces from 120 kB downto 25kB (with 24kB just the vg method)
After that I used a HashTable to minimize the run time.
The result came within a second after my little magic.


Thanks to the creator of that challenge


Fido

[kne1p]

I decompiled with jad and made transformations similar to fido2509's, but i took it way too far until i finally took a look at the stack in the debugger and replaced the branch in the else clause with

else return 0L;

Great challenge, but i could really bite my ass for going that long into the wrong direction.

[aurora]

this one was an interesting challenge. i too wrote an optimization script with php and stumbled over the functions eL, lC, sy which let to crash my script because of an endless loop. after analyzing these functions and recognizing, that they always return 0, the rest was quite easy

[magnus]

After finding the recursion

long eL(long l10) {
if (l10 == 0L) return 0x8a74526L; else return lC(l10 - 1L) ^ sy(l10 - 1L);
}
long lC(long l10) {
if (l10 == 0L) return 0x8a74526L; else return sy(l10 - 1L) ^ eL(l10 - 1L);
}
long sy(long l10) {
if (l10 == 0L) return 0x8a74526L; else return eL(l10 - 1L) ^ lC(l10 - 1L);
}

it was simple. I found it while debugging and watching the call-stack.

[Hippo]

I have decompiled, looked at the java source and got feeling each function is called just for one parameter (or does not depend on it at all). I was surprised why it tooks ages, but decided to simplify the code.

To make it by hand will last ages so I have coded a parser doing the stuff for me.
(OK there was a loop the bad parser missed, but nevermind when I uploaded the changed code to eclipse, it highlighted the place where the 3 functions are ... removing loop gave me immediate answer).

BTW: I like the save subresults solution preventing stupid recursion. ... What I was triing to do in parser there was let to runtime .

[yes-man]

This was a really nice challenge!

It took me a few days to create a C# program that optimizes the code in iterations. After maybe 15min of calculations the program stopped (new code length == old code length) and I stared at the triple we now all know (eL, lC and sy).
Took me a minute to realize what I'm looking at. Replaced it all with 0L and after that, running it in Java as well as the C# optimizer gave me the same answer quickly :D

Niiiiice!