[Question]
  [
My Precalc teacher has one of his favorite problems that he made up (or more likely ~~stole~~ inspired by [xkcd](https://blog.xkcd.com/2009/09/02/urinal-protocol-vulnerability/)) that involves a row of `n` urinals. "Checkmate" is a situation in which every urinal is already occupied OR has an occupied urinal next to them. For instance, if a person is an `X`, then
`X-X--X`
is considered checkmate. Note that a person cannot occupy a urinal next to an already occupied urinal.
## Task
Your program will take a number through `stdin`, command line args, or a function argument. Your program will then print out or return the number of ways that checkmate can occur in with the inputted number of urinals.
## Examples
`0 -> 1` (the null case counts as checkmate)  
`1 -> 1` (`X`)  
`2 -> 2` (`X-` or `-X`)  
`3 -> 2` (`X-X` or `-X-`)  
`4 -> 3` (`X-X-`, `-X-X`, or `X--X`)  
`5 -> 4` (`X-X-X`, `X--X-`, `-X-X-`, or `-X--X`)  
`6 -> 5` (`X-X-X-`, `X--X-X`, `X-X--X`, `-X--X-` or `-X-X-X`)  
`7 -> 7` (`X-X-X-X`, `X--X-X-`, `-X-X--X`, `-X--X-X`, `X-X--X-`, `X--X--X` or `-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-`)  
`...`
## Scoring
The smallest program in bytes wins.
  
[Answer]
# [Oasis](http://github.com/Adriandmen/Oasis), 5 bytes
**Code**
```
cd+2V
```
**Extended version**
```
cd+211
```
**Explanation**
```
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
```
[Try it online!](http://oasis.tryitonline.net/#code=Y2QrMlY&input=&args=OA)
[Answer]
## Java 7, ~~65~~ 42 bytes
```
int g(int u){return u>1?g(u-2)+g(u-3):1;}
```
The sequence just adds previous elements to get new ones. Hat tip to orlp and Rod for this shorter method ;)
**Old:**
```
int f(int u){return u<6?new int[]{1,1,2,2,3,4}[u]:f(u-1)+f(u-5);}
```
After the fifth element, the gap in the sequence rises by the element five previous.
[Answer]
# Python 2, 42 40 39 35 bytes
```
f=lambda n:n>1and f(n-2)+f(n-3)or 1
```
Generating the actual sets:
```
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")]
```
[Answer]
# Ruby, ~~58~~ 34 bytes
Heavily inspired by Geobits' original Java answer.
```
f=->n{n<3?n:n<6?n-1:f[n-1]+f[n-5]}
```
See it on repl.it: <https://repl.it/Dedh/1>
## First attempt
```
->n{(1...2**n).count{|i|!("%0#{n}b"%i)[/11|^00|000|00$/]}}
```
See it on repl.it: <https://repl.it/Dedh>
[Answer]
## Python, 33 bytes
```
f=lambda n:+(n<2)or f(n-2)+f(n-3)
```
Uses the shifted base cases `f(-1) = f(0) = f(1) = 1`. If `True` could be used for 1, we would not need 3 bytes for the `+()`.
[Answer]
# J, ~~31~~ ~~27~~ 23 bytes
*Saved 4 bytes thanks to miles!*
```
0{]_&(]}.,+/@}:)1 1 2"_
```
An explanation is to come soon.
## Old solution
```
(>.1&^)`(-&3+&$:-&2)@.(2&<)
```
This is an agenda. The LHS is a gerund composed of two verbs: `>.1&^` and `-&3+&$:-&2`. The first one is used if the condition (`2&<`) fails. That means the fork `>.1&^` is activated over the argument. Observe:
```
   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
```
Here, `>.` takes the max of two values. Thus, it yields 1, 1, and 2 as the initial terms.
The second verb in the gerund is a fork:
```
-&3 +&$: -&2
```
The left and right tines are applied to the verb, subtracting 3 and 2 respectively; then the middle verb is called with left and right arguments equal to those. `$:` calls the verb on each argument, and `+` adds those two. It's basically equivalent to `($: arg - 3) + ($: arg - 2)`
### Test cases
```
   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
```
[Answer]
# [MATL](http://github.com/lmendo/MATL), ~~25~~ 23 bytes
```
W:qB7BZ+t!XAw3BZ+!3>a>s
```
[Try it online!](http://matl.tryitonline.net/#code=VzpxQjdCWit0IVhBdzNCWishMz5hPnM&input=NQ) Or [check all test cases](http://matl.tryitonline.net/#code=IkAKVzpxQjdCWit0IVhBdzNCWishMz5hPnMKRA&input=MDo4).
### Explanation
*Two* convolutions! Yay!
This builds an array, say A, where each possible configuration is a row. `1` in this array represents an occupied position. For example, for input `4` the array A is
```
0 0 0 0
0 0 0 1
0 0 1 0
···
1 1 1 0
1 1 1 1
```
The code then convolves array A with `[1 1 1]`. This gives an array B. Occupied positions and neighbours of occupied positions in A give a nonzero result in array B:
```
0 0 0 0
0 0 1 1
0 1 1 1
···
2 3 2 1
2 3 3 2
```
So the first condition for a configuration to be a checkmate is that B contains no zeros in that row. This means that in that row of A there no empty positions, or there were some but were neighbours of occupied positions.
We need a second condition. For example, the last row fulfills the above condition, but is not part of the solution because the configuration was not valid to begin with. A valid configurations cannot have two neighbouring occupied positions, i.e cannot have two contiguous `1`'s in A. Equivalently, it cannot have two contiguous values in B exceeding `1`. So we can detect this by convolving B with `[1 1]` and checking that in the resulting array, C,
```
0 0 0 0
0 1 2 1
1 2 2 1
···
5 5 3 1
5 6 5 2
```
no value in that row exceeds `3`. The final result is the number of configurations that fulfill the two 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)
```
[Answer]
# PHP, ~~105~~ ~~113~~ 93 bytes
+3 for `n=1`; +9 for `$argv`, -1-3 golfed  
-20: noticed that I don´t have to the combinations, but only their count
```
for($i=1<<$n=$argv[1];$i--;)$r+=!preg_match("#11|(0|^)0[0,]#",sprintf("%0{$n}b,",$i));echo$r;
```
run with `-r`
loop from 2\*\*n-1 to 0:
* check binary n-digit representation for `11`, `000`, `00` at the beginning or the end, or a single `0`
* if no match, increase result
print result
**same size, slightly simpler regex**
```
for($i=1<<$n=$argv[1];--$i;)$r+=!preg_match("#11|^00|00[,0]#",sprintf("%0{$n}b,",$i));echo$r;
```
* loop from 2\*\*n-1 to 1 (instead of 0)
* check binary representation for `11`, `00` at the beginning or the end, or `000`
* prints nothing for n=0
**PHP, 82 bytes**
[Arnauld´s answer](https://codegolf.stackexchange.com/q/94085#94085) ported and golfed:
```
for($i=$k=1<<$n=$argv[1];--$i;)$r+=!($i&$x=$i/2|$i*2)&&(($i|$x)&~$k)==$k-1;echo$r;
```
prints nothing for n=0
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 11 [bytes](https://github.com/DennisMitchell/jelly/wiki/Code-page)
```
,’fR_2ß€So1
```
[Try it online!](http://jelly.tryitonline.net/#code=LOKAmWZSXzLDn-KCrFNvMQ&input=&args=MTk) or [verify all test cases](http://jelly.tryitonline.net/#code=LOKAmWZSXzLDn-KCrFNvMQo54bi2wrXFvMOH4oKsRw&input=).
### How it works
```
,’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.
```
[Answer]
# JavaScript (ES6) / Recursive, ~~30~~ 27 bytes
*Edit: saved 3 bytes thanks to 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-recursive ~~90~~ 77 bytes
*Edit: saved 13 bytes thanks to Conor O'Brien and 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));
}
```
[Answer]
# Mathematica, 35 bytes
```
a@0=a@1=1;a@2=2;a@b_:=a[b-2]+a[b-3]
```
Defines a function `a`. Takes an integer as input and returns an integer as output. Simple recursive solution.
[Answer]
# [AnyDice](http://anydice.com), 51 bytes
```
function:A{ifA<3{result:(A+2)/2}result:[A-2]+[A-3]}
```
There should be more AnyDice answers around here.
My solution defines a recursive function that calculates `a(n)=a(n-2)+a(n-3)`. It returns `a(0)=a(1)=1` and `a(2)=2` using some integer division magic.
[Try it online](http://anydice.com/program/96c7)
Note: the output may look weird, and that's because it's usually used to output dice probabilities. Just look at the number to the left of the bar chart.
[Answer]
# Perl, ~~35~~ 34 bytes
Includes +1 for `-p`
Give input on STDIN
```
checkmate.pl <<< 8
```
`checkmate.pl`:
```
#!/usr/bin/perl -p
$\+=$b-=$.-=$\-$b*4for(++$\)x$_}{
```
A newly developed secret formula. Ripple update 3 state variables without the need for parallel assignments.
It is equally short (but a lot slower and taking a lot more memory) to just solve the original problem:
```
#!/usr/bin/perl -p
$_=grep!/XX|\B-\B/,glob"{X,-}"x$_
```
but that doesn't work for `0`
[Answer]
## JavaScript (ES6), 62 bytes
```
n=>[1,...Array(n)].reduce(($,_,i,a)=>a[i]=i<3?i:a[i-3]+a[i-2])
```
This is the first time that I've needed two dummy variable names. A recursive version would probably be shorter, but I really like `reduce`... Edit: Found a solution, also 62 bytes, which only has one dummy variable:
```
n=>[1,...Array(n)].reduce((p,_,i,a)=>a[i]=i<5?i+2>>1:a[i-5]+p)
```
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 19 [bytes](https://github.com/DennisMitchell/jelly/wiki/Code-page)
The recursive solution [is ~~probably~~](https://codegolf.stackexchange.com/a/94125/53748) shorter...
```
Ḥ⁹_c@⁸
+3µ:2R0;ç€µS
```
See it at **[TryItOnline](http://jelly.tryitonline.net/#code=4bik4oG5X2NA4oG4CiszwrU6MlIwO8On4oKswrVT&input=&args=OQ)**  
Or see the series for `n = [0, 99]`, also at **[TryItOnline](http://jelly.tryitonline.net/#code=4bik4oG5X2NA4oG4CiszwrU6MlIwO8On4oKswrVTCsKz4bi2w4figqw&input=)**
How?
Returns the `n+3`th Padovan's number by counting combinations
```
Ḥ⁹_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
```
[Answer]
# [><>](https://esolangs.org/wiki/Fish), 25+2 = 27 bytes
```
211rv
v!?:<r@+@:$r-1
>rn;
```
Needs the input to be present on the stack at program start, so +2 bytes for the `-v` flag. [Try it online!](http://fish.tryitonline.net/#code=MjExcnYKdiE_OjxyQCtAOiRyLTEKPnJuOw&input=&args=LXYgOA)
The first line initialises the stack to `1 1 2 n`, where `n` is the input number. The second line, running backwards, checks that `n` is greater than 1. If it is, `n` is decremented and the next element in the sequence is generated as follows:
```
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
```
The final line outputs the number on the bottom of the stack, which is the required element in the sequence.
[Answer]
# FRACTRAN, ~~104~~ 93 bytes
Input is `11**n*29` and output is `29**checkmate(n)`.
This is mostly for fun, especially since I'm currently being outgolfed by Python, JS, *and* Java. Same number of bytes as PHP though :D Golfing suggestions welcome.
```
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).
```
[Answer]
# [CJam](http://sourceforge.net/projects/cjam/), 20 bytes
```
1_2_{2$2$+}ri*;;;o];
```
[Try it online!](http://cjam.tryitonline.net/#code=MV8yX3syJDIkK31yaSo7OztvXTs&input=OA)
### Explanation
This uses the recurrence relationship shown in the [OEIS page](http://oeis.org/A228361).
```
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
```
[Answer]
# [05AB1E](http://github.com/Adriandmen/05AB1E), 12 bytes
```
XXXIGX@DŠ0@+
```
**Explanation**
```
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
```
[Try it online!](http://05ab1e.tryitonline.net/#code=WFhYSUdYQETFoDBAKw&input=MTU)
[Answer]
# Actually, 25 bytes
This seems a little long for a simple `f(n) = f(n-2) + f(n-3)` recurrence relation. Golfing suggestions welcome. [Try it online!](http://actually.tryitonline.net/#code=4pWXMjEx4pWcwqxgKTsoKylgbmFr4pWcMuKVnDI8SUBF&input=OA)
```
╗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.
```
[Answer]
# [Actually](https://github.com/Mego/Seriously), 18 bytes
This is an Actually port of Dennis' longer Jelly answer. Golfing suggestions welcome. [Try it online!](https://tio.run/##ASwA0/9hY3R1YWxsef//Mys74pWWwr1MdXLijKA7z4TilZwtQOKWiOKMoU3Oo///OQ "Actually – Try It 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.
```
[Answer]
# [Haskell](https://www.haskell.org/), 27 bytes
```
r=1:1:2:zipWith(+)r(tail r)
```
[Try it online!](https://tio.run/##y0gszk7Nyfn/v8jW0MrQysiqKrMgPLMkQ0Nbs0ijJDEzR6FI839uYmaebUFRZl6JQnSRomJFTYWNbrShnp6RQWzsfwA "Haskell – Try It Online")
[Answer]
# [Vyxal](https://github.com/Vyxal/Vyxal), 7 bytes
```
⁺»‡_+TḞ
```
[Try it Online!](https://vyxal.pythonanywhere.com/?v=2&c=1#WyIiLCIiLCLigbrCu+KAoV8rVOG4niIsIiIsIiJd)
Uses the same recurrence relation `a(n) = a(n-2) + a(n-3)`
```
      Ḟ # Create an infinite list
⁺»      # Starting from digits of 112
  ‡     # Generate new terms by a function
     T  # Taking in the last three terms
   _    # Pop the first
    +   # Add the other two together
```
[Answer]
# [Stax](https://github.com/tomtheisen/stax), 7 [bytes](https://github.com/tomtheisen/stax/blob/master/docs/packed.md#packed-stax)
```
ÉKΦΘÄO¢
```
[Run and debug it](https://staxlang.xyz/#p=904be8e98e4f9b&i=1%0A2%0A3%0A4%0A5%0A6%0A7%0A8%0A9&a=1&m=2)
Uses the recurrence relation. `C(n) = C(n-2) + C(n-3)`
[Answer]
# [C (gcc)](https://gcc.gnu.org/), 33 bytes
```
f(n){return n<2?1:f(n-2)+f(n-3);}
```
[Try it online!](https://tio.run/##Fcg9CoAwDEDh3VMEQUioBa2b9eciLlKtZDBK0Uk8e63Le/A5vTkXo0ehJ6zXHQSkM2PdJtGG1L@G7Bv3mQXpAX8EZLmA@8pyZ1KUIjhDMo95sYAeoFgmyUsuPTKRhTeLHw "C (gcc) – Try It Online")
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E/wiki/Commands), 8 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage)
```
ƵBSλè₂₃+
```
[Try it online](https://tio.run/##yy9OTMpM/f//2Fan4HO7D6941NT0qKlZ@/9/CwA) or [verify the infinite list](https://tio.run/##yy9OTMpM/f//2Fan4HO7HzU1PWpq1v7/HwA).
**Explanation:**
```
ƵB        # Push compressed integer 112
  S       # Convert it to a list of digits: [1,1,2]
   λ      # Start a recursive environment,
    è     # to output the 0-based (implicit) input'th value
          # (which will be output implicitly as result afterwards)
ƵBS       # Starting at a(0)=1, a(1)=1, a(2)=2
          # And where every following a(n) is calculated as:
     ₂₃+  #  a(n-2) + a(n-3)
```
[See this 05AB1E tip of mine (section *How to compress large integers?*)](https://codegolf.stackexchange.com/a/166851/52210) to understand why `ƵB` is `112`.
]