Why does this code using random strings print "hello world"?

Asked 2023-09-21 08:08:39 View 849,924

The following print statement would print "hello world". Could anyone explain this?

System.out.println(randomString(-229985452) + " " + randomString(-147909649));

And randomString() looks like this:

public static String randomString(int i)
{
    Random ran = new Random(i);
    StringBuilder sb = new StringBuilder();
    while (true)
    {
        int k = ran.nextInt(27);
        if (k == 0)
            break;

        sb.append((char)('`' + k));
    }

    return sb.toString();
}
  • Well, those particular seeds just so happen to work out perfectly. Random is not truly random, it is pseudorandom. - anyone
  • It works, as others have said, because random isn't. To me, a more interesting question would be did the person that wrote that, brute force it, or is there an easy way to predict what random would generate for the next N values for a given seed. Brute forcing is easy and with modern hardware shouldn't take too long, so that was ceertain a viable way of doing it. Given that it is static, you could even easily distribute the search across a network. - anyone
  • I wonder the purpose of n in for (int n = 0; ; n++). They could use for(;;) or while(true) instead! - anyone
  • In a truly random sequence every possible string will eventually appear. In a high quality pseudo random sequence on can reasonable expect every possible string of length (log_s(N) - n) bits (where N is the number of bits in the PRNGs internal state and n is a small number, lets pick 8 for convenience) to appear in the cycle. This code gets some help from the use of a freely chosen hardcoded start point (the value of the character backtick) which gets almost the whole 8 bits back. - anyone
  • If I were to refactor this, I would – besides refactoring the curly braces – only change the method name to a more descriptive one: fixedAndNotSoRandomString or something... - anyone

Answers

The other answers explain why, but here is how.

Given an instance of Random:

Random r = new Random(-229985452)

The first 6 numbers that r.nextInt(27) generates are:

8
5
12
12
15
0

and the first 6 numbers that r.nextInt(27) generates given Random r = new Random(-147909649) are:

23
15
18
12
4
0

