Código Sierpinskified

47

Escriba un bloque rectangular de texto que, cuando se arregla en una alfombra Sierpinski , utilizando bloques de espacios del mismo tamaño para las porciones vacías, crea un programa que genera el número de iteración de la alfombra.

Por ejemplo, si su bloque de texto es

TXT
BLK

luego ejecuta el programa

TXTTXTTXT
BLKBLKBLK
TXT   TXT
BLK   BLK
TXTTXTTXT
BLKBLKBLK

debería salir 1porque la forma del programa representa la primera iteración de la alfombra Sierpinski.

Del mismo modo, corriendo

TXTTXTTXTTXTTXTTXTTXTTXTTXT
BLKBLKBLKBLKBLKBLKBLKBLKBLK
TXT   TXTTXT   TXTTXT   TXT
BLK   BLKBLK   BLKBLK   BLK
TXTTXTTXTTXTTXTTXTTXTTXTTXT
BLKBLKBLKBLKBLKBLKBLKBLKBLK
TXTTXTTXT         TXTTXTTXT
BLKBLKBLK         BLKBLKBLK
TXT   TXT         TXT   TXT
BLK   BLK         BLK   BLK
TXTTXTTXT         TXTTXTTXT
BLKBLKBLK         BLKBLKBLK
TXTTXTTXTTXTTXTTXTTXTTXTTXT
BLKBLKBLKBLKBLKBLKBLKBLKBLK
TXT   TXTTXT   TXTTXT   TXT
BLK   BLKBLK   BLKBLK   BLK
TXTTXTTXTTXTTXTTXTTXTTXTTXT
BLKBLKBLKBLKBLKBLKBLKBLKBLK

debería dar salida 2 porque esta es la forma de la segunda iteración de la alfombra Sierpinski.

Ejecutando el bloque de texto como está

TXT
BLK

debería salir 0porque puede considerarse la iteración cero.

Esto debería funcionar para todas las iteraciones posteriores. (Al menos en teoría, suponiendo que la computadora tenga la memoria y todo).

Detalles

  • Los programas no pueden leer o acceder a información sobre su código fuente. Trate esto como un estricto desafío de quine.
  • La salida va a stdout o una alternativa similar. Solo muestra el número y una nueva línea final opcional. No hay entrada
  • El bloque de texto puede contener caracteres que no se consideran terminadores de línea . El bloque de texto puede contener espacios.
  • El "espacio vacío" en la alfombra debe consistir completamente en caracteres espaciales .
  • Opcionalmente, puede suponer que todos los programas tienen una nueva línea final.

Puede usar este fragmento de pila para generar una alfombra para un bloque de texto dado en cualquier iteración:

<style>#o,#i{font-family:monospace;}</style><script>function c(e){e=e.split("\n");for(var n=new Array(3*e.length),t=0;t<n.length;t++){var l=t%e.length;n[t]=e[l]+(t>=e.length&&t<2*e.length?e[l].replace(/./g," "):e[l])+e[l]}return n.join("\n")}function f(){for(i=document.getElementById("i").value,n=parseInt(document.getElementById("n").value);n>0;)i=c(i),n--;document.getElementById("o").value=i}</script><textarea id='i'placeholder='code block...'rows='8'cols='32'></textarea><br>Iterations <input id='n'type='text' value='1'><br><br><button type='button'onclick='f()'>Generate</button><br><br><textarea id='o'placeholder='output...'rows='8'cols='32'style='background-color:#eee'readonly></textarea>

Puntuación

El envío cuyo bloque de texto inicial es más pequeño por área (ancho por alto) es el ganador. El TXT\nBLKejemplo es 3 por 2 para una puntuación de 6. (Básicamente gana el código más corto, de ahí la etiqueta de código de golf).

Tiebreaker va al envío que utiliza la menor cantidad de caracteres distintos en su bloque de texto. Si todavía está empatado, la respuesta obtuvo las primeras victorias.

