Dynamic programming on trees

free/brute_force.py

"""The fewest cameras by brute force: try sets of halls, smallest sets first, and count the sets tried."""
import random
from itertools import combinations
from math import comb

from museum import build, halls_and_doors, random_museum


def fewest_cameras_brute(root):
    """The size of the smallest set of halls whose cameras see every hall, and how many sets were tried."""
    order, doors = halls_and_doors(root)
    tried = 0
    for k in range(1, len(order) + 1):
        for chosen in combinations(order, k):
            tried += 1
            seen = set(chosen)
            for hall in chosen:
                seen.update(doors[hall])
            if len(seen) == len(order):
                return k, tried
    raise AssertionError("a camera in every hall sees every hall")


MUSEUMS = {
    "museum A": ["A", "B", "C", "D", "E", None, "F", None, None, None, None, "G"],
    "museum B, a corridor of five halls": ["A", "B", None, "C", None, "D", None, "E"],
    "museum C, one hall": ["A"],
}
for label, names in MUSEUMS.items():
    k, tried = fewest_cameras_brute(build(names))
    print(f"{label}: {k} camera{'s' if k > 1 else ''}, {tried:,} set{'s' if tried > 1 else ''} of halls tried")

rng = random.Random(5)
for size in (10, 15, 20):
    k, tried = fewest_cameras_brute(random_museum(rng, size))
    print(f"a random museum of {size} halls: {k} cameras, {tried:,} sets tried")

# A corridor of n halls needs a camera in every third hall, so a smallest-first search first rejects every smaller set.
for n in (30, 60, 90):
    need = -(-n // 3)
    rejected = sum(comb(n, i) for i in range(need))
    print(f"a corridor of {n} halls needs {need} cameras; sets rejected first: {rejected:.2e}")

museum A: 2 cameras, 17 sets of halls tried
museum B, a corridor of five halls: 2 cameras, 8 sets of halls tried
museum C, one hall: 1 camera, 1 set of halls tried
a random museum of 10 halls: 3 cameras, 124 sets tried
a random museum of 15 halls: 6 cameras, 7,319 sets tried
a random museum of 20 halls: 8 cameras, 204,292 sets tried
a corridor of 30 halls needs 10 cameras; sets rejected first: 2.30e+07
a corridor of 60 halls needs 20 cameras; sets rejected first: 3.58e+15
a corridor of 90 halls needs 30 cameras; sets rejected first: 6.02e+23

free/museum.py

"""Museums as binary trees of halls, built from a level-order list of hall names (None where a hall is missing)."""
from collections import deque


class Hall:
    def __init__(self, name):
        self.name = name
        self.left = None
        self.right = None


def build(names):
    """The museum of a level-order list: the two halls below each hall follow in turn, None where there is none."""
    root = Hall(names[0])
    waiting = deque([root])
    i = 1
    while i < len(names):
        parent = waiting.popleft()
        for side in ("left", "right"):
            if i < len(names) and names[i] is not None:
                child = Hall(names[i])
                setattr(parent, side, child)
                waiting.append(child)
            i += 1
    return root


def halls_and_doors(root):
    """Every hall from the entrance down, and for each hall the halls one door away (its parent and children)."""
    order, doors, queue = [], {root: []}, deque([root])
    while queue:
        hall = queue.popleft()
        order.append(hall)
        for child in (hall.left, hall.right):
            if child is not None:
                doors[hall].append(child)
                doors[child] = [hall]
                queue.append(child)
    return order, doors


def random_museum(rng, size):
    """A random museum of `size` halls named h0, h1, ...: each new hall hangs at a random free place."""
    root = Hall("h0")
    places = [(root, "left"), (root, "right")]
    for k in range(1, size):
        parent, side = places.pop(rng.randrange(len(places)))
        child = Hall(f"h{k}")
        setattr(parent, side, child)
        places += [(child, "left"), (child, "right")]
    return root