Il existe un résultat combinatoire classique selon lequel le nombre de façons de carreler une 2*nbande par des 1*2dominos est le ^nième nombre de Fibonacci. Votre objectif est d'imprimer tous les pavages pour une donnée n, dessinés avec des tirets et des lignes verticales comme ces 8 pavages pour n=5:

|————
|————

——|——
——|——

|||——
|||——

————|
————|

||——|
||——|

|——||
|——||

——|||
——|||

|||||
|||||

Vous devez fournir un programme ou une fonction nommée qui prend nen entrée et imprime la sortie requise. Le moins d'octets gagne.

Contribution

Un nombre nentre 1et 10inclus via STDIN ou entrée de fonction.

Production

Imprimez tous les carrelages domino possibles de la 2*nbande, dessinés horizontalement. Les pavages peuvent être dans n'importe quel ordre, mais chacun doit apparaître exactement une fois. Ils doivent être séparés par une ligne vierge.

Un domino vertical est composé de deux barres verticales ( |) et un domino horizontal est composé de deux tirets ( —). Vous pouvez utiliser des tirets ( -) à la place des tirets pour rester en ASCII.

Vous pouvez tout faire avec des espaces tant que la sortie imprimée est identique.

C, 106

Version golfée

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

Version originale

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

Comment ça fonctionne

La variable iva de 1<<n-10 à 0, produisant tous les nombres binaires possibles avec des nchiffres. 0 code pour |et 1 code pour -. Nous sommes intéressés par les nombres qui contiennent des paires de 1. De toute évidence, ces nombres sont divisibles par 3.

Lorsqu'un nombre est divisé par 3, le nombre d'origine peut être récupéré en multipliant le résultat par 2 et en l'ajoutant à lui-même (en le multipliant par 3). La plupart des nombres nécessitent un report, mais lorsque le processus est effectué sur le nombre de l'intérêt, aucun report n'est requis, donc dans ces cas seulement, OU peut être utilisé à la place de l'addition. Ceci est utilisé pour tester les nombres d'intérêt, car ce sont les seuls où l'expression i/3|i/3*2renvoie la valeur d'origine de i. Voir l'exemple ci-dessous.

1111= 15 ---> 0101= 5 ---> 1111= 15 (valide, 0101|1010== 0101+1010)

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

La valeur de test est toujours égale ou inférieure à la valeur d'origine. Comme les nombres qui ne sont pas des multiples de 3 renvoient également un nombre inférieur à l'original lorsqu'ils sont divisés par 3 puis multipliés par 3, le test donne également le FAUX souhaité sur ces nombres.

Dans la version originale, quelques boucles jsont utilisées pour parcourir les bits iet produire la sortie. Dans la version golfée, une seule forboucle est utilisée, dans laquelle hpasse tous les nombres de (n*2)*(1<<n)-10 à 0. Les valeurs de isont générées par h/2/n. La variable jn'est plus utilisée, car la quantité équivalente est obtenue à partir de h%n. L'utilisation de n*2permet aux deux lignes d'être imprimées à partir de la même boucle, avec un multiplexage astucieux dans l' putsinstruction pour imprimer une ou deux nouvelles lignes à la fin de la ligne.

Notez que la viande de ceci est dans la position d'incrémentation du for()support et est donc exécutée après le i=h/2/h.

Exemple de sortie n = 6:

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

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

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

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

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

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

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

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

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

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

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

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

||||||
||||||

CJam, 33 27 octets

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

Merci à @ jimmy23013 pour avoir joué au golf sur 6 octets!

Essayez-le en ligne!

Contexte

Il s'agit d'une implémentation itérative d'un algorithme récursif:

Les pavages possibles pour n peuvent être obtenus en ajoutant un domino vertical aux pavages possibles pour n - 1 et deux dominos horizontaux aux pavages possibles pour n - 2 .

De cette façon, le nombre de pavages pour n est la somme des nombres de pavages pour n - 1 et n - 2 , c'est-à-dire le n ^ème nombre de Fibonacci.

Comment ça fonctionne

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

Exemple d'exécution

$ 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

Haskell, 89 octets

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

fest une fonction qui, étant donné un nombre, renvoie une liste d'une ligne de tous les pavages de Fibonacci possibles de longueur n possible. peu importe qu'il renvoie une ligne, car les deux lignes de tous les pavages sont identiques.

ffonctionne en appelant récursivement sur n-1et n-2et en ajoutant "|"et "--"(respectivement) aux chaînes.

gest la fonction qui répond aux questions. il appelle essentiellement fl'entrée, double chaque chaîne de sorte qu'il affiche deux lignes et les joint toutes par des retours à la ligne.

exemple de sortie:

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

|||--
|||--

||--|
||--|

|--||
|--||

|----
|----

--|||
--|||

--|--
--|--

----|
----|

CJam, 42 37 octets

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

J'ai compté les tirets comme un octet chacun puisque la question permet de les remplacer par des tirets ASCII.

Essayez-le en ligne.

Comment ça fonctionne

