Bead kit bracelets

A workshop kit comes with four bins of beads and a paper plan that says which bin each slot on the thread is drawn from. The tutor wants every bracelet the plan allows, printed on one sheet.

The problem

The kit has four bins, each stocked with a fixed set of colours:

bin a  ->  r (ruby), g (grass), b (bronze)
bin b  ->  y (yolk), o (ochre)
bin c  ->  p (plum), w (wheat), k (kelp)
bin d  ->  t (teal), n (navy)

A plan is a string of bin labels, one per slot, read left to right. Slot i takes any one colour from the bin named at position i. Bins never run out, so a bin may appear in several slots and a colour may be used more than once.

Produce every bracelet the plan allows, as a string of colour letters in slot order. An empty plan describes no bracelet, so its answer is the empty list.

Input. plan — a string of bin labels drawn from a, b, c, d.

Output. A list of strings, one per bracelet. The examples list them in the order the search produces, taking each bin's colours in the order written above.

Example.

plan = "ab"   ->  ry, ro, gy, go, by, bo

Bin a offers three colours and bin b offers two, so there are six bracelets: every ruby-first bracelet, then every grass-first one, then bronze.

A second example, showing that a repeated bin is not a repeated bead:

plan = "bb"   ->  yy, yo, oy, oo

Both slots draw from bin b, and yy is legal — the bin holds plenty of yolk beads. plan = "" gives [].

Constraints.

• 0 <= len(plan) <= 8
• Every character of plan is one of a, b, c, d
• The bin table above is fixed and is not part of the input

Hints

Approach

Brute force

Multiply the bin sizes, then decode every index below that product into a bracelet by repeated division and remainder. An eight-slot plan of bin a gives 6,561 bracelets, each costing eight divisions plus a mixed-radix table you have to build and keep right.

The insight

One slot's choice never restricts another's, so the bracelets are exactly the leaves of a tree whose branching factor at depth i is the size of slot i's bin — build the string as you descend and read it off at each leaf.

Independence is the precondition. Nothing ties two slots together and no bin runs out, so no branch can fail and the search needs no pruning — just a base case at depth len(plan). The number of calls is then within a constant factor of the number of bracelets.

Algorithm

1. If the plan is empty, return the empty list.
2. Call extend(0) with an empty working list of beads.
3. If slot == len(plan), join the beads into a string, record it, and return.
4. Look up the bin for plan[slot].
5. For each colour in that bin: append it, call extend(slot + 1), then pop it.

Complexity

Time O(L · B^L) where L is the plan length and B the largest bin — the number of leaves times the cost of joining each. Space O(L) for the working beads and the recursion depth, excluding the output.

Solution

"""Bead kit bracelets — one slot at a time, every colour the bin allows."""

BINS = {
    "a": "rgb",   # ruby, grass, bronze
    "b": "yo",    # yolk, ochre
    "c": "pwk",   # plum, wheat, kelp
    "d": "tn",    # teal, navy
}


def solve(plan):
    if not plan:
        return []                     # no slots means no bracelet, not an empty one
    bracelets, beads = [], []

    def extend(slot):
        if slot == len(plan):
            bracelets.append("".join(beads))
            return
        # invariant: `beads` holds one chosen colour for each slot before `slot`
        for colour in BINS[plan[slot]]:
            beads.append(colour)
            extend(slot + 1)
            beads.pop()               # free the slot for the next colour in this bin

    extend(0)
    return bracelets

TESTS = [
    (("ab",), ["ry", "ro", "gy", "go", "by", "bo"]),
    (("c",), ["p", "w", "k"]),
    (("",), []),
    (("da",), ["tr", "tg", "tb", "nr", "ng", "nb"]),
    (("bb",), ["yy", "yo", "oy", "oo"]),
]

Pitfalls

• Returning [""] for an empty plan instead of []. One is "a bracelet with no beads", the other is "no bracelet"; the second is what the workshop means.
• Forgetting the pop after the recursive call leaves the previous colour in place, so slot lengths grow and the joined strings run long.
• Recording the working list rather than the joined string stores a reference that later pops empty out.
• Indexing the bins by slot number rather than by the label at that slot breaks as soon as the plan repeats a bin, as in "bb".

Variants

• Carillon peals — the same left-to-right construction, except the choices are consumed, so each one narrows what is left.
• Donation hampers — a two-way choice per position, with a rule that suppresses branches leading to repeats.