35
5
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.
3Related. – betseg – 2016-09-21T16:43:50.447
3Related – mbomb007 – 2016-09-21T16:51:26.110
2The test cases keep getting updated. Can we have a program to verify them once and for all? And preferably get one higher, out of sequence?) – Geobits – 2016-09-21T17:08:01.200
Alright, the test cases are correct according to my results. Also, there's no need for any more test cases. – AMACB – 2016-09-21T17:15:00.940
12The 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 – 2016-09-21T17:24:29.36712oeis.org/A228361 – James – 2016-09-21T17:32:31.280
19No toilet at all is indeed a checkmate situation. :D – Titus – 2016-09-21T19:37:12.150
The urinal problem has been around much longer than XKCD. I first encountered it a decade before Randal's blog post; and have no reason to believe the flash game implementation that was shared around the dorm lan my freshman year was the origin of it. – Dan is Fiddling by Firelight – 2016-09-22T11:06:12.617
Does the cubicle count in this problem? – Ed Heal – 2016-09-22T19:22:35.967