Pour obtenir tous les pavages possibles de 2 × L , nous itérons sur tous les entiers non négatifs I <3 ^L , en faisant correspondre les chiffres pairs de la base 3 aux dominos horizontaux et les chiffres impairs aux verticaux.

Étant donné que chaque I a L ou moins de chiffres dans la base 3, cela génère toutes les façons possibles de couvrir la bande 2 × L. Il ne reste plus qu'à filtrer les revêtements plus grands ou plus petits que 2 × L et imprimer les revêtements restants.

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

Exemple d'exécution

$ 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

JavaScript (E6) 102

Générez des configurations à partir de séquences de bits, 0 -> '-' et 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?'|':'--';
}

Test dans la console Firefox / Firebug

F(5)

Production

|----
|----

--|--
--|--

----|
----|

|||--
|||--

||--|
||--|

|--||
|--||

--|||
--|||

|||||
|||||

Haskell: 109 octets

Ceci est une traduction de la célèbre ligne unique de Haskell pour calculer paresseusement la séquence des nombres 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 séquence principale des cordes de carrelage, non golfée:

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

Et le Fibonacci one-liner pour comparaison:

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

Exemple d'utilisation:

$ 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>

Cobra - 176

J'ai hâte d'avoir terminé le forfait 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'

J - 54 car

Prise de fonction ncomme argument à droite.

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

La racine principale de ce golf est le (];'--'&,"1@[,'|',"1])&>/. Cela prend une liste de pavages de longueur (N-2) et (N-1), et renvoie une liste de pavages de longueur (N-1) et N. Il s'agit de la récurrence standard de Fibonacci, à l'algèbre linéaire. ];renvoie la liste de droite comme nouvelle gauche (car il n'y a pas de changement). '--'&,"1@[ajoute des --tuiles à la liste de gauche, tandis que '|',"1]ajoute des |tuiles à la liste de droite, et celles-ci constituent la nouvelle liste de droite.

Nous répétons cela maintes et maintes nfois (c'est le @[&0) et commençons par le pavage vide et le pavage unique de longueur 1. Ensuite, nous retournons le premier de la paire avec 0{::. Cela signifie que si nous l'exécutons zéro fois, nous renvoyons simplement le premier, c'est-à-dire le pavage vide. Si nous l'exécutons nfois, nous calculons jusqu'à la paire net ( n+1), mais jetons cette dernière. C'est du travail supplémentaire mais moins de personnages.

C'est (1 2$,:)quelque chose que J doit faire pour rendre les pavages dans les listes facilement extensibles. Nous faisons de la liste de départ gauche une liste à 1 élément d'une matrice de caractères à 2 lignes, chaque ligne ayant une longueur 0. La liste de départ droite est la même, mais les lignes ont une longueur 1, remplie de |. Ensuite, nous ajoutons les nouvelles tuiles à chaque ligne et ajoutons les listes de matrices lorsque nous joignons les deux ensembles de mosaïques ensemble. Il s'agit d'une simple application d'un concept que J appelle rang: manipuler essentiellement la dimensionnalité de ses arguments et boucler implicitement lorsque cela est nécessaire.

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

--|--
--|--

--|||
--|||

|----
|----

|--||
|--||

||--|
||--|

|||--
|||--

|||||
|||||

Essayez - le pour vous - même à tryj.tk .

Python 3: 70 octets

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

Génère récursivement toutes les chaînes possibles sreprésentant une ligne de dominos, qui sont dupliquées et imprimées. En commençant spar le caractère de nouvelle ligne, la ligne vierge apparaît automatiquement.

le == entre les deux appels à fest juste pour effectuer les appels de fonction. Celles-ci reviennent généralement Noneparce qu'elles impriment simplement et ==sont l'un des rares opérateurs définis pour None.

le and s et ors doivent produire le bon comportement de court-circuit pour reproduire les ifs et elses du code non golfé.

Non 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)

Rétine , 44 octets

Remarque: la rétine est plus jeune que ce défi.

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

Prend entrée en unaire avec une nouvelle ligne de fin.

Chaque ligne doit aller dans son propre fichier et #doit être remplacée par un retour à la ligne dans le fichier. Ceci n'est pas pratique, mais vous pouvez exécuter le code tel quel comme un fichier avec l' -sindicateur, en conservant les #marqueurs (et en changeant la nouvelle ligne #en entrée également). #Si vous le souhaitez, vous pouvez remplacer le retour par des sauts de ligne dans la sortie pour plus de lisibilité. Par exemple:

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

||--
||--

|--|
|--|

--||
--||

----
----

Méthode:

• À partir de l'entrée, nous échangeons chaque ligne avec deux autres: une avec le premier 1changement en |et une avec les deux premiers 1en --. Nous faisons cela jusqu'à ce que nous ayons des lignes avec au moins deux 1.
• Quand il n'y a que des célibataires 1 , nous les avons remplacés par |des.
• Nous doublons chaque ligne et y ajoutons une nouvelle ligne supplémentaire et nous obtenons la sortie souhaitée.