Standing the pipe rank

An organ builder's shop book has one rule for standing a rank of pipes: two pipes may stand side by side only if their speaking lengths add to a perfect square. Nobody remembers why, and nobody breaks it.

The problem

A rank is a single row of pipes on the windchest, read left to right. Every pipe in the box goes into it — none is left out and none is added. The shop rule applies to neighbours only: for each pair of pipes standing next to each other, the two speaking lengths in millimetres must add to a perfect square. Pipes that are not neighbours never constrain one another.

The pipes are plain unmarked metal, so two cut to the same length cannot be told apart. Two orders are the same arrangement when one becomes the other by swapping equal-length pipes.

Count the distinct arrangements of the whole rank that obey the rule.

Input. lengths — a list of integers, the speaking length of each pipe in millimetres.

Output. The number of distinct left-to-right orders of all the pipes in which every neighbouring pair of lengths sums to a perfect square.

Example.

lengths = [4, 12, 21]   ->  2

4 + 12 = 16 and 4 + 21 = 25, but 12 + 21 = 33 is not a square, so the 4 has to stand in the middle: 12, 4, 21 and 21, 4, 12.

A second example, where two pipes are cut alike:

lengths = [9, 9, 16, 16]   ->  2

9 + 16 = 25 is the only join available — 18 and 32 are not squares — so the rank alternates: 9, 16, 9, 16 or 16, 9, 16, 9. Telling the two nines apart, and the two sixteens, would report 8 orders where there are only 2 arrangements.

Constraints.

• 1 <= len(lengths) <= 12
• 1 <= lengths[i] <= 10^9
• Lengths may repeat.
• No order need exist; the answer is then 0.

Hints

Approach

Brute force

Generate all n! orders and check the n - 1 joins in each. At twelve pipes that is 479,001,600 orders and roughly five billion square tests, and duplicates force you to hold the accepted orders in a set to deduplicate them.

The insight

A half-built rank needs only two facts to be finished: which pipes are already standing, and which one is on the right-hand end.

The rule looks at neighbours and nothing else, so the next pipe is legal or not by the current right end alone. Two different build orders that used the same set and ended on the same pipe therefore have exactly the same completions, and can share one counter. With n <= 12 the set is twelve bits, giving 2¹² · 12 = 49,152 states in place of 479 million paths.

Algorithm

1. Precompute joins[i][j] — whether lengths[i] + lengths[j] is a perfect square, using an integer square root.
2. Seed ways[1 << i][i] = 1 for every i: any pipe may start the rank.
3. Sweep masks in increasing order. From a non-zero state (mask, last), extend to each unused j with joins[last][j], adding the count into (mask | 1 << j, j).
4. Add up ways[full][i] over every i. That is the count with the pipes treated as distinguishable.
5. Divide by c! for each length occurring c times, and return the result.

Complexity

Time O(2ⁿ · n²) — 49,152 states, each trying at most twelve extensions: under 600,000 steps. Space O(2ⁿ · n) for one counter per state, 49,152 integers.

Solution

"""Standing the pipe rank — bitmask DP over the set of pipes already standing."""

from collections import Counter
from math import factorial, isqrt


def is_square(total):
    """True when total is a perfect square; isqrt avoids float rounding."""
    root = isqrt(total)
    return root * root == total


def solve(lengths):
    n = len(lengths)
    joins = [[is_square(lengths[i] + lengths[j]) for j in range(n)] for i in range(n)]
    full = (1 << n) - 1

    # ways[mask][last]: orders of exactly the pipes in mask, with `last` on the
    # right-hand end, counting the pipes as distinguishable. Nothing else about
    # mask can affect what comes next, because the rule only sees neighbours.
    ways = [[0] * n for _ in range(1 << n)]
    for i in range(n):
        ways[1 << i][i] = 1

    for mask in range(1 << n):           # masks only grow, so a state is final when read
        row = ways[mask]
        for last in range(n):
            count = row[last]
            if not count:
                continue
            for nxt in range(n):
                if mask >> nxt & 1 or not joins[last][nxt]:
                    continue
                ways[mask | 1 << nxt][nxt] += count

    total = sum(ways[full])
    # Each real arrangement was counted once per permutation of its equal-length
    # pipes among themselves, so take that factor back out.
    for repeats in Counter(lengths).values():
        total //= factorial(repeats)
    return total

TESTS = [
    (([4, 12, 21],), 2),
    (([9, 9, 16, 16],), 2),
    (([5, 20, 20, 44],), 6),
    (([3, 5, 7],), 0),
    (([7],), 1),
    (([8, 8],), 1),
    (([16, 9, 9, 16, 7],), 3),
    (([1, 3, 6, 10, 15, 21],), 4),
]

Pitfalls

• Not dividing out the repeats. The sweep counts labelled orders, so [9, 9, 16, 16] comes back as 8 — every real arrangement counted 2!·2! times.
• Seeding one start instead of all of them. Filling only ways[1][0] returns 0 on [4, 12, 21], because a rank beginning with the 4 dies at the second join.
• Making the table boolean. A reachability table answers "can the rank be stood at all", not "how many ways": on [5, 20, 20, 44] it reports 1 where the answer is 6.
• Assuming a single pipe is a special case. One pipe has no joins, so it stands one way; the answer there is 1, not 0.

Variants

• Booking the soundstages — another count under a neighbours-only rule, where the state is the last row rather than a subset.
• Tree, digit and bitmask DP — where the "subset held in an integer" state comes from.