NACLO 2023 - Problem EBengalese Finch Song

Nothing to say about E1: just count the letters. $P(\text{L1}\to\text{L2})$ is the ratio of the previous two columns.

In E2, just find the letter with the highest probability that it follows k. The probabilities are 1/6, 1/6, 1/12, and 7/12, so the answer is a with 7/12.

In E3, the problem says that Bengalese finch song is more predictable than human speech, so we want to find two strings where one letter transitions more deterministically to another. The real way to do it is of course to count all transitions. Since we are doing this in posterity anyway, I actually wrote a program to do this.

from collections import Counter
import seaborn as sns
import matplotlib.pyplot as plt

def count_transitions(s):
    transitions = Counter()
    for a, b in zip(s, s[1:]):
        transitions[(a, b)] += 1
    return transitions

strings = [
    "abcbdaefbdgdabhijigdbcbhgdabkieidgdahbjaficblbfefkbcf",
    "abacdefghahbhicdefghahbhgicdefgbjklcdefgammlcdefgajkl",
    "abcdefbfcdefbfcdeaghijkbcdefafcdebcdeaghiffcdefafcdef",
    "abcdedfgfdfgbahibjdkbghcbfcbffjdcbgbidgdldbgfdibjdgba",
]

plt.figure(figsize=(10, 8))

for i, s in enumerate(strings):
    transitions = count_transitions(s)
    ax = plt.subplot(2, 2, i + 1)
    sns.heatmap(
        [[transitions[(a, b)] for b in "abcdefghijk"] for a in "abcdefghijk"],
        xticklabels="abcdefghijk",
        yticklabels="abcdefghijk",
        ax=ax
    )

plt.savefig(f"E.png", bbox_inches="tight")

python

It's obvious that sequences B and C feature fewer transitions, with most concentrated along a diagonal, while A and D have the transitions spread out more evenly across all combinations.

In the real test, it's probably impossible to enumerate all 121 transitions for 4 sequences. The next best thing is to count the number of letters each letter can be followed by. For example, for sequence A:

a → b, e, f, h
b → c, d, f, h, j, k, l
c → b, f
d → a, b, g
e → f, i
f → b, e, i, k
g → d
h → b, g, i
i → c, d, e, g, j
j → a, i
k → b, i
l → b

For sequence B:

a → b, c, h, j, m
b → a, h, j
c → d
d → e
e → f
f → g
g → a, b, h, i
h → a, b, g, i
i → c
j → k
k → l
l → c
m → l, m

It's still a really painful process (52 transitions to check for each sequence), but much easier to manage by hand, and the results are easy to visualize.

In E4, we just need to find a sequence with the matching probabilities.

.40 must be RE.
After E, a .15 transition can be either R or S. However, the next one is .20 and R has no .20 transition, so it must be S.
After S, the .20 transition must be T.
After T, the .05 transition can be either L or S, but S has no .35 transition, so it must be L.
...

Again, very tedious to do by hand, but not a lot of thinking involved—just reuse the same way of reasoning as above.

NACLO 2023 - Problem EBengalese Finch Song

Nothing to say about E1: just count the letters.

P(\text{L1}\to\text{L2})

is the ratio of the previous two columns.

In E2, just find the letter with the highest probability that it follows k. The probabilities are 1/6, 1/6, 1/12, and 7/12, so the answer is a with 7/12.

from collections import Counter
import seaborn as sns
import matplotlib.pyplot as plt

def count_transitions(s):
    transitions = Counter()
    for a, b in zip(s, s[1:]):
        transitions[(a, b)] += 1
    return transitions

strings = [
    "abcbdaefbdgdabhijigdbcbhgdabkieidgdahbjaficblbfefkbcf",
    "abacdefghahbhicdefghahbhgicdefgbjklcdefgammlcdefgajkl",
    "abcdefbfcdefbfcdeaghijkbcdefafcdebcdeaghiffcdefafcdef",
    "abcdedfgfdfgbahibjdkbghcbfcbffjdcbgbidgdldbgfdibjdgba",
]

plt.figure(figsize=(10, 8))

for i, s in enumerate(strings):
    transitions = count_transitions(s)
    ax = plt.subplot(2, 2, i + 1)
    sns.heatmap(
        [[transitions[(a, b)] for b in "abcdefghijk"] for a in "abcdefghijk"],
        xticklabels="abcdefghijk",
        yticklabels="abcdefghijk",
        ax=ax
    )

plt.savefig(f"E.png", bbox_inches="tight")

python

It's obvious that sequences B and C feature fewer transitions, with most concentrated along a diagonal, while A and D have the transitions spread out more evenly across all combinations.

a → b, e, f, h

b → c, d, f, h, j, k, l

c → b, f

d → a, b, g

e → f, i

f → b, e, i, k

g → d

h → b, g, i

i → c, d, e, g, j

j → a, i

k → b, i

l → b

For sequence B:

a → b, c, h, j, m

b → a, h, j

c → d

d → e

e → f

f → g

g → a, b, h, i

h → a, b, g, i

i → c

j → k

k → l

l → c

m → l, m

It's still a really painful process (52 transitions to check for each sequence), but much easier to manage by hand, and the results are easy to visualize.

In E4, we just need to find a sequence with the matching probabilities.

.40 must be RE.

After E, a .15 transition can be either R or S. However, the next one is .20 and R has no .20 transition, so it must be S.

After S, the .20 transition must be T.

After T, the .05 transition can be either L or S, but S has no .35 transition, so it must be L.

...

Again, very tedious to do by hand, but not a lot of thinking involved—just reuse the same way of reasoning as above.