hacker.org

Posted: **Sun Nov 23, 2008 4:44 am**

that one was pure evil ... first i wasted bunch of hours installing disassemblers which looked completely uncomprehensible to me... almost broke my virtual xp installation with softice. Then I decompiled with RemoteSoft samander and figured out the loops. Just when i figured out the exact value for the computation which is

f[k_] := 16 k^5 + 5 k^4 ((Sum[1 + Floor[Log[10, i]], {i, 1, k - 1}]) + 1)

I realized that there are bunch of shitting int overflows, so had to rewrite the program in C++ and optimize it.

Posted: **Sun Nov 23, 2008 4:52 am**

It took me like 20 minutes to do this since it was in C#

The name of the program is a hint, a C# executable is not a true executable, it is a .NET executable which is like a java .jar or .class file.

Use .NET reflector to see the original source code (viewable in six different languages), which is the following:

Code: Select all

private static int calc(int num)
{
    int num2 = 0;
    for (int i = 0; i < num; i++)
    {
        for (int j = 0; j < num; j++)
        {
            for (int k = 0; k < num; k++)
            {
                for (int m = 0; m < num; m++)
                {
                    for (int n = 0; n < num; n++)
                    {
                        string str = i.ToString() + " to " + j.ToString() + " to " + k.ToString() + " to " + m.ToString() + " to " + n.ToString();
                        num2 += str.Length;
                    }
                }
            }
        }
    }
    return num2;
}

 private static void Main(string[] args)
{
    Console.WriteLine("calculating...");
    int num = 0x63;
    for (int i = num; i >= 0; i--)
    {
        Console.WriteLine(i);
        Console.WriteLine("val: " + calc(num - i).ToString());
    }
}

You can mathematically count the number of loops that is executed and then go from there... I can't remember what exactly it involved but you have to use .NET reflector, I do not know if there is equivalent for linux.

Posted: **Sun Nov 23, 2008 10:05 am**

Allosentient wrote: You can mathematically count the number of loops that is executed and then go from there... I can't remember what exactly it involved but you have to use .NET reflector, I do not know if there is equivalent for linux.

I haven't found a linux equivalent, but the following website offers an online decompiler,
which shows essentially the same code:

http://www.remotesoft.com/salamander/

Posted: **Sun Nov 23, 2008 2:20 pm**

I used .NET Decompiler aswell and then used C++ to count through that. It worked but took too long so I did some maths: 99^4*((89*2+10)*5+99*16) mod 2^32

Posted: **Mon Nov 24, 2008 1:46 am**

hmm, i got similar (probably the same) mathematical closed form formula (see it in my first post, writen in Mathematica syntax) but i was not sure how to mathematically calculate the int overflow. I see you used mod 2^32, but that won't explain how you get negative answers, which happens with int overflow?

Posted: **Mon Nov 24, 2008 2:28 am**

To my surprise I didn't need to use windoze for that challenge, neither for executing the file nor for disassembling and analysing it. MONO was the key to success on linux machines - I never used any of that before and it was the first time to see CIL bytecode (disassembled it with a tool called "monodis"), so it was quite an interesting new experience.

After getting the routine I thought of solving the problem by using some combinatorics maths like some of you guys did, but well it shouldn't take _that_ long to execute this in an optimized version so I rewrote the loop in C, and got the answer in about 2 minutes.

Posted: **Fri Jan 16, 2009 4:00 pm**

I got the cil code, too, it was really quite fun to learn the instruction set (or part of it) by just looking at the code. The loop in the Main function was helpful because I already knew what it was supposed to do and once I understood that the rest wasn't all that hard.

Posted: **Sat Mar 21, 2009 8:21 pm**

Finding the CIL code rather menacing, I opted for a C# decompiler instead of a mere disassembler. "Exemplar" from the Anakrino9 package did the trick for me, after having delighted an otherwise quite useful vmware image with the dotnet framework... shudder. My formula (Unix "bc" notation):

x^5 * 26 + 10 *5* x^4 *25 + 10^2 * 10* x^3 *24 + 10^3 *10* x^2 *23 + 10^4 *5*x*22 + 10^5 *21,

x being 89 for value 0. Formula is based on the number of cases with 0, 1, 2, ...5 one-digit numbers in the inner loop.
x is the maximum number of 2-digit numbers.

Getting to take the result module 2^32 took some staring unbelievingly at the ".... is incorrect" page.
The summation in the C# code indeed gets negative at some point, where it simply continues to add positive values, finally becoming positive again... that is why modulo 2^32 of the end result only still works.

Posted: **Sat Mar 21, 2009 9:43 pm**

I don't have a Windows PC at home and did not want to mess with Mono in Linux.
So, call me lazy, I simply started the program on a work PC and left for some holidays.

I don't know how long the program ran, but when I went back the result was calculated.

Posted: **Sat Mar 21, 2009 10:09 pm**

YOU are the reason of global warming!

@ Challenge author:
Polynomial time is lame. Make it exponential complexity next time, that would prevent such an approach. For some time...

Posted: **Sun Mar 22, 2009 1:45 pm**

You're completely right! I apologize to mother earth!

To my defense: The PC (a server) was running anyway.

Am I the only person who simply executed the program to see what it does?
As I saw that it progressed rather quickly I left it running.
I don't know how long it would have taken me to find the solution... I never messed with .Net/Mono
so it might be very possible that my decision was the better one for the climate

Posted: **Sat Jun 20, 2009 7:42 pm**

By factoring the first 20 numbers I figured out the formula:
(99-k)^4 * ( (88-k)*26 + 236)
Implementing this in Java for k=0 gave me the right result.

I thought the name is a hint, but I didn't get it.
Anyway it's nice to know how to decompile C#-executables now ..

Posted: **Fri Nov 20, 2009 5:55 am**

Ahhh! That took forever (2-3 hours)

Used first 20-30 factors to work out the formula =(k-1)^5*21+k^3*5*k*MAX(0, k-10)
where k = 100-(time left)

Then used Excel to work out the binary crap along with http://www.subnetonline.com/pages/conve ... to-dec.php

Posted: **Sat Jul 02, 2011 1:37 pm**

megabreit wrote: Am I the only person who simply executed the program to see what it does?

No, you are not the only one who just let it run.

Posted: **Mon Jul 04, 2011 3:44 pm**

So... how long did it run?

hacker.org

countdown calc

countdown calc