We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Loading...
  • Practice
  • Compete
  • Jobs
  • Leaderboard
  • Hiring developers?
  1. Practice
  2. Security
  3. Cryptography
  4. PRNG Sequence Guessing
  5. Discussions

PRNG Sequence Guessing

  • Problem
  • Submissions
  • Leaderboard
  • Discussions

Sort 48 Discussions, By:

votes
  • recency
  • votes

Please Login in order to post a comment

  • delamath 3 years ago+ 1 comment

    For those who are not using Java to solve this problem, the following is some related source code from the java.util.Random library. ;)

     public synchronized void setSeed(long seed)
     {
       this.seed = (seed ^ 0x5DEECE66DL) & ((1L << 48) - 1);
       haveNextNextGaussian = false;
     }
     
     protected synchronized int next(int bits)
     {
       seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
       return (int) (seed >>> (48 - bits));
     }
     
     public int nextInt(int n)
     {
       if (n <= 0)
         throw new IllegalArgumentException("n must be positive");
       if ((n & -n) == n) // i.e., n is a power of 2
         return (int) ((n * (long) next(31)) >> 31);
       int bits, val;
       do
       {
          bits = next(31);
          val = bits % n;
       }
       while (bits - val + (n - 1) < 0);
       return val;
     }
    
    7|
    Permalink
    • karthik018 2 years ago+ 0 comments

      what could be the initial seed value ?

      3|
      ParentPermalink
  • thexguy 4 years ago+ 3 comments

    Test case #4 clearly violates the definition of the problem. In the description it says "The first line of input is a number N<10..." while Test case #4 provides exactly 10 test cases.

    7|
    Permalink
    • global4g 4 years ago+ 1 comment

      You have to parse the input and if you can do for upto 10 then you can do for more as well :) but good catch!

      1|
      ParentPermalink
      • thexguy 4 years ago+ 0 comments

        It's not a big issue and the algorithm will definitely work for 10 or more. It's just frustrating when you follow the instructions and a test fails.

        5|
        ParentPermalink
    • asailijhijr 3 years ago+ 0 comments

      Yeah, it makes sense in the real world to check your inputs against the constraints given, you should throw an error in your code if someone else's code isn't functioning properly and that'll cause an error in your code. On the other hand, code that's as robust as possible and "just works" virtually no matter what without using too much memory has its own place in the scheme of things.

      0|
      ParentPermalink
    • qwrtyuiuytres 2 years ago+ 0 comments

      N<=10

      0|
      ParentPermalink
  • zouhair_madid 5 years ago+ 4 comments

    Hello, Is it even possible to solve this challenge in C++?

    7|
    Permalink
    • dayteed 5 years ago+ 2 comments

      Nope, doesn't look like it. No matter what I have tried you cannot get the same sequences... The exercice should be constrained to Java...

      0|
      ParentPermalink
      • zouhair_madid 5 years ago+ 1 comment

        I want to see the other submissions, I will submit the code in JAVA and then check if someone was able to solve it in c++.

        0|
        ParentPermalink
        • zouhair_madid 5 years ago+ 1 comment

          I had to solve it in java, most solutions were in java or java8, few python and only 5 solution in c++, they had to implement the nextInt() of java by themselves. I hope this help!

          7|
          ParentPermalink
          • BugshotGG 4 years ago+ 1 comment

            May I ask you, which functions should we implement from the java.util.Random? I am lost, it has so many and I do not know which of these are useful etc.

            0|
            ParentPermalink
            • Tuxdude 4 years ago+ 1 comment

              Look at setSeed(long) and nextInt(int)

              0|
              ParentPermalink
              • BugshotGG 4 years ago+ 0 comments

                Should final AtomicLong seed; be a long long in c++?

                0|
                ParentPermalink
      • code_eagle 3 years ago+ 0 comments

        what about python?

        4|
        ParentPermalink
    • Tuxdude 5 years ago+ 0 comments

      Yep you can, but you need to implement a Random number generator exactly how java.util.Random does, both the seeding as well as generating the next random number

      This is one thing which really puzzled me in this problem. The problem as it is, is not that hard to solve for people using Java or other languages which probably use the identical PRNG implementation.

      I still have the question, whether the authors intended the problem to be solved this way or there is a better approach which is not obvious.

      1|
      ParentPermalink
    • dfionov 5 years ago+ 0 comments

      You can. Just look at http://docs.oracle.com/javase/7/docs/api/java/util/Random.html and http://developer.classpath.org/doc/java/util/Random-source.html

      6|
      ParentPermalink
    • martin_kipfer 5 years ago+ 0 comments

      I solved it using C++. Basically you just have to implement the Random class from java. It's a waste of time, but I did it as an exercise... It gave me headaches until I realized java and c++ don't use the same length for long integers...had to use long long.

      6|
      ParentPermalink
  • sherifmowafy 3 years ago+ 1 comment

    Couldn't help but notice that all the submitted codes for this problem do not match the current problem statement input, they had extra "start time" and "end time" inputs which makes the problem much easier. Has anybody solved this problem lately without these inputs?

    5|
    Permalink
    • pliptor 3 years ago+ 0 comments

      I just finished solving it. I'm not sure if I'm missing something to not have a solution as short as others solving the old problem with "start time" and "end time".

      0|
      ParentPermalink
  • Chandika 4 years ago+ 1 comment

    Is it even possible to solve this challenge in Python?

    4|
    Permalink
    • YiSH 4 years ago+ 1 comment

      Hi, I followed dfionov's suggestion and implemented a JavaRandom in python. It works on all test cases except the last one(No.4), which is a Time Limit Exceeded. I was stucked here. And I looked at the last test case. It is a ten single-seed input. So the execution time is just measuring the performance of that self-implemented PRNG, i.e. for 10 seeds, each generates about 20 randint(1000). Could use anyone's help. Thx. Maybe it would be better just relax the time limit on that last testcase of python.

      3|
      ParentPermalink
      • denalilumma 3 years ago+ 0 comments

        Would you share your code with me? I have a partially working Python 2 solution, but I am stuck.

        -2|
        ParentPermalink
  • codeharrier 4 years ago+ 1 comment

    This challenge could be improved greatly. It assumes java, forcing everyone else to write the RNG themselves, and some of the test-case inputs aren't even numerical.

    3|
    Permalink
    • Gabbek 4 years ago+ 0 comments

      I have no idea what to think of last two test cases as they are just random strings and there's no numerical input... it seems it's a fresh bug, as pretty much any solution doesn't have hard-coded solutions to the said two strings (most likely meaning that the bug had to appear lately)

      1|
      ParentPermalink
  • amart42 3 years ago+ 0 comments

    Go to hell with it, please. If you constrain this challange strictly to Java and it's Random library, please do it explictly, not the implict way.

    2|
    Permalink
  • haveagr8day 3 years ago+ 1 comment

    Is this problem still solveable? The past solutions all refer to timestamps which don't seem to exist in the input of the current version of the problem.

    2|
    Permalink
    • pliptor 3 years ago+ 0 comments

      Yes, all testcases within 0.2 seconds in C++. It took me a while to crack it though.

      0|
      ParentPermalink
  • tsite 3 years ago+ 1 comment

    Someone else mentioned this already, but I agree that the time given for test case four should be increased a bit. My solution is able to pass all the test cases except for this one. I looked over the top scoring solution on the leaderboard to see how they dealt with test case 4. They used the given timestamps to brute force the seed which imo is a much less interesting way to solve the challenge than what I did.

    My approach involved using the randomly generated numbers themselves to directly determine the seed, without relying on when these numbers were generated. The parameters of the linear congruence generator used by Java are necessary for this, included below:

    unsigned long long m=1L<<48, a=0x5DEECE66D, a1=0xdfe05bcb1365, b=0xB, c=17;

    m is the modulus, the lcg is given by state'=(a*state+b)%m

    a1 is the modular inverse of a, ie state=a1*(state'-b)%m

    c is the number of hidden bits used by the lcg, ie nextInt(n) returns (state'>>c)%n

    And of course, the seed is given by state xor a

    This should help with solving the challenge in a more interesting way. If you still have difficulty, see the spoiler below

    [spoiler]

    http://pastebin.com/rA0vXju5

    Edit:

    Got the fourth test case to work; used lcm(1L<<20,1000) for the second loop instead of 1L<<20

    [/spoiler]

    2|
    Permalink
    • mrussotto 3 years ago+ 1 comment

      Yep, I just solved it the same way. Using the mod 125 part is necessary for that last test case.

      0|
      ParentPermalink
      • kmdism 3 years ago+ 1 comment

        Got every testcase with the exception of 4. Don't follow this recommendation. Could you please elaborate?

        0|
        ParentPermalink
        • mrussotto 3 years ago+ 1 comment

          1000 = 125 * 8.

          By the Chinese remainder theorem, if

          X = Y (mod 1000),

          then X = Y (mod 8)

          and

          X = Y (mod 125)

          You can get all the other testcases by ignoring the second fact and concentrating on the first. To get that last one you need to use the second fact. tsite's idea about lcm(2^20, 1000) is the same (note that lcm(2^20, 1000) = 125 * 2^20).

          0|
          ParentPermalink
          • Medes 1 year ago+ 0 comments

            I think we can use just 1000 * 2^20, can't we?

            However my Python 3 implementation fails with timeout error on testcase 4 even with this optimization :(

            UPD: Rewrote my program to C++ and it successfully passed all cases.

            0|
            ParentPermalink
  • yogesh_suthar 4 years ago+ 0 comments

    I know C,Python 3 I don't know Java and C++ How can i solve this ?

    2|
    Permalink
Load more conversations

Need Help?


View top submissions
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature