Partitioning strings with backtracking

Partitioning a string means cutting it into consecutive pieces so that every piece passes a test. Backtracking makes the cuts from left to right: choose the next piece, check it at once, solve the rest, and undo. Restoring IP addresses is the classic case: a string of digits is cut into four parts, each a number from 0 to 255 without a leading zero. In palindromic partitioning every piece must read the same backwards. A length bound stops a split when the characters left cannot fill the pieces left. A precomputed table answers each palindrome check in O(1). Memoised counts for each suffix give the number of partitions without listing them.

Two problems about cutting strings

Problem A: restore the addresses. A log lost the dots of its IPv4 addresses. Write restore_addresses(digits), which returns every dotted-decimal address that uses all the digits in order. Limits: up to 20 digits; fewer than 4 or more than 12 give none.

• 172162541 gives 6 addresses, among them 172.16.254.1 and 17.216.25.41.
• 10010 gives 1.0.0.10 and 10.0.1.0, and 0000 gives only 0.0.0.0.

Problem B: palindromic pieces. Write palindrome_partitions(word), which lists every way to cut a word into palindromes. Limits: up to 40 letters, with at most 100,000 partitions in the answer. noon gives n o o n, n oo n and noon; malayalam gives 8.

The brute force, and where it stops

For A, try every placement of three dots and check the four parts. For B, try every set of cut positions and check every piece:

"""Both problems by brute force: try every way to cut the string, then check every piece."""
import time
from itertools import combinations


def valid_part(part):
    """A part of a dotted-decimal IPv4 address: 1 to 3 digits, no leading zero, at most 255."""
    return 1 <= len(part) <= 3 and part.isdigit() and part.isascii() and (part == "0" or part[0] != "0") and int(part) <= 255


def addresses_brute(digits):
    """Every way to put three dots between the digits, kept when all four parts are valid."""
    found = []
    for a, b, c in combinations(range(1, len(digits)), 3):  # the three cut positions
        parts = [digits[:a], digits[a:b], digits[b:c], digits[c:]]
        if all(valid_part(p) for p in parts):
            found.append(".".join(parts))
    return found


def palindromes_brute(word):
    """Every set of cut positions, kept when every piece reads the same backwards."""
    n, found = len(word), []
    for mask in range(1 << max(n - 1, 0)):  # bit i: cut after letter i
        pieces, start = [], 0
        for i in range(n - 1):
            if mask >> i & 1:
                pieces.append(word[start : i + 1])
                start = i + 1
        pieces.append(word[start:])
        if all(p == p[::-1] for p in pieces):
            found.append(pieces)
    return found


print(addresses_brute("172162541"), addresses_brute("10010"), addresses_brute("0000"))
print(palindromes_brute("noon"))
print("letters  cut sets tried  palindromic partitions  time")
for n in (14, 16, 18):
    word = "abcdefghijklmnopqrstuvwxyz"[:n]
    start = time.perf_counter()
    found = palindromes_brute(word)
    seconds = time.perf_counter() - start
    print(f"{n:7} {1 << (n - 1):>15,} {len(found):>23}  {seconds:.2f} s")
print(f"40 letters: {1 << 39:,} cut sets to try")

['17.216.25.41', '17.216.254.1', '172.16.25.41', '172.16.254.1', '172.162.5.41', '172.162.54.1'] ['1.0.0.10', '10.0.1.0'] ['0.0.0.0']
[['noon'], ['n', 'oo', 'n'], ['n', 'o', 'o', 'n']]
letters  cut sets tried  palindromic partitions  time
     14           8,192                       1  0.01 s
     16          32,768                       1  0.09 s
     18         131,072                       1  0.90 s
40 letters: 549,755,813,888 cut sets to try

For A the brute force is fine: 12 digits allow only C(11, 3) = 165 placements, and a search over parts of 1 to 3 digits is at most four levels deep with three choices each, 121 calls at most. The difficulty is in the rules. For B each letter doubles the cut sets. Words of distinct letters have a single partition, yet 18 letters cost 131,072 cut sets, and 40 letters would cost 549,755,813,888.

What to notice

A bad piece ruins every split that contains it, so check each piece the moment it is cut. For addresses, the digits left must also fit the parts left, one to three digits each. For palindromes, every single letter passes, so every branch of the search reaches a full partition. The work then follows the size of the answer, and only the checks need to become faster.

Restoring addresses step by step, with a dry run Pro: opens with a Pro, Premium or Ultimate pass