Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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.

share|improve this question
2  
Perfect task for developing genetic algorithms with open-ended evolution. I've always wondered how it might be done. –  mellamokb Jun 21 '11 at 15:03
1  
I think the lack of a fixed specification makes this a bad question. "Structurally different" is open to interpretation, and in some interpretations this is an extremely simple problem. –  Peter Taylor Jun 21 '11 at 15:27
1  
All one really needs to do is golf a program that can generate a random sentence from a given BNF grammar (this is trivial). Then just plug in the grammar for any other programming language and poof: a valid program in that language. This will work for any context-free language (which unfortunately rules out Perl). –  ESultanik Jun 21 '11 at 17:00
2  
main(seed) { return 4; // Chosen by dice roll - Guaranteed to be random } Reference –  Neil Jun 29 '11 at 16:27
1  
Neil: Just to note: Probably everyone here knows xkcd, especially the linked one. They probably also know the Dilbert one on random numbers. And it has no relevance here as it's asking for a program with random structure, not just a random number. –  Joey Jul 4 '11 at 11:36
show 10 more comments

15 Answers

up vote 16 down vote accepted

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.

share|improve this answer
    
you can also use if o: s+=0(NL)else: s+='['+b()+']' –  Alexandru Jun 21 '11 at 17:02
    
@Alexandru: Thanks! I missed that. Your code didn't seem to work exactly, but it helped me get it shorter. –  ESultanik Jun 21 '11 at 17:51
2  
Does this somehow mean Brainfuck is your favorite language? –  zneak Jun 22 '11 at 2:49
1  
Not that this is a problem, but the outputted code will likely cause an infinite loop. –  Peter Olson Jun 22 '11 at 16:20
5  
@Peter, true, but avoiding that using this method of random generation is likely equivalent to solving the Halting Problem! –  ESultanik Jun 22 '11 at 16:33
show 14 more comments

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)

random Piet program

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).

share|improve this answer
add comment

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
share|improve this answer
add comment

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);
share|improve this answer
2  
Could you please include an output example? –  Alexandru Jun 21 '11 at 15:58
add comment

Python -> HQ9+ : 108 chars

import random
def g(): return ''.join([random.choice(['H','Q','9','+']) for x in range(random.randint(1,9))])
share|improve this answer
add comment

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

share|improve this answer
add comment

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


share|improve this answer
add comment

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
share|improve this answer
add comment

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.

share|improve this answer
add comment

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))
share|improve this answer
add comment

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__
share|improve this answer
add comment

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
share|improve this answer
add comment

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")
share|improve this answer
    
Where's the seed? –  Doorknob Dec 5 '13 at 3:13
add comment

Perl -> HQ9+ (42 Characters)

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

Example input

4264532623562346

Output

Q
share|improve this answer
add comment

Game Maker Language -> Arduino or Ti84-Basic, 63 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...

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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