35
\$\begingroup\$

The infinite monkey theorem states that, given infinite time, a machine sending an endless stream of random characters will always type any given text.

That sounds to me like a great idea for a challenge.

Process

In order to monkey-ize a string A, the following steps should be taken:

  1. Take an empty string. We will call this string B.
  2. Pick a uniformly random printable ASCII character (characters in the range 0x20 to 0x7E) and add that character to B.
  3. If A is a substring of B, B is our monkey-ized string. Otherwise, repeat step 2 until A is a substring of B.

This process is only an example, easier methods may exist depending on your language. You do not need to follow this method exactly, as long as the same distribution of outputs is achieved.

The challenge

Write a program or function that, given a non-empty string in any reasonable format, returns a monkey-ized version of that string.

Your program only has to practically work for inputs of length 3 or less. For longer inputs, it is allowed to terminate early with or without outputting anything.

Example

Unfortunately, it's kind of hard to create examples for this question due to the random nature of it and the large outputs.

However, I can supply a single example for the input hi, on Hastebin.

Scoring

Since this is , the submission with the fewest bytes wins.

\$\endgroup\$
  • \$\begingroup\$ Sandbox \$\endgroup\$ – LyricLy Nov 5 '17 at 22:38
  • 11
    \$\begingroup\$ Do we need to follow the described procedure to produce the output? If yes, that's an unobservable requirement, which is problematic. If not, we can generate B directly by prepending a non-negative number n of random characters to A. The only real problem then is to know the distribution of n (I bet on a geometric distribution) \$\endgroup\$ – Luis Mendo Nov 5 '17 at 23:24
  • 1
    \$\begingroup\$ @seshoumara You may not. \$\endgroup\$ – LyricLy Nov 6 '17 at 8:03
  • 7
    \$\begingroup\$ @LuisMendo I thought along these lines, and it's actually not easy to generate the prefix directly. It can't contain the target string, including crossing the boundary where it meets the appended string. And the distribution of prefix lengths depends not just on the length of the target string, but its structure as well. \$\endgroup\$ – xnor Nov 6 '17 at 9:03
  • 10
    \$\begingroup\$ Some of the solution computer programs below, such as .W!}zH+ZOrd\k, look a lot like what a monkey has typed. \$\endgroup\$ – Jeppe Stig Nielsen Nov 7 '17 at 22:46

38 Answers 38

1
\$\begingroup\$

Excel VBA, 84 bytes

Dim b
Sub m(a)
b=b &Chr(Int(113*Rnd+14))
If InStr(1,b,a)Then [A1]=b Else m a
End Sub

It's a straightforward implementation. Output is to cell A1 in the active sheet

\$\endgroup\$
1
\$\begingroup\$

Jelly, 17 bytes

³ẇ®¬
ḟµ;©ØṖX¤ø¢¿Ḋ

Try it online!

Explanation

³ẇ®¬            First link
³               Program input...
 ẇ              ...is a contiguous sublist of...
  ®             ...the register?
   ¬            Logical NOT

ḟµ;©ØṖX¤ø¢¿Ḋ    Main link
ḟ               Filter: With only one input this returns the empty list. Note ⁸ doesn't work here.
 µ              New monadic chain
    ØṖX¤        Random (X) element from printable ASCII (ØṖ).
  ;             Concatenate with the above
   ©            Copy the result of the concatenation with the above to check if program input is a sublist.
        ø       New niladic chain.
         ¢      Calls first link.
          ¿     Repeat the monadic chain until the first link returns false.
           Ḋ    Removes the first element of the result. 
                For some reason (???) the integer 0 is always at the beginning of the result which needs to be removed.

Tested with one and two character inputs (two character sometimes takes a long time or seems to stall) but should work in theory for any length input.

The recursive solution I came up with below is slightly longer.

Jelly, 19 bytes

³ẇ®¬
;©ØṖX¤ßµ¢¡
ḟ`Ç

Try it online!

\$\endgroup\$
1
\$\begingroup\$

PowerShell, 55 73 bytes

+18 thanks to mazzy bringing it up to spec

for(;$args-cne-join($b+=[char](32..126|random))[-"$args".Length..-1]){}$b

Try it online!

First, it picks randomly an int from the printable range, casts that to a character, and appends it to our accumulator string. The monkeys will always form the word with the last character so keeps going until the ending of our generated string is the target word. So with that fact, it then compares the last n characters joined into a string (via reserve indexing) to the target.

\$\endgroup\$
1
\$\begingroup\$

J, 38 33 30 29 bytes

-9 bytes thanks to FrownyFrog

(],a.{~32+?@95}.~1#.E.)^:_&''

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ (],a.{~32+?@95}.~1 e.E.)^:_&'' \$\endgroup\$ – FrownyFrog Apr 16 at 15:27
  • \$\begingroup\$ Nice. I didn't know that '' -: 99 + '' \$\endgroup\$ – Jonah Apr 16 at 16:08
  • 1
    \$\begingroup\$ 1 e.E.-> 1#.E. \$\endgroup\$ – FrownyFrog Apr 19 at 13:41
0
\$\begingroup\$

JavaScript 91 bytes

for(b="",a=prompt();b.search(a)<1;b+=String.fromCharCode(~~(Math.random()*95+32)));alert(b)
\$\endgroup\$
0
\$\begingroup\$

Noether, 24 bytes

I~a""~b1(b94R32+BP+~ba/)

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Perl 6, 52 bytes

{("",*~(' '..'~').roll...*).grep(*.contains($_))[0]}

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Emacs Lisp, 113 bytes

(lambda(a)(let((case-fold-search)(b""))(while(not(string-match a b))(setq b(concat b(string(+(random 95)32)))))))

Try it online!

Try-it-online version has an additional byte for printing purposes.

(case-fold-search) assures string-match proper casing, it can be omitted depending on your Emacs configurations (18 bytes).

Better readable version:

((lambda (a)
    (let ((case-fold-search) (b ""))
      (while (not (string-match a b))
    (setq b (concat b (string (+ (random 95) 32)))))
      )))
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.