Loading the glaze shed

A pottery loads its drying shed one shelf at a time. Filling every shelf as full as it goes is not the same as filling the shed.

The problem

The shed's back wall is a grid of slots, one string per shelf from the floor upward. A . is a sound slot; an x is a warped batten that holds nothing.

A tile going in is still wet, and wet glaze spoils. Two tiles in neighbouring slots on the same shelf touch at the edges and both are ruined. Mist also rolls off the front lip and rises, drifting one slot sideways, so a tile spoils the two slots diagonally above it. The slot directly above is safe.

Load as many tiles as the shed will take with nothing spoiled.

Input. shelves — a list of equal-length strings, one per shelf from the floor up, each character . or x.

Output. The largest number of tiles the shed can hold at once.

Example.

shelves = ["..x..",
           ".....",
           "x...x"]   ->  6

Two on the bottom shelf (slots 0 and 4), three on the middle (0, 2 and 4), one on the top (slot 2): the full middle shelf costs the top one, where only slot 2 escapes a diagonal.

A second example, where the tempting reading is wrong:

shelves = ["...",
           "..."]     ->  4

Slots 0 and 2 on both shelves: a tile straight above another is allowed, so the loading repeats.

Constraints.

• 1 <= len(shelves) <= 8
• 1 <= len(shelves[0]) <= 8
• every string in shelves is the same length

Hints

Approach

Brute force

Try every subset of sound slots and reject the ones with a clash: thirty sound slots is 2^30 subsets, a billion, each needing a scan.

The insight

Everything the shed remembers collapses into one 8-bit picture: which slots of the shelf you just filled are occupied.

Spoiling reaches one shelf and stops, so two shelves are independent once the one between them is fixed — the precondition a row-by-row table needs. A shelf has at most 2^8 loadings, so carry a best running total for each.

Algorithm

1. For each shelf, build sound, the mask of . slots, and list its legal loadings: masks with mask & ~sound == 0 and mask & (mask << 1) == 0.
2. Keep a table from loading of the shelf just placed to most tiles so far, starting at {0: 0}: an empty floor clashes with nothing.
3. For each legal mask, take the largest value whose key below satisfies mask & (below << 1) == 0 and mask & (below >> 1) == 0, and add the bit count of mask.
4. The answer is the largest value left after the top shelf.

Complexity

Time O(r · 4^c) — every pair of loadings is considered once per shelf, at most 8 · 256 · 256 pairs at r = c = 8. Space O(2^c) — one entry per loading of a single shelf.

Solution

"""Loading the glaze shed — row-by-row bitmask DP over shelf loadings."""


def shelf_loadings(shelf):
    """Every loading of one shelf: sound slots only, never two slots side by side."""
    sound = 0
    for i, slot in enumerate(shelf):
        if slot == ".":
            sound |= 1 << i
    return [mask for mask in range(1 << len(shelf))
            if mask & ~sound == 0 and not mask & (mask << 1)]


def solve(shelves):
    # State is the loading of the shelf just placed, because spoiling reaches
    # exactly one shelf: anything lower is already accounted for by the total.
    best = {0: 0}                       # empty floor below the first shelf
    for shelf in shelves:
        nxt = {}
        for mask in shelf_loadings(shelf):
            tiles = bin(mask).count("1")
            for below, placed in best.items():
                # A tile is spoiled by a diagonal neighbour only, so `below` is
                # compared shifted; the unshifted overlap is legal on purpose.
                if mask & (below << 1) or mask & (below >> 1):
                    continue
                if placed + tiles > nxt.get(mask, -1):
                    nxt[mask] = placed + tiles
        best = nxt                      # mask 0 is always legal, so this is never empty
    return max(best.values())

TESTS = [
    ((["..x..", ".....", "x...x"],), 6),
    ((["...", "..."],), 4),
    ((["x...", "...x"],), 3),
    ((["xxx", "xxx"],), 0),
    (([".x."],), 2),
    ((["."],), 1),
    ((["........"] * 8,), 32),
    ((["x.x.x.x.", "........", ".x.x.x.x"],), 8),
]

Pitfalls

• Banning a tile directly above another. Reading the rule as eight-way touching turns the two-by-three shed into 2 instead of 4. The vertical overlap is deliberate.
• Filling each shelf greedily. Locally largest loadings claim 2 + 3 + 2 = 7 on the first example; the middle shelf has to be paid for above it.
• Enumerating masks without the sound filter. The first example then reports 9, loading warped battens.

Variants

• Booking the soundstages — the same no-two-neighbours choice on one line, where the state is a single bit.
• Wax pours — a subset as state again, but the bits are blocks used, not slots.