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

Question

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();
}

Monacid

Well, those particular seeds just so happen to work out perfectly. Random is not truly random, it is pseudorandom. – Unlash

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. – Stickney

I wonder the purpose of n in for (int n = 0; ; n++). They could use for(;;) or while(true) instead! – Vday

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. – Metritis

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... – Settles

Answer 1

When java.util.Random is instantiated 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.

Iorgo

Was this something the people who designed Java intentionally did (as an Easter egg?) It's just a bit mind-blowing that you could possibly product the Hello, world String, which just happens to be the most favourite string in any programming languages. – Asexual

@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. – Crystallization

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! – Brit

@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. – Bushwhacker

@Bushwhacker -- 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... – Brit

@OneTwoThree It's almost always very important that a random number generator can be predictable when needed, as it's very hard to test things otherwise, as running the same code twice can produce different results. Using seeds in PRNGs means you can use a specific seed when testing (or at least report the seed so a result can be reproduced), and then later you can use a seed which will change - e.g. new Random() uses a seed taken from the current time. – Uppsala

Note that the javadoc does not specify the exact details of the implementation. Hence you cannot rely on this being portable across JVM implementations. – Fishery

@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." – Iorgo

So in gambling online games, if we know exactly what the seed is, then we could probably predict the result right? – Sistrunk

@AnNguyen only if they use this specific random number generator, which they are unlikely to use. – Daviddavida

Answer 2

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

Vday

Pedantically, new Random(-229985452).nextInt(27) always returns 8. – Radmen

@immibis why? i mean Random() should return random number every time, not a fix ordered number set? – Pannonia

@rootTraveller For a start, new Random() doesn't return a number at all. – Radmen

@Pannonia "Random" is a deterministic psuedo-random number generator. If you initialise it with a fixed seed it will produce a fixed sequence of numbers. – Acicular

Is there a way these seeds are calculated? There must be some logic...or is it just brute force. – Deck

@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. – Peseta

Answer 3

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

Atwekk

Answer 4

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.

Trantham

Answer 5

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 

Conception

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 ) – Undistinguished

Answer 6

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.

Dissuasive

Answer 7

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();
    }
  }
}

Rumal

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. :) – Cletis

Answer 8

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!

Landan

I doubt if he "knows the Random sequence very well". More likely, he just tried billions of possible seeds until finding one that worked. – Bushwhacker

@Bushwhacker Real programmers don't merely use the PRNG, they remember the whole period by heart and enumerate values as needed. – Blackboard

"Random always return the same sequence" - put () after Random or show it as a code. Otherwards the sentence is false. – Thunder

Answer 9

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

Domeniga

Answer 10

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 :/");
}

Asben

Answer 11

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.

Intolerable

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. – Vida

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?) – Intolerable

@Intolerable 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. – Cariotta

Answer 12

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

Technics

Answer 13

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 :/");
}

Phira

Answer 14

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

Sherronsherry