Istahar Black

Greenhorn

Posts: 1

posted 8 years ago

I'm trying to learn Design Patterns and come up with this problem.

The problem: There are 100 prisoners in solitary cells. and a living room with one light bulb; this bulb is initially off. No prisoner can see the light bulb from his own cell. Everyday, the warden picks a prisoner equally at random (that, in theory, the same prisoner may be chosen for 1000 consecutive days), and that prisoner visits the living room. While there, the prisoner can toggle the bulb if he she wishes. Also, the prisoner has the option of asserting that all 100 prisoners have been to the living room by now. If this assertion is true, all prisoners are set free. The prisoners are allowed to get together one night in the courtyard, to discuss a plan. What plan should they agree on, so that eventually, someone will make a correct assertion? (Detailed info can be reached here)

The solution: The prisoners choose a Leader. Initially each prisoner is a Lighter except the Leader. Whenever a Lighter enters the room he turns the light bulb on if it's off and becomes a Sleeper. A Sleeper does nothing whatsoever. Whenever the Leader enters the room he increments his counter by 1 if the light is on and turns the light off. So, after turning the bulb off for 99 times he knows that all other prisoners have been into the room at least once.

Implementation of this algorithm (Java): Rather easy as you'd expect. I've created a class called Prisoner. A prisoner has these attributes: status (Leader, Lighter, Sleeper) and count. This class also have a method called "visit". I also have other classes: TheRoom, Guardian, Time, etc.

So far okay.

Here is my trouble. There are also other algorithms to solve this problem. The algorithm above is the worst one; it takes (on average) more than 10 years before the Leader can claim that everybody has been into the room.

Solution 2: There is no pre-chosen Leader. The first prisoner to enter the room for the second time

Implementation of this second algorithm: Still baby thing. But, either I need to rewrite most of the code or I need to put some "if"s in the visit method; that if the agreed strategy is Fixed Leader than

So far still okayish, but...

There are even better algorithms. One of them is called

Now, the visit method really gets messy. I can do it but the reason I bug is that I'm trying to learn Design Patterns and do things Object Oriented way, and properly.

I reckon that a prisoner should also have a strategyAgreed attribute and I should have a classes for each strategy. Then, whenever somebody come up with a new strategy I just write new Strategy class without messing up the previous code.

But I couldn't figure out how to implement this. Say the prisoner class looks like:

Now, whenever the guardian takes a random prisoner to the room the prisoner's visit method should consult to the proper strategy class according to the prisoner.strategyAgreed property and act according to the prisoner.status property. How do I do that?

I guess I will need to have interfaces, but aren't interfaces for multiple objects implementing the same method? Here I have one basic object (prisoner) oh whom method (visitRoom) varies according to his status and the agreed strategy, and that confuses me.

I didn't want to write a different class for Leader, Lighter, Sleeper, etc. because a Sleeper is no different from a prisoner only that his role differs. And if I did that I'd have to turn an object into another object which (I guess) is needless here.

Please let me make one point clear: I did write the algorithms for all known methods and they all work. I'm not trying to find a way to solve this question. I'm trying to learn how to design OO way.

Sorry, if this was long.

The problem: There are 100 prisoners in solitary cells. and a living room with one light bulb; this bulb is initially off. No prisoner can see the light bulb from his own cell. Everyday, the warden picks a prisoner equally at random (that, in theory, the same prisoner may be chosen for 1000 consecutive days), and that prisoner visits the living room. While there, the prisoner can toggle the bulb if he she wishes. Also, the prisoner has the option of asserting that all 100 prisoners have been to the living room by now. If this assertion is true, all prisoners are set free. The prisoners are allowed to get together one night in the courtyard, to discuss a plan. What plan should they agree on, so that eventually, someone will make a correct assertion? (Detailed info can be reached here)

The solution: The prisoners choose a Leader. Initially each prisoner is a Lighter except the Leader. Whenever a Lighter enters the room he turns the light bulb on if it's off and becomes a Sleeper. A Sleeper does nothing whatsoever. Whenever the Leader enters the room he increments his counter by 1 if the light is on and turns the light off. So, after turning the bulb off for 99 times he knows that all other prisoners have been into the room at least once.

Implementation of this algorithm (Java): Rather easy as you'd expect. I've created a class called Prisoner. A prisoner has these attributes: status (Leader, Lighter, Sleeper) and count. This class also have a method called "visit". I also have other classes: TheRoom, Guardian, Time, etc.

So far okay.

Here is my trouble. There are also other algorithms to solve this problem. The algorithm above is the worst one; it takes (on average) more than 10 years before the Leader can claim that everybody has been into the room.

Solution 2: There is no pre-chosen Leader. The first prisoner to enter the room for the second time

**for the first time**is the Leader. This way we gain about 3000 days on average.Implementation of this second algorithm: Still baby thing. But, either I need to rewrite most of the code or I need to put some "if"s in the visit method; that if the agreed strategy is Fixed Leader than

*do these*, if the agreed strategy is Dynamic Leader then*do those*, etc.So far still okayish, but...

There are even better algorithms. One of them is called

*Multiple Counter Method*where the Leader has helpers called Counters, etc.Now, the visit method really gets messy. I can do it but the reason I bug is that I'm trying to learn Design Patterns and do things Object Oriented way, and properly.

I reckon that a prisoner should also have a strategyAgreed attribute and I should have a classes for each strategy. Then, whenever somebody come up with a new strategy I just write new Strategy class without messing up the previous code.

But I couldn't figure out how to implement this. Say the prisoner class looks like:

Now, whenever the guardian takes a random prisoner to the room the prisoner's visit method should consult to the proper strategy class according to the prisoner.strategyAgreed property and act according to the prisoner.status property. How do I do that?

I guess I will need to have interfaces, but aren't interfaces for multiple objects implementing the same method? Here I have one basic object (prisoner) oh whom method (visitRoom) varies according to his status and the agreed strategy, and that confuses me.

I didn't want to write a different class for Leader, Lighter, Sleeper, etc. because a Sleeper is no different from a prisoner only that his role differs. And if I did that I'd have to turn an object into another object which (I guess) is needless here.

Please let me make one point clear: I did write the algorithms for all known methods and they all work. I'm not trying to find a way to solve this question. I'm trying to learn how to design OO way.

Sorry, if this was long.

John Kimball

Ranch Hand

Posts: 96

posted 8 years ago

I didn't really read everything, but it sounds like Strategy pattern (fancy name for a simple concept, imho). This lets you plug in different types of algorithms at run time, for the same problem.

In some other languages and for simple problems, this is solved using a function pointer.

In some other languages and for simple problems, this is solved using a function pointer.