Revestimiento de dominó de Fibonacci

11

Hay resultado clásico combinatoria que el número de formas de baldosas de una 2*nfranja de 1*2fichas de dominó es el n º número de Fibonacci. Su objetivo es imprimir todas las inclinaciones para un determinado n, dibujado con guiones y líneas verticales como estas 8 inclinaciones para n=5:

|————
|————

——|——
——|——

|||——
|||——

————|
————|

||——|
||——|

|——||
|——||

——|||
——|||

|||||
|||||

Debe proporcionar un programa o función con nombre que tome ncomo entrada e imprima la salida requerida. Pocos bytes ganan.

Entrada

Un número nentre 1e 10inclusive a través de STDIN o entrada de función.

Salida

Imprima todas las posibles inclinaciones de dominó de la 2*ntira, dibujadas horizontalmente. Las inclinaciones pueden estar en cualquier orden, pero cada una debe aparecer exactamente una vez. Deben estar separados por una línea en blanco.

Un dominó vertical está compuesto por dos barras verticales ( |) y un dominó horizontal está compuesto por dos guiones en em ( ). Puede usar guiones ( -) en lugar de guiones largos para permanecer en ASCII.

Puede hacer cualquier cosa con espacios en blanco siempre que la salida impresa se vea igual.

xnor
fuente
¿Un salto de línea adicional después del último mosaico quedaría debajo de cualquier espacio en blanco ?
Dennis
@ Dennis Sí, las líneas en blanco adicionales están bien.
xnor
Estoy realmente sorprendido de ver tantos enfoques diferentes para resolver el mismo problema. ¿Lo esperabas?
Level River St
@steveverrill No, no lo hice totalmente, ¡y estoy encantado de ver la variedad! Y el tuyo toma el pastel por lo inesperado. Principalmente tenía en mente una recursión al estilo de Fibonacci, como la mayoría de las soluciones que usé. No esperaba que el filtrado fuera efectivo, y en la medida en que lo hice, pensé que sería filtrar cadenas de ——y |por longitud como las de Dennis, no ncadenas de longitud y |filtradas apareciendo en pares. Y para este último, esperaría que fuera a través de expresiones regulares u operaciones de cadena en la cadena producida, como s.split('——) `, no por un enfoque aritmético como el suyo.
xnor
Creo que "dominó 1x2" es redundante.
SuperJedi224

Respuestas:

5

C, 106

Versión de golf

f(n){
  for(int i,h=n*2<<n;h--;(i/3|i/3*2)-i||(putchar(i>>h%n&1?45:124),h%n||puts(h%(n*2)?"":"\n")))
    i=h/2/n;
}

Versión original

i,j,n;
main(){
  scanf("%d",&n);
  for(i=1<<n;i--;)if((i/3|i/3*2)==i){
    for(j=1<<n;j/=2;)printf("%c",i&j?'-':'|');puts("");
    for(j=1<<n;j/=2;)printf("%c",i&j?'-':'|');puts("\n");
  }
}

Cómo funciona

La variable iva de 1<<n-1abajo a 0, produciendo todos los números binarios posibles con ndígitos. 0 codifica para |y 1 codifica para -. Nos interesan los números que contienen 1 en pares. Obviamente, tales números son divisibles por 3.

Cuando un número se divide por 3, el número original se puede recuperar multiplicando el resultado por 2 y agregándolo a sí mismo (efectivamente multiplicando por 3.) La mayoría de los números requerirán un acarreo, pero cuando el proceso se lleva a cabo en los números de interés, no se requiere llevar, por lo que solo en estos casos, O se puede usar en lugar de agregar. Esto se usa para probar los números de interés, ya que son los únicos en los que la expresión i/3|i/3*2devuelve el valor original de i. Ver ejemplo a continuación.

1111= 15 ---> 0101= 5 ---> 1111= 15 (válido, 0101|1010== 0101+1010)

1001= 9 ---> 0011= 3 ---> 0111= 7 (inválido 0011|0110,! = 0011+0110)

El valor de la prueba es siempre igual o menor que el valor original. Como los números que no son múltiplos de 3 también devuelven un número menor que el original cuando se divide por 3 y luego se multiplica por 3, la prueba también proporciona el FALSO deseado en estos números.

En la versión original, jse utilizan un par de bucles para explorar los bits iy producir la salida. En la versión de golf forse utiliza un solo bucle, en el que se hejecuta a través de todos los números desde (n*2)*(1<<n)-1hasta 0. Los valores de ison generados por h/2/n. La variable jya no se usa, ya que se obtiene la cantidad equivalente h%n. El uso de n*2permite que ambas líneas se impriman desde el mismo bucle, con un ingenioso multiplexado en la putsdeclaración para imprimir una o dos líneas nuevas al final de la fila.

Tenga en cuenta que la carne de este está en la posición de la subasta del for()soporte y, por tanto, es ejecutado después de la i=h/2/h.

Salida de muestra n = 6:

$ ./a
6
------
------

----||
----||

--|--|
--|--|

--||--
--||--

--||||
--||||

|----|
|----|

|--|--
|--|--

|--|||
|--|||

||----
||----

||--||
||--||

|||--|
|||--|

||||--
||||--

||||||
||||||
Level River St
fuente
¡El i/3|i/3*2truco es ingenioso! No esperaba una expresión aritmética para la gramática.
xnor
3

CJam, 33 27 bytes

LN{_'|f+@"——"f++}ri*\;{_N}/

¡Gracias a @ jimmy23013 por jugar golf en 6 bytes!

Pruébalo en línea!

Antecedentes

Esta es una implementación iterativa de un algoritmo recursivo:

Las posibles inclinaciones para n pueden obtenerse agregando un dominó vertical a las posibles inclinaciones para n - 1 y dos fichas de dominó horizontales a las posibles inclinaciones para n - 2 .

De esta manera, el número de mosaicos para n es la suma de los números de los embaldosados para n - 1 y n - 2 , es decir, el n ésimo número de Fibonacci.

Cómo funciona

LN                                " A:= [''] B:= ['\n']                         ";
  {             }ri*              " Repeat int(input()) times:                  ";
   _'|f+                          "   C = copy(B); for T ∊ C: T += '|'          ";
              @                   "   Swap A and B.                             ";
               "——"f+             "   for T ∊ B: T += "——"                      ";
                     +            "   B = C + B                                 ";
                        \;        " Discard A.                                  ";
                          {_N}/   " for T ∊ B: print T, T + '\n'                ";

Ejecución de ejemplo

$ alias cjam='java -jar cjam-0.6.2.jar'

$ cjam domino.cjam <<< 3
|||
|||

——|
——|

|——
|——

$ for i in {1..10}; do echo $[$(cjam domino.cjam <<< $i | wc -l) / 3]; done1
2
3
5
8
13
21
34
55
89
Dennis
fuente
LNli{_'|f\@"——"f\+2/}*\;{_N}/.
jimmy23013
f\aún no se había implementado en 0.6.2, pero pude combinar nuestros enfoques. ¡Gracias!
Dennis
2

Haskell, 89 bytes

f(-1)=[]
f 0=[""]
f n=map('|':)(f$n-1)++map("--"++)(f$n-2)
g=unlines.(>>= \x->[x,x,""]).f

fes una función que dado un número devuelve una lista de una línea de todas las posibles inclinaciones de Fibonacci de longitud n posibles. no importa que devuelva una línea, porque ambas líneas de todas las inclinaciones son iguales.

ffunciona llamando recursivamente a n-1y n-2y agregando "|"y "--"(respectivamente) a las cadenas.

ges la función que responde las preguntas. básicamente llama fa la entrada, dobla cada cadena para que muestre dos líneas y las une a todas con nuevas líneas.

salida de ejemplo:

*Main> putStrLn $ g 5
|||||
|||||

|||--
|||--

||--|
||--|

|--||
|--||

|----
|----

--|||
--|||

--|--
--|--

----|
----|
orgulloso Haskeller
fuente
2

CJam, 42 37 bytes

3li:L#,{3b"——|"2/f=s}%{,L=},_&{N+_N}/

He contado los guiones como un byte cada uno ya que la pregunta permite reemplazarlos con guiones ASCII.

Pruébalo en línea.

Cómo funciona

Para obtener todas las posibles inclinaciones de 2 × L , iteramos sobre todos los enteros no negativos I <3 L , haciendo que los dígitos pares en la base 3 correspondan a los dominós horizontales y los dígitos impares a los verticales.

Como cada I tiene L o menos dígitos en la base 3, esto genera todas las formas posibles de cubrir la tira de 2 × L. Todo lo que queda es filtrar las cubiertas que son más grandes o más pequeñas que 2 × L e imprimir las cubiertas restantes.

3li:L#,      " Read an integer L from STDIN and push A := [ 0 1 ... (3 ** N - 1) ].       ";
{            " For each integer I in A:                                                   ";
  3b         " Push B, the array of I's base 3 digits.                                    ";
  "——|"2/    " Push S := [ '——' '|' ].                                                    ";
  f=         " Replace each D in B with S[D % 2] (the modulus is implicit).               ";
  s          " Flatten B.                                                                 ";
}%           " Collect the result in an array R.                                          ";
{,L=},       " Filter R so it contains only strings of length L.                          ";
_&           " Intersect R with itself to remove duplicates.                              ";
{N+_N}/      " For each string T in B, push (T . '\n') twice, followed by '\n'.           ";

Ejecución de ejemplo

$ cjam domino.cjam <<< 3
|——
|——

——|
——|

|||
|||

$ for i in {1..10}; do echo $[$(cjam domino.cjam <<< $i | wc -l) / 3]; done
1
2
3
5
8
13
21
34
55
89
Dennis
fuente
Frio. Me pregunto por qué no usaste la base 2 como edc65 en lugar de la base 3. Eso te habría salvado de tener duplicados. Supongo que es porque los ceros iniciales probablemente se truncan en el paso 3b. ¿Está bien?
Level River St
1
@steveverrill: Sí, esa es precisamente la razón. Tal como están las cosas, los ceros iniciales no corresponden a ningún dominó. Pero no tener duplicados me permitiría reemplazar los tres bloques con uno solo. Tendré que pensar en esto un poco más.
Dennis
@steveverrill: no logré hacer que la base 2 funcione, pero un enfoque recursivo parece ser aún más corto.
Dennis
2

JavaScript (E6) 102

Genere configuraciones a partir de secuencias de bits, 0 -> '-' y 1 -> '|'.

F=n=>{
  for(i=0;(j=++i)<2<<n;s.length==1+n&&console.log('\n'+s+s))
    for(s='\n';j>1;j>>=1)s+=j&1?'|':'--';
}

Prueba en la consola firefox / firebug

F(5)

Salida

|----
|----

--|--
--|--

----|
----|

|||--
|||--

||--|
||--|

|--||
|--||

--|||
--|||

|||||
|||||
edc65
fuente
1

Haskell: 109 bytes

Esta es una traducción del conocido Haskell one-liner para calcular perezosamente la secuencia de números de Fibonacci:

b=map.map.(++)
w=zipWith
z=w(++)
s=["\n"]:["|\n"]:z(b"--"s)(b"|"$tail s)
f=sequence_.map putStrLn.(w z s s!!)

La secuencia principal de cadenas de mosaico, sin golf:

dominos = [""] : ["|"] : zipWith (++) ("--" `before` dominos) ("|" `before` tail dominos)
    where before = map . map . (++)

Y el one-liner de Fibonacci para comparar:

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Ejemplo de uso:

$ ghci fibtile
GHCi, version 7.6.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
[1 of 1] Compiling Main             ( fibtile.hs, interpreted )
Ok, modules loaded: Main.
*Main> f 5
----|
----|

--|--
--|--

--|||
--|||

|----
|----

|--||
|--||

||--|
||--|

|||--
|||--

|||||
|||||

*Main>
Matt Noonan
fuente
1

Cobra - 176

No puedo esperar hasta que haya terminado el paquete de golf Cobra.

def m(n)
    for t in.f(n),print t+t
def f(n,x='')as String*
    if x.length<n,for i in.f(n,x+'-').toList+.f(n,x+'|').toList,yield i
    else if not'-'in x.replace('--',''),yield x+'\n'
Οurous
fuente
1

J - 54 char

Función tomando ncomo argumento a la derecha.

0{::(];'--'&,"1@[,'|',"1])&>/@[&0&((1 2$,:)&.>'';,'|')

La raíz principal de este golf es el (];'--'&,"1@[,'|',"1])&>/. Esto toma una lista de inclinaciones de longitud (N-2) y (N-1), y devuelve una lista de inclinaciones de longitud (N-1) y N. Esta es la recurrencia estándar de Fibonacci, al álgebra lineal. ];devuelve la lista de la derecha como la nueva izquierda (ya que no hay cambio). '--'&,"1@[agrega --mosaicos a la lista de la izquierda, mientras que '|',"1]agrega |mosaicos a la lista de la derecha, y todos juntos son la nueva lista de la derecha.

