Istnieje klasyczny wynik kombinatoryczny , w którym liczba sposobów na układanie 2*npaska według 1*2kostek domina to n- ^ta liczba Fibonacciego. Twoim celem jest wydrukowanie wszystkich pochyleń dla danego n, narysowanych za pomocą myślników i linii pionowych, takich jak 8 pochyleń dla n=5:

|————
|————

——|——
——|——

|||——
|||——

————|
————|

||——|
||——|

|——||
|——||

——|||
——|||

|||||
|||||

Masz dostarczyć program lub nazwaną funkcję, która przyjmuje ndane wejściowe i drukuje wymagane dane wyjściowe. Wygrywa najmniej bajtów.

Wejście

Liczba npomiędzy 1i 10włącznie poprzez STDIN lub wejście funkcji.

Wynik

Wydrukuj wszystkie możliwe nachylenia 2*npaska domina , rysowane w poziomie. Pochylenia mogą być w dowolnej kolejności, ale każda powinna pojawić się dokładnie raz. Muszą być oddzielone pustą linią.

Domino pionowe składa się z dwóch pionowych pasków ( |), a domino poziome składa się z dwóch kresek ( —). Możesz użyć łączników ( -) zamiast myślników em, aby pozostać w ASCII.

Z białymi znakami możesz zrobić wszystko, o ile wydruk będzie wyglądał tak samo.

C, 106

Wersja golfowa

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

Orginalna wersja

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

Jak to działa

Zmienna idziała od 1<<n-1zera do 0, tworząc wszystkie możliwe liczby binarne z ncyframi. 0 koduje |i 1 koduje dla -. Interesują nas liczby zawierające 1 w parach. Oczywiście liczby te można podzielić przez 3.

Gdy liczba jest dzielona przez 3, pierwotną liczbę można odzyskać, mnożąc wynik przez 2 i dodając go do siebie (skutecznie mutliplując przez 3). Większość liczb wymaga przeniesienia, ale gdy proces jest przeprowadzany na liczbach odsetki, nie jest wymagane przenoszenie, więc tylko w tych przypadkach można użyć LUB zamiast dodawania. Służy to do testowania interesujących liczb, ponieważ są one jedynymi, w których wyrażenie i/3|i/3*2zwraca pierwotną wartość i. Zobacz przykład poniżej.

1111= 15 ---> 0101= 5 ---> 1111= 15 (ważne, 0101|1010== 0101+1010)

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

Wartość testowa jest zawsze równa lub mniejsza niż wartość pierwotna. Ponieważ liczby, które nie są wielokrotnościami 3, zwracają również liczbę mniejszą od oryginału, gdy są dzielone przez 3, a następnie mnożone przez 3, test daje również pożądaną FAŁSZ na tych liczbach.

W oryginalnej wersji kilka pętli jsłuży do skanowania bitów ii generowania danych wyjściowych. W wersji golfowej stosowana jest pojedyncza forpętla, w której hprzebiega wszystkie liczby od (n*2)*(1<<n)-1zera do 0. Wartości isą generowane przez h/2/n. Zmienna jnie jest już używana, ponieważ równoważna ilość jest uzyskiwana z h%n. Użycie opcji n*2umożliwia drukowanie obu linii z tej samej pętli, z pewnym sprytnym multipleksowaniem w putsinstrukcji, aby wydrukować jedną lub dwie nowe linie na końcu wiersza.

Zauważ, że mięso to jest w położeniu przyrost for()wspornika i dlatego zostanie wykonany poi=h/2/h .

Próbka wyjściowa n = 6:

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

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

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

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

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

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

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

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

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

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

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

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

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

CJam, 33 27 bajtów

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

Dzięki @ jimmy23013 za grę w golfa z 6 bajtów!

Wypróbuj online!

tło

To jest iteracyjna implementacja algorytmu rekurencyjnego:

Możliwe nachylenia dla n można uzyskać przez dodanie pionowego domina do możliwych pochyleń dla n - 1 i dwóch poziomych domino do możliwych pochyleń dla n - 2 .

W ten sposób liczba przechyleń dla n jest sumą liczb przechyleń dla n - 1 i n - 2 , tj. N- ^ta liczba Fibonacciego.

Jak to działa

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

Przykładowy przebieg

$ 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 bajtów

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

fjest funkcją, która po podaniu liczby zwraca listę wszystkich wierszy wszystkich możliwych nachyleń Fibonacciego o możliwej długości n. nie ma znaczenia, że ​​zwraca jedną linię, ponieważ obie linie wszystkich nachyleń są takie same.

fDziała poprzez wywołanie rekurencyjne na n-1i n-2oraz dodanie "|"i "--"(odpowiednio) do strun.

gto funkcja, która odpowiada na pytania. w zasadzie wywołuje fdane wejściowe, podwaja każdy ciąg, aby wyświetlał dwie linie i łączył je wszystkimi znakami nowej linii.

przykładowe dane wyjściowe:

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

|||--
|||--

||--|
||--|

|--||
|--||

|----
|----

--|||
--|||

--|--
--|--

----|
----|

CJam, 42 37 bajtów

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

Liczę myślniki jako jeden bajt, ponieważ pytanie pozwala zastąpić je myślnikami ASCII.

Wypróbuj online.

Jak to działa

Aby uzyskać wszystkie możliwe nachylenia 2 × L , iterujemy wszystkie nieujemne liczby całkowite I <3 ^L , dzięki czemu parzyste cyfry w podstawie 3 odpowiadają poziomym domino, a cyfry nieparzyste pionowym.

Ponieważ każde I ma L lub mniej cyfr w podstawie 3, generuje to wszystkie możliwe sposoby pokrycia paska 2 × L. Pozostało tylko odfiltrować pokrycia większe lub mniejsze niż 2 × L i wydrukować pozostałe pokrycia.

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

Przykładowy przebieg

$ 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

Generuj konfiguracje z sekwencji bitów, 0 -> '-' i 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?'|':'--';
}

Testuj w firefox / firebug console

F(5)

Wynik

|----
|----

--|--
--|--

----|
----|

|||--
|||--

||--|
||--|

|--||
|--||

--|||
--|||

|||||
|||||

Haskell: 109 bajtów

To jest tłumaczenie znanego jedno-liniowego Haskella do leniwego obliczania sekwencji liczb Fibonacciego:

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

Główna sekwencja ciągów kafelków, bez golfa:

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

I dla porównania jednowarstwowa Fibonacciego:

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

Przykład użycia:

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

Kobra - 176

Nie mogę się doczekać, aż skończę pakiet golfowy 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 znak

Funkcja njako argument po prawej stronie.

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

Głównym źródłem tego golfa jest (];'--'&,"1@[,'|',"1])&>/. Pobiera to listę pochyleń długości (N-2) i (N-1) i zwraca listę przechyleń długości (N-1) i N. Jest to standardowa rekurencja Fibonacciego, algebra liniowa. ];zwraca prawą listę jako nową lewą (ponieważ nie ma zmian). '--'&,"1@[dodaje --kafelki do lewej listy, a '|',"1]dodaje |kafelki do prawej listy, a te razem są nową prawą listą.

Powtarzamy to w kółko n(to jest to @[&0) i zaczynamy od pustego kafelka i pojedynczego kafelka o długości 1. Następnie zwracamy pierwszą z pary z 0{::. Oznacza to, że jeśli uruchomimy to zero razy, zwracamy tylko pierwszą, tj. Pustą płytkę. Jeśli wykonamy to nrazy, obliczamy do pary ni ( n+1), ale odrzucamy tę drugą. To dodatkowa praca, ale mniej znaków.

Jest (1 2$,:)to coś, co J musi zrobić, aby przechyłki na listach były łatwo rozszerzalne. Sprawiamy, że lewa lista początkowa jest 1-elementową listą 2-wierszowej matrycy znaków, każdy wiersz ma długość 0. Prawa lista początkowa jest taka sama, ale wiersze mają długość 1 i są wypełnione |. Następnie dodajemy nowe kafelki do każdego wiersza i dołączamy listy macierzy, gdy łączymy ze sobą dwa zestawy nachyleń. Jest to proste zastosowanie pojęcia, które J nazywa rangą: zasadniczo manipuluje wymiarowością swoich argumentów i domyślnie zapętla się w razie potrzeby.

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

--|--
--|--

--|||
--|||

|----
|----

|--||
|--||

||--|
||--|

|||--
|||--

|||||
|||||

Go wypróbować na tryj.tk .

Python 3: 70 bajtów

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

Rekurencyjnie buduje wszystkie możliwe ciągi sreprezentujące jeden wiersz domin, które są powielane i drukowane. Rozpoczęcie sod znaku nowej linii powoduje, że pusta linia pojawia się automatycznie.

==Między dwoma połączeniami za fto tylko, aby wykonać zarówno wywołań funkcji. Zwykle zwracają się, Noneponieważ po prostu drukują i ==są jednym z niewielu zdefiniowanych operatorów None.

W ands i ors są w celu wytworzenia odpowiedniego zachowania Zwarcie do odtworzenia ifS i elseS w kodzie ungolfed.

Nie golfowany:

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

Siatkówka , 44 bajty

Uwaga: Retina jest młodsza od tego wyzwania.

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

Pobiera dane wejściowe jednoargumentowe z końcowym znakiem nowej linii.

Każda linia powinna przejść do własnego pliku i #powinna zostać zmieniona na nową linię w pliku. Jest to niepraktyczne, ale możesz uruchomić kod w postaci pliku z -sflagą, zachowując #znaczniki (i zmieniając znak nowej linii również #na wejściu). Możesz zmienić #powrót do nowych linii w wyjściu dla czytelności, jeśli chcesz. Na przykład:

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

||--
||--

|--|
|--|

--||
--||

----
----

Metoda:

• Zaczynając od danych wejściowych, zamieniamy każdą linię na dwie inne: jedną z pierwszą 1zmianą na |i jedną z pierwszymi dwoma 1zmienionymi na --. Robimy to, dopóki nie będziemy mieć linii z co najmniej dwoma kreskami 1.
• Kiedy zostały już tylko single 1, zmieniliśmy je na |.
• Podwajamy każdą linię i dodajemy do niej dodatkową nową linię i otrzymujemy pożądany wynik.