Choosing where to cut

The choice is not which item to take, but where the next piece ends.

Key idea

The shape

For problems about breaking a sequence into consecutive pieces, each level of the search chooses where the current piece ends. The loop runs over possible end positions rather than over items.

You wrote this in the first lab of this unit. Adding a condition on which pieces are allowed turns it into a constrained search, and the condition is where the pruning goes.

1def splits_into_short_pieces(text, limit):2    results, current = [], []3 4    def explore(start):5        if start == len(text):6            results.append(current[:])7            return8        for end in range(start + 1, len(text) + 1):9            piece = text[start:end]10            if len(piece) > limit:11                break                  # every later end is longer too12            current.append(piece)13            explore(end)14            current.pop()15 16    explore(0)17    return results18 19print(splits_into_short_pieces("abc", 2))

Predict the output· 5 min

Predict the output: which cuts are even worth trying

At each position the search may cut after any number of characters, and most of those cuts lead nowhere. Type the four lines it prints.

Python

1def mirrored(piece):2    return piece == piece[::-1]3 4text = "aab"5for end in range(1, len(text) + 1):6    piece = text[:end]7    print("cut after", end, "gives", piece, "->", "keep" if mirrored(piece) else "abandon")8 9print("branches worth taking:", sum(1 for end in range(1, len(text) + 1) if mirrored(text[:end])))

Printed output

Problem· 28 min

Palindrome Partitioning

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.

1def splits_into_short_pieces(text, limit):2 results, current = [], []3 4 def explore(start):5 if start == len(text):6 results.append(current[:])7 return8 for end in range(start + 1, len(text) + 1):9 piece = text[start:end]10 if len(piece) > limit:11 break # every later end is longer too12 current.append(piece)13 explore(end)14 current.pop()15 16 explore(0)17 return results18 19print(splits_into_short_pieces("abc", 2))

1def mirrored(piece):2 return piece == piece[::-1]3 4text = "aab"5for end in range(1, len(text) + 1):6 piece = text[:end]7 print("cut after", end, "gives", piece, "->", "keep" if mirrored(piece) else "abandon")8 9print("branches worth taking:", sum(1 for end in range(1, len(text) + 1) if mirrored(text[:end])))