Then just add those numbers to the integer representation of the character ` (which is 96):

8  + 96 = 104 --> h
5  + 96 = 101 --> e
12 + 96 = 108 --> l
12 + 96 = 108 --> l
15 + 96 = 111 --> o

23 + 96 = 119 --> w
15 + 96 = 111 --> o
18 + 96 = 114 --> r
12 + 96 = 108 --> l
4  + 96 = 100 --> d

Answered   2023-09-21 08:08:39

  • Pedantically, new Random(-229985452).nextInt(27) always returns 8. - anyone
  • @rootTraveller For a start, new Random() doesn't return a number at all. - anyone
  • @roottraveller "Random" is a deterministic psuedo-random number generator. If you initialise it with a fixed seed it will produce a fixed sequence of numbers. - anyone
  • Is there a way these seeds are calculated? There must be some logic...or is it just brute force. - anyone
  • @SohitGore Given that Java's default Random isn't cryptographically secure (I'm pretty sure it's a Mersenne Twister, but don't quote me on that), it's probably possible to work backwards from "I want these numbers" to "this is the seed I would use". I've done something similar with the standard C linear congruential generator. - anyone

When an instance of java.util.Random is constructed with a specific seed parameter (in this case -229985452 or -147909649), it follows the random number generation algorithm beginning with that seed value.

Every Random constructed with the same seed will generate the same pattern of numbers every time.

Answered   2023-09-21 08:08:39

  • @Vulcan - the javadoc says that the seed is 48 bits. docs.oracle.com/javase/7/docs/api/java/util/Random.html. And besides, the actual seeds are 32 bit values. - anyone
  • Each element of the random number sequence is taken modulo 27, and there are 6 elements in each of "hello\0" and "world\0". If you assumed a truly random generator, the odds would be 1 in 27^6 (387,420,489) of getting the sequence you were looking for -- so it's pretty impressive but not quite mind-blowing! - anyone
  • @RussellBorogove: But with those odds, and 2^64 possible seeds, there are an expected 47.6 billion seed values that give that sequence. It's just a matter of finding one. - anyone
  • @dan04 -- I wasn't quite willing to make that estimate; depending on the implementation of the PRNG, the size of the seed word might not equal the size of the state, and sequence paths might not be evenly distributed. But still, the odds are definitely good, and if you couldn't find a pair you could try again with different casing ("Hello" "World"), or using 122-k instead of 96+k, or... - anyone
  • @ThorbjørnRavnAndersen The Javadoc specifies that "particular algorithms are specified for the class Random. Java implementations must use all the algorithms shown here for the class Random, for the sake of absolute portability of Java code." - anyone

I'll just leave it here. Whoever has a lot of (CPU) time to spare, feel free to experiment :) Also, if you have mastered some fork-join-fu to make this thing burn all CPU cores (just threads are boring, right?), please share your code. I would greatly appreciate it.

public static void main(String[] args) {
    long time = System.currentTimeMillis();
    generate("stack");
    generate("over");
    generate("flow");
    generate("rulez");

    System.out.println("Took " + (System.currentTimeMillis() - time) + " ms");
}

private static void generate(String goal) {
    long[] seed = generateSeed(goal, Long.MIN_VALUE, Long.MAX_VALUE);
    System.out.println(seed[0]);
    System.out.println(randomString(seed[0], (char) seed[1]));
}

public static long[] generateSeed(String goal, long start, long finish) {
    char[] input = goal.toCharArray();
    char[] pool = new char[input.length];
    label:
    for (long seed = start; seed < finish; seed++) {
        Random random = new Random(seed);

        for (int i = 0; i < input.length; i++)
            pool[i] = (char) random.nextInt(27);

        if (random.nextInt(27) == 0) {
            int base = input[0] - pool[0];
            for (int i = 1; i < input.length; i++) {
                if (input[i] - pool[i] != base)
                    continue label;
            }
            return new long[]{seed, base};
        }

    }

    throw new NoSuchElementException("Sorry :/");
}

public static String randomString(long i, char base) {
    System.out.println("Using base: '" + base + "'");
    Random ran = new Random(i);
    StringBuilder sb = new StringBuilder();
    for (int n = 0; ; n++) {
        int k = ran.nextInt(27);
        if (k == 0)
            break;

        sb.append((char) (base + k));
    }

    return sb.toString();
}

Output:

-9223372036808280701
Using base: 'Z'
stack
-9223372036853943469
Using base: 'b'
over
-9223372036852834412
Using base: 'e'
flow
-9223372036838149518
Using base: 'd'
rulez
Took 7087 ms

Answered   2023-09-21 08:08:39

  • @OneTwoThree nextInt(27) means within the range [0, 26]. - anyone
  • @Vulcan Most seeds are very close to the maximum value, just like if you select random numbers between 1 and 1000, most numbers you end up picking will have three digits. It's not surprising, when you think about it :) - anyone
  • @Vulcan In fact if you do the math you'll see they are about as close to the maximum value as to zero (I suppose the seed is being interpreted as an unsigned in the generation code). But because the number of digits grow only logarithmically with the actual value, the number looks really close when it really isn't. - anyone
  • Great answer. And for bonus points, can you find a seed that will initialize a Random which will produce the sequence of 4 seeds required for initialization of the final randoms? - anyone
  • @Marek: I don't think gods of pseudo random would approve of such behaviour. - anyone

Everyone here did a great job of explaining how the code works and showing how you can construct your own examples, but here's an information theoretical answer showing why we can reasonably expect a solution to exist that the brute force search will eventually find.

The 26 different lower-case letters form our alphabet Σ. To allow generating words of different lengths, we further add a terminator symbol to yield an extended alphabet Σ' := Σ ∪ {⊥}.

Let α be a symbol and X a uniformly distributed random variable over Σ'. The probability of obtaining that symbol, P(X = α), and its information content, I(α), are given by:

P(X = α) = 1/|Σ'| = 1/27

I(α) = -log₂[P(X = α)] = -log₂(1/27) = log₂(27)

For a word ω ∈ Σ* and its ⊥-terminated counterpart ω' := ω · ⊥ ∈ (Σ')*, we have

I(ω) := I(ω') = |ω'| * log₂(27) = (|ω| + 1) * log₂(27)

Since the Pseudorandom Number Generator (PRNG) is initialized with a 32-bit seed, we can expect most words of length up to

λ = floor[32/log₂(27)] - 1 = 5

to be generated by at least one seed. Even if we were to search for a 6-character word, we would still be successful about 41.06% of the time. Not too shabby.

For 7 letters we're looking at closer to 1.52%, but I hadn't realized that before giving it a try:

#include <iostream>
#include <random>
 
int main()
{
    std::mt19937 rng(631647094);
    std::uniform_int_distribution<char> dist('a', 'z' + 1);
 
    char alpha;
    while ((alpha = dist(rng)) != 'z' + 1)
    {
        std::cout << alpha;
    }
}

See the output: http://ideone.com/JRGb3l

Answered   2023-09-21 08:08:39

I wrote a quick program to find these seeds:

import java.lang.*;
import java.util.*;
import java.io.*;

public class RandomWords {
    public static void main (String[] args) {
        Set<String> wordSet = new HashSet<String>();
        String fileName = (args.length > 0 ? args[0] : "/usr/share/dict/words");
        readWordMap(wordSet, fileName);
        System.err.println(wordSet.size() + " words read.");
        findRandomWords(wordSet);
    }

    private static void readWordMap (Set<String> wordSet, String fileName) {
        try {
            BufferedReader reader = new BufferedReader(new FileReader(fileName));
            String line;
            while ((line = reader.readLine()) != null) {
                line = line.trim().toLowerCase();
                if (isLowerAlpha(line)) wordSet.add(line);
            }
        }
        catch (IOException e) {
            System.err.println("Error reading from " + fileName + ": " + e);
        }
    }

    private static boolean isLowerAlpha (String word) {
        char[] c = word.toCharArray();
        for (int i = 0; i < c.length; i++) {
            if (c[i] < 'a' || c[i] > 'z') return false;
        }
        return true;
    }

    private static void findRandomWords (Set<String> wordSet) {
        char[] c = new char[256];
        Random r = new Random();
        for (long seed0 = 0; seed0 >= 0; seed0++) {
            for (int sign = -1; sign <= 1; sign += 2) {
                long seed = seed0 * sign;
                r.setSeed(seed);
                int i;
                for (i = 0; i < c.length; i++) {
                    int n = r.nextInt(27);
                    if (n == 0) break;
                    c[i] = (char)((int)'a' + n - 1);
                }
                String s = new String(c, 0, i);
                if (wordSet.contains(s)) {
                    System.out.println(s + ": " + seed);
                    wordSet.remove(s);
                }
            }
        }
    }
}

I have it running in the background now, but it's already found enough words for a classic pangram:

import java.lang.*;
import java.util.*;

public class RandomWordsTest {
    public static void main (String[] args) {
        long[] a = {-73, -157512326, -112386651, 71425, -104434815,
                    -128911, -88019, -7691161, 1115727};
        for (int i = 0; i < a.length; i++) {
            Random r = new Random(a[i]);
            StringBuilder sb = new StringBuilder();
            int n;
            while ((n = r.nextInt(27)) > 0) sb.append((char)('`' + n));
            System.out.println(sb);
        }
    }
}