Repetimos eso una y otra nvez (ese es el @[&0) y comenzamos con el mosaico vacío y el mosaico único de longitud 1. Luego devolvemos el primero del par con 0{::. Es decir, si lo ejecutamos cero veces, solo devolvemos el primero, es decir, el mosaico vacío. Si lo ejecutamos nveces, calculamos hasta el par ny ( n+1), pero descartamos el último. Es trabajo extra pero menos personajes.

Esto (1 2$,:)es algo que J tiene que hacer para que las inclinaciones en las listas sean fácilmente extensibles. Hacemos que la lista de inicio izquierda sea una lista de 1 elemento de una matriz de caracteres de 2 filas, cada fila tiene una longitud 0. La lista de inicio derecha es la misma, pero tiene las filas de longitud 1, llenas |. Luego, agregamos los nuevos mosaicos a cada fila y agregamos las listas de matrices cuando unimos los dos conjuntos de inclinaciones. Es una aplicación simple de un concepto que J llama rango: esencialmente manipulando la dimensionalidad de sus argumentos y haciendo un bucle implícito cuando es necesario.

   0{::(];'--'&,"1@[,'|',"1])&>/@[&0&((1 2$,:)&.>'';,'|')5
----|
----|

--|--
--|--

--|||
--|||

|----
|----

|--||
|--||

||--|
||--|

|||--
|||--

|||||
|||||

Pruébelo usted mismo en tryj.tk .

Algoritmo de tiburón
fuente
1

Python 3: 70 bytes

f=lambda n,s="\n":n>0and f(n-1,"|"+s)==f(n-2,"--"+s)or n or print(s*2)

Crea recursivamente todas las cadenas posibles que srepresentan una fila de fichas de dominó, que se duplican e imprimen. Comenzar scomo el carácter de nueva línea hace que la línea en blanco suceda automáticamente.

El ==de una llamada para fes sólo para llevar a cabo ambas llamadas a funciones. Por lo general, regresan Noneporque solo imprimen y ==es uno de los pocos operadores definidos para None.

Los ands y ors son para producir el comportamiento de cortocircuito derecho a reproducir las ifs y elses del código ungolfed.

Sin golf:

def f(n,s="\n"):
 if n==-1:pass
 elif n==0: print(s*2)
 else: f(n-1,"|"+s);f(n-2,"--"+s)
xnor
fuente
1

Retina , 44 bytes

Nota: Retina es más joven que este desafío.

+`([-|]*)11(1*#)
$1|1$2$1--$2
1
|
.*?#
$0$0#

Toma entrada en unario con una nueva línea final.

Cada línea debe ir a su propio archivo y #debe cambiarse a nueva línea en el archivo. Esto no es práctico, pero puede ejecutar el código tal como está en un archivo con la -sbandera, manteniendo los #marcadores (y cambiando la nueva línea #en la entrada también). Puede #volver a cambiar las líneas nuevas en la salida para facilitar la lectura si lo desea. P.ej:

> echo 1111# | retina -s fib_tile | tr # '\n'
||||
||||

||--
||--

|--|
|--|

--||
--||

----
----

Método:

  • Comenzando desde la entrada, intercambiamos cada línea con otras dos: una con el primer 1cambio a |y otra con las dos primeras 1cambiadas a --. Hacemos esto hasta que tengamos líneas con al menos dos 1.
  • Cuando solo quedan solos 1, cambiamos esos a |'s.
  • Duplicamos cada línea y le agregamos una nueva línea adicional y obtenemos el resultado deseado.
randomra
fuente
La nueva línea final está bien.
xnor