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).
Do quines but then altering the code a litte bit count? – facepalm42 – 2019-07-23T06:37:50.963
2Perfect task for developing genetic algorithms with open-ended evolution. I've always wondered how it might be done. – mellamokb – 2011-06-21T15:03:56.393
1I 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 – 2011-06-21T15:27:14.933
@Peter: What interpretations of 'structurally different' do you see? For example,
return 1 + (seed times) + 1
is according to rules. – Alexandru – 2011-06-21T15:32:44.507If rnd(seed) mod 2 == 0 then ';' else ''
would seem to be a valid answer. The output is Golfscript. – Peter Taylor – 2011-06-21T15:35:05.507Not necessarily. You get the same answer for different seeds (2, 4, 6). Your set of possible programs is of size 2, while I specifically forbid that. – Alexandru – 2011-06-21T15:37:29.993
Where? The only restriction on the way the program depends on the seed is "The generated programs should be structurally different (given different seeds)" - which can be interpreted either as that no two seeds can give isomorphic abstract syntax trees (likely to be impractical) or that at least two seeds give non-isomorphic ASTs. – Peter Taylor – 2011-06-21T16:08:41.433
The idea was not to choose between a small set of predefined programs as per your suggestion. I understand that it is possible to get unintentional collisions, so I will not disqualify such programs. The spirit of the question is meta-programming. You are welcome to improve the question or provide some other suggestions. – Alexandru – 2011-06-21T16:16:38.243
@PeterTaylor let us continue this discussion in chat
– Alexandru – 2011-06-21T16:16:54.047Seems like this would make a better code-challenge than code-golf. – mellamokb – 2011-06-21T16:21:20.927
1All 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 – 2011-06-21T17:00:19.943
@ESultanik: Most languages, on the semantic level, are not context-free. The question says "valid program (including no undefined behavior)". Ensuring that variables are declared before use, that subscripts are in range, etc. goes beyond the definition of a context-free grammar. – Joey Adams – 2011-06-21T23:10:31.013
@Joey: True. I guess the method I described would just produce programs that have correct syntax. – ESultanik – 2011-06-22T00:21:15.550
2
main(seed) { return 4; // Chosen by dice roll - Guaranteed to be random }
Reference – Neil – 2011-06-29T16:27:09.8531Neil: 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 – 2011-07-04T11:36:02.057
Target language must be Turing-complete? – Ming-Tang – 2011-07-20T03:56:45.717