(Demo on ideone.)

Ps. -727295876, -128911, -1611659, -235516779.

Answered   2023-09-21 08:08:39

I was intrigued by this, I ran this random word generator on a dictionary word list. Range: Integer.MIN_VALUE to Integer.MAX_VALUE

I got 15131 hits.

int[] arrInt = {-2146926310, -1885533740, -274140519, 
                -2145247212, -1845077092, -2143584283,
                -2147483454, -2138225126, -2147375969};

for(int seed : arrInt){
    System.out.print(randomString(seed) + " ");
}

Prints

the quick browny fox jumps over a lazy dog 

Answered   2023-09-21 08:08:39

  • You made my day man :D I tried it with Long.Min/Max and search for names of my colleagues and only found peter : ( peter 4611686018451441623 peter 24053719 peter -4611686018403334185 peter -9223372036830722089 peter -4611686017906248127 peter 521139777 peter 4611686018948527681 peter -9223372036333636031 peter -4611686017645756173 peter 781631731 peter 4611686019209019635 peter -9223372036073144077 peter -4611686017420317288 peter 1007070616 peter -9223372035847705192 ) - anyone

Most random number generators are, in fact, "pseudo random." They are Linear Congruential Generators, or LCGs (http://en.wikipedia.org/wiki/Linear_congruential_generator)

LCGs are quite predictable given a fixed seed. Basically, use a seed that gives you your first letter, then write an app that continues to generate the next int (char) until you hit the next letter in your target string and write down how many times you had to invoke the LCG. Continue until you've generated each and every letter.

Answered   2023-09-21 08:08:39

As multi-threading is very easy with Java, here is a variant that searches for a seed using all cores available: http://ideone.com/ROhmTA

import java.util.ArrayList;
import java.util.Random;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.ThreadFactory;

public class SeedFinder {

  static class SearchTask implements Callable<Long> {

    private final char[] goal;
    private final long start, step;

    public SearchTask(final String goal, final long offset, final long step) {
      final char[] goalAsArray = goal.toCharArray();
      this.goal = new char[goalAsArray.length + 1];
      System.arraycopy(goalAsArray, 0, this.goal, 0, goalAsArray.length);
      this.start = Long.MIN_VALUE + offset;
      this.step = step;
    }

    @Override
    public Long call() throws Exception {
      final long LIMIT = Long.MAX_VALUE - this.step;
      final Random random = new Random();
      int position, rnd;
      long seed = this.start;

      while ((Thread.interrupted() == false) && (seed < LIMIT)) {
        random.setSeed(seed);
        position = 0;
        rnd = random.nextInt(27);
        while (((rnd == 0) && (this.goal[position] == 0))
                || ((char) ('`' + rnd) == this.goal[position])) {
          ++position;
          if (position == this.goal.length) {
            return seed;
          }
          rnd = random.nextInt(27);
        }
        seed += this.step;
      }

      throw new Exception("No match found");
    }
  }

  public static void main(String[] args) {
    final String GOAL = "hello".toLowerCase();
    final int NUM_CORES = Runtime.getRuntime().availableProcessors();

    final ArrayList<SearchTask> tasks = new ArrayList<>(NUM_CORES);
    for (int i = 0; i < NUM_CORES; ++i) {
      tasks.add(new SearchTask(GOAL, i, NUM_CORES));
    }

    final ExecutorService executor = Executors.newFixedThreadPool(NUM_CORES, new ThreadFactory() {

      @Override
      public Thread newThread(Runnable r) {
        final Thread result = new Thread(r);
        result.setPriority(Thread.MIN_PRIORITY); // make sure we do not block more important tasks
        result.setDaemon(false);
        return result;
      }
    });
    try {
      final Long result = executor.invokeAny(tasks);
      System.out.println("Seed for \"" + GOAL + "\" found: " + result);
    } catch (Exception ex) {
      System.err.println("Calculation failed: " + ex);
    } finally {
      executor.shutdownNow();
    }
  }
}

Answered   2023-09-21 08:08:39

  • To java noob like me, you need to suffix the output number with L and change the argument type to long, i.e. randomString(long i) in order to play around. :) - anyone

