Telha de dominó de Fibonacci

11

Há um resultado combinatório clássico de que o número de maneiras de ladrilhar uma 2*nfaixa por 1*2dominós é o número n- ésimo de Fibonacci. Seu objetivo é imprimir todas as inclinações para um determinado item n, desenhadas com traços e linhas verticais como essas 8 inclinações para n=5:

|————
|————

——|——
——|——

|||——
|||——

————|
————|

||——|
||——|

|——||
|——||

——|||
——|||

|||||
|||||

Você deve fornecer um programa ou função nomeada que tome ncomo entrada e imprima a saída necessária. Menos bytes ganha.

Entrada

Um número nentre 1e 10inclusive via STDIN ou entrada de função.

Resultado

Imprima todas as inclinações de dominó possíveis da 2*ntira, desenhadas horizontalmente. As inclinações podem estar em qualquer ordem, mas cada uma deve aparecer exatamente uma vez. Eles devem ser separados por uma linha em branco.

Um dominó vertical é feito de duas barras verticais ( |) e um dominó horizontal é feito de dois traços ( ). Você pode usar hífens ( -) no lugar dos traços para permanecer no ASCII.

Você pode fazer qualquer coisa com espaço em branco, desde que a saída impressa pareça a mesma.

xnor
fonte
Um avanço de linha extra após o último ladrilho se encaixaria em algo com espaço em branco ?
Dennis
@ Dennis Sim, linhas em branco extras são boas.
Xnor
Estou realmente surpreso ao ver tantas abordagens diferentes para resolver o mesmo problema. Você esperava isso?
Level River St
@steveverrill Não, eu não o fiz totalmente, e estou encantado de ver a variedade! E o seu leva o bolo para o inesperado. Eu principalmente tinha em mente uma recursão no estilo Fibonacci, como a maioria das soluções usadas. Eu não esperava que a filtragem seja eficaz, e na medida em que fiz, apesar de que seria filtragem cordas de ——e |por comprimento como Dennis, não Length- ncordas de e |filtrados por aparecer em pares. E para o último, eu esperaria que fosse através de expressões regulares ou operações de string na string produzida, como s.split('——) `, não por uma abordagem aritmética como a sua.
xnor
Eu acho que "1x2 dominó" é redundante.
SuperJedi224

Respostas:

5

C, 106

Versão Golfed

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;
}

Versão 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");
  }
}

Como funciona

A variável ivai de 1<<n-1baixo a 0, produzindo todos os números binários possíveis com ndígitos. 0 codifica para |e 1 codifica para -. Estamos interessados ​​em números que contêm 1's em pares. Obviamente, esses números são divisíveis por 3.

Quando um número é dividido por 3, o número original pode ser recuperado multiplicando o resultado por 2 e adicionando-o a si mesmo (efetivamente mutliplicando por 3.) interesse, não é necessário transporte, portanto, nesses casos, apenas OR pode ser usado em vez de adição. Isso é usado para testar os números de interesse, pois eles são os únicos em que a expressão i/3|i/3*2retorna o valor original de i. Veja o exemplo abaixo.

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

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

O valor do teste é sempre igual ou menor que o valor original. Como números que não são múltiplos de 3 também retornam um número menor que o original quando dividido por 3 e depois multiplicado por 3, o teste também fornece o FALSO desejado nesses números.

Na versão original, alguns loops jsão usados ​​para varrer os bits ie produzir a saída. Na versão golfed, um único forloop é usado, no qual hpercorre todos os números de (n*2)*(1<<n)-1até 0. Valores de isão gerados por h/2/n. A variável jnão é mais usada, pois a quantidade equivalente é obtida de h%n. O uso de n*2permite que ambas as linhas sejam impressas a partir do mesmo loop, com um pouco de multiplexação na putsinstrução para imprimir uma ou duas novas linhas no final da linha.

Observe que a carne disso está na posição de incremento do for()suporte e, portanto, é executada após o i=h/2/h.

Saída de amostra n = 6:

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

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

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

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

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

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

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

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

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

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

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

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

||||||
||||||
Level River St
fonte
O i/3|i/3*2truque é engenhoso! Eu não esperava uma expressão aritmética para a gramática.
Xnor
3

CJam, 33 27 bytes

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

Graças a @ jimmy23013 por jogar fora 6 bytes!

Experimente online!

fundo

Esta é uma implementação iterativa de um algoritmo recursivo:

As possíveis inclinações para n podem ser obtidas adicionando um dominó vertical às possíveis inclinações para n - 1 e dois dominós horizontais às possíveis inclinações para n - 2 .

Desta forma, o número de pavimentações para n é a soma dos números de pavimentações para n - 1 e n - 2 , ou seja, o n ° número de Fibonacci.

Como 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'                ";

Exemplo de execução

