"Lo siento, joven, ¡pero son las tortugas hasta el fondo!"

21

Ejecutar un sistema Lindenmayer

Un sistema Lindenmayer (o sistema L) está relacionado con los sistemas Thue y Post , y se utiliza en el modelado botánico y la generación fractal .

Un sistema L se describe mediante la reescritura de cadenas donde un símbolo del alfabeto de símbolos se asigna a una secuencia de símbolos de reemplazo . Una colección de estas asignaciones constituye el sistema L propiamente dicho.

El método de salida gráfica ideado por Prusinkiewicz interpreta la secuencia resultante después de que las asignaciones se hayan aplicado a una secuencia inicial para un número específico de iteraciones , como comandos de Dibujo de tortuga: adelante, atrás, izquierda, derecha, ese tipo de cosas. Esto puede requerir un código adicional para controlar la escala del dibujo, ya que diferentes recuentos de iteraciones pueden producir imágenes de tamaños drásticamente diferentes.

Su tarea es ejecutar un sistema L en la menor cantidad de caracteres. Su programa debe ser capaz de representar tanto la Curva del Dragón como los Tallos de Ramificación desde la página de Wikipedia proporcionando la entrada adecuada (archivo, línea de comando, pero externa a la fuente, por favor).

Tallos ramificados Curva del dragón

Este es el código de golf.

Editar: Aquí hay algunos ejemplos que he publicado en la ciudad. responda a SO / rotate-to-north { Donde descubrí por primera vez el sistema L } , responda a SO / how-to-program-a-fractal , responda a SO / recursion-in-postscript , discusión de comp.lang.postscript / recital , postscript l-system collection , codegolf.SE/draw-a-sierpinski-triangle {origen de la competencia entre yo y thomasW} .

luser droog
fuente
Se saltó la caja de arena. Esto parece relativamente sencillo y debería ser divertido.
luser droog
Por cierto, ¿alguien sabe el origen de la cita anterior? Escuché a William James y escuché a Faraday.
luser droog
1
Wikipedia dice que el origen está en disputa, la mejor suposición es Bertrand Russel.
ugoren
ITYM Bertrand Russell .
Paul R
1
¿Hay algún límite en el tamaño del alfabeto, el número de reglas, el número de rondas o las posibles reglas (visualización) (dibuje una línea recta, empuje / posición de posición / ángulo, gire cuántos grados, etc.) Si solo necesitamos dibujar esos dos necesitaríamos empujar y saltar, dibujar líneas rectas y poder girar 45 grados en ambas direcciones, solo dos reglas y un alfabeto de tamaño 4.
shiona

Respuestas:

31

Mathematica 200 198 188 171 168

Espacios añadidos para mayor claridad:

