Yesterday's train is going somewhere, but there also has to be a place where trains come from.
Here is a similar piece of code for helping the description, again Java, again built around java.util.Random

    public static void main(String[] args) {
        java.util.Random r=new java.util.Random(42091840247402l);
        byte b[]=new byte[5];
        r.nextBytes(b);
        System.out.println(new String(b));
        System.out.println(r.nextInt());
        System.out.println(r.nextInt());
    }

It displays five characters and two numbers, which is similar to what has happened with the other train, but the order has changed. The puzzle part also says something similar: knowing the 2 numbers is enough to find out the previously generated characters (or anything else). The numbers are 1812438423 and 1443536622.
In contrast to the previous puzzle, this one is about finding a counterpart for 42091840247402 (strictly said it is enough to find the number which follows it), and it involves discrete maths. 281474976710656 is (too) much more than 65536, by the way.

Hint 0: the links from the previous train still might have some use here
Hint 1a: solving the other train is part of solving this one
Hint 1b: the strange equation "(a*x) % m=b" is called a linear congruence, and it is solvable. Its normal notation is axb (mod m)
Hint 2: I was not exactly interested in coding a congruence solver from scratch. But searching for online linear congruence solver with Google delivers results
Hint 2a: JavaScript solvers use 32-bit precision, however they are very easy to port into other programming languages
Hint 2b: The WolframAlpha widget does not show its source code, but it seems to have the necessary precision (tried shortly)

Hint pack all+1

  • 1L << 48 is 2^48. Binary and-ing with ((1L << 48) - 1) is a modulo operation with 2^48. Example with smaller numbers: 2^4=16, something&15=something%16
  • do not forget subtracting the 11 (0xBL) from the "target" seed
  • if you want to use the example code, note that the constructor Random(x) immediately xor-s the seed, so you will need to initialize with new java.util.Random(calculatedseed^0x5DEECE66DL) in order to set the internal state to calculatedseed
  • the WolframAlpha widget

Megahint / example calculation
The example displays 1480905861 (or 5844D485 in hexadecimal) as the second number. Let us assume that we know the entire seed for this moment, 97052646561403 (5844D485D67B in hexadecimal).
Take a small note of 0x5DEECE66DL being 25214903917 in decimal, and 0xBL being 11 as already mentioned a bit above. Our modulo is 2^48, which is 281474976710656.
Then the congruence to solve is 25214903917x97052646561403-11 (mod 281474976710656)
97052646561403-11 happens to be 97052646561392, and then the entire thing can be typed into the WolframAlpha widget. 25214903917x to the first line (the x is necessary), 281474976710656 to the second, and 97052646561392 to the third.
After a few moments the widget will produce some x=16(17592186044416m+4005227429539) result, where 17592186044416*16 is simply 281474976710656, the modulus (2^48), and 4005227429539*16 is 64083638872624, the number what we need. It is 3A48A287EA30 in hexadecimal, and indeed the previous number was 977838727 (3A48A287 in hexadecimal).
Or one can also check that 3A48A287EA30*5DEECE66D+B=19055844D485D67B


Solution

The internal seed can be found exactly as for the other train, and then congruences described in Megahint can be solved 2-3 times.

    public static void main(String[] args) {
        long currknown=1812438423L << 16; // known part of the current seed
        long nextknown=1443536622L << 16; // known part of the next seed
        long nextmask=0xFFFFFFFF0000L; // mask for testing the known part of the number only

        long mul = 0x5DEECE66DL; // from Java documentation
        long add = 0xBL; // from Java documentation

        for (int i = 0; i < 65536; i++)
        {
            long currtest=currknown+i;
            if( ((currtest*mul+add) & nextmask) == nextknown ) // do an actual generation step and test the result
                System.out.println(currtest);
        }
    }

The result will be 118779964526270.
Solving the congruence once results in 228952716318111 (d03b3553959f).
Solving it for the second time results in 98150579699556 (5944766fff64).
Then one can either grab the values from these seeds, or solve the congruence for a third time, and run the original code with 277356786112797l^0x5DEECE66DL passed to new java.util.Random(...).
The solution leads to http://www.steamgifts.com/giveaway/ovDYS/, a train of 4 giveaways.
The example leads to a 140.

9 years ago*

Comment has been collapsed.

Too much math, I think. Will wait for the hint :P

9 years ago
Permalink

Comment has been collapsed.

This one is much harder then the previous one...

9 years ago
Permalink

Comment has been collapsed.

Bump for solved

9 years ago
Permalink

Comment has been collapsed.

Bump for "Hint 1" posted a little while ago

9 years ago
Permalink

Comment has been collapsed.

The quote copied below is really throwing me off. I guess 65536 is the number of brute force possibilities from the first part of this puzzle. But where did 281474976710656 come from?

281474976710656 is (too) much more than 65536, by the way.

9 years ago
Permalink

Comment has been collapsed.

That is the number of all possible states, 2^48. The remark says that this puzzle is not feasible for brute forcing. Except for the starting point of course (hint 1a)

