Mój nauczyciel Precalc ma jeden ze swoich ulubionych problemów, które wymyślił (lub bardziej prawdopodobne, że ukradł zainspirowany xkcd ), który dotyczy szeregu npisuarów. „Szach-mat” to sytuacja, w której każdy pisuar jest już zajęty LUB ma obok niego zajęty pisuar. Na przykład, jeśli dana osoba jest X, to

X-X--X

jest uważany za mat. Pamiętaj, że osoba nie może zajmować pisuaru obok już zajętego pisuaru.

Zadanie

Twój program przyjmie liczbę stdin, argumenty wiersza poleceń lub argument funkcji. Twój program wydrukuje następnie lub zwróci liczbę sposobów, w jakie może wystąpić mat z wprowadzoną liczbą pisuarów.

Przykłady

0 -> 1(zero przypadku liczona jako mata)
1 -> 1( X)
2 -> 2( X-i -X)
3 -> 2( X-Xi -X-)
4 -> 3( X-X-, -X-X, a X--X)
5 -> 4( X-X-X, X--X-, -X-X-, a -X--X)
6 -> 5( X-X-X-, X--X-X, X-X--X, -X--X-i -X-X-X)
7 -> 7( X-X-X-X, X--X-X-, -X-X--X, -X--X-X, X-X--X-, X--X--Xi -X-X-X-)
8 -> 9( -X--X--X, -X--X-X-, -X-X--X-, -X-X-X-X, X--X--X-, X--X-X-X, X-X--X-X, X-X-X--X, X-X-X-X-)
...

Punktacja

Najmniejszy program w bajtach wygrywa.

Oaza , 5 bajtów

Kod

cd+2V

Rozszerzona wersja

cd+211

Wyjaśnienie

1 = a(0)
1 = a(1)
2 = a(2)

a(n) = cd+
       c      # Calculate a(n - 2)
        d     # Calculate a(n - 3)
         +    # Add them up

Wypróbuj online!

Java 7, 65 42 bajtów

int g(int u){return u>1?g(u-2)+g(u-3):1;}

Sekwencja po prostu dodaje poprzednie elementy, aby uzyskać nowe. Kapelusz do orlp i Rod dla tej krótszej metody;)

Stary:

int f(int u){return u<6?new int[]{1,1,2,2,3,4}[u]:f(u-1)+f(u-5);}

Po piątym elemencie odstęp w sekwencji wzrasta o element pięć poprzednich.

Python 2, 42 40 39 35 bajtów

f=lambda n:n>1and f(n-2)+f(n-3)or 1

Generowanie rzeczywistych zestawów:

lambda n:["{:0{}b}".format(i,n).replace("0","-").replace("1","X")for i in range(2**n)if"11"not in"{:0{}b}".format(i*2,2+n).replace("000","11")]

Rubin, 58 34 bajtów

Mocno zainspirowany oryginalną odpowiedzią Javy na Geobits.

f=->n{n<3?n:n<6?n-1:f[n-1]+f[n-5]}

Zobacz na repl.it: https://repl.it/Dedh/1

Pierwsze podejscie

->n{(1...2**n).count{|i|!("%0#{n}b"%i)[/11|^00|000|00$/]}}

Zobacz na repl.it: https://repl.it/Dedh

Python, 33 bajty

f=lambda n:+(n<2)or f(n-2)+f(n-3)

Wykorzystuje przesunięte skrzynki podstawowe f(-1) = f(0) = f(1) = 1. Gdyby Truemożna było użyć dla 1, nie potrzebowalibyśmy 3 bajtów dla +().

J, 31 27 23 bajtów

Zaoszczędzone 4 bajty dzięki kilometrom!

0{]_&(]}.,+/@}:)1 1 2"_

Wyjaśnienie będzie wkrótce.

Stare rozwiązanie