f[i_, b_, h_, j_, r_, n_] :=
 (a = h; p = j; s = k = {}; t = Flatten;
  (Switch[#,
      6, s = {a, p, s},
      8, {a, p, s} = s,
      _C, k = {k, Line@{p, p += {Cos@a, Sin@a}}}];
     If[# < 9, a += I^# b ]) & /@ t@Nest[# /. r &, i, n];
  Graphics@t@k)

Dónde:

i: estado inicial;
b: ángulo de rotación
h: ángulo inicial
j: posición inicial
r: reglas de producción
n: iteraciones

Gramática de reglas de producción:

2 = girar a la izquierda (-);
4 = girar a la derecha (+);
6 = Empujar y girar a la izquierda ("[");
8 = Pop y girar a la derecha ("]");
C [i] = Dibujar (Cualquier número de símbolos)
Cualquier otro símbolo = No hacer nada, solo úselo para producir el siguiente estado (Cualquier número de símbolos)

La secuencia {2,4,6,8} está ahí porque estoy usando I^n( I= unidad imaginaria) para hacer turnos.

Ejemplos:

f[{C[1], X}, Pi/2, 0, {0, 0}, {X -> {X, 4, Y, C[1]}, Y -> {C[1], X, 2, Y}}, 10]

Gráficos de Mathematica

f[{C@1}, Pi/2, 0, {0,0}, {C@1->{C@1, 2, C@1, 4, C@1, 4, C@1, 2, C@1}}, 6]

Gráficos de Mathematica

f[{C[1]}, Pi/4, Pi/2, {0, 0}, {C[2] -> {C[2], C[2]}, C[1] -> {C[2], 6, C[1], 8, C[1]}}, 10]

Gráficos de Mathematica

f[{C[1]}, Pi/3, 0, {0, 0}, {C@1 -> {C@2, 4, C@1, 4, C@2}, C@2 -> {C@1, 2, C@2, 2, C@1}}, 10]

Gráficos de Mathematica

f[{X},5/36 Pi, Pi/3, {0,0},{X->{C@1, 4, 6, 6, X, 8, 2, X, 8, 2, C@1, 6, 2, C@1, X, 8, 4, X},
                            C@1->{C@1, C@1}}, 6]

Gráficos de Mathematica

Dr. belisario
fuente
Basta con modificar Graphics@kpor Graphics@Flatten@ksi va a utilizar muchas iteraciones. De lo contrario, un límite de recursión lo morderá y su sesión de MMA se cancelará.
Dr. belisarius
Mi método de macroexpansión tuvo un problema similar con iteraciones más altas. Las cuerdas se vuelven enormes. Pero la solución no era no para aplanar. :)
luser droog
2
+1 muy agradable de hecho;) Podría ser una buena demostración. ¿Los envías?
Vitaliy Kaurov
@VitaliyKaurov Nope, pero siéntete libre de usarlo si crees que vale la pena el esfuerzo
Dr. belisarius
3
@belisarius demonstrations.wolfram.com/GraphicalLSystems
Vitaliy Kaurov
9

Python, 369 294

No soy un ganador, pero publicaré lo que he intentado de todos modos.

from turtle import*
I=open('l').read().split()
s,S,p=I[0],'',[]
for j in range(8):
    for i in s:S+=eval('{'+I[1]+'}')[i]
    s,S=S,''
for k in s:
    if k=='[':p+=[heading(),pos()];continue
    if k==']':pu();goto(p.pop());seth(p.pop());pd();continue
    try:{'f':fd,'F':fd,'+':rt,'-':lt}[k](5)
    except:pass

No es bueno jugando al golf en Python ... Tal vez alguien más pueda hacerlo.

Entrada

La entrada es de un archivo externo llamado "l" (sin extensión), con el siguiente formato:
Línea 1 : Estado inicial (Axiom)
Línea 2 : Reglas separadas por comas

Símbolos
f y F: avance
+: gire a la derecha 5 grados
-: gire a la izquierda 5 grados
[: guarde la posición y el encabezado
]: posición y encabezado pop La
función de dibujo ignora otros símbolos.

Reglas
Una regla tiene el formato "predecessor":"successor(s)"
Tenga en cuenta que las comillas son necesarias, ya sean simples o dobles.
predecessordebe ser un solo personaje.
Además, no hay constantes implícitas: debe especificar explícitamente una regla de no cambio para ellas.

Ejemplos

Tallos ramificados

------------------f
'-':'-','+':'+','[':'[',']':']','F':'FF','f':'F[+++++++++f]---------f'

Salida

Tenga en cuenta que la fuente se modifica para sacar esto puesto SOLO PARA ESCALAR ABAJO EL GRÁFICO AL ÁREA VISIBLE. La consola también se usa para ocultar la "tortuga".

Curva del dragón

fx
'-':'-','+':'+','[':'[',']':']','f':'f','x':'x++++++++++++++++++yf','y':'fx------------------y'

Salida

De nuevo, la consola se utiliza para ocultar la "tortuga".

Triángulo Sierpinski

