Cigarette Smokers Problem
Three smokers each have one of three ingredients (tobacco, paper, matches). An agent randomly drops two of the three on the table; the smoker with the missing ingredient must roll and smoke. Tests whether the candidate can avoid 'helper threads' (Patil's restriction) and use only counting semaphores cleanly.
The setup
Suhas Patil posed this in 1971. To smoke a cigarette you need three ingredients: tobacco, paper, and matches. Three smokers sit at a table. Each smoker has an infinite supply of exactly one ingredient — let's call them the Tobacco-smoker, the Paper-smoker, and the Matches-smoker.
In the middle of the table is an agent. On every round the agent does this:
- Pick two of the three ingredients at random (one of three possible pairs).
- Put them on the table.
- Wait until somebody smokes.
- Repeat.
The rule for the smokers: the smoker whose ingredient is NOT on the table is the one who can roll and smoke. The other two have to wait — they already have what's on the table, but they're missing the third.
So the mapping is:
| Agent puts on table | Missing ingredient | Smoker who smokes |
|---|---|---|
| paper + matches | tobacco | Tobacco-smoker |
| tobacco + matches | paper | Paper-smoker |
| tobacco + paper | matches | Matches-smoker |
A picture of one round
The whole synchronization question is: how does the right smoker get woken up, given which pair is on the table?
Patil's twist (the reason this is a puzzle)
The artificial constraint
The agent's code is fixed. It can put ingredients down and signal, but it cannot contain if statements that pick which smoker to wake. The agent is "dumb" — it doesn't know who has what.
Without that rule, the problem is trivial: the agent looks at the pair, signals the right smoker, done. Patil's restriction is what makes the problem interesting.
So the smokers can't be woken directly by the agent. The agent only signals "tobacco is now on the table" and "paper is now on the table" (etc.) — three independent signals. Somebody has to assemble those signals into "the pair tobacco+paper appeared, wake the matches-smoker."
The trick: pusher threads
Add three helper threads called pushers, one per ingredient. Each pusher watches its own ingredient signal from the agent, then checks: is one of the OTHER two ingredients already on the table?
- If yes → the pair is now complete; wake the smoker who is missing the right one.
- If no → record "my ingredient is now on the table" and let the next pusher complete the pair.
The pushers form a small 3-input → 3-output dispatch table. Each pusher only knows about its own ingredient and a shared flag — none of them needs to know the smokers' identities.
What this problem actually tests
The real lesson "I have N event types and M subscribers, each waiting for a specific combination of events. Wake the right subscriber when its combination appears."
Production-grade equivalents of this same shape:
- CEP / Rete-style routing in engines like Drools or Esper.
- Reactive streams with
combineLatest/zipoperators (RxJava, RxJS, Project Reactor). - Event correlation in observability pipelines (alert when metric A and metric B fire within the same window).
The pushers are doing exactly what combineLatest does inside a reactive library: collect signals from independent sources, fire downstream when the right combination is complete.
Why most engineers haven't seen the puzzle
It's academic. In production, the dispatch logic lives in the producer ("I see tobacco+paper on the table → wake the matches-smoker"); Patil's "no if in the agent" rule doesn't appear in any real system. The puzzle is interesting precisely because the rule is artificial — it forces you to invent the dispatch layer instead of folding it into the producer.
If asked in an interview, lead with the simplification Senior move: "With Patil's restriction the canonical answer uses pusher threads. Without it I'd just put the dispatch logic in the agent. Which version do you want?" That signals you understand both the academic constraint and the judgment to relax it.
Implementations
Three pushers, one per ingredient. Each pusher waits for its ingredient to appear, then checks if the OTHER ingredient is also available. If both are, signal the smoker that needs them. Avoids putting logic in the agent.
1 import java.util.concurrent.Semaphore;
2
3 class Smokers {
4 private final Semaphore agent = new Semaphore(1);
5 private final Semaphore tobacco = new Semaphore(0);
6 private final Semaphore paper = new Semaphore(0);
7 private final Semaphore matches = new Semaphore(0);
8 private final Semaphore tobaccoSmoker = new Semaphore(0);
9 private final Semaphore paperSmoker = new Semaphore(0);
10 private final Semaphore matchesSmoker = new Semaphore(0);
11 private boolean isTobacco, isPaper, isMatches;
12 private final Object mu = new Object();
13
14 public void agent() throws InterruptedException {
15 while (true) {
16 agent.acquire();
17 // Random pair of ingredients
18 int r = (int) (Math.random() * 3);
19 if (r == 0) { tobacco.release(); paper.release(); }
20 else if (r == 1) { paper.release(); matches.release(); }
21 else { matches.release(); tobacco.release(); }
22 }
23 }
24 // Each pusher checks: did I just see the SECOND ingredient?
25 public void tobaccoPusher() throws InterruptedException {
26 while (true) {
27 tobacco.acquire();
28 synchronized (mu) {
29 if (isPaper) { isPaper = false; matchesSmoker.release(); }
30 else if (isMatches) { isMatches = false; paperSmoker.release(); }
31 else { isTobacco = true; }
32 }
33 }
34 }
35 // paperPusher and matchesPusher follow the same shape
36 public void smokerWithMatches() throws InterruptedException {
37 while (true) { matchesSmoker.acquire(); smoke(); agent.release(); }
38 }
39 }Key points
- •Three smokers, each with infinite supply of one ingredient
- •Agent puts two ingredients on the table; smoker with the third must take and smoke
- •Patil's restriction: NO conditional statements in the agent code (just put + signal)
- •Trick: use 'pusher' threads as helpers, they observe what's available and signal the matching smoker
- •Modern view: this 'difficulty' is contrived and the helpers pattern is fine