Pasatiempos de Calvin
fuente

Respuestas:

23

CJam, 9 bytes

Creo que esto se puede mejorar, pero por ahora, vamos con eso ...

];U):U8mL

Cómo funciona :

];             "Wrap everything on stack in an array and discard it";
               "Before this point, the only thing on array can be the log 8 result of";
               "last updated value of U, or nothing, if its the first code";
  U):U         "Increment by 1 and update the value of U (which is pre initialized to 0)";
      8mL      "Take log base 8 of U. This is the property of Sierpinski carpet that";
               "the occurrence of the code is 8 to the power iteration count, indexed 0";

Pruébalo en línea aquí

Optimizador
fuente
35

piet - 32 * 6 = 192

ingrese la descripción de la imagen aquí

Llené el espacio vacío con el patrón de cuadros. Creo que hace que el Sierpinski sea un poco más extraño.

Aquí está la segunda iteración: ingrese la descripción de la imagen aquí

original: 32 * 7

ingrese la descripción de la imagen aquí

captncraig
fuente
19

> <> , 11 * 2 = 22

";n"00pbi1v
+$3*:@3-0.>

Aquí tomamos un enfoque diferente usando la funcionalidad de salto / teletransporte de> <>.

El programa solo ejecuta bloques en la fila superior, ejecuta el primer / segundo bloque, luego los bloques tercero / cuarto, bloques noveno / décimo, bloques 27 ° / 28 °, etc. (subiendo en potencias de 3). Como la fila superior tiene 3^nbloques, solo los nbloques se ejecutan antes de que el programa regrese al inicio, emite la parte superior de la pila y se detiene (debido a la ninstrucción colocada a través de p).

El programa explota la regla "No hay entrada", ya que el icomando empuja -1 a la pila si se cumple EOF. Entonces, para probar esto, necesitará colocar un archivo vacío.


Presentación previa, 7 * 4 = 28

