3
\$\begingroup\$

The string 2123132133 has the property that no subsequence of length 3 is the same as any other subsequence of length 3.

Your task is to build a program that will output as long of a string as possible that satisfies this property for sequences of length 9 with the characters from 1 to 9.

The source code of your program may not be longer than 16 kilobytes (16,384 bytes). The program that wins is the one that outputs the longest sequence of digits from 1 to 9 such that no subsequence of 9 digits is the same.

\$\endgroup\$
  • \$\begingroup\$ You may want to tighten up the output requirements so that the only output is the sequence such that no subsequence is the same. Otherwise, as it currently reads, it may be possible to submit a while(1){putchar('1'+rand()%9);} submission that just spews random digits forever and it could be argued that its output will contain (given enough time) "the longest sequence of digits from 1 to 9 such that no subsequence of 9 digits is the same." That would be a dick move, for sure, but easily prevented. Cheers. \$\endgroup\$ – Darren Stone Dec 15 '13 at 5:49
  • \$\begingroup\$ I'm pretty sure that "outputs the longest sequence of digits" implies that the entire sequence of digits that a program outputs must satisfy the subsequence requirement. Thanks for your concern, though. \$\endgroup\$ – Joe Z. Dec 15 '13 at 5:58
  • \$\begingroup\$ Related \$\endgroup\$ – Peter Taylor Dec 15 '13 at 8:22
2
\$\begingroup\$

What I'm starting with here is a De Bruijn sequence. Stealing some reference code on the topic, here is my submission:

#!/usr/bin/env python

def de_bruijn(k, n):
    """ De Bruijn sequence for alphabet size k and subsequences of length n. """
    a = [0] * k * n
    sequence = []
    def db(t, p):
        if t > n:
            if n % p == 0:
                for j in range(1, p + 1):
                    sequence.append(a[j])
        else:
            a[t] = a[t - p]
            db(t + 1, p)
            for j in range(a[t - p] + 1, k):
                a[t] = j
                db(t + 1, t)
    db(1, 1)
    return sequence

seq = de_bruijn(9, 9) # cyclic
seq = seq + seq[:8]   # extended to max 
print(''.join(map(lambda n: chr(49+n), seq)))

After running for ten minutes, the output is a 387,420,497 digit sequence. This is 9^9 + 8 digits, as expected. (Thank you @PeterTaylor for the +8 tip on the cyclic output.)

\$\endgroup\$
  • \$\begingroup\$ Almost. De Bruijn sequences are cyclic, so you can copy the first 8 characters to the end to get a maximum-length non-cyclic string. \$\endgroup\$ – Peter Taylor Dec 15 '13 at 7:55
  • \$\begingroup\$ Hmm, didn't know that theorem existed. Looks like your answer will be the accepted one. \$\endgroup\$ – Joe Z. Dec 15 '13 at 8:37
  • \$\begingroup\$ Thank you, @PeterTaylor. That makes sense. I've extended the sequence. \$\endgroup\$ – Darren Stone Dec 15 '13 at 8:37

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.