hacker.org

Posted: **Wed Nov 26, 2008 11:25 pm**

Well, I'm confused now.

I spent ages analyzing the bytecode, reimplementing in Python (including the exact behaviour of java's Random class), and simplifying the calculation, only to get the wrong answer every time. Even poking the bytecode to get it to output intermediate results, to compare with the Python - e.g. checking the Random class output the right number sequence. So finally I bit the bullet and reimplemented the algorithm in Java, optimized the loop a bit, doing it all with integer maths and avoiding the string conversions, and got the right answer.

I need to work out what was wrong with my Python - I had simplified the calculation further, but I also implemented the actual loop used (x = x*2+1) as a verification, and when my simplification said the answer was right, the long loop agreed anyway. I guess I somehow got it to ignore some correct answers.

Still, it was interesting to finally write some Java code, having previously hacked on the bytecode so many times now for these challenges. It's weird how some things are supported in bytecode but harder to actually express in the language itself! I must be missing something though.

Posted: **Thu Nov 27, 2008 12:34 am**

Oh, it was just a bug in the way I combined two 32-bit numbers into a long in my implementation of the Random class - the Java Random class uses signed addition, while I treated the two ints being combined as unsigned. It meant 50% of my numbers off by 1<<32, and I hadn't compared the sequence closely enough with a genuine Java sequence to spot that - the first few decimal digits were still correct.

Posted: **Sun Feb 15, 2009 9:57 pm**

I took another nice approach: I calculated the ending strings from 1 upwards recognizing that the ending patterns occur only at some numbers. At the end of my optimization, I had the condition "l % 390625 == 259683" which I added to the while-loop which sets l to the next random number. And so I get the valid solution after very little time.

Posted: **Sun Feb 15, 2009 11:52 pm**

I took the easy way (I guess):
Following a hint in the forum I simply removed string operations and turned BigInteger types into long.
Then I took all calculations and numbers modulo 1000000000.

The program ran about half an hour, but compared to the effort this was OK.

Code: Select all

import java.io.PrintStream;
import java.util.Random;

public class Patience
{

    public Patience()
    {
    }

    public static void main(String args[])
    {
        Random rnd = new Random(739391L);
        long l;
        long biginteger;
        do
        {
            while((l = rnd.nextLong()) < 0L) ;

            biginteger = l%1000000000;

            for(int i = 0; i < 20000; i++)
            {
                biginteger = (biginteger +biginteger +1)%1000000000;
            }

        } while(biginteger != 843997183);
        System.out.println(l);
    }
}

It's probably very easy to implement this in any other language because the RNG sequence is not really important. It should be possible to find the solution with brute force, trying every possible long value...
but one does not win the speed award

gfoot: I don't really understand your problems with signedness...

The while loop around rnd.nextLong filters out all negative numbers. So the addition loop is working just with unsigned numbers...

Posted: **Mon Feb 16, 2009 12:20 am**

megabreit wrote: It's probably very easy to implement this in any other language because the RNG sequence is not really important. It should be possible to find the solution with brute force, trying every possible long value...
but one does not win the speed award

It's been a while, so my memory is hazy, but I think my first attempt was just to run the calculation backwards to work out which inputs would work, and there were a lot of them, and the site only accepts the one the java RNG would spit out first.

gfoot: I don't really understand your problems with signedness... The while loop around rnd.nextLong filters out all negative numbers. So the addition loop is working just with unsigned numbers...

Java's RNG generates 32-bit numbers by generating two 16-bit numbers, shifting one left 16 places, and adding them together. It comes down, again, to providing the right one of the many inputs that pass the condition in the loop - my slightly wrong RNG generated a different solution first, which wasn't the first one the Java Random class would have generated, and hence wasn't the solution the website was expecting.

Posted: **Mon Feb 16, 2009 6:37 pm**

Hm... didn't thought of the possibility that the result might not be unique.
But, further thinking about it, it's quite logical.
Do you know how many solutions exist? I wonder if it's another way of solving to simply
calculate them all and try

... just in case java is not an option

Posted: **Thu Aug 20, 2009 12:32 pm**

I solved this one quickly by doing some little math:
f(0) = l
f(k) = 2*f(k-1)+1
=> f(k) = pow(2, k)*l + (pow(2, k) - 1)
with f(20000) % 1000000000 = "843997183"

That way I implemented a class which solved the challenge within seconds.

Code: Select all

import java.math.BigInteger;
import java.util.Random;

public class Berechnung {
	public static void main(String arg[])
    {
		// using shortened version of pow(2, k)... in order to reduce calc time
		// also only the last 9 digits are interesting
		BigInteger twok = new BigInteger("21663406309376");
		
		Random args = new Random(0xb483fL);
        long l;
        String s;
        do
        {
            while((l = args.nextLong()) < 0L) ;
            BigInteger fk;
            BigInteger fzero = new BigInteger(Long.toString(l));
            s = null;
            // f_k = 2^k*(f_0 + 1) - 1
            fk = twok.multiply(fzero.add(new BigInteger("1"))).subtract(new BigInteger("1"));
            s = fk.toString();
        } while(!(s = s.substring(s.length() - 9)).equals("843997183"));
        System.out.println(l);
        
    }
}

Using only the last few numbers of pow(2, k) made the trick. I used more than 9 digits just to be sure.

To answer the question of megabreit:
Yeah, using the formula f(k) + 1 = pow(2,k)*(l+1) it is possible to calc all valid numbers.
But as only the last 9 digits matter the result will be all numbers that end with a valid 9 digit sequence.
I tried it and found around 50 9-digit-number-sequences.
Thinking about that any 64 bit number which ends with one of this 50 sequences is a possible solution, you might get the answer faster by simply running the program and being patient.

Fido

Posted: **Fri Oct 16, 2009 2:51 pm**

This one took me about 2 sec to solve the challenge

Code: Select all

import java.math.BigInteger;
import java.util.Random;

public class Patience2
{

    public Patience2()
    {
    }

    public static void main(String args[])
    {
        Random argu = new Random(0xb483fL);
        long l;
        String s;
        do
        {
            while((l = argu.nextLong()) < 0L) ;

            /* last 9 digits for x0 = 0 */
            BigInteger start = new BigInteger("406309375");

            /* last 9 digits for 2**20000, which is the 
             * increment value for each successive number
             */
            BigInteger inc = new BigInteger("406309376");
            BigInteger biginteger;
            s = null;

            /* replaced the inner for-loop by faster formula:
             * x = start + inc * l
             */
            biginteger = start.add(inc.multiply(new BigInteger(Long.toString(l))));
            s = biginteger.toString();
        } while(!(s = s.substring(s.length() - 9)).equals("843997183"));
        System.out.println(l);
    }
}

Posted: **Tue Jan 12, 2010 6:24 pm**

i took a 3 step approach.. first, i removed the loop and just assembled a string of 0xffff"*20000/16 , then to see what the first, second, third, ect number was i pluged in 0 1 2 3..., found the easy sequence(base 1431558 + n*1953125), and just did

Code: Select all

Random var7 = new Random(739391L);
long var2=0;
do {
	   while((var2 = var7.nextLong()) < 0L) {
            ;
           }
}
while(!((var2%1953125-1431558)==0));
System.out.println(var2);

btw there seems to be a bug in the code,
(!var5.substring(var5.length() - 9).equals("843997183"))
fails every time even on the correct number, yet
String var6=var5.substring(var5.length() - 9);
if (var6.equals("843997183"))
break;
works. mayby eclipse bugged out a bit on very long strings.

i was also very noobish for a while... i was going... "it cant be 843997183 because its always going to have FFFFFFFFF" not realizing i was in the wrong base

Posted: **Sun May 30, 2010 1:35 pm**

Code: Select all

import java.io.PrintStream;
import java.util.Random;

public class Patience
{
  public static void main(String[] paramArrayOfString)
  {
    Random b = new Random(739391L);
    long l;
    long localLong;
    int n = 20000;
    long sub = 406309375;
    long exp = 406309376;
    long TenNine = 1000000000;
    do
    {
      l = b.nextLong();
      localLong = l % TenNine;
	
      localLong = ((exp * localLong) % TenNine) + sub;
      localLong %= TenNine;
    }
    while (!(localLong == 843997183));
    System.out.println(l);
  }
}

Less than a second!

Posted: **Sat Jul 20, 2013 4:29 pm**

Yay ! Funny maths \o/

I just took the first number such that l%1953125==1431558 which takes no time of course.

I was surprised so many people could do that but actually most just optimized a bit the processing