Practice: Splitting Market Stalls Between Two Days

Stalls that sell the same goods must not trade on the same day; decide whether two days are enough and which stall goes where.

Splitting things into two groups so that no two things that clash share a group is the bipartite test in disguise. This exercise gives a market with seven stalls and asks for the split.

A weekend market runs on two days. Two stalls that sell any of the same goods must trade on different days.

The table lists each stall and the goods it sells.

The seven stalls and the goods each sells
Stall	Goods
Ana	bread, eggs
Ben	bread, cheese
Caro	cheese, honey
Dev	honey, eggs
Eli	flowers
Fay	flowers, plants
Gus	fish

Draw the graph: which stalls are the vertices, and which pairs are the edges?
Are two days enough? If so, which stalls trade on each day?
How many separate groups of stalls are there, groups whose days can be decided without looking at the others?
A new stall, Hal, wants to sell bread and honey. Are two days still enough?

Answer all four parts, then compare with the run below.

The stalls' days, with each clash and the goods behind it
Day	Stalls	Clashes it separates
Day 1	Ana, Caro, Eli, Gus	Ana from Ben (bread) and Dev (eggs); Caro from Ben (cheese) and Dev (honey); Eli from Fay (flowers)
Day 2	Ben, Dev, Fay	Gus clashes with no one and could trade on either day

The stalls are the vertices, and an edge joins two stalls that share a good. Ana, Ben, Caro and Dev form a cycle of 4 edges, which is even, so it colours. Eli and Fay share one edge, and Gus has none. A breadth-first search from each stall not yet coloured gives the two days and finds 3 groups. Hal clashes with Ana and Ben over bread, and Ana and Ben clash with each other, so Ana, Ben and Hal form a cycle of 3 edges and two days are no longer enough. The listing below builds the graph from the goods and colours it.

stalls.pypy

from collections import deque

STALLS = {
    "Ana": {"bread", "eggs"},
    "Ben": {"bread", "cheese"},
    "Caro": {"cheese", "honey"},
    "Dev": {"honey", "eggs"},
    "Eli": {"flowers"},
    "Fay": {"flowers", "plants"},
    "Gus": {"fish"},
}


def clash_graph(stalls):
    names = list(stalls)
    graph = {name: [] for name in names}
    for i, a in enumerate(names):
        for b in names[i + 1:]:
            if stalls[a] & stalls[b]:
                graph[a].append(b)
                graph[b].append(a)
    return graph


def two_days(graph):
    day = {}
    groups = 0
    for start in graph:
        if start in day:
            continue
        groups += 1
        day[start] = 1
        queue = deque([start])
        while queue:
            stall = queue.popleft()
            for other in graph[stall]:
                if other not in day:
                    day[other] = 3 - day[stall]
                    queue.append(other)
                elif day[other] == day[stall]:
                    return None, groups
    return day, groups


graph = clash_graph(STALLS)
print("clashes:", ", ".join(f"{a}-{b} ({' '.join(sorted(STALLS[a] & STALLS[b]))})" for a in graph for b in graph[a] if a < b))
day, groups = two_days(graph)
print(f"separate groups of stalls: {groups}")
if day is None:
    print("two days are not enough")
else:
    for d in (1, 2):
        print(f"day {d}: {' '.join(name for name in STALLS if day[name] == d)}")
STALLS["Hal"] = {"bread", "honey"}
graph = clash_graph(STALLS)
day, groups = two_days(graph)
print(f"with Hal (bread, honey): {'two days are not enough' if day is None else 'two days suffice'}")

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

clashes: Ana-Ben (bread), Ana-Dev (eggs), Ben-Caro (cheese), Caro-Dev (honey), Eli-Fay (flowers)
separate groups of stalls: 3
day 1: Ana Caro Eli Gus
day 2: Ben Dev Fay
with Hal (bread, honey): two days are not enough

← → move through sections and cards