Random always return the same sequence. It's used for shuffling arrays and other operations as permutations.

To get different sequences, it's necessary initialize the sequence in some position, called "seed".

The randomSting get the random number in the i position (seed = -229985452) of the "random" sequence. Then uses the ASCII code for the next 27 character in the sequence after the seed position until this value are equal to 0. This return the "hello". The same operation is done for "world".

I think that the code did not work for any other words. The guy that programmed that knows the random sequence very well.

It's very great geek code!

Answered   2023-09-21 08:08:39

  • I doubt if he "knows the Random sequence very well". More likely, he just tried billions of possible seeds until finding one that worked. - anyone
  • @dan04 Real programmers don't merely use the PRNG, they remember the whole period by heart and enumerate values as needed. - anyone
  • "Random always return the same sequence" - put () after Random or show it as a code. Otherwards the sentence is false. - anyone

The principal is the Random Class constructed with the same seed will generate the same pattern of numbers every time.

Answered   2023-09-21 08:08:39

Derived from Denis Tulskiy's answer, this method generates the seed.

public static long generateSeed(String goal, long start, long finish) {
    char[] input = goal.toCharArray();
    char[] pool = new char[input.length];
    label:
        for (long seed = start; seed < finish; seed++) {
            Random random = new Random(seed);

            for (int i = 0; i < input.length; i++)
                pool[i] = (char) (random.nextInt(27)+'`');

            if (random.nextInt(27) == 0) {
                for (int i = 0; i < input.length; i++) {
                    if (input[i] != pool[i])
                        continue label;
                }
                return seed;
            }

        }

    throw new NoSuchElementException("Sorry :/");
}

