28
1
Introduction
Suppose for a moment that the vipers and cliff are only two steps away, instead of three.
o
---
Hsss! |
';;' ___ /_\ ___ _
|
You are, unfortunately, a captive of a sadistic torturer. You must take a step either to the left or to the right every turn. If you don't, they shoot you dead instantly. You are allowed to plan out your steps beforehand, but once you take your first step, you can't change your plan. (And no dawdling either; they'll shoot you.)
Suddenly, a bright idea comes to mind...
Ah! I can just alternate stepping right and left! Step right, step left, step right, step left, and so on...
Ah ah ah, not so fast. Like I said, the torturer is sadistic. They get to choose whether you take every step, or every second step, or every third step, and so on. So if you naively choose the sequence RLRLRL...
then they can force you to take every second step, which starts with LL
. Uh oh! You've been bitten by vipers! Blackness swoops over you and all else fades away...
Actually no, you're not dead yet. You still have to come up with your plan. After thinking about it for a few minutes, you realize you are doomed. There is no way to plan out a series of steps that will guarantee your survival. The best you can come up with is RLLRLRRLLRR
.1 Eleven safe steps and no more. If the twelfth step is R
, then the Torturer will make you take every step and then the last three steps send you off the cliff. If the twelfth step is L
, then the Torturer will make you take every third step (LRLL
), which puts you right in the brood of vipers and their lethal bites.
You pick R
as the twelfth step, hoping to delay your demise as long as possible. With the wind roaring in your ears, you wonder to yourself...
What if I had three steps?
Spoiler alert!
You would still die. As it turns out, no matter how many steps you have, there will be some point where no matter what choice you make, there is a sequence of steps your Torturer can pick to ensure you meet your deadly fate.2 However, when the vipers and cliff are three steps away, you can take a total of 1160 safe steps and when they're four steps away, there are at least 13,000 safe steps!3
The challenge
Given a single integer n < 13000
, output a sequence of n
safe steps, assuming the cliff and the vipers are four steps away.
Rules
- Can be either a full program or a function.
- Input can be taken through STDIN or equivalent, or as a function argument.
- Output must have two distinct characters (which can be
+/-
,R/L
,1/0
, etc.). - Any whitespace in the output doesn't matter.
- Hard-coding a solution is not allowed. That would trivialize this challenge.
- Your program should (in theory) finish in a decent amount of time. As in,
n=13000
might take like a month, but it shouldn't take a thousand years or more. That is, no brute force. (Well, at least try to avoid it.) - Life bonus: provide a series of
2000
safe steps. If you do this, the Torturer will be so impressed by your tenacity, perseverance, and forethought that they'll let you live. This one time. (Treat this sequence as a binary number and provide the decimal equivalent for verification. This is intended to reward answers that finish quickly as answers are allowed to take a very long time.) - Score: bytes, unless you qualify for the bonus - multiply by 0.75.
1 There is a good explanation of this problem and "solution" by one of the stars of Numberphile, James Grime, over on his YouTube channel here: https://www.youtube.com/watch?v=pFHsrCNtJu4 .
2 This 80-year-old conjecture, known as Erdos' discrepancy problem, was proved very recently by Terence Tao. Here is a very nice article on Quanta Magazine about this: https://www.quantamagazine.org/20151001-tao-erdos-discrepancy-problem/ .
3 Source: A SAT Attack on the Erdos Discrepancy Conjecture, by Boris Konev and Alexei Lisitsa. Retrieved from here: http://arxiv.org/pdf/1402.2184v2.pdf .
1So, if I make a solution for
n=13000
, will the first 2000 instructions of it win a bonus? Seems pointless, so you probably meant something else? – anatolyg – 2015-10-05T12:32:03.740@anatolyg: All solutions should theoretically be able to handle
n=13000
within like, a year, maybe ten. Are you going to wait a month forn=2000
? Probably not. And if you do, then you deserve the bonus anyway. – El'endia Starman – 2015-10-05T18:38:17.107