9
The idea here is to produce an almost repeating pattern. That is, the sequence being constructed changes at the last moment to avoid a repetition of some subsequence. Subsequences of the type AA and ABA are to be avoided (where B is no longer than A).
Examples:
I'll go ahead and start by listing all of the small examples to make my description clearer. Let's start with 0.
Valid: 0 Invalid: 00 (AA pattern) Valid: 01 Invalid: 010 (ABA pattern) Invalid: 011 (AA pattern) Valid: 012 Valid: 0120 Invalid: 0121 (ABA pattern) Invalid: 0122 (AA pattern) Invalid: 01200 (AA pattern) Invalid: 01201 (ABA pattern; 01-2-01) Invalid: 01202 (ABA pattern) Valid: 01203
Now, I strongly believe that a 4
is never needed, though I do not have a proof, because I have easily found sequences of hundreds of characters long that use only 0123
. (It's probably closely related to how only three characters are needed to have infinite strings that do not have any AA patterns. There's a Wikipedia page on this.)
Input/Output
Input is a single, positive, non-zero integer n
. You may assume that n <= 1000
.
Output is an n
-character sequence with no subsequences that match either prohibited pattern (AA or ABA).
Sample inputs and outputs
>>> 1 0 >>> 2 01 >>> 3 012 >>> 4 0120 >>> 5 01203 >>> 50 01203102130123103201302103120132102301203102132012
Rules
- Only the characters
0123
are allowed. - B is no longer than A. This is to avoid the situation where
012345
has to be followed by6
because0123451
has this:1-2345-1
. In other words, the sequence would be trivial and uninteresting. n
may be inputted through any method desired, except hard-coding.- Output may be either a list or a string, depending on which is easier.
- No brute force; the run time should be on the order of minutes, at most an hour on a really slow machine, for
n=1000
. (This is intended to disqualify solutions that just loop through alln
-length permutations of{0,1,2,3}
, so that trick and similar tricks are disallowed.) - Standard loopholes are disallowed, as usual.
- Scoring is in bytes. This is code-golf, so the shortest entry wins (probably - see bonus).
- Bonus: pick the lowest allowed digit at each step. If
1
and3
are possible choices for the next digit in the sequence, pick1
. Subtract 5 bytes from your score. However, take note of the note below.
Note!
Dead-ends are possible. Your program or function must avoid these. Here's an example:
Stump: 0120310213012310320130210312013210230120310213201230210312013023103201230213203102301203210231201302103123013203102130120321023013203123021032012310213012031023013203123021320123102130120 Stump: 0120310213012310320130210312013210230120310213201230210312013023103201230213203102301203210231201302103123013203102130120321023013203123021032012310213012031023013203123021320123102130123 Stump: 012031021301231032013021031201321023012031021320123021031201302310320123021320310230120321023120130210312301320310213012032102301320312302103201231021301203102301320312302132012310320 Stump: 012031021301231032013021031201321023012031021320123021031201302310320123021320310230120321023120130210312301320310213012032102301320312302103201231021301203102301320312302132012310321301203102130
Each of these sequences cannot be extended any further (without using a 4
). But also note that there is a crucial difference between the first two and the second two. I'll replace the shared initial subsequence with an X
to make this clearer.
Stump: X2130120 Stump: X2130123 Stump: X320 Stump: X321301203102130
The last two digits of X
are 10
, so the only possible choices for the next digit are 2
and 3
. Choosing 2
leads to a situation where the sequence must terminate. The greedy algorithm will not work here. (Not without backtracking, anyway.)
Can one use a brute force strategy of testing every possible string, even if it will not give an output in realistic time? Do you know there to be a solution for all
n
? If someone gives a heuristic semi-greedy algorithm, how will you check that it does not run into problems for a very large length? The general problem is an interesting one, and I haven't been able to find anything on pattern avoidance where we restrict the length of part of the pattern. If someone can produce a general recipe, I expect that to be the best approach. – xnor – 2015-09-16T20:03:51.580I believe I disallowed brute force in the rules. I should probably highlight that. I do not have a proof that there exists a solution for all
n
, but given that the stumps my program finds tend to get longer by an average of 10 digits each time, I'm very sure that an infinite sequence exists. I'm not sure how a semi-greedy algorithm could be tested for arbitrarily large sequences. I could restrict the requirement ton
=1000 and just not worry about highern
. – El'endia Starman – 2015-09-16T20:21:14.1904I suppose
AA
is really typeABA
whereB
is empty. This could perhaps help to streamline some solutions. – mathmandan – 2015-09-16T22:47:11.980