Answered   2023-09-21 08:08:39

From the Java docs, this is an intentional feature when specifying a seed value for the Random class.

If two instances of Random are created with the same seed, and the same sequence of method calls is made for each, they will generate and return identical sequences of numbers. In order to guarantee this property, particular algorithms are specified for the class Random. Java implementations must use all the algorithms shown here for the class Random, for the sake of absolute portability of Java code.

http://docs.oracle.com/javase/1.4.2/docs/api/java/util/Random.html

Odd though, you would think there are implicit security issues in having predictable 'random' numbers.

Answered   2023-09-21 08:08:39

  • That is why the default constructor of Random "sets the seed of the random number generator to a value very likely to be distinct from any other invocation of this constructor" (javadoc). In the current implementation this is a combination of the current time and a counter. - anyone
  • Indeed. Presumably there are practical use-cases for specifying the initial seed value, then. I guess that's the operating principle of those pseudorandom keyfobs you can get (RSA ones?) - anyone
  • @deed02392 Of course there are practical use-cases for specifying a seed value. If you're simulating data to use some sort of monte carlo approach to solving a problem then it's a good thing to be able to reproduce your results. Setting an initial seed is the easiest way to do that. - anyone

It is about "seed". Same seeds give the same result.

Answered   2023-09-21 08:08:39

Here is a minor improvement for Denis Tulskiy answer. It cuts the time by half

public static long[] generateSeed(String goal, long start, long finish) {
    char[] input = goal.toCharArray();

    int[] dif = new int[input.length - 1];
    for (int i = 1; i < input.length; i++) {
        dif[i - 1] = input[i] - input[i - 1];
    }

    mainLoop:
    for (long seed = start; seed < finish; seed++) {
        Random random = new Random(seed);
        int lastChar = random.nextInt(27);
        int base = input[0] - lastChar;
        for (int d : dif) {
            int nextChar = random.nextInt(27);
            if (nextChar - lastChar != d) {
                continue mainLoop;
            }
            lastChar = nextChar;
        }
        if(random.nextInt(27) == 0){
            return new long[]{seed, base};
        }
    }

    throw new NoSuchElementException("Sorry :/");
}

Answered   2023-09-21 08:08:39

It's all about the input seed. Same seed give the same results all the time. Even you re-run your program again and again it's the same output.

public static void main(String[] args) {

    randomString(-229985452);
    System.out.println("------------");
    randomString(-229985452);

}

private static void randomString(int i) {
    Random ran = new Random(i);
    System.out.println(ran.nextInt());
    System.out.println(ran.nextInt());
    System.out.println(ran.nextInt());
    System.out.println(ran.nextInt());
    System.out.println(ran.nextInt());

}

Output

-755142161
-1073255141
-369383326
1592674620
-1524828502
------------
-755142161
-1073255141
-369383326
1592674620
-1524828502

Answered   2023-09-21 08:08:39