13
4
Introduction
"Muhuhuhahahah!" The mad scientist laughs. "You're trapped in my own little game!"
In front of you is a deadly pit of snakes, while behind you is a bottomless chasm. There's no way out, you're stuck!
"Two steps in front of you is the snake pit, and two steps behind you is the chasm. But! Before you move, you MUST write down a sequence of steps, forwards and backwards, and give them to me. But! because I'm feeling a bit evil today, I can make you take, instead of every step, every nth step, where n is less than your sequence length!
Choose wisely, now."
What's the maximum number of steps you can take before your imminent death?
Task
The intro above is a twist on the Erdős discrepancy conjecture, which was recently proven true (if you want to understand more about this, go to this video, by James Grime - I "stole" the twist question off of him).
The answer to the intro is 11 steps, but I won't go too in-depth with a proof. The answer, if the distance between you and the two "dangers" were 3 steps, is 1160 steps, although that isn't validated properly yet.
Your task is to make a program that generates the longest sequence of steps you can achieve for a larger x, where x is the number of steps between you and the two "dangers". Your program must take an input for x, and output a valid sequence for that x.
For the purposes of this challenge, + represents a step forward, and - represents a step back.
So, an output for an input 2 is:
+--+-++--++
Which works, no matter what n the mad scientist chooses. For our challenge, x = 5.
NOTE: This challenge is not a dupe of this challenge or this challenge, as my challenge focuses on the output, as opposed to the code itself - in other words, it's not a code golf challenge. As well as that, these challenges are based off of x = 3, which already has an established upper bound.
Rules:
- Your entire program should fit into your answer. However, if it doesn't fit, please provide an additional Github repository, or something similar.
- You may update both your answer and your program, if you can get a better score via optimising your code - but by doing so, you must update everything in the list below.
- In your answer, you must have:
- Your program, in its entirety, or a link to a GH repository hosting your code
- The amount of steps generated - this will be your final score.
- You must also provide an online version of the sequence in a Pastebin, or something similar. This is so we can check your answer.
- The time your final score was last updated, so I don't have to check your history
- You may NOT hardcode sequences beforehand.
- Your program must work for all
x(wherexis the number of steps between you and the pit & chasm), but you only need to provide the score forx = 5.
The answer with the largest score wins!
clismique
Posted 2017-06-05T09:57:56.607
Reputation: 6 600
Just to check my understanding, you need a sequence where even if you took every other, or every third element, you survive? – Notts90 supports Monica – 2017-06-05T11:23:14.313
1@Notts90 Yup - it musn't just work for that, though. It must work if you took every
nth step, wherenis any number below your sequence size. – clismique – 2017-06-05T11:24:27.847Very closely related. (I called this up as a potential duplicate in the sandbox; I'd have therefore expected the text of the challenge to at least discuss it.) – None – 2017-06-05T16:06:12.363
I think this challenge is impossible, practically speaking. Finding the maximum discrepancy length for
– xnor – 2017-06-05T17:29:27.777x=5would require a major breakthrough that would be worthy of publication. Consider that the maximum of 1160 forx=3was proven and published in 2014 and no further values are known..Is 0 a proper N? – tuskiomi – 2017-06-05T17:30:27.140
@xnor I'm only asking for people to generate the largest sequence they can, not necessarily the largest sequence possible, so how is the task impossible? Also, how is this a dupe of Dennis's challenge? The goal of my challenge is to generate the longest sequence compared to other answers, while his challenge is a code golf. – clismique – 2017-06-05T20:45:16.710
@Qwerp-Derp Ah, I'd misunderstood then. When you write "make a program that generates the longest sequence of steps you can", I took "you can" to mean "is mathematically possible", not "the best you can accomplish for your submission". – xnor – 2017-06-05T20:51:56.237
@xnor Sorry if I sound a bit defensive, I was just trying to prove my stance, and now when I look back at it, it looks defensive... – clismique – 2017-06-06T06:06:36.870
@ais523 Issue addressed. – clismique – 2017-06-06T06:28:51.143
@tuskiomi Nope, but even if it were valid it wouldn't make a difference. – clismique – 2017-06-06T10:25:49.613
I don't understand, that "Your program must work for all x" and "generate the largest sequence you can" seems contradicting. And why do you require the code to be uploaded? – user202729 – 2017-06-06T11:54:12.980
Is
+--+-++--+-valid for x=2? The video suggests the only solution is+--+-++--++but I wrote a brute force method and got both patterns. – Notts90 supports Monica – 2017-06-06T20:30:11.187@user202729 When I say "your code must work for all x", I mean that your program must output a valid sequence that follows all of the rules for if the length between you and the dangers are
x, givenxas an input. – clismique – 2017-06-06T20:37:24.457But any sequence that valid for
xis valid forx+kfor all non negative integerk. – user202729 – 2017-06-07T05:48:56.190@Notts90 Yes, that is valid. – clismique – 2017-06-07T07:21:23.087
@user202729 Yeah, I know that... what's your point? Also, the requirement for the code to be uploaded was so 1) The code could be checked against, and 2) I want to look at the code. – clismique – 2017-06-07T07:22:25.120