NACLO 2022 - Problem LStopping for a Spell

Invitational round | 5 points | 100.00% | Problem statement | Official solution | Tags: Computational

For L1, just walk the state transition diagram.

1. • At the start
   • Read "t", take "t" transition to start, output "T"
   • Read "i", take "i" transition to start, output "AY"
   • Read "m", take "m" transition to the top node, output "M"
   • Read "e", take "e" transition to the right node, output "∅"
   • Result: "TAYM"
2. • At the start
   • Read "t", take "t" transition to start, output "T"
   • Read "r", take "r" transition to start, output "R"
   • Read "a", take "a" transition to start, output "EY"
   • Read "d", take "d" transition to the bottom node, output "D"
   • Read "ed", take "ed" transition to the right node, output "UHD"
   • Result: "TREYDUHD"
3. • At the start
   • Read "s", "t", "r", "i", all looping back to the start, output "S", "T", "R", "AY"
   • Read "d", take "d" transition to the bottom node, output "D"
   • Read "ing", take "ing" transition to the right node, output "IHNG"
   • Result: "STRAYDIHNG"
4. • At the start
   • Read "f", "r", "a", all looping back to the start, output "F", "R", "EY"
   • Read "m", take "m" transition to the top node, output "M"
   • Read "ing", take "ing" transition to the right node, output "IHNG"
   • Result: "FREYMIHNG"

In L2, observe that "g" can cause the machine to either stay at start or go to the top node. Only "stage" contains "g", so it's the answer.

In L3, we are now exploring this "g" ambiguity.

1. • At the start
   • Read "s", "t", "a", "g", all looping back to the start, output "S", "T", "EY", "G"
   • Read "e", but there's no transition from the start on "e"; invalid.
   • Backtrack to "g", transition to the top node and output "DJ"
   • Read "ing", take "ing" transition to the right node, output "IHNG"
   • Result: "STEYDJIHNG"
2. • At the start
   • Read "g", take "g" transition to the top node, output "DJ"
   • Read "a", but there's no transition from the top node on "a"; invalid.
   • Backtrack to "g", stay at the start and output "G"
   • Read "a", take "a" transition to the start, output "EY"
   • Read "m", take "m" transition to the top node, output "M"
   • Read "ing", take "ing" transition to the right node, output "IHNG"
   • Result: "GAMIHNG"

In L4, we want to construct an FST that produces the desired output. Start with the known transition. "people", "phase", "built" all take this transition to the next node. The next transition must accept "o", "a", and "ui" as continuations of these three phrases respectively. So (4) matches (A).

Next, these three phrases continue with "p", "se", and "l", split across two transitions. We have (D) and (E) that exactly cover them. Because finally we want "people" to use the "le:UHL" transition, (5) should match to (E), while (2) matches to (D).

After returning, "built" still has a "t" left. The other two phrases: "colonel", "he" also start here. So (1) or (3) must at least recognize "t", "c", and "h". This can use nothing other than (C). Because (C) looks like it needs to be looped multiple times by "he" and "colonel", it should be the self-loop transition (1). Finally, upon seeing "n" for "colonel", we have to take (3), which matches to (B). Finally (6) will match (F) and takes the "el".

For L5, start at "start", read the output and find the transition that would produce said output, and apply the transition.

• R: lo (stay at start)
• UH: o (stay at start)
• F: ph (go to next state)
• ∅: o (go to next state; must use this because (4) = (A) has no other output that matches "L")
• L: l (go to start)
• EA: e (go to start)

So the result is "loophole".¹

Footnotes

1. This is a really brilliant problem. How did someone even come up with this? ↩