I think I got it! The answer is
given as the following Python code:
target = 'abcacbaabbccaaccbbabacabcbcaaabaacbbbcbabbacccacaabccbcbbcababcaacaccabbbaaacccbacbccccaaaabbabbcbcb'
s = 'abc'
for i in range(3, len(target)):
cur_best = (1e9, 1e9, '')
for c in 'abc':
s2 = s + c
for l in range(1, len(s2)): # identify the length of shortest unseen suffix
if s2[-l:] not in s: break
dup = s2[-l+1:] # longest seen suffix
app = s.rfind(dup) # its last appearance
cur_best = min(cur_best, (l, app, c)) # choose shorter unseen suffix,
# with earlier last appearance as the tiebreaker
s += cur_best[2]
print(s)
assert s == target[:len(s)]
Attempt this online!
Ever[y] character is the best possible character to create a novel, never-before-seen sequence...
Out of abc, the character that forms the shortest suffix that is unseen yet is chosen.
For example, after abcacba, aa is unseen but both ab and ac are already seen, so a is chosen.
And if by some odd coincidence you have seen it before, I hope it was as far in the past as possible.
If there are ties, find the suffixes that are 1 character shorter than the unseen suffix. Choose the one that has the earliest last appearance.
For example, after abcacbaabbcca,
- all of
aa, ab, ac are seen. cac is seen, but caa and cab are not, so the candidates are a and b.- The last appearance of
aa is earlier than that of ab, so a is chosen.
Since this ruleset uniquely chooses one of abc at every step, the sequence can go forever with the given rules.
