“Hello World”, randomly!

~by Albert Zakhia

I once read that given infinite time, if a monkey is provided with a typewriter, it is guaranteed that it will eventually type the entire Bible or any other book of your preference.

Googling it, I find it defined more eloquently in Wikipedia under the title ‘Infinite monkey theorem‘ as such:

The infinite monkey theorem states that a monkey hitting keys at random on a typewriter keyboard for an infinite amount of time will almost surely type any given text, such as the complete works of William Shakespeare. In fact, the monkey would almost surely type every possible finite text an infinite number of times. However, the probability that monkeys filling the entire observable universe would type a single complete work, such as Shakespeare’s Hamlet, is so tiny that the chance of it occurring during a period of time hundreds of thousands of orders of magnitude longer than the age of the universe is extremely low (but technically not zero). The theorem can be generalized to state that any sequence of events which has a non-zero probability of happening, at least as long as it hasn’t occurred, will almost certainly eventually occur.

Wikipedia

Lately, a very good friend of mine, with whom I enjoy discussing coding techniques, brought to my attention unfamiliar ways of displaying the infamous “Hello World”. Displaying “hello world” is usually the first program every developer tries when learning a new language.
The code below shows how we can display the said string by the use of a random number generator, in Java. (In case you don’t have java, you can run it by pasting it on https://www.jdoodle.com/online-java-compiler/)

import java.util.Random;
 public class MyClass {
     public static void main(String args[]) {
         System.out.println(randomString(-229985452) + " " + randomString(-147909649));
     }
     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(); 
     }
 }

How does it work? Well let’s see your best guess. Shouldn’t be that hard.
Original post:
http://stackoverflow.com/questions/15182496/why-does-this-code-using-random-strings-print-hello-world

Let’s take it one step further…

First, we will have to move to c-sharp, as I feel more comfortable using it. C# uses different random generation algorithms, so seeds do not necessarily give the same pseudo-sequence.

While in Java, a random seed of -229985452 generates ‘hello’, this same seed in C# (visual studio Version 16.11.8 under framework version 4.8.04084) will return ‘terkc’ (instead of ‘hello’).

But the seed should exist, somewhere within the random pool.. We will find it brute-forcing the random generator.

Before we continue, we need to define our alphabet. Every alphabet would require different implementations.

The given algorithm above squeezes the character space from 256 characters down to 27, which are the 26 alphabet letters (1 for a, 2 for b, 3 for c, …) and a ZERO, as a generic value for the rest. So when the random generator gives a value of 0, it means it is out of alphabetical space and the method exists. Otherwise, the value would be 1 for ‘a’ to 26 for ‘z’.

Our alphabet is defined as follow:

0 –> ‘\0’ End of String
1 –> ‘a’
2 –> ‘b’
26 –> ‘z’
27 –> ‘ ‘ (space)

Alphabet

Great.. Now time to play…

We will create a method to which we will provide some string, it will return the correct seed, if any, that can generate the required string using the given random seed.

        /// <summary>
         /// Given an array of characters, this method will try and find the random seed that can generate the same sequence
         /// </summary>
         /// <param name="searchFor">The char array to search for</param>
         /// <param name="randomSeed">The seed that can generate the same string sequence</param>
         /// <param name="iterations">Number of iterations done</param>
         /// <returns>True, if we find a sequence and 'seed' is usable, false otherwise</returns>
         static bool FindRandomSeedForString(char[] searchFor, out int randomSeed, out long iterations)
         {
             // copy the array into its byte representation
             // the array is offset-ed from the lower case range (0 for end of string, 97 normalized 1 to 26 for 'a' .. something for 'z' and 27 for space)
             // remember, 97 is the ascii code for lower case 'a', 98 for 'b', ...
             // Hence we create our own alphabet mapped as follow:
             //  0 --> '\0' End of String
             //  1 --> 'a'
             //  2 --> 'b'
             // 26 --> 'z'
             // 27 --> ' ' (space)
             byte[] arr = new byte[searchFor.Length + 1]; // add space for eol (End Of Line
             for (int i = 0; i < searchFor.Length; i++)
             {
                 if (searchFor[i] == ' ')
                     arr[i] = 27;
                 else
                     arr[i] = (byte)(char.ToLower(searchFor[i]) - 'a' + 1); // normalizing 97..122 to 1..26
             }
 
             // let us add EOL as a sentinel value
             arr[searchFor.Length] = 0;
             iterations = 0;
 
             // in the below loop, we will brute force the random generator 
             // for all int values and check which seed value will return the correct string
             // given or alphabet
             for (randomSeed = int.MinValue; randomSeed < int.MaxValue; randomSeed++)
             {
                 Random ran = new Random(randomSeed);
 
                 // now we need to check that for the given seed,
                 // we will get the number and sequence of values in our string
                 for (int j = 0; j < arr.Length; j++)
                 {
                     ++iterations;
                     int k = ran.Next(28);// this will return 0 to 27, so EOL = \0, 'a' is 1, 'z' is 26 anf space = 27
                     if (k != arr[j]) break;
                     if (j == searchFor.Length)
                         return true;
                 }
             }
             return false;
         }

We also need to create a method that will return the word related to any given random seed. Remember, in our alphabet, the word is always terminated with a binary 0 ‘\0’.

        /// <summary>
         /// Given any random seed, find the zero terminated string it represents within our alphabet
         /// </summary>
         /// <param name="seed">The random seed to provide</param>
         /// <returns></returns>
         static string RandomString(int seed)
         {
             string s = string.Empty;
             Random ran = new Random(seed);
             while (true)
             {
                 int k = ran.Next(28);
                 if (k == 0) break;
                 if (k == 27)
                     s += ' ';
                 else
                     s += (char)(k + 'a' - 1);
             }
             return s;
         }

Now for the main block, we will provide an array of words, and the system will try, for any word, find the random seed that can generate it. Remember, the longer the word, exponentially is the time it requires to find its seed. So keep words short.

        static void Main(string[] args)
         {
             Stopwatch w = new Stopwatch();
             w.Start();
 
             string[] searchFor = { "h", "he", "hel", "hello", "world", "hello world" };
             int[] randomSeeds = new int[searchFor.Length];
             for (int i = 0; i < searchFor.Length; i++)
             {
                 long t = w.ElapsedMilliseconds;
                 bool found = FindRandomSeedForString(searchFor[i].ToCharArray(), out randomSeeds[i], out long iterations);
                 t = w.ElapsedMilliseconds - t;
                 Console.WriteLine($"{searchFor[i]} {(found ? $"found at seed {randomSeeds[i]} " : $"not found ")}. {t} ms ({iterations * 1000 / t} iterations/sec)");
                 if (found)
                     Console.WriteLine($"{RandomString(randomSeeds[i])}");
             }
 
             Console.WriteLine();
             Console.Write("Finished, press any key to exit...");
             Console.ReadKey();
         }
 

The cherry on the cake

Now that we know how to find random seeds that could generate the strings we need (using our alphabet), why, instead of using two method calls to find ‘hello world’, one for ‘hello’, the other for ‘world’, we do not try and find a single seed for ‘hello world’? Remember, our alphabet allows for space, so we are good.

Well, the bad news is that there is no cherry 🙂 I have ran the code only to find nothing! No random seed under ASP.NET can generate the string ‘hello world”

Of course, there are ways to cut down the running time. We need to improve the algorithms a bit, but what we have is fine for the context of this post.

Anyway, that was a light, amusing way to spend the evening.

Hope you enjoyed it!