9 years ago
Permalink

Comment has been collapsed.

Thanks for the clarification. I found some sample code which should solve this new challenge, and which other people confirmed as valid, but it doesn't return correct values for me. Argh!

9 years ago
Permalink

Comment has been collapsed.

Something about hint -1 from the other train?
Anyway, when you read this, hint 2 may be available already

9 years ago
Permalink

Comment has been collapsed.

Bump for all hints are available and plenty of time is left

9 years ago
Permalink

Comment has been collapsed.

Thanks for interesting puzzles, however I'm not sure if I found everything. Unless you have a giveway that's not part of these two puzzle trains.

9 years ago
Permalink

Comment has been collapsed.

Indeed, there seems to be a missed one (or you just really do not want it). Check for something oldschool in a non-train.

9 years ago
Permalink

Comment has been collapsed.

Ah, yes, I did miss that last one. Thanks for the hint!

9 years ago
Permalink

Comment has been collapsed.

Ahoy! Bump for another nice one.

9 years ago
Permalink

Comment has been collapsed.

Bump for still a lot of time left

9 years ago
Permalink

Comment has been collapsed.

Bump for addressing some (most) possible pitfalls

9 years ago
Permalink

Comment has been collapsed.

Bump for bump

9 years ago
Permalink

Comment has been collapsed.

Bump

9 years ago
Permalink

Comment has been collapsed.

Less than 3 days left... I should start trying it... Lazynesss >_<

9 years ago
Permalink

Comment has been collapsed.

Bump for made it very simple to solvers of the first train

9 years ago
Permalink

Comment has been collapsed.

Go puzzle, go. You are so simple now

9 years ago
Permalink

Comment has been collapsed.

Megahint / example calculation
The example displays 1480905861 (or 5844D485 in hexadecimal) as the second number. Let us assume that we know the entire seed for this moment, 97052646561403 (5844D485D67B in hexadecimal).

The part I can't wrap my head around is: why don't either of the code snippets below output 1480905861?

public static void main(String[] args) {
    java.util.Random r=new java.util.Random(97052646561403L);
    System.out.println(r.nextInt());
}

-1004185531

public static void main(String[] args) {
    java.util.Random r=new java.util.Random(97052646561403L^0x5DEECE66DL);
    System.out.println(r.nextInt());
}

-1744429294

9 years ago
Permalink

Comment has been collapsed.

Because the seed is updated before generating the number. So 64083638872624 paired with the second attempt will display what you expect. Or just make the example code generate a 3rd number, and that should be the -1744...

9 years ago
Permalink

Comment has been collapsed.

Bump for less than 7 hours left. Right now the puzzle is dummies-friendly (since I could solve it)

9 years ago
Permalink

Comment has been collapsed.

For the life of me, I can't figure out why this puzzle is giving me so much trouble! Consider the following code, which uses the seed from the first example:

public static void main(String[] args) {
    java.util.Random r=new java.util.Random(88572484529474l);
    System.out.println(r.nextInt());
    System.out.println(r.nextInt());
    System.out.println(r.nextInt());
}

Here is the output, along with the hex equivalent and each corresponding seed:

Int Hex Seed
1526088980 5AF64514 88572484529474L
1497528471 59427897 100002340297571L
1181382225 466A7651 98164270691692L

Let's assume we don't know any of the data in the first row and are trying to determine it using the second row. I plug 100002340297560 (100002340297571-11) into WolframAlpha and get:
x=8(35184372088832m + 17880314901047)
17880314901047*8=143042519208376 or 0x8218AE8B91B8
nextInt() with Random(143042519208376L) = -1979973613
nextInt() with Random(143042519208376L^0x5DEECE66DL) = 1525914616

None of this matches up with any of the known data in the table above. What the heck am I missing / doing wrong?

9 years ago
Permalink

Comment has been collapsed.

The seed in the first line is 88572484529474L^0x5DEECE66DL

9 years ago
Permalink

Comment has been collapsed.

Sorry, but that's doesn't mean anything to me.
88572484529474L^0x5DEECE66DL = 88561111452463 (0x508BBD96CB2F). That still doesn't match up with anything that WolframAlpha gave me.

EDIT: Nevermind, I think I see it now. I'll be back after a quick lunch break.

9 years ago*
Permalink

Comment has been collapsed.

88561111452463*25214903917+11 is 6BAD5AF64514BD0E, so something has to be right about it. Remember that the number "inside" the current seed has been generated already - so from this point of view the Seed column should start one row above the others

9 years ago
Permalink

Comment has been collapsed.

I'm very happy to say, "Bump for solved!"

9 years ago
Permalink

Comment has been collapsed.

Wolfram widget is broken (404) :(

Edit: working now!

9 years ago*
Permalink

Comment has been collapsed.

Bumped for solve!

9 years ago
Permalink

Comment has been collapsed.

Bump for solved

9 years ago
Permalink

Comment has been collapsed.

Sign in through Steam to add a comment.