34
\$\begingroup\$

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.

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.

\$\endgroup\$
  • 3
    \$\begingroup\$ Related. \$\endgroup\$ – betseg Sep 21 '16 at 16:43
  • 3
    \$\begingroup\$ Related \$\endgroup\$ – mbomb007 Sep 21 '16 at 16:51
  • 12
    \$\begingroup\$ 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. \$\endgroup\$ – orlp Sep 21 '16 at 17:24
  • 12
    \$\begingroup\$ oeis.org/A228361 \$\endgroup\$ – DJMcMayhem Sep 21 '16 at 17:32
  • 18
    \$\begingroup\$ No toilet at all is indeed a checkmate situation. :D \$\endgroup\$ – Titus Sep 21 '16 at 19:37

23 Answers 23

20
\$\begingroup\$

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!

\$\endgroup\$
  • 7
    \$\begingroup\$ This is a strange answer, the language was created about a month ago with no proper documentation in the repo.... \$\endgroup\$ – user56309 Sep 21 '16 at 17:29
  • 2
    \$\begingroup\$ @tuskiomi It do have a doc, in info.txt \$\endgroup\$ – TuxCrafting Sep 21 '16 at 17:30
  • 6
    \$\begingroup\$ @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. \$\endgroup\$ – user56309 Sep 21 '16 at 17:35
  • 1
    \$\begingroup\$ @tuskiomi info.txt is useful, it contains a documentation for every Oasis commands \$\endgroup\$ – TuxCrafting Sep 21 '16 at 17:38
  • 8
    \$\begingroup\$ @tuskiomi That's the result of procrastination and lazyness. I'll try to add a concise documentation on how the actual language works today. \$\endgroup\$ – Adnan Sep 21 '16 at 17:38
12
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ If u=3 then your function returns 1 but the examples show that it should be 2. \$\endgroup\$ – Poke Sep 21 '16 at 17:36
  • \$\begingroup\$ Oops! I was using my f function from the other snippet instead of recursing. Stupid me, fixing... \$\endgroup\$ – Geobits Sep 21 '16 at 17:40
  • 1
    \$\begingroup\$ Can't that last part (u>0?u:1;) become 1;? \$\endgroup\$ – Conor O'Brien Sep 21 '16 at 17:45
  • 2
    \$\begingroup\$ @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. \$\endgroup\$ – Geobits Sep 21 '16 at 17:50
  • 1
    \$\begingroup\$ 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 \$\endgroup\$ – Rod Sep 21 '16 at 19:54
9
\$\begingroup\$

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")]
\$\endgroup\$
8
\$\begingroup\$

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

\$\endgroup\$
6
\$\begingroup\$

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

\$\endgroup\$
6
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

MATL, 25 23 bytes

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

Try it online! Or check all test cases.

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)
\$\endgroup\$
4
\$\begingroup\$

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

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

Jelly, 11 bytes

,’fR_2߀So1

Try it online! or verify all test cases.

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.
\$\endgroup\$
  • 2
    \$\begingroup\$ How does this work? Does it use the recursive formula, or something else? \$\endgroup\$ – Conor O'Brien Sep 21 '16 at 23:13
  • \$\begingroup\$ @ConorO'Brien Yes, it uses the recursive formula. I've added an explanation. \$\endgroup\$ – Dennis Sep 22 '16 at 0:09
4
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ I think ((i|r|l)&(k-1)) can become ((i|r|l)&k-1), or even ((i|r|l)&~-k) \$\endgroup\$ – Conor O'Brien Sep 21 '16 at 17:33
  • \$\begingroup\$ one byte: i<<1 -> i*2 or i+i \$\endgroup\$ – Titus Sep 21 '16 at 18:02
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Titus Sep 21 '16 at 18:18
  • \$\begingroup\$ &(k-1) needs no parens anyway; but you can use &~k instead. \$\endgroup\$ – Titus Sep 21 '16 at 18:58
  • 1
    \$\begingroup\$ i'm just gonna leave this here: f=n=>n<3?n||1:f(n-2)+f(n-3) \$\endgroup\$ – Shaun H Sep 22 '16 at 15:03
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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)
\$\endgroup\$
2
\$\begingroup\$

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

+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
\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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# Add them
              ;;;      e# Discard the last three elements
                 o     e# Output
                  ];   e# Discard the rest to avoid implicit display
\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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).
\$\endgroup\$
1
\$\begingroup\$

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.
\$\endgroup\$
1
\$\begingroup\$

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.
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.
\$\endgroup\$
0
\$\begingroup\$

Stax, 7 bytes

ÉKΦΘÄO¢

Run and debug it

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

\$\endgroup\$
0
\$\begingroup\$

C (gcc), 33 bytes

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

Try it online!

New contributor
jnfnt is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.