# Checkmate (aka the urinal problem)

My Precalc teacher has one of his favorite problems that he made up (or more likely stole inspired by xkcd) 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.

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.

• – betseg Sep 21 '16 at 16:43
• Related – mbomb007 Sep 21 '16 at 16:51
• The n=0 case should be 1. There is exactly one setup which is checkmate, and that's ''. This is the same as with factorial and permutations, 0! = 1, because there is exactly 1 way to arrange 0 items. – orlp Sep 21 '16 at 17:24
• oeis.org/A228361 – James Sep 21 '16 at 17:32
• No toilet at all is indeed a checkmate situation. :D – Titus Sep 21 '16 at 19:37

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


Try it online!

• This is a strange answer, the language was created about a month ago with no proper documentation in the repo.... – user56309 Sep 21 '16 at 17:29
• @tuskiomi It do have a doc, in info.txt – TuxCrafting Sep 21 '16 at 17:30
• @TùxCräftîñg sure, if you want to be technical. I could draw a horse and call it documentation towards my programming project. that doesn't make it useful, or decisive. – user56309 Sep 21 '16 at 17:35
• @tuskiomi info.txt is useful, it contains a documentation for every Oasis commands – TuxCrafting Sep 21 '16 at 17:38
• @tuskiomi That's the result of procrastination and lazyness. I'll try to add a concise documentation on how the actual language works today. – Adnan Sep 21 '16 at 17:38

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

• If u=3 then your function returns 1 but the examples show that it should be 2. – Poke Sep 21 '16 at 17:36
• Oops! I was using my f function from the other snippet instead of recursing. Stupid me, fixing... – Geobits Sep 21 '16 at 17:40
• Can't that last part (u>0?u:1;) become 1;? – Conor O'Brien Sep 21 '16 at 17:45
• @Jordan If there are zero urinals, then "every urinal is already occupied" in the one configuration possible. I believe the test case shown in the question is wrong. – Geobits Sep 21 '16 at 17:50
• You can replace u>0?u:1;) by 1; if you change the first comparison to u>1, then on u=2 the output will be g(0)+g(-1), which will be 2 – Rod Sep 21 '16 at 19:54

# Python 2, 424039 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")]


# 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

->n{(1...2**n).count{|i|!("%0#{n}b"%i)[/11|^00|000|00$/]}}  See it on repl.it: https://repl.it/Dedh ## 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 +(). # J, 3127 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


# MATL, 25 23 bytes

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


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


# PHP, 105113 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 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

• add 3 bytes for the new n=0: insert ?:1 before the final ; – Titus Sep 21 '16 at 19:36

# Jelly, 11 bytes

,’fR_2ß€So1


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

• How does this work? Does it use the recursive formula, or something else? – Conor O'Brien Sep 21 '16 at 23:13
• @ConorO'Brien Yes, it uses the recursive formula. I've added an explanation. – Dennis Sep 22 '16 at 0:09

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

• I think ((i|r|l)&(k-1)) can become ((i|r|l)&k-1), or even ((i|r|l)&~-k) – Conor O'Brien Sep 21 '16 at 17:33
• one byte: i<<1 -> i*2 or i+i – Titus Sep 21 '16 at 18:02
• You can use one variable for l and r, saving 6 bytes: !(i&(x=i>>1|i+i))&&((i|x)&(k-1))==k-1; and if you can insert ,k-- somewhere, you can replace k-1 with k to save parens. – Titus Sep 21 '16 at 18:18
• &(k-1) needs no parens anyway; but you can use &~k instead. – Titus Sep 21 '16 at 18:58
• i'm just gonna leave this here: f=n=>n<3?n||1:f(n-2)+f(n-3) – Shaun H Sep 22 '16 at 15:03

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

# AnyDice, 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

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.

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


# Jelly, 19 bytes

The recursive solution is probably shorter...

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


See it at TryItOnline
Or see the series for n = [0, 99], also at TryItOnline

How?

Returns the n+3th 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))

µ       µ  - monadic chain separation
: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
S - sum


# ><>, 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! 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. # CJam, 20 bytes 1_2_{2$2$+}ri*;;;o];  Try it online! ### Explanation This uses the recurrence relationship shown in the OEIS page. 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# Discard the last three elements
o     e# Output
];   e# Discard the rest to avoid implicit display


# 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!

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


# 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!

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


# Actually, 18 bytes

This is an Actually port of Dennis' longer Jelly answer. Golfing suggestions welcome. Try it online!

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


Ungolfing

         Implicit input n.
;╖       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 bytes

ÉKΦΘÄO¢


Run and debug it

Uses the recurrence relation. C(n) = C(n-2) + C(n-3)

# C (gcc), 33 bytes

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


Try it online!

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