Prisoners problem

Description

Prisoners sample shows how to implement solution visualization for well-known logical problem.

Problem

Court has found ten criminals guilty and sentenced them to punishment with following conditions.

  • Every criminal will be put to his own isolated room without any possibility to communicate with other criminals.
  • Every day (beginning from the first day of imprisonment) at morning one criminal will be selected by warden and be put to the special punishment cell. At evening of the day criminal will be returned back to his room.
  • There is a lamp in the punishment cell. Criminal being in the cell can turn this lamp on or off. Warden controls that criminal don't leave any messages in the cell other then state of the lamp. At the same time only criminals being in the cell turn the lamp on or off.
  • The imprisonment will finish the day when one of the criminals notifies jailer that every of the ten criminals have been visited the punishment cell at least once. If this notification is true then the criminals will be released otherwise they will be executed.
  • Before the imprisonment the criminals are collected and have a possibility to develop an algorithm of release. This algorithm can't take in account means didn't described in this problem statement.
  • Warden has a plan of punishment cell visits for infinite number of days. Also warden is present at criminals' algorithm development so he can modify his plan basing on knowledge of the algorithm.
  • There are two limitations for the warden's plan: every prisoner will visit the punishment cell, after each visit of the cell prisoner will be put there again after finite number of days.

The problem is to create criminals' algorithm.

Solution

Let us select one prisoner who will collect information. We'll call him a Head. Other criminals will supply information to the Head using the lamp. Note that every criminal should notify the Head about visiting the cell and at the same time notifications from different criminals shouldn't overlap.

  • Every criminal but the Head must turn the lamp on exactly one time.
  • Only the Head can turn the lamp off. Turning the lamp off he finds out that one more criminal has visited the cell at least one time.
  • The Head is the criminal who is put to the cell at the first day. If the lamp at the first day is turned on then he turns it off. It is reasonable that he doesn't think that any of the other criminals has been put to the cell before the first day.
  • When the Head have turned the lamp off nine times he would notify the jailer.

The behavior of each criminal could be easily described by state machine. This state machine is defined in the sample.

Sample Features

In the sample one state machine describes behavior of the ten criminals. At every moment active states of different criminals may differ. To distinguish criminals we use unique Config for each criminal and one ConfigStore that will select appropriate Config basing on event context. Warden Event Provider puts number of selected criminal to Event parameters. StateMachineEngine in turn puts all event parameters to event context.

Run Sample from Eclipse

To run sample from within Eclipse.

  1. Import “com.evelopers.unimod.sample.prisoners” sample into the Eclipse workspace (see Samples Usage Guidelines).
  2. Open “resources/diagrams/prison.unimod”.
  3. Select state machine A1 on Connectivity Diagram.
  4. Open context menu and select “Launch A1!”.