f------------------------F------------------------F
'-':'-','+':'+','[':'[',']':']','f':'f------------------------F++++++++++++++++++++++++f++++++++++++++++++++++++F------------------------f','F':'FF'



Generaciones de salida reducidas a 5 aquí.

TwiNight
fuente
3
Usted puede obtener un ahorro decente (lo hago 32 caracteres) mediante la eliminación de las funciones f, r, l; agregando un parámetro ficticio a oy c; y luego cambiando el pseudo-cambio a{'f':fd,'F':fd,'+':rt,'-':lt,'[':o,']':c}[k](5)
Peter Taylor
También puede hacer en línea g, y creo oy cvalen la eliminación de la línea ifdeclaraciones (más barato que la globaldeclaración)
Peter Taylor
@PeterTaylor buen trabajo. Tenía la intuición de que algunas de esas funciones podrían estar alineadas, pero no sabía lo suficiente de Python para sugerirlo de manera articulada.
luser droog
1
@luserdroog, tampoco conozco Python: acabo de hacer prueba y error para ver qué funcionó, es decir, algunas de las cosas que intenté (por ejemplo, usar lambdas para oy cdirectamente en el pseudointerruptor) dieron errores de sintaxis, pero otras no t.
Peter Taylor
Consejos para seguir jugando al golf: 1. Cambie el formato de entrada: requiera llaves alrededor de las reglas y separe el axioma de las reglas por un espacio (no una nueva línea). 2. Leer de la entrada estándar: s,R,*p=input().split(). 3. Genere el valor final de sby exec('s="".join(map(eval(R).get,s));'*8). 4. Dejar de lado continue. 5. Sangría solo 1 espacio. 6. Ahorre espacio después ifde cambiar los lados de la prueba. 7. Ponga k:intla dict(primera entrada) y luego no la necesita except: try:. (Obtengo 215 caracteres.)
Restablece a Monica el
7

Javascript (179 bytes)

No estoy completamente seguro de que esto califique, ya que el objeto de reglas hace todo el dibujo real.

Demostración (Dragón, animación):
- Ampliado: http://jsfiddle.net/SVkMR/9/show/light
- Con Código: http://jsfiddle.net/SVkMR/9/

Minified:

function L(c,r,n){o=(function g(d,s,o,i){for(o=i='';a=d&&s[i++];)o+=r.r[a]?g(d-1,r.r[a]):a;return o||s;})(n,r.r[r.s]);(function z(i){r[s=o[i]]&&r[s](c)||setTimeout(z,10,i+1)})(0)}

Legible (ish):

function L(c,r,n){
    o=(function g(d,s,o,i){
        for(o=i='';a=d&&s[i++];)o+=r.r[a]?g(d-1,r.r[a]):o+=a
        return o||s
    })(n,r.r[r.s]);

    (function p(i){
        r[s=o[i]]&&r[s](c)||setTimeout(p,10,i+1)
    })(0)
}

Entrada:

var sierspinski = {
    r:{'A':'B-A-B','B':'A+B+A'},
    '+':function(c){c.rotate(-this.a);c.rotate(this.a-=Math.PI/3)},
    '-':function(c){c.rotate(-this.a);c.rotate(this.a+=Math.PI/3)},
    'A':function(c){c.beginPath();c.moveTo(0,0);c.translate(this.m,0);c.lineTo(0,0);c.stroke()},
    'B':function(c){this['A'](c)},
    s:'A',
    a:0,
    m:1
};