(>.1&^)`(-&3+&$:-&2)@.(2&<)

To jest agenda. LHS jest gerundem złożonym z dwóch czasowników: >.1&^i -&3+&$:-&2. Pierwszy jest używany, jeśli warunek ( 2&<) nie powiedzie się. Oznacza to, że rozwidlenie >.1&^jest aktywowane nad argumentem. Przestrzegać:

   1 ^ 0 1 2
1 1 1
   (1&^) 0 1 2
1 1 1
   0 1 2 >. (1&^) 0 1 2
1 1 2
   (>.1&^) 0 1 2
1 1 2

Tutaj >.bierze maksymalnie dwie wartości. Zatem daje 1, 1 i 2 jako warunki początkowe.

Drugi czasownik w gerund to rozwidlenie:

-&3 +&$: -&2

Lewe i prawe zęby są stosowane do czasownika, odejmując odpowiednio 3 i 2; wtedy środkowy czasownik jest wywoływany z lewymi i prawymi argumentami równymi tym. $:wywołuje czasownik dla każdego argumentu i +dodaje te dwa. Jest to w zasadzie odpowiednik($: arg - 3) + ($: arg - 2)

Przypadki testowe

   f =: (>.1&^)`(-&3+&$:-&2)@.(2&<)
   f 0
1
   f 2
2
   f 4
3
   f 6
5
   f 8
9
   F =: f"0         NB. for tables
   F i.13
1 1 2 2 3 4 5 7 9 12 16 21 28
   i.13
0 1 2 3 4 5 6 7 8 9 10 11 12
   (,. F) i.13
 0  1
 1  1
 2  2
 3  2
 4  3
 5  4
 6  5
 7  7
 8  9
 9 12
10 16
11 21
12 28

MATL , 25 23 bajtów

W:qB7BZ+t!XAw3BZ+!3>a>s

Wypróbuj online! Lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie

Dwie zwoje! Tak!

To buduje tablicę, powiedzmy A, gdzie każda możliwa konfiguracja jest rzędem. 1w tej tablicy reprezentuje zajmowaną pozycję. Na przykład dla danych wejściowych 4tablica A to

0 0 0 0
0 0 0 1
0 0 1 0
···
1 1 1 0
1 1 1 1

Kod następnie przekształca tablicę A za pomocą [1 1 1]. Daje to tablicę B. Zajęte pozycje i sąsiedzi zajętych pozycji w A dają niezerowy wynik w tablicy B:

0 0 0 0
0 0 1 1
0 1 1 1
···
2 3 2 1
2 3 3 2

Zatem pierwszym warunkiem, aby konfiguracja była matą, jest to, że B nie zawiera zer w tym wierszu. Oznacza to, że w tym rzędzie A nie ma pustych pozycji lub były pewne, ale byli sąsiedzi zajętych pozycji.

Potrzebujemy drugiego warunku. Na przykład ostatni wiersz spełnia powyższy warunek, ale nie jest częścią rozwiązania, ponieważ konfiguracja nie była poprawna na początek. Prawidłowe konfiguracje nie mogą mieć dwóch sąsiednich zajętych pozycji, tj. Nie mogą mieć dwóch sąsiadujących ze sobą liter 1w A. Równolegle nie mogą mieć dwóch sąsiadujących wartości w B przekraczających 1. Możemy to wykryć, splatając B [1 1]i sprawdzając, że w wynikowej tablicy C,

0 0 0 0
0 1 2 1
1 2 2 1
···
5 5 3 1
5 6 5 2

żadna wartość w tym wierszu nie przekracza 3. Ostatecznym wynikiem jest liczba konfiguracji, które spełniają dwa warunki.

W:q    % Range [0 1 ... n-1], where n is implicit input
B      % Convert to binary. Each number produces a row. This is array A
7B     % Push array [1 1 1] 
Z+     % 2D convolution, keeping size. Entries that are 1 or are horizontal 
       % neighbours of 1 produce a positive value. This is array B
t!     % Duplicate and transpose (rows become columns)
XA     % True for columns that contain no zeros
w      % Swap. Brings array B to top
3B     % Push array [1 1]
Z+     % 2D convolution, keeping size. Two horizontally contiguous entries
       % that exceed 1 will give a result exeeding 3. This is array C
!      % Transpose
3>     % Detect entries that exceed 3
a      % True for columns that contain at least one value that exceeds 3
>      % Element-wise greater-than comparison (logical and of first
       % condition and negated second condition)
s      % Sum (number of true values)

