In 1978, inspired by this Peanuts cartoon, Nathaniel Hellerstein invented the Linus sequence1.
The Linus sequence is a sequences of 1s and 2s in which each new entry is chosen to prevent the longest possible pattern from emerging at the end of the sequence. We start with the digit 1:
1
Now, if the second digit were also a 1 then we would have a repeating pattern. So we append a 2 instead:
12
If we choose 2 for the third entry, we'll have 22 at the end of the sequence, another emerging pattern. Prevent that by choosing 1:
121
Now what? Choosing 2 would give us the disastrously tidy 1212, so choose 1 again:
1211
But now the ones at the end are looking rather pleased with themselves, so choose 2 as the next digit:
12112
And so on. The rule is to avoid the longest possible doubled suffix: this is the longest possible repeated string of digits and the end of the sequence. For example, choosing 1 at this point would give the sequence 121121, in which the end of the sequence (indeed, the entire sequence) is a repeated string of the three digits 121. This is avoided if we would append a 2 to obtain the sequence 121122, which only ends with a repetition of a single digit (2). So, in this case, we choose to append the digit 2.
Admittedly, this isn't exactly the sequence that Linus was describing in the comic strip, but it opens up a world of its own with many surprising properties2, as these things tend to do.
It's also possible to compile a related sequence by making note of the length of each repetition that you avoided in the Linus sequence. That's called the Sally sequence3.
Assignment
We say that a string $$v$$ is a suffix of a given string $$s$$ if there exists a string $$u$$ such that $$s = uv$$, or in other words if the string $$s$$ ends with the string $$v$$. By definition, the empty string and the entire string $$s$$ are respectively the shortest and longest suffix of the string $$s$$.
We say that a suffix $$v$$ is a doubled suffix of a given string $$s$$ if there exists a string $$u$$ such that $$s = uvv$$.
In this assignment we only consider strings $$s$$ that are composed of the digits 1 and 2. Your task:
-
Write a function lds that takes a string $$s$$. The function must return the length of the longest doubled suffix of $$s$$.
-
Write a function extend that takes a string $$s$$. The function must return a tuple containing three elements: i) the length of the longest doubled suffix of $$s$$1, ii) the length of the longest doubled suffix of $$s$$2, and iii) the string $$s$$1 or $$s$$2 whose longest doubled suffix is the shortest (pick $$s$$1 if both have a longest doubled suffix of equal length).
Note
With the string $$s$$1 we mean the string that is obtained by appending the digit 1 to the string $$s$$. Analoguously, the $$s$$2 is obtained by appending the digit 2 at the end of the string $$s$$.
-
Write a function linus that takes a number $$n \in \mathbb{N}$$. The function must return a string $$s$$ that represents the Linus sequence of length $$n$$. The string $$s$$ is constructed starting from the empty string, and repetitively appending either a 1 or a 2 whichever yields the string that has the shortest possible longest doubled suffix (append a 1 if the two resulting strings have longest doubled suffices of equal length). Repeat this procedure until a string $$s$$ of length $$n$$ is obtained.
- Write a function sally that takes a number $$n \in \mathbb{N}$$. The function must return the $$n$$-th element in the Sally sequence. To compute this number we start from the Linus sequence of length $$n$$, respectively append a 1 and a 2, and determine the length of the longest doubled suffix of the two resulting strings. The function must return the maximum of these two lengths.
Example
>>> lds('1211')
1
>>> lds('1212')
2
>>> extend('1')
(1, 0, '12')
>>> extend('12')
(0, 1, '121')
>>> extend('121')
(1, 2, '1211')
>>> extend('1211')
(1, 0, '12112')
>>> extend('12112')
(3, 1, '121122')
>>> linus(0)
''
>>> linus(1)
'1'
>>> linus(6)
'121122'
>>> linus(40)
'1211221211212211211122121122111211221211'
>>> sally(0)
0
>>> sally(1)
1
>>> sally(6)
1
>>> sally(11)
6
Epilogue: AAAAAAAAAAUUGH
In 1947, Charles M. Schulz was working as an art instructor at a Minneapolis correspondence school when the accounting department hired a pretty redhead named Donna Mae Johnson. "I just thought she was wonderful," Schulz said. On his way in to work he would stop off on the second floor to draw cartoons on her desk calendar, and in February 1950 they began to date.
The trouble was that Donna had a second boyfriend, a local boy named Alan Wold whom she had been dating since 1948. "I knew quite soon in the relationship that it was Al that I wanted," she said, yet "I really loved Sparky too at the same time." She asked her diary on May 8, 1950: "How will you ever decide?"
On June 14, after signing a deal with a newspaper syndicate to publish
his comic strip, Peanuts, Schulz went to her and proposed
marriage. All she could say was "I don't want to marry anybody. I just
wish everybody would leave me alone."
He pressed her for three weeks, but she was firm. Schulz eventually moved to Colorado, married Joyce Halverson, and started a family, but he kept in touch with Donna for the rest of his life. One night he grew sentimental listening to Joni James sing about unrequited love:
That was the mindset that got me going on Charlie Brown sitting at the playground, eating his lunch, and he looks across the playground, and he sees the little red-haired girl, and from that, that whole series came, one thing after another.
"You never do get over your first love," he said at age 75. "The whole of you is rejected when a woman says, 'You are not worth it.'"