l"v"10p
v>:1=?v
3  ;n{<
<^}+1{,

La primera línea empuja continuamente la longitud de la pila para cada bloque, y cambia la primera "cita a una flecha hacia abajo vusando el pcomando put. Cuando termina la primera línea, la pila parece

[0, 1, 2, .., 3^n]

(Tenga en cuenta que la inicial lse usa dos veces).

Las últimas tres líneas cuentan las veces que necesitamos dividir por 3 antes de que lleguemos a 1 (ya que> <> no tiene una función de registro). El cero inferior se utiliza para realizar un seguimiento del recuento.

Sp3000
fuente
13

Perl, 26

$_+=.91/++$n;
die int."\n";

Utiliza la serie armónica para aproximar el logaritmo de base 3. Creo que funciona, pero solo lo he probado con números pequeños. Gracias a aprensivo ossifrage por la idea de usar die.

Versión anterior (34):

$n--or$n=3**$s++;
print$s-1if!$o++;
grc
fuente
Eso es muy bueno!
aprensivo ossifrage
10

Perl, 30 (15 × 2)

En primer lugar, voy a afirmar que 10 iteraciones es un límite razonable, no 2 32 . Después de 10 iteraciones, un programa que consta de N bytes se habrá expandido a ( N × 3 20 ) bytes (más saltos de línea), que es más de 3 gigabytes incluso para N = 1. Una arquitectura de 32 bits sería completamente incapaz de manejar 11 iteraciones. (Y obviamente no hay suficientes partículas en el universo para 2 32 iteraciones).

Así que aquí está mi solución:

$n++; $_=log$n;
print int;exit;

Esto funciona incrementando la variable $nen la primera línea y calculando su logaritmo en cada paso. La segunda línea imprime la parte entera de este logaritmo y se cierra.

Un logaritmo simple para la base e (2.718 ..) está lo suficientemente cerca como para dar resultados correctos para las primeras 10 iteraciones.

ossifrage aprensivo
fuente
2
Según el OP, en teoría debería funcionar para todas las iteraciones.
Nathan Merrill
2
@NathanMerrill Bueno, está bien. Pero para cumplir con la especificación original, también habría tenido que funcionar en universos alternativos. La pregunta ha sido editada desde entonces.
aprensivo ossifrage
Cambié la pregunta por los buenos puntos hechos aquí. Estoy de acuerdo en que usar el registro natural es más bien un área gris, pero, sinceramente, no estoy demasiado preocupado ya que esto no está ganando.
Aficiones de Calvin
La mayoría de estas presentaciones mantienen el control solo en la fila superior de 3 ^ nx 1 mosaicos. Si solo genera ese segmento de la alfombra, puede escalar un poco más. Es casi seguro que los errores de redondeo lo romperán.
captncraig
1
Como ya mencioné, la pregunta original pedía un código que pudiera escalar a un número "razonable" de iteraciones (hasta 2 ^ 32) . Si hace los cálculos, encontrará que incluso un solo byte se expandiría a más de 10 ^ 4098440370 bytes después de tantas iteraciones. Propuse una respuesta que pensé que era un poco más razonable, pero desde entonces la palabra "razonable" ha desaparecido de la pregunta: - /. Mira, he terminado aquí. Simplemente rechace esta respuesta si no le gusta.
aprensivo ossifrage
9

Golfscript, 9 * 2 = 18

0+       
,3base,(}

(Tenga en cuenta que la primera línea tiene espacios finales para que sea rectangular)

No pude encontrar una función de registro para Golfscript, así que basetuve que hacerlo.

Golfscript comienza con una cadena vacía, por lo que 0+solo aumenta la longitud de la cadena en 1 (por coerción). Para cuando termine la primera línea, la pila tendrá una cadena de longitud 3^n, de la cual tomaremos la base de registro 3 antes de hacer un super comentario. nluego se imprime automáticamente.

Sp3000
fuente
Puede guardar 2 caracteres utilizando un número entero en lugar de una cadena y, por lo tanto, guardando ,en la segunda línea. Primera línea: 0or); segunda linea 3base,(}. El otro objetivo obvio es el (de la segunda línea. Esto es más complicado, pero también se puede eliminar reemplazando la primera línea con 1+~abs(un rectángulo de 7 * 2.
Peter Taylor
8

C, 12x8 = 96

Inspirado por @ciamej, lo he reducido. Utiliza ese truco de dividir por 3, más la comprensión de que la alfombra convierte efectivamente un bucle if en un while.

El código fue probado en gcc / Ubuntu para iteraciones de hasta 3.

#ifndef A //
#define A //
x;main(a){//
a++;/*    */
if(a/=3)x++;
printf(   //
"%d",x);} //
#endif    //

Solución anterior: C, 11x12

No es un ganador del tamaño, pero bueno, es C.

Encuentra log2 de la cuenta de bloque mediante desplazamiento de bits, luego usa algunos números mágicos y truncamiento int para estimar log3. Las matemáticas deberían funcionar hasta 26 iteraciones (un número de 42 bits).

#ifndef A//
#define A//
int n=0;//_
int main//_
(v,c){//___
n+=1;/*..*/
while(n//__
>>=1)v++;//
n=.3+.62*v;
printf(//__
"%d",n);}//
#endif//__
AShelly
fuente
Hola, publiqué una versión abreviada de tu solución.
ciamej
Buen truco con eso si! ;)
ciamej
6

CJam, 9 bytes

La idea de usar ]es de Optimizer, pero utiliza un método muy diferente para contar.

X~]:X,8mL

Pruébalo en línea

Cómo funciona:

X~          "push X and dump its contents.  On the zeroth iteration, X is a single number, but later is it an array.";
  ]         "wrap everything into an array.  The stack would contain the contents of X plus the result of the previous instance of the code";
   :X       "store this array back into X.  X is now 1 element longer";
     ,      "take the length of X";
      8mL   "do a base-8 logarithm of it";