PHP, 105 113 93 bajtów

+3 dla n=1; +9 za $argv, -1-3 grał w golfa
-20: zauważyłem, że nie muszę kombinować, ale tylko ich liczbę

for($i=1<<$n=$argv[1];$i--;)$r+=!preg_match("#11|(0|^)0[0,]#",sprintf("%0{$n}b,",$i));echo$r;

Biegnij z -r

pętla od 2 ** n-1 do 0:

• sprawdzić binarny n-cyfrową reprezentację 11, 000, 00na początku lub na końcu, czy pojedyncza0
• jeśli nie pasuje, zwiększ wynik

wydrukuj wynik

ten sam rozmiar, nieco prostsze wyrażenie regularne

for($i=1<<$n=$argv[1];--$i;)$r+=!preg_match("#11|^00|00[,0]#",sprintf("%0{$n}b,",$i));echo$r;

• pętla od 2 ** n-1 do 1 (zamiast 0)
• sprawdź reprezentację binarną dla 11, 00na początku lub na końcu, lub000
• nie drukuje nic dla n = 0

PHP, 82 bajty

Odpowiedź Arnaulda została przeniesiona i zagrana w golfa:

for($i=$k=1<<$n=$argv[1];--$i;)$r+=!($i&$x=$i/2|$i*2)&&(($i|$x)&~$k)==$k-1;echo$r;

nie drukuje nic dla n = 0

Galaretka , 11 bajtów

,’fR_2߀So1

Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe .

Jak to działa

,’fR_2߀So1  Main link. Argument: n

 ’           Decrement; yield n - 1.
,            Pair; yield [n, n - 1].
   R         Range; yield [1, ..., n].
  f          Filter; keep the elements that are common to both lists.
             This yields [n, n - 1] if n > 1, [1] if n = 1, and [] if n < 1.
    _2       Subtract 2 from both elements, yielding [n - 2, n - 3], [-1], or [].
      ߀     Recursively call the main link for each integer in the list.
        S    Take the sum of the resulting return values.
         o1  Logical OR with 1; correct the result if n < 1.

JavaScript (ES6) / Recursive, 30 27 bajtów

Edycja: zapisane 3 bajty dzięki Shaun H.

let

f=n=>n<3?n||1:f(n-2)+f(n-3)

for(var n = 1; n < 16; n++) {
  console.log(n, f(n));
}

JavaScript (ES6) / Nierekurencyjne 90 77 bajtów

Edycja: zapisano 13 bajtów dzięki Conorowi O'Brienowi i Tytusowi

let f =

n=>[...Array(k=1<<n)].map((_,i)=>r+=!(i&(x=i>>1|i+i))&&((i|x)&~k)==k-1,r=0)|r

for(var n = 1; n < 16; n++) {
  console.log(n, f(n));
}

Mathematica, 35 bajtów

a@0=a@1=1;a@2=2;a@b_:=a[b-2]+a[b-3]

Definiuje funkcję a. Pobiera liczbę całkowitą jako dane wejściowe i zwraca liczbę całkowitą jako wartość wyjściową. Proste rozwiązanie rekurencyjne.

AnyDice , 51 bajtów

function:A{ifA<3{result:(A+2)/2}result:[A-2]+[A-3]}

Tutaj powinno być więcej odpowiedzi AnyDice.

Moje rozwiązanie definiuje funkcję rekurencyjną, która oblicza a(n)=a(n-2)+a(n-3). Powraca a(0)=a(1)=1i a(2)=2używa magii podziału na liczby całkowite.

Wypróbuj online

Uwaga: wynik może wyglądać dziwnie, a to dlatego, że zwykle służy do wyrzucania prawdopodobieństwa kości. Wystarczy spojrzeć na liczbę po lewej stronie wykresu słupkowego.

Perl, 35 34 bajtów

Obejmuje +1 dla -p

Podaj dane na STDIN

checkmate.pl <<< 8

checkmate.pl:

