Mon professeur Precalc a l’un de ses problèmes préférés qu’il a inventé (ou plus probablement une étole inspirée de xkcd ) qui implique une rangée d’ nurinoirs. "Checkmate" est une situation dans laquelle chaque urinal est déjà occupé OU a un urinoir occupé à côté. Par exemple, si une personne est un X, alors

X-X--X

est considéré comme maté. Notez qu'une personne ne peut pas occuper un urinoir à côté d'un urinoir déjà occupé.

Tâche

Votre programme utilisera un nombre stdin, des arguments de ligne de commande ou un argument de fonction. Votre programme imprimera ensuite ou renverra le nombre de façons dont Checkmate peut se produire avec le nombre d’urinaux entrés.

Exemples

0 -> 1(cas nul compte comme mat)
1 -> 1( X)
2 -> 2( X-ou -X)
3 -> 2( X-Xou -X-)
4 -> 3( X-X-, -X-X, ou X--X)
5 -> 4( X-X-X, X--X-, -X-X-, ou -X--X)
6 -> 5( X-X-X-, X--X-X, X-X--X, -X--X-ou -X-X-X)
7 -> 7( X-X-X-X, X--X-X-, -X-X--X, -X--X-X, X-X--X-, X--X--Xou -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-)
...

Notation

Le plus petit programme en octets gagne.

Oasis , 5 octets

Code

cd+2V

Version étendue

cd+211

Explication

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

Essayez-le en ligne!

Java 7, 65 42 octets

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

La séquence ajoute simplement les éléments précédents pour en obtenir de nouveaux. Chapeau pointe à orlp et Rod pour cette méthode plus courte;)

Vieux:

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

Après le cinquième élément, l’écart dans la séquence augmente de l’élément cinq précédent.

Python 2, 42 40 39 35 octets

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

Générer les ensembles réels:

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")]

Ruby, 58 34 octets

Fortement inspiré par la réponse Java originale de Geobits.

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

Voir sur repl.it: https://repl.it/Dedh/1

Premier essai

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

Voir sur repl.it: https://repl.it/Dedh

Python, 33 octets

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

Utilise les cas de base décalés f(-1) = f(0) = f(1) = 1. Si Truepouvait être utilisé pour 1, nous n’aurions pas besoin de 3 octets pour le +().

J, 31 27 23 octets

4 octets sauvés grâce aux miles!

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

Une explication est à venir bientôt.

Ancienne solution

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

Ceci est un agenda. Le LHS est un gérond composé de deux verbes: >.1&^et -&3+&$:-&2. Le premier est utilisé si la condition ( 2&<) échoue. Cela signifie que la fourchette >.1&^est activée sur l'argument. Observer:

   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

Ici, >.prend le maximum de deux valeurs. Ainsi, il donne 1, 1 et 2 comme termes initiaux.

Le deuxième verbe dans le gérondif est une fourchette:

-&3 +&$: -&2

Les dents gauche et droite sont appliquées au verbe, en soustrayant 3 et 2 respectivement; alors le verbe du milieu est appelé avec des arguments gauche et droit égaux à ceux-ci. $:appelle le verbe sur chaque argument et +ajoute les deux. C'est fondamentalement équivalent à($: arg - 3) + ($: arg - 2)

Cas de test

   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 octets

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

Essayez-le en ligne! Ou vérifiez tous les cas de test .

Explication

Deux convolutions! Yay!

Cela construit un tableau, dit A, où chaque configuration possible est une ligne. 1dans ce tableau représente une position occupée. Par exemple, pour l’entrée, 4le tableau A est

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

Le code convoque ensuite le tableau A avec [1 1 1]. Cela donne un tableau B. Les positions occupées et les voisins des positions occupées dans A donnent un résultat non nul dans le tableau B:

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

Donc, la première condition pour qu'une configuration soit un compagnon est que B ne contienne aucun zéros dans cette ligne. Cela signifie que dans cette rangée de A, il n'y a pas de positions vides, ou il y en avait mais étaient voisins des positions occupées.

Nous avons besoin d'une deuxième condition. Par exemple, la dernière ligne remplit la condition ci-dessus, mais ne fait pas partie de la solution car la configuration n'était pas valide pour commencer. Une configuration valide ne peut pas avoir deux positions occupées voisines, c'est-à-dire ne peut pas avoir deux contigus 1dans A. De la même manière, elle ne peut pas avoir deux valeurs contiguës dans B dépassant 1. Donc, nous pouvons le détecter en convoquant B avec [1 1]et en vérifiant que, dans le tableau résultant, C,

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

