Generate a random program in your favorite language

Question

We all heard of testing compilers using randomly generated inputs. Your task is to write a program to generate a valid program (including no undefined behavior) in your favorite language. The generating program language doesn't have to be the same as the generated program language.

Your program will receive an integer as the argument which you can use as seed for your random number generator. The generated programs should be structurally different (given different seeds) not just different variable names or constants.

Examples:

$ ./generate 1
int main() { return 0; }

$ ./generate 2
#include <math.h>
int main() { return (int) pow(4, 3); }

Please include a couple of outputs in your answers.

The shortest solution wins. I will give a small bonus based on the number of votes, so please vote the most creative solutions.

Answer 1

Python → Brainf*ck (185 223 233 255 285 287 303 characters)

Code

import random as r,sys
r.seed(int(sys.argv[1]))
c=list('<>.,+-')+['']
n=9/r.random()
def b():
 global n
 s=''
 while n>0:n-=1;o=r.choice(c);s+=o if o else'[%s]'%b()
 return s
print b()

• 303 → 287 Characters: Removed math.ceil (it's not really necessary).
• 287 → 285 Characters: Switched to an empty string to denote the branch operator.
• 285 → 255 Characters: Condensed the if statement in the while loop.
• 255 → 233 Characters: Implemented JBernardo's suggestions from the comments.
• 233 → 223 Characters: Implemented tjko's suggestion from the comments.
• 223 → 185 Characters: Implemented some whitespace reduction suggestions from the comments.

Examples

$ python generate.py 1
-->,,+-<<-,-<,->[[<<,[.>.<>,,>>>,.<-,+>[[<.-+[.-+.+[-,+<>-.>,++.,,-,.,<<+[+]]]]]]]]
$ python generate.py 2
[<<--+.+++>]
$ python generate.py 3
,.++<<->>[,-,+>+[,-+<-+.<[,-[+[.-,[[<<>[,+.]]]]]]]]

Actually figuring out what the resulting BF programs do is left as an exercise to the reader.

Answer 2

Python -> Piet, 385 345 char

It's possible to generate any Piet program with this. I could've just stopped at random pixels, but I wanted to make "interesting" programs. The function m paints a pixel a color, and recursively steps into each of that pixels neighbors. There are better ways to draw random blobs, but this is tuned to terminate in a reasonable number of steps, so it's good enough for golf. The function R(w,h,n) draws n random blobs onto a (w x h) white image, and prints the result in PPM format.

I'm especially proud of how I generate the colors -- for a random choice of 0 <= c < 20,

`[0,192,255][int(x)]`for x in'0002212220200101121100'[c:c+3]

is the decimal code for a valid color in the Piet palette by way of a single-track Gray code. That is, each color is represented by 3 adjacent bits, and every slice '0003...0'[c:c+3] represents a different color. Since this isn't the full list of 27 words on 3 letters, I really lucked out in finding the Gray code.

from random import*
r=randint
def R(w,h,n):
 M=[6]*h*w
 def m(x,y,c,d):M[y%h*w+x%w]=c;t=r(0,15)*(r(0,d)<2);t&8and m(x+1,y,c,d+1);t&4and m(x-1,y,c,d+1);t&2and m(x,y+1,c,d+1);t&1and m(x,y-1,c,d+1)
 while n:m(r(0,w),r(0,h),r(0,19),0);n-=1
 print"P3 %s %s 255 "%(w,h)+' '.join(`[0,192,255][int(x)]`for c in M for x in'0002212220200101121100'[c:c+3])

Sample output, generated by the command R(30,40,500)

Without the import, I can write it as a proper (semicolon-free) 1-liner, too:

import random
R=(lambda P,I,E,T:lambda w,h,n:E(w,h,I(w,h,n,lambda z,c,d,t:sum((((z,c),)*t*T(0,1)or m((z[0]+a,z[1]+b),c,d+1,T(0,d)>1)for a,b in((0,1),(1,0),(-1,0),(0,-1))),()))))(range,lambda w,h,n,m:dict(sum((m((T(0,w),T(0,h)),T(0,19),0,0)for _ in P(n)),())),lambda w,h,M:"P3 %s %s 255 "%(w,h)+' '.join(' '.join(`(x&1)*255+(x&2)*96`for x in map(int,'0001121110100202212200'[c:c+3]))for c in(M[z]if z in M else 6for z in((x,y)for y in P(h)for x in P(w)))),random.randint)

but it's ridiculously slow (and almost 100 characters longer)... though I'm not entirely sure why (and not terribly inclined to find out).

Answer 3

Python -> Python, 135 chars

import random,sys
random.seed(int(sys.argv[1]))
R=range(9)
print'print 1'+''.join(random.choice('+*')+'%d'%random.choice(R)for x in R)

Generates little random expression evaluations, like this:

> ./genprogram.py 1
print 1+7*2+4*7+0*3*0+6+8
> ./genprogram.py 2
print 1*8+0*6*2*5*1+3*8*4
> ./genprogram.py 3
print 1+4+5*0+7+2*4*4*1*7
> ./genprogram.py 4
print 1+0+1+3*7*1*2+0+8*7

Answer 4

Python -> HQ9+ : 108 chars

import random
def g(): return ''.join([random.choice(['H','Q','9','+']) for x in range(random.randint(1,9))])

Answer 5

PHP, 352 characters

Generates PHP code in PHP.

I decided I didn't care as much about length, but instead wanted an interesting and diverse set of solutions. This is my answer to that.

Code

<?php mt_srand(0+$argv[1]);$r=mt_rand(1,100);$s="\$i=rand(1,$r);";while($r>0){$s.='$i';if(!($r%10))$s.='*=2;';if(!($r%9))$s.='++;';if(!($r%8))$s.='=pow($i,rand(1,$i));';if(!($r%7))$s.='--;';if(!($r%6))$s.='=substr($i,0,2);';if(!($r%5))$s.='/=2;';if(!($r%4))$s.='+=4;';if(!($r%3))$s.='*=-1;';$r-=mt_rand(1,5);}$s.='var_dump($i);';echo"<?php $s
";

Ungolfed

<?php
mt_srand(0+$argv[1]);
$r = mt_rand(1,100);
$s = "\$i=rand(1,$r);";
while ($r > 0)
{
    if (!($r%10)) $s .= '$i*=2;';
    if (!($r%9))  $s .= '$i++;';
    if (!($r%8))  $s .= '$i=pow($i,rand(1,$i));';
    if (!($r%7))  $s .= '$i--;';
    if (!($r%6))  $s .= '$i=substr($i,0,2);';
    if (!($r%5))  $s .= '$i/=2;';
    if (!($r%4))  $s .= '$i+=4;';
    if (!($r%3))  $s .= '$i*=-1;';
    $r -= mt_rand(1,5);
}
$s .= 'var_dump($i);';
echo "<?php $s
";

Example

> php r.php 1
<?php $i=rand(1,58);$i*=-1;$i=pow($i,rand(1,$i));$i=substr($i,0,2);$i+=4;$i*=-1;$i=pow($i,rand(1,$i));$i=substr($i,0,2);$i+=4;$i*=-1;$i*=2;$i/=2;$i+=4;$i/=2;$i*=-1;$i*=2;$i/=2;$i=substr($i,0,2);$i*=-1;var_dump($i);
> php r.php 2
<?php $i=rand(1,57);$i*=-1;$i+=4;$i--;$i=substr($i,0,2);$i*=-1;$i*=-1;$i--;$i+=4;$i/=2;$i++;$i=substr($i,0,2);$i*=-1;$i=pow($i,rand(1,$i));$i+=4;$i--;$i=substr($i,0,2);$i+=4;$i*=-1;$i--;$i+=4;var_dump($i);

Answer 6

scala: 1543 (scala => scala)

I have variables (x, y, z), functions (mul, add, neg, abs), values and balanced parenthesis.

<!--code:language-scala-->
object FormelBauer {
    val fun = List (" mul10 (", " add1 (", " neg (", " abs (")
    val ops = List (" * ", " + ", " - ", " / ")
    def c(maxLen: Int, m: Int) : String = {
        def f()= new StringBuffer (fun (r.nextInt (fun.length)))
        def w()= new StringBuffer ("" + (r.nextInt (180) - 90))
        def v()= new StringBuffer ("" + ('x' + r.nextInt (3)).toChar)
        def o()= new StringBuffer (ops (r.nextInt (ops.length)))
        def g(t: Int, b: Int, d: List [Char]) : StringBuffer ={
            var a = d.filterNot (x => if (b > 0) x == '.' else x == ')')
            if (b > m) a = a.filterNot (_ == 'k')
            if (b > m) a = a.filterNot (_ == 'f')
            if (t > maxLen) a = a.filterNot (_ == '+')
            val elem = r.nextInt (a.length)
            val start = a(elem)
            start match {
                case '.' => new StringBuffer ("")
                case 'f' => f.append(g (t + 1, b + 1, List ('(', '8', 'x')))
                case '(' => new StringBuffer ("(").append   (g (t + 1, b + 1, List ('(', '8', 'x')))
                case '8' => w.append(g (t + 1, b, List ('.', ')', '+')))
                case 'x' => v.append(g (t + 1, b, List ('.', ')', '+')))
                case ')' => new StringBuffer (") ").append  (g (t + 1, b -1, List ('.', ')', '+')))
                case '+' => o.append(g (t + 1, b, List ('f', '(', '8', 'x')))
        }}
        (g (0,0,List('f','(','8','x'))).toString
    }
import util._
  var r : Random = _    
    def main (as: Array [String]) : Unit = {
      val s=as(0).toInt
        r=new Random(s) 
        "xyz".map(c=>println("val "+c+"="+(c+r.nextInt(s))))
        println("""def mul10(i:Int)=10*i
def add1(i:Int)=i+1
def neg(i:Int)= -i
def abs(i:Int)=if(i<0)-i else i
"""+c(45,5))}
}

As you see, it is not very golfed. Because, it will not get me close to the other solutions, but a problem is, that more variation costs more. 3 variables, 4 functions could be easily reduced to two, for example.

Generating some samples:

for i in {1..7} ; do scala FormelBauer $i; echo; done

val x=120
val y=121
val z=122
def mul10(i:Int)=10*i
def add1(i:Int)=i+1
def neg(i:Int)= -i
def abs(i:Int)=if(i<0)-i else i
(y)  / 79

val x=121
val y=121
val z=123
def mul10(i:Int)=10*i
def add1(i:Int)=i+1
def neg(i:Int)= -i
def abs(i:Int)=if(i<0)-i else i
 add1 ((((78 +  neg (z * z) )  / x) ) )  + -23 - ((-83)  * y) 

val x=122
val y=123
val z=122
def mul10(i:Int)=10*i
def add1(i:Int)=i+1
def neg(i:Int)= -i
def abs(i:Int)=if(i<0)-i else i
x / -71 - (y) 

val x=122
val y=124
val z=125
def mul10(i:Int)=10*i
def add1(i:Int)=i+1
def neg(i:Int)= -i
def abs(i:Int)=if(i<0)-i else i
x

val x=122
val y=123
val z=126
def mul10(i:Int)=10*i
def add1(i:Int)=i+1
def neg(i:Int)= -i
def abs(i:Int)=if(i<0)-i else i
-24 + z

val x=121
val y=121
val z=124
def mul10(i:Int)=10*i
def add1(i:Int)=i+1
def neg(i:Int)= -i
def abs(i:Int)=if(i<0)-i else i
 abs (z) 

val x=123
val y=126
val z=126
def mul10(i:Int)=10*i
def add1(i:Int)=i+1
def neg(i:Int)= -i
def abs(i:Int)=if(i<0)-i else i
 add1 (-62 - 30 * (-68)  /  neg (x - 69 + 33 / 45 + x * x)  -  abs (-18 * (y + x)  /  neg (x)  - y)  *  abs ((61) ) )  + (y) 

Testing the longest one:

add1 (-62 - 30 * (-68)  /  neg (x - 69 + 33 / 45 + x * x)  -  abs (-18 * (y + x)  /  neg (x)  - y)  *  abs ((61) ) )  + (y) 

res6: Int = -5425

Answer 7

Perl -> shell : 66 chars

@p=split(':',$ENV{PATH});
@c=`ls @p[@ARGV[0]]`;
print @c[rand($#c)];

Possibly a little off topic, but maybe so.

s153254@helios:/home/s153254/lab$ perl code.p 1
telnet
s153254@helios:/home/s153254/lab$ perl code.p 2
in.rlogind
s153254@helios:/home/s153254/lab$ perl code.p 2
df
s153254@helios:/home/s153254/lab$ perl code.p 3
svenv

Answer 8

Ruby → Brainfuck (110 107 characters)

s="";m=%w:< > . , + -:;rand(99).downto(r=0){s<<(rand(40)==0? (r+=1)&&'[%s':'%s')%m.shuffle[0]};p(s<<']'*r)

Usage

$ ruby bf.rb

Produces an executable brainfuck program.

Sort of a shameless ripoff of ESultanik's, so I will credit him for the idea.

• Changed .zero? to ==0

Answer 9

Javascript -> Brainf*ck: 119 chars

s=prompt();a=["+","-",">","<",".",",","[-]"];i=0;b="";while(i++<s*s){b+=a[Math.floor(((Math.random()*s)%1)*7)]}alert(b)

Sample I/O:

10
.--.+,-><->.<+.[-].->.>[-][-]<+,[-]>><-[-]>,,>>[-].-+<[-]+>,<[-][-]<<[-]<[-]+,+[-][-][-].-[-],[-]>.<<[-]-..<-.->.++,>+-[-],.[-]..+,<-[-].+-[-]
11
,..[-]--,[-].,[-]>[-]->..[-]<,<..>[-]<>++-.[-].,,<[-].<+<[-]>-->[-]+-[-]+>-[-][-]>-,[-]->>-,-..++<+,,-,.,[-]->[-]<,+[-][-]+.,-,>+->.[-],.>..,++,.[-],+[-]-,.,--.--,

The code could definitely be shorter, but some things would, IMHO, make it less interesting. But if someone else comes up with a shorter program, I'll cut down more.

Answer 10

Game Maker Language -> Arduino or Ti84-Basic, 6³ characters

a=argument0;if a mod 2{return("void setup(){Serial.begin(9600);}void loop(){Serial.print"+string(a*random(9))+";delay("+string(floor(random(999)))+")}"}else{return(":Lbl A:Horizontal "+string(a*random(9))+":Goto A")}

Explanation:

a=argument0 Puts the input into variable a

if a mod 2 Basically, half the chance the program will be Arduino, half Ti-Basic 84

The Arduino program outputs random stuff at random intervals, randomly skipping random things.

The Ti-Basic Program draws horizontal lines like crazy.

Also, there is a bonus - the generated programs are already golfed! Not sure if that would be helpful...

Answer 11

Python -> Python, 148 chars

Longer than the other Python entries at the expense of being (subjectively) a little more interesting.

import sys as s,random as r
w,o=s.stdout.write,__builtins__
r.seed(s.argv[1])
w('print\\')
for i in'\n....':n=r.choice(dir(o));o=getattr(o,n);w(i+n)

This prints a deeply nested attribute of a built-in object.

$ python randprog.py 1
print\
round.__setattr__.__delattr__.__init__.__class__

Answer 12

PowerShell, generating PowerShell – 43

In the spirit of Keith's solution:

-join(0.."$input"|%{'-','+'|random;random})

generates random expressions of additions and subtractions:

PS> -join(0..(random 9)|%{'-','+'|random;random 9})
+2-0-0+3-7
PS> -join(0..(random 9)|%{'-','+'|random;random 9})
-7+1+7+1-5+2+8
PS> -join(0..(random 9)|%{'-','+'|random;random 9})
-1+7+7-0-6-0-2
PS> -join(0..(random 9)|%{'-','+'|random;random 9})
+2-6-5+3-2+7
PS> -join(0..(random 9)|%{'-','+'|random;random 9})
-6

Answer 13

Python -> Fractran (117)

import random as r,sys
r.seed(int(sys.argv[1]))
z=r.randint
print','.join(`z(1,99)`+'/'+`z(1,99)`for q in[0]*z(1,99))

Answer 14

JavaScript -> Javascript (44 characters)

alert('alert("'+Math.random()*prompt()+'")')

And with 43 characters, it can execute the generated program instead of displaying it's source:

eval('alert("'+Math.random()*prompt()+'")')

Examples:

Seed: 5
Executed 3 times:

alert("2.335241624386981")
alert("0.4577956395223737")
alert("0.8359265828039497")

Answer 15

Perl -> HQ9+ (42 Characters)

$a="HQ9+";for(1..<>%4){chop$a}print chop$a

Example input

4264532623562346

Output

Q