Otras dos soluciones de 9 bytes

]X+:X,8mL

],X+:X8mL
PhiNotPi
fuente
Esto realmente vincula a Optimizer, incluso con el desempate. : P Tiebreakerbreaker: la publicación anterior gana.
Los pasatiempos de Calvin el
Creo que es una buena solución independientemente. No he podido vencer a 9 caracteres.
PhiNotPi
Creo que el enfoque general es el mismo (y cuál es el único enfoque que tiene sentido): tenga una variable, increméntela en 1 de alguna manera.
Optimizador
4

Pitón 2, 15 * 3 = 45

m=n=0;E=exit  ;
m+=1;n+=m>3**n;
print n;E()   ;

Otra implementación de la idea contar-primera-fila-luego-registrar-tres-y-salir. Probablemente todavía se pueda jugar al golf un poco más.

Sp3000
fuente
2

a. C., 2 * 16 + 1 = 33

El +1 adicional en el puntaje se debe a que -lse requiere la opción bc:

a+=1;          
l(a)/l(3);halt;
Trauma digital
fuente
2

Golfscript, 7 * 2 = 14

1+~abs(
3base,}

Esto está inspirado en la respuesta de Sp3000 y, en particular, en el deseo de optimizar la larga segunda línea. 3base,es tan corto como un logaritmo de base 3 se obtendrá en GS, y el súper comentario }es claramente óptimo.

Lo que se requiere para la primera línea es mapear la cadena vacía ''del stdin inicial a 0, y luego mapear cada entero no negativo a su sucesor. De esta manera terminamos la primera línea con 3^n - 1en la pila, y 3base,no requiere ningún decremento.

Peter Taylor
fuente
2

C, 13x8

#ifndef A//__
#define A//__
x;a;main(){//
a++;;;;;;;;;;
while(a/=3)//
x++;printf(//
"%d",x);}//__
#endif//_____
ciamej
fuente
1

Perl, 76

Sé que probablemente no tenga mucho sentido publicar esto ya que ya ha sido completamente superado, pero de todos modos esta es mi solución actual.

$_++;                                 
if(not$_&$_-1){print log()/log 8;$_--}
PhiNotPi
fuente
@Alex Eso no parece funcionar, incluso en la primera iteración.
PhiNotPi
Sí, funciona tal como está. ¿Has probado tu método?
PhiNotPi
El mío funciona en ideone: ideone.com/othumP .
PhiNotPi
Gotcha Me perdí un detalle importante que impedía que funcionara antes. Tienes razón, mi sugerencia es incorrecta.
Alex A.
1

> <> (Pez), 12 * 3 = 36

Una solución más sencilla> <>:

'v'00p0l1+  
>  :2-?v$1+v
^$+1$,3< ;n<

Primero ejecutamos la fila superior de los bloques superiores. 'v'00pse coloca ven la primera posición de todo el programa dirigiendo el puntero del programa hacia abajo cuando vuelve al inicio después de llegar al final de la línea. Antes de eso, cada bloque empuja 0 y la longitud de la pila + 1 sobre él. (pila será 0 2 0 4 0 6 ...)

En la primera mitad del segundo y tercero contamos cuántas veces podemos dividir el elemento de la pila superior antes de obtener 2 (almacenamos esto en el segundo elemento superior).

Al final sacamos el segundo elemento superior de la pila.

randomra
fuente
1

Lua, 3 * 17 = 51

La misma estrategia que la mayoría de las personas:

x=(x or 0)+1;    
y=math.log(x,3)  
print(y)os.exit()
Omar
fuente
1

PHP, 22 × 2 = 44 27 × 2 = 54

<?php $i++          ?>
<?php die(log($i,3))?>

Solo otra versión de count-log3-out. No muy pequeño, pero mi primer golf;)

Lars Ebert
fuente
En PCG.SE como en cualquier otro lugar, consulte la documentación antes de publicar :).
Blackhole
@Blackhole Buena captura! Gracias
Lars Ebert