aucune valeur dans cette ligne ne dépasse 3. Le résultat final est le nombre de configurations qui remplissent les deux conditions.

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 octets

+3 pour n=1; +9 pour $argv, -1-3 joué au golf
-20: remarqué que je n'ai pas à faire les combinaisons, mais seulement leur compte

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

courir avec -r

boucle de 2 ** n-1 à 0:

• vérifier la représentation binaire à n chiffres pour 11, 000, 00au début ou à la fin, ou un seul0
• si aucune correspondance, augmenter le résultat

résultat d'impression

même taille, regex légèrement plus simple

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

• boucle de 2 ** n-1 à 1 (au lieu de 0)
• vérifier la représentation binaire pour 11, 00au début ou à la fin, ou000
• n'imprime rien pour n = 0

PHP, 82 octets

La réponse d’Arnauld a porté et joué au golf :

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

n'imprime rien pour n = 0

Gelée , 11 octets

,’fR_2߀So1

Essayez-le en ligne! ou vérifier tous les cas de test .

Comment ça marche

,’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) / Récursif, 30 à 27 octets

Edit: sauvegardé 3 octets grâce à 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) / Non récursif 90 77 octets

Edit: 13 octets sauvegardés grâce à Conor O'Brien et Titus

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 octets

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

Définit une fonction a. Prend un entier en entrée et retourne un entier en sortie. Solution récursive simple.

AnyDice , 51 octets

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

Il devrait y avoir plus de réponses AnyDice ici.

Ma solution définit une fonction récursive qui calcule a(n)=a(n-2)+a(n-3). Elle retourne a(0)=a(1)=1et en a(2)=2utilisant la magie de la division entière.

Essayez-le en ligne

Remarque: le résultat peut paraître étrange, car il est généralement utilisé pour générer des probabilités de dés. Il suffit de regarder le nombre à gauche du graphique à barres.

Perl, 35 à 34 octets

Comprend +1 pour -p

Donnez votre avis sur STDIN

checkmate.pl <<< 8

checkmate.pl:

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

Une formule secrète nouvellement développée. Ripple met à jour 3 variables d'état sans avoir besoin d'assignations parallèles.

Il est tout aussi court (mais beaucoup plus lent et prenant beaucoup plus de mémoire) de résoudre simplement le problème initial:

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

mais cela ne fonctionne pas pour 0

JavaScript (ES6), 62 octets

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

C'est la première fois que j'ai besoin de deux noms de variables factices. Une version récursive serait probablement plus courte, mais j'aime beaucoup reduce... Edit: Une solution, également de 62 octets, a été trouvée.

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

Gelée , 19 octets

La solution récursive est probablement plus courte ...

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

Voir à TryItOnline
Ou voir la série pour n = [0, 99], également à TryItOnline

Comment?

Retourne le n+3nombre de Padovan en comptant les combinaisons

Ḥ⁹_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 octets

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

L'entrée doit être présente sur la pile au démarrage du programme, donc +2 octets pour le -vdrapeau. Essayez-le en ligne!

La première ligne initialise la pile sur 1 1 2 n, où nest le numéro saisi. La deuxième ligne, en marche arrière, vérifie que la valeur nest supérieure à 1. Si c'est le cas, elle nest décrémentée et l'élément suivant de la séquence est généré comme suit:

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

La dernière ligne affiche le nombre au bas de la pile, qui est l'élément requis de la séquence.

CJam , 20 octets

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

Essayez-le en ligne!

Explication

Ceci utilise la relation de récurrence indiquée dans la page 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 octets

XXXIGX@DŠ0@+

Explication

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

Essayez-le en ligne!

FRACTRAN, 104 93 octets

L'entrée est 11**n*29et la sortie est 29**checkmate(n).

C’est surtout pour le plaisir, d’autant plus que Python, JS et Java me font perdre leur identité . Même nombre d’octets que PHP: D suggestions de golf bienvenues.

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

En fait, 25 octets

Cela semble un peu long pour une f(n) = f(n-2) + f(n-3)relation de récurrence simple . Les suggestions de golf sont les bienvenues. Essayez-le en ligne!

╗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.

En fait , 18 octets

Ceci est en fait un port de la réponse de Jelly plus longue de Dennis. Les suggestions de golf sont les bienvenues. Essayez-le en ligne!

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 octets

ÉKΦΘÄO¢

Exécuter et déboguer

Utilise la relation de récurrence. C(n) = C(n-2) + C(n-3)

C (gcc) , 33 octets

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

Essayez-le en ligne!

Haskell , 27 octets

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

Essayez-le en ligne!