Hay resultado clásico combinatoria que el número de formas de baldosas de una 2*n
franja de 1*2
fichas 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 n
como entrada e imprima la salida requerida. Pocos bytes ganan.
Entrada
Un número n
entre 1
e 10
inclusive a través de STDIN o entrada de función.
Salida
Imprima todas las posibles inclinaciones de dominó de la 2*n
tira, 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.
——
y|
por longitud como las de Dennis, non
cadenas 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, comos.split('——
) `, no por un enfoque aritmético como el suyo.Respuestas:
C, 106
Versión de golf
Versión original
Cómo funciona
La variable
i
va de1<<n-1
abajo a 0, produciendo todos los números binarios posibles conn
dí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*2
devuelve el valor original dei
. Ver ejemplo a continuación.1111
= 15 --->0101
= 5 --->1111
= 15 (válido,0101|1010
==0101+1010
)1001
= 9 --->0011
= 3 --->0111
= 7 (inválido0011|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,
j
se utilizan un par de bucles para explorar los bitsi
y producir la salida. En la versión de golffor
se utiliza un solo bucle, en el que seh
ejecuta a través de todos los números desde(n*2)*(1<<n)-1
hasta 0. Los valores dei
son generados porh/2/n
. La variablej
ya no se usa, ya que se obtiene la cantidad equivalenteh%n
. El uso den*2
permite que ambas líneas se impriman desde el mismo bucle, con un ingenioso multiplexado en laputs
declaració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 lai=h/2/h
.Salida de muestra n = 6:
fuente
i/3|i/3*2
truco es ingenioso! No esperaba una expresión aritmética para la gramática.CJam,
3327 bytes¡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
Ejecución de ejemplo
fuente
LNli{_'|f\@"——"f\+2/}*\;{_N}/
.f\
aún no se había implementado en 0.6.2, pero pude combinar nuestros enfoques. ¡Gracias!Haskell, 89 bytes
f
es 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.f
funciona llamando recursivamente an-1
yn-2
y agregando"|"
y"--"
(respectivamente) a las cadenas.g
es la función que responde las preguntas. básicamente llamaf
a la entrada, dobla cada cadena para que muestre dos líneas y las une a todas con nuevas líneas.salida de ejemplo:
fuente
CJam,
4237 bytesHe 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.
Ejecución de ejemplo
fuente
3b
. ¿Está bien?JavaScript (E6) 102
Genere configuraciones a partir de secuencias de bits, 0 -> '-' y 1 -> '|'.
Prueba en la consola firefox / firebug
Salida
fuente
Haskell: 109 bytes
Esta es una traducción del conocido Haskell one-liner para calcular perezosamente la secuencia de números de Fibonacci:
La secuencia principal de cadenas de mosaico, sin golf:
Y el one-liner de Fibonacci para comparar:
Ejemplo de uso:
fuente
Cobra - 176
No puedo esperar hasta que haya terminado el paquete de golf Cobra.
fuente
J - 54 char
Función tomando
n
como argumento a la derecha.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
n
vez (ese es el@[&0
) y comenzamos con el mosaico vacío y el mosaico único de longitud 1. Luego devolvemos el primero del par con0{::
. Es decir, si lo ejecutamos cero veces, solo devolvemos el primero, es decir, el mosaico vacío. Si lo ejecutamosn
veces, calculamos hasta el parn
y (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.Pruébelo usted mismo en tryj.tk .
fuente
Python 3: 70 bytes
Crea recursivamente todas las cadenas posibles que
s
representan una fila de fichas de dominó, que se duplican e imprimen. Comenzars
como el carácter de nueva línea hace que la línea en blanco suceda automáticamente.El
==
de una llamada paraf
es sólo para llevar a cabo ambas llamadas a funciones. Por lo general, regresanNone
porque solo imprimen y==
es uno de los pocos operadores definidos paraNone
.Los
and
s yor
s son para producir el comportamiento de cortocircuito derecho a reproducir lasif
s yelse
s del código ungolfed.Sin golf:
fuente
Retina , 44 bytes
Nota: Retina es más joven que este desafío.
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-s
bandera, 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:Método:
1
cambio a|
y otra con las dos primeras1
cambiadas a--
. Hacemos esto hasta que tengamos líneas con al menos dos1
.1
, cambiamos esos a|
's.fuente