var koch = {
    r: {'F':'F+F-F-F+F'},
    '+':function(c){c.rotate(-this.a);c.rotate(this.a-=Math.PI/2)},
    '-':function(c){c.rotate(-this.a);c.rotate(this.a+=Math.PI/2)},
    'F':function(c){c.beginPath();c.moveTo(0,0);c.translate(this.m,0);c.lineTo(0,0);c.stroke()},
    s:'F',
    a:0,
    m:2
};
var dragon = {
    r: {'X':'X+YF','Y':'FX-Y'},
    '+':function(c){c.rotate(-this.a);c.rotate(this.a-=Math.PI/2)},
    '-':function(c){c.rotate(-this.a);c.rotate(this.a+=Math.PI/2)},
    'F':function(c){c.beginPath();c.moveTo(0,0);c.translate(this.m,0);c.lineTo(0,0);c.stroke()},
    s:'X',
    a:0,
    m:5
};

var algae = {
    r: {'A':'B[A]A','B':'BB'},
    '[':function(c){c.save();c.rotate(Math.PI/4);},  // save/restore will push/pop current state of context. 
    ']':function(c){c.restore();c.rotate(-Math.PI/4);},
    'A':function(c){c.beginPath();c.moveTo(0,0);c.translate(this.m,0);c.lineTo(0,0);c.stroke()},
    'B':function(c){this['A'](c);},
    s:'A',
    a:-Math.PI/2,
    m:1
};

var tree = {
    r:{'X':'F-[[X]+X]+F[+FX]-X','F':'FF'},
    '+':function(c){c.rotate(-this.a);c.rotate(this.a+=Math.PI/180*25)},
    '-':function(c){c.rotate(-this.a);c.rotate(this.a-=Math.PI/180*25)},
    '[':function(c){c.save();},
    ']':function(c){c.restore();},
    'F':function(c){c.beginPath();c.moveTo(0,0);c.translate(this.m,0);c.lineTo(0,0);c.stroke()},
    s:'X',
    a:-Math.PI/180*25,
    m:5
};

Uso:

var ctx = document.getElementById('l').getContext('2d'); // grab context
ctx.translate(299.5,199.5); // start drawing from center, fractional pixels because the canvas draws lines centered on the x/y coord specified
L(ctx, dragon, 8); // pass in context, rules object, and recursion cap

Bono: Golden Spiral http://jsfiddle.net/SVkMR/35/show/light/

var golden = {
    r:{'A':'FT[TT]A','T':'+F'},
    'F':function(c){c.beginPath();c.moveTo(0,0);c.translate(this.m,0);c.lineTo(0,0);c.stroke()},
    '[':function(c){c.save();},
    ']':function(c){
        c.restore();

        c.beginPath();
        c.arc(0,-this.m,this.m,Math.PI/2,Math.PI);
        c.stroke();

        this.m+=this.d;this.d=this.m-this.d
    },
    '+':function(c){c.rotate(-Math.PI/2);},
    s:'A',
    a:-Math.PI/2,
    m:1,
    d:0
};
Shmiddty
fuente
Creo que la animación compensa con creces cualquier libertad con las reglas. ¡Buen trabajo! +1
luser droog
:) ¡Cosas divertidas! .
Shmiddty
5

Posdata 264 298 295 255

Aquí está mi intento de hacerlo de manera diferente. En lugar de la macroexpansión que utilizo habitualmente, esta comprueba el tamaño de la pila de ejecución para vincular la recursividad. Si se supera el límite, deja de examinar el procedimiento de forma recursiva e intenta interpretar los comandos de tortuga (y descarta lo pop popcontrario). Una ventaja de este método es que no requiere enormes cantidades de memoria. Una desventaja es que el control de recursión es bastante torpe, ya que el tamaño de la pila crece en más de 1 de un nivel de recursión al siguiente.

Editar: +34 caracteres para ramificación.
Editar: -3 caracteres. Rediseñado para usar la pila de operandos para el control de recursividad. Esto hace que el sistema básico sea mucho más simple. Pero los paréntesis necesitan una pila independiente, así que puse la posición guardada en la pila del diccionario y casi pagué todos los ahorros.

Además, rediseñado para usar cadenas y enteros en lugar de matrices y nombres.