$ 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
fonte
LNli{_'|f\@"——"f\+2/}*\;{_N}/.
Jimmy23013 27/02
f\ainda não havia sido implementado no 0.6.2, mas consegui combinar nossas abordagens. Obrigado!
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

fé uma função que, dado um número, retorna uma lista de uma linha de todas as possíveis inclinações de Fibonacci possíveis de comprimento n possível. não importa que retorne uma linha, porque as duas linhas de todas as inclinações são iguais.

ffunciona chamando recursivamente em n-1e n-2e adicionando "|"e "--"(respectivamente) para as cordas.

gé a função que responde às perguntas. basicamente chama fa entrada, dobra cada string para mostrar duas linhas e une todas por novas linhas.

saída de exemplo:

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

|||--
|||--

||--|
||--|

|--||
|--||

|----
|----

--|||
--|||

--|--
--|--

----|
----|
orgulhoso haskeller
fonte
2

CJam, 42 37 bytes

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

Eu contei os traços como um byte cada, pois a pergunta permite substituí-los por hífens ASCII.

Experimente online.

Como funciona

Para obter todas as inclinações possíveis de 2 × L , iteramos sobre todos os números inteiros não negativos I <3 L , fazendo com que os dígitos pares na base 3 correspondam aos dominós horizontais e os ímpares aos verticais.

Como cada I possui L ou menos dígitos na base 3, isso gera todas as formas possíveis de cobrir a faixa de 2 × L. Tudo o que resta é filtrar as coberturas maiores ou menores que 2 × L e imprimir as coberturas 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'.           ";

Exemplo de execução

$ 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
fonte
Legal. Estou apenas me perguntando por que você não usou a base 2 como edc65 em vez da base 3. Isso teria evitado que você tivesse duplicatas. Suponho que é porque os zeros à esquerda provavelmente serão truncados na etapa 3b. Isso está certo?
Level River St
1
@ steveverrill: Sim, essa é precisamente a razão. Como é, zeros à esquerda não correspondem a dominó. Mas não ter duplicatas me permitiria substituir os três blocos por um único. Vou ter que pensar um pouco mais sobre isso.
Dennis
@ steveverrill: Eu não consegui fazer a base 2 funcionar, mas uma abordagem recursiva parece ser ainda mais curta.
Dennis
2

JavaScript (E6) 102

Gere configurações a partir de seqüências de bits, 0 -> '-' e 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?'|':'--';
}

Teste no console do firefox / firebug

F(5)

Resultado

|----
|----

--|--
--|--

----|
----|

|||--
|||--

||--|
||--|

|--||
|--||

--|||
--|||

|||||
|||||
edc65
fonte
1

Haskell: 109 bytes

Esta é uma tradução do conhecido one-liner Haskell para calcular preguiçosamente a sequência dos 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!!)

A sequência principal de seqüências de caracteres lado a lado, não destruídas:

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

E o one-liner de Fibonacci para comparação:

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

Exemplo 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
fonte
1

Cobra - 176

Mal posso esperar até eu terminar o pacote de golfe 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'
Furioso
fonte
1

J - 54 char

Função tomada ncomo argumento à direita.

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

A principal raiz deste golfe é o (];'--'&,"1@[,'|',"1])&>/. Isso pega uma lista de inclinações de comprimento (N-2) e (N-1) e retorna uma lista de inclinações de comprimento (N-1) e N. Essa é a recorrência padrão de Fibonacci, à álgebra linear. ];retorna a lista da direita como a nova esquerda (como não há alterações). '--'&,"1@[adiciona --blocos à lista da esquerda, enquanto '|',"1]adiciona |blocos à lista da direita, e esses juntos são a nova lista da direita.

Repetimos isso várias nvezes (esse é o @[&0) e começamos com o ladrilho vazio e o ladrilho único de comprimento 1. Em seguida, retornamos o primeiro do par com 0{::. Ou seja, se o executarmos zero vezes, retornamos o primeiro, ou seja, o ladrilho vazio. Se o executarmos nvezes, calculamos até o par n( n+1), mas descartamos o último. É trabalho extra, mas menos personagens.

O (1 2$,:)é algo J tem que fazer, a fim de fazer as pavimentações nas listas facilmente extensível. Tornamos a lista inicial esquerda uma lista de 1 item de uma matriz de caracteres de 2 linhas, cada linha tendo o comprimento 0. A lista inicial direita é a mesma, mas tem as linhas com o comprimento 1, preenchidas |. Em seguida, adicionamos os novos blocos a cada linha e anexamos as listas de matrizes quando unimos os dois conjuntos de inclinações. É uma aplicação simples de um conceito que J chama de classificação: manipulando essencialmente a dimensionalidade de seus argumentos e fazendo um loop implicitamente quando necessário.

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

--|--
--|--

--|||
--|||

|----
|----

|--||
|--||

||--|
||--|

|||--
|||--

|||||
|||||

Tente você mesmo no tryj.tk .

algoritmshark
fonte
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)

Cria recursivamente todas as seqüências possíveis que srepresentam uma linha de dominós, que são duplicadas e impressas. Iniciar scomo o caractere de nova linha faz com que a linha em branco aconteça automaticamente.

O ==entre as duas chamadas fé apenas para realizar as duas chamadas de função. Eles geralmente retornam Noneporque são impressos e ==é um dos poucos operadores definidos None.

As ands e ors são para produzir o comportamento-circuito curto direito de reproduzir as ifs e elses do código ungolfed.

Ungolfed:

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
fonte
1

Retina , 44 bytes

Nota: A retina é mais jovem que esse desafio.

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

Recebe a entrada unária com uma nova linha à direita.

Cada linha deve ir para seu próprio arquivo e #deve ser alterada para nova linha no arquivo. Isso é impraticável, mas você pode executar o código como um arquivo com o -ssinalizador, mantendo os #marcadores (e alterando a nova linha para #na entrada também). Você pode alterar as #costas para novas linhas na saída para facilitar a leitura, se desejar. Por exemplo:

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

||--
||--

|--|
|--|

--||
--||

----
----

Método:

  • A partir da entrada, trocamos todas as linhas por duas outras: uma com a primeira 1alteração para |e uma com as duas primeiras 1alteradas para --. Fazemos isso até termos linhas com pelo menos dois 1.
  • Quando 1sobraram apenas um single , mudamos para |um.
  • Dobramos cada linha, adicionamos uma nova linha extra e obtemos a saída desejada.
randomra
fonte
Trailing newline está bom.
Xnor