#!/usr/bin/perl -p
$\+=$b-=$.-=$\-$b*4for(++$\)x$_}{

Nowo opracowana tajna formuła. Ripple aktualizuje 3 zmienne stanu bez potrzeby równoległych przypisań.

Jest równie krótki (ale o wiele wolniejszy i zajmuje dużo więcej pamięci), aby rozwiązać pierwotny problem:

#!/usr/bin/perl -p
$_=grep!/XX|\B-\B/,glob"{X,-}"x$_

ale to nie działa 0

JavaScript (ES6), 62 bajty

n=>[1,...Array(n)].reduce(($,_,i,a)=>a[i]=i<3?i:a[i-3]+a[i-2])

Po raz pierwszy potrzebuję dwóch fałszywych nazw zmiennych. Wersja rekurencyjna byłaby prawdopodobnie krótsza, ale naprawdę podoba mi się reduce... Edycja: Znaleziono rozwiązanie, również 62 bajty, które ma tylko jedną zmienną fikcyjną:

n=>[1,...Array(n)].reduce((p,_,i,a)=>a[i]=i<5?i+2>>1:a[i-5]+p)

Galaretka , 19 bajtów

Rozwiązanie rekurencyjne jest prawdopodobnie krótsze ...

Ḥ⁹_c@⁸
+3µ:2R0;瀵S

Zobacz na TryItOnline
Lub zobacz serię n = [0, 99], także na TryItOnline

W jaki sposób?

Zwraca n+3liczbę th Padovana, licząc kombinacje

Ḥ⁹_c@⁸ - Link 1, binomial(k, n-2k): k, n
Ḥ      - double(2k)
 ⁹     - right argument (n)
  _    - subtract (n-2k)
     ⁸ - left argument (k)
   c@  - binomial with reversed operands (binomial(k, n-2k))

+3µ:2R0;瀵S - Main link: n
  µ       µ  - monadic chain separation
+3           - add 3 (n+3)
   :2        - integer divide by 2 ((n+3)//2)
     R       - range ([1,2,...,(n+3)//2]
      0;     - 0 concatenated with ([0,1,2,...,(n+3)//2]) - our ks
        ç€   - call previous link as a dyad for each
           S - sum

> <> , 25 + 2 = 27 bajtów

211rv
v!?:<r@+@:$r-1
>rn;

Wymaga obecności danych wejściowych na stosie przy starcie programu, więc +2 bajty dla -vflagi. Wypróbuj online!

Pierwszy wiersz inicjuje stos do 1 1 2 n, gdzie njest liczbą wejściową. Drugi wiersz, biegnący do tyłu, sprawdza, że njest większy niż 1. Jeśli tak, njest zmniejszany, a następny element w sekwencji jest generowany w następujący sposób:

r$:@+@r              a(n-3) a(n-2) a(n-1) n

r        Reverse   - n a(n-1) a(n-2) a(n-3)
 $       Swap      - n a(n-1) a(n-3) a(n-2)
  :      Duplicate - n a(n-1) a(n-3) a(n-2) a(n-2)
   @     Rotate 3  - n a(n-1) a(n-2) a(n-3) a(n-2)
    +    Add       - n a(n-1) a(n-2) a(n)
     @   Rotate 3  - n a(n) a(n-1) a(n-2)
      r  Reverse   - a(n-2) a(n-1) a(n) n

Ostatni wiersz wyświetla liczbę na dole stosu, która jest wymaganym elementem w sekwencji.

CJam , 20 bajtów

1_2_{2$2$+}ri*;;;o];

Wypróbuj online!

Wyjaśnienie

Wykorzystuje to relację powtarzalności pokazaną na stronie OEIS .

1_2_                   e# Push 1, 1, 2, 2 as initial values of the sequence
           ri          e# Read input
    {     }  *         e# Repeat block that many times
     2$2$              e# Copy the second and third elements from the top
         +             e# Add them
              ;;;      e# Discard the last three elements
                 o     e# Output
                  ];   e# Discard the rest to avoid implicit display

05AB1E , 12 bajtów

XXXIGX@DŠ0@+

Wyjaśnienie

XXX            # initialize stack as 1, 1, 1
   IG          # input-1 times do:
     X@        # get the item 2nd from bottom of the stack
       DŠ      # duplicate and push one copy down as 2nd item from bottom of the stack
         0@    # get the bottom item from the stack
           +   # add the top 2 items of the stack (previously bottom and 2nd from bottom)
               # implicitly print the top element of the stack after the loop

Wypróbuj online!

FRACTRAN, 104 93 bajty

Wejście jest 11**n*29i wyjście jest 29**checkmate(n).

Jest to głównie dla zabawy, zwłaszcza, że ​​obecnie jestem obeznany z Pythonem, JS i Javą. Jednak taka sama liczba bajtów jak PHP: D Sugestie dotyczące gry w golfa mile widziane.

403/85 5/31 3/5 9061/87 3/41 37/3 667/74 37/23 7/37 38/91 7/19 5/77 1/7 1/17 1/2 340/121 1/11

Ungolfing

               At the start we have 11**n * 29
1/11           If n < 2, we remove the 11s and print 29**1
340/121        If n >= 2, we subtract two 11s (n-2) and add one 17, two 2s and one 5.
                 We now have 17**1 * 29**1 * 2**2 * 5.
                 These are the register for a, b, c at registers 17, 29, and 2.
                 5 is an indicator to start the first loop.
                 This loop will move a to register 13.
403/85 5/31    Remove the 17s one at a time, adds them to the 13 register.
                 5 and 31 reset the loop.
3/5            Next loop: moves b to a and adds b to a in register 13.
9061/87 3/41   Remove the 29s one at a time, adds them to the 17 and 13 registers.
                 3 and 41 reset the loop.
37/3           Next loop: moves c to b in register 29.
667/74 37/23   Remove the 2s one at a time, adds them to the 29 register.
                 37 and 23 reset the loop.
7/37           Next loop: moves a+b to c in register 2.
38/91 7/19     Remove the 13s one at a time, adds them to the 2 register.
                 7 and 19 reset the loop.
5/77           Move to the first loop if and only if we have an 11 remaining.
1/7 1/17 1/2   Remove the 7 loop indicator, and all 17s and 2s.
               Return 29**checkmate(n).

Właściwie 25 bajtów

Wydaje się to trochę za długie jak na f(n) = f(n-2) + f(n-3)relację nawrotu. Sugestie dotyczące gry w golfa mile widziane. Wypróbuj online!

╗211╜¬`);(+)`nak╜2╜2<I@E

Ungolfing

         Implicit input n.
╗        Save n to register 0.
211      Stack: 1, 1, 2. Call them a, b, c.
╜¬       Push n-2.
`...`n   Run the following function n-2 times.
  );       Rotate b to TOS and duplicate.
  (+       Rotate a to TOS and add to b.
  )        Rotate a+b to BOS. Stack: b, c, a+b
         End function.
ak       Invert the resulting stack and wrap it in a list. Stack: [b, c, a+b]
╜        Push n.
2        Push 2.
╜2<      Push 2 < n.
I        If 2<n, then 2, else n.
@E       Grab the (2 or n)th index of the stack list.
         Implicit return.

Właściwie 18 bajtów

To właściwie port dłuższej galaretki Dennisa. Sugestie dotyczące gry w golfa mile widziane. Wypróbuj online!

3+;╖½Lur⌠;τ╜-@█⌡MΣ

Ungolfing

         Implicit input n.
3+       Add 3. For readibility, m = n+3.
;╖       Duplicate and store one copy of m in register 0.
½Lu      floor(m/2) + 1.
r        Range from 0 to (floor(m/2)+1), inclusive.
⌠...⌡M   Map the following function over the range. Variable k.
  ;        Duplicate k.
  τ╜-      Push m-2k. Stack: [m-2k, k]
  @█       Swap k and m-2k and take binomial (k, m-2k).
            If m-2k > k, █ returns 0, which does not affect the sum() that follows.
         End function.
Σ        Sum the list that results from the map.
         Implicit return.

Stax , 7 bajtów

ÉKΦΘÄO¢

Uruchom i debuguj

Wykorzystuje relację powtarzalności. C(n) = C(n-2) + C(n-3)

C (gcc) , 33 bajty

f(n){return n<2?1:f(n-2)+f(n-3);}

Wypróbuj online!

Haskell , 27 bajtów

r=1:1:2:zipWith(+)r(tail r)

Wypróbuj online!