Editar: -40 caracteres. Se agregaron dos procedimientos para llamar a los nombres del sistema por número (parece que no puedo hacer que funcionen los tokens binarios en bruto . Pero este modismo funciona para mí).

/*{<920>dup 1 4 3 roll put cvx exec}def/${//* 73
*}def[/T[48{}49{}43{A<88>$}45{A<6e88>$}70{R
0<85>$}91{<1e39>$[/.[<286827>$]cvx>><0d0d>$}93{.<9c6b1e39390d>$}>>/S{dup
B eq{T<0d3e>${<643f>$}<4939>$}{exch{<643e>$ 1 add S}73 *}85 * 1 sub}>><0d6b>$
0 S<a7>$

Binario semi-comentado.

/*{<920>dup 1 4 3 roll put cvx exec}def/${//* 73 *}def %73=forall
[/T[70{R 0<85>$}48{}49{} %<85>=rlineto
43{A<88>$}45{A<6e88>$} %<88>=rotate <6e>=neg
91{<1e39>$ %<1e>=currentdict <39>=end
    [/.[<286827>$]cvx>> %<28>=currentpoint <68>=matrix <27>=currentmatrix
        <0d0d>$} %<0d>=begin
93{.<9c6b1e39390d>$}>> %<9c>=setmatrix <6b>=moveto
/S{dup B eq{T<0d3e>${<643f>$}<4939>$} %<3e>=exch <64>=load <3f>=exec <49>=forall
{exch{<643e>$ 1 add S}73 *}85 * 1 sub}>>
<0d6b>$ 0 S<a7>$  % 85=ifelse <a7>=stroke

Un- "binario".

[/T[70{R 0 rlineto}48{}49{}43{A rotate}45{A neg rotate}91{currentdict
end[/.[currentpoint matrix currentmatrix]cvx>>begin begin}93{. setmatrix
moveto currentdict end end begin}>>/S{dup B eq{T begin exch{load exec}forall
end}{exch{load exch 1 add S}forall}ifelse 1 sub }>>begin moveto 0 S stroke

Requiere que el sistema L se defina en un diccionario en el dictstack, con la cadena inicial y la posición inicial de la tortuga en la pila de operandos (antepuesta a la fuente, por ejemplo gs dragon.sys lsys.ps).

Curva del Dragón

%!
[                     %begin dictionary construction
    % productions are described by integer-key/string-value pairs
    48(0+1F) %0       %ascii code for '0' defined as the string "0+1F"
    49(F0-1) %1       %  "     "   "  '1'   "     "   "    "    "F0-1"
    43(+) %+          %  "     "   "  '+' defined as itself
    45(-) %-          %  "     "   "  '-'   "     "   "
    70(F) %F          %  "     "   "  'F'   "     "   "
    % parameters
    /A 90 %angle
    /R 2  %radius
    /B 10 %maximum recursion-level
>>begin  % L-system dictionary on top of dictstack
(F0)     % initial string on stack
300 400  % starting position on stack

Tallos ramificados.

[
    48(F[+0]-0) %0
    49(F0-1) %1
    43(+) %+
    45(-) %-
    70(FF) %F
    91([) %[
    93(]) %]
    /A 45 %angle
    /R 5  %radius
    /B 3 %recursion
>>begin
(++0)     % initial string
300 400  % starting position

Ungolfed y comentó.

[                                 % begin dictionary construction
    /T[                           % /T is the Turtle dictionary containing
                                  % integer-key/procedure-value pairs
                                  % keyed to ascii values
        70{R 0 rlineto}        %F  
        48{}                   %0
        49{}                   %1  
        43{A rotate}           %+  
        45{A neg rotate}       %-  

          % For brackets, create a dictionary containing a single procedure '.' (dot)
          % which holds a saved matrix (orientation+size) and currentpoint.
          % Since this procedure is called while the Turtle dict is on top of the
          % dictstack, the temporary dictionary is placed just under the top.
        91{currentdict end[/.[currentpoint matrix currentmatrix]cvx>>begin begin} %[
          % Right bracket: reset position and orientation,
          % pop the dict just under the top.
        93{. setmatrix moveto currentdict end end begin}    %]  
    >>  
    /S{ % stack contains: string recursion-level
        dup B eq{ % hit recursion bound, interpret string as turtle commands
            T begin
                exch % level string
                %dup =
                {                      % iterate through string
                    load exec          % execute turtle command by integer code
                } forall % level       % string has been consumed
            end
            %(B)= pstack
        }{ % recurse
            %(A)= pstack
            exch % level string
            { % level char                   iterate through string
                load exch % string level   process production:load string by int code
                1 add S   % string level+1   increase level and call self
            } forall                       % string has been consumed
        }ifelse
        1 sub            % return level-1
        %(C)= pstack
    }
>>begin
moveto 0 S stroke

Para ejecutarlo, estos 3 bloques se pueden guardar como 3 archivos: dragon.ps, stems.ps, lsys.ps (cualquiera de los bloques de programa anteriores funcionará de manera idéntica). Luego corre con gs: gs dragon.ps lsys.pso gs stems.ps lsys.ps. También se pueden concatenar primero, si se desea: cat dragon.ps lsys.ps | gs -o cat stems.ps lsys.ps | gs -.

curva de dragón

No hay imagen de tallos. No se vuelve más interesante a mayores profundidades.

luser droog
fuente
4

Mathematica 290

Esta implementación básica se centra en el resultado en lugar del procesamiento. No utiliza reglas de producción. Por lo tanto, puede que no sea una respuesta adecuada al desafío.

Tallos ramificados adaptados de la demostración de Theo Gray .

Código

f@{a_, b_} := {{a, #}, {b, #}} &[a + (b - a)/2 + {{0, 1/2}, {-1/2, 0}}.(b - a)]; w = Flatten;
h[s_, g_] :=Graphics[If[s == 0,Line /@ Nest[w[f /@ #, 1] &, {{{0, 0}, {1, 0}}}, g], 
 MapIndexed[Line@# &, NestList[w[Map[{{#[[2]], #[[2]] + m.(#[[2]] - #[[1]])}, {#[[2]], 
 #[[2]] + ({{1, -1}, {-1,1}} m).(#[[2]] - #[[1]])}} &, #], 1] &, {{{0, -1}, {0, 0}}}, g]]]]

Uso

El primer parámetro determina si se mostrarán Dragon Curve o Branch Stems. El segundo término se refiere a la generación.

h[0, 5]
h[1, 5]

segunda foto


Más ejemplos

GraphicsGrid@Partition[Flatten[Table[h[j, k], {j, 0, 1}, {k, 10}]], 5]

fractal3

DavidC
fuente
1
Muy bonito. ¿Pero no guardaría algunos bytes para pasar la regla como argumento?
luser droog
Si esta fuera una solución general, tal vez uno podría pasar una regla en lugar de parámetros. Tendría que estar más informado sobre los sistemas Lindenmayer de lo que estoy actualmente.
DavidC
No leo matematicas. Debería ir a aprender un poco. (agréguelo a la pila :) Pero puede interpretar que significa "cualquier cosa que constituya la descripción de la imagen, a diferencia del motor que la maneja" puede ser eliminada. Si luego puede modificar los datos para controlar alguna característica de la imagen, independientemente de tocar el motor propiamente dicho ; Consideraría que es "funcionalmente equivalente" a un sistema L. [ Eso debería darte muchas lagunas para trabajar;) ]. +1 de todos modos porque es muy bonito.
luser droog
1
@dude Creo que es porque los requisitos gráficos no son adecuados para ellos
Dr. belisarius
1
Finalmente descubrí el sistema l para su árbol: A->F[+A][-A]dónde Fse mueve, +gira a la izquierda 30, -gira a la derecha 30 y [/ ]son push / pop
Shmiddty