You flip a fair coin repeatedly, writing down H or T. Write expected_flips_until(pattern: str) -> Fraction that returns the exact expected number of flips until pattern (a non-empty string of H/T) first appears as a run of consecutive flips.
expected_flips_until("H") # Fraction(2, 1)
expected_flips_until("HT") # Fraction(4, 1)
expected_flips_until("HH") # Fraction(6, 1)
expected_flips_until("HTH") # Fraction(10, 1)
Constraints: 1 <= len(pattern) <= 20.
Why is HH slower than HT? Waiting for HT, a miss after the first H is another H, which still counts as progress. Waiting for HH, a miss is a T, which throws away everything.
Simulation isn't exact: return the exact value.
Hint: With one state per matched length 0..m, write the expected remaining flips from each state in terms of the states one flip later, and solve that system exactly with Fractions.
Show hint
All that matters at any moment is how many characters of the pattern you have matched so far. After a flip, how far along are you now? (It isn't always zero after a miss, as the HT case shows.)