AllenDowney / LittleBookOfSemaphores

LaTeX source and supporting code for The Little Book of Semaphores, by Allen Downey.
273 stars 77 forks source link

Clarify the rules of the Sushi Bar problem #20

Open Spoonbender opened 2 years ago

Spoonbender commented 2 years ago

The sushi bar problem description doesn't clarify all the rules that the solution must comply with. The rules can be inferred from the solutions, but they should be stated in advance.

For reference, here is the problem description as of version 2.2.1

Imagine a sushi bar with 5 seats. If you arrive while there is an empty seat, you can take a seat immediately. But if you arrive when all 5 seats are full, that means that all of them are dining together, and you will have to wait for the entire party to leave before you sit down.

Scenario 1:

  1. Bar is filling up with customers #1-#5, all 5 seats are now taken
  2. Customer #6 arrives, sees bar is full, realizes he must wait for entire party to leave
  3. Customer #1, who was just seated and eating, leaves the bar
  4. Customer #7 arrives, sees only 4 seated customers and 1 empty sit, has no reason to think the 4 customers are dining together...
    • Question: can customer #7 sit down?
    • By looking at the solutions: no, customer #7 must wait (expressed by the must_wait variable). He somehow knows the 4 customers are a party, even though he never saw the 5 seats full in his own eyes. Perhaps customer #6 told him.

Scenario 2:

  1. Bar is filling up with customers #1-#5, all 5 seats are now taken
  2. Customer #1, who was just seated and eating, leaves the bar
  3. Customer #6 arrives, sees only 4 seated customers and 1 empty sit, has no reason to think the 4 customers are dining together...
    • Question: can customer #6 sit down?
    • By looking at the solutions: no, customer #6 must wait. He somehow knows the 4 remaining customers used to be 5 and are part of a party, even though no other customer has arrived to see all 5 seats full. Maybe there is a waiter telling him, or maybe there is a "bar is full" sign hanging.

A different interpretation of these rules will yield a different solution, and might lead to other questions such as "do we need to ensure no-starvation?"

AllenDowney commented 2 years ago

Thanks for pointing this out. I am saving up issues like this for the next time I revise the book because it is more efficient for me to handle them in batches. But I will get to it as soon as I can!