Why does this code using random strings print "hello world"?
JavaStringRandomJava Problem Overview
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();
}
Java Solutions
Solution 1 - Java
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
Solution 2 - Java
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.
Solution 3 - Java
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
Solution 4 - Java
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
Solution 5 - Java
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);
}
}
}
Ps. -727295876, -128911, -1611659, -235516779.
Solution 6 - Java
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
Solution 7 - Java
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.
Solution 8 - Java
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();
}
}
}
Solution 9 - Java
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!
Solution 10 - Java
The principal is the Random Class constructed with the same seed will generate the same pattern of numbers every time.
Solution 11 - Java
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 :/");
}
Solution 12 - Java
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.
Solution 13 - Java
It is about "seed". Same seeds give the same result.
Solution 14 - Java
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 :/");
}
Solution 15 - Java
> 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