Carrying a range instead of a value

When a choice is genuinely undecidable now, track every outcome it could lead to at once.

Why it works

Track the smallest and largest possible open count

You cannot decide what a wildcard is when you meet it. So do not. Carry the range of open-bracket counts that are still possible, as two numbers: the lowest and the highest.

An opener raises both. A closer lowers both. A wildcard lowers the low and raises the high, since it could be either.

The string is valid if the range never becomes entirely negative along the way, and if zero is inside the range at the end.

The range is easiest to believe when you watch it widen and narrow. Below it is printed after each character, with no decisions made anywhere.

1text = "(*))"2 3low = high = 04for ch in text:5    if ch == "(":6        low, high = low + 1, high + 17    elif ch == ")":8        low, high = low - 1, high - 19    else:10        low, high = low - 1, high + 1     # could be either, or nothing11    print(f"after {ch}: possible open counts run from {low} to {high}")

The negative lows are interpretations that already failed. Two of the guards this lesson describes deal with exactly those.

Predict the output· 5 min

Predict the output: is every value in the range really achievable?

After two wildcards, the possible counts of open brackets are listed by working out every interpretation. Type the two lines it prints.

Python

1from itertools import product2 3counts = set()4for choices in product("(),", repeat=2):        # each wildcard: open, close, nothing5    open_count = 06    for choice in choices:7        open_count += 1 if choice == "(" else (-1 if choice == ")" else 0)8    counts.add(open_count)9 10print(sorted(counts))11print("gaps in that range:", [n for n in range(min(counts), max(counts) + 1) if n not in counts])

Printed output

Problem· 30 min

Valid Parenthesis String

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1text = "(*))"2 3low = high = 04for ch in text:5 if ch == "(":6 low, high = low + 1, high + 17 elif ch == ")":8 low, high = low - 1, high - 19 else:10 low, high = low - 1, high + 1 # could be either, or nothing11 print(f"after {ch}: possible open counts run from {low} to {high}")

1from itertools import product2 3counts = set()4for choices in product("(),", repeat=2): # each wildcard: open, close, nothing5 open_count = 06 for choice in choices:7 open_count += 1 if choice == "(" else (-1 if choice == ")" else 0)8 counts.add(open_count)9 10print(sorted(counts))11print("gaps in that range:", [n for n in range(min(counts), max(counts) + 1) if n not in counts])