Code Golf: The Unisex Restroom Simulation

Question

Background

The unisex restroom problem is a classical synchronization problem in computer science.

The general class of problems that this simulates is as follows: If you have k types of threads that need to execute tasks using n shared resources, and at any time only one thread type may be using the resources, then it's a generalization of a unisex bathroom problem. Here k=2 and there exists some n which is the number of bathroom stalls; the threads represent humans who need to use the bathroom; and the two types, male and female, obviously cannot share the restroom.

Challenge

The unisex restroom at a small local hole-in-the-wall tavern goes into maintenance halfway through the normal business hours. The tavern is famous for having a roaring trade for its size; thus the twenty minutes in which it is unusable lead to a sizable queue forming. Sadly, the tavern is in an abandoned part of town and the streets are highly unsanitary and sketchy, and so nobody would dare think to go elsewhere. The restroom's reopening thus is a major event every night, and people have been looking for a fair, efficient algorithm for determine who goes in when.

The constraints:

• At any time, only women or men may be in the restroom. If the next person to enter is the opposite sex, then all of the people already using the bathroom must finish doing their business.
• Up to n women or men may use the stalls at a time. When one leaves, if the next person to enter is of the same gender, that person may immediately occupy that stall.
• The men in the queue and the women in the queue must use the restroom in the order they arrive. A man may preempt women (or a woman may preempt men) if that allows for greater efficiency; however, a man may not preempt another man, nor a woman preempt another woman, at any time.

The input:

• The number of stalls in the unisex restroom
• The queue of customers who have arrived to use the restroom (in the order they have arrived), along with how long they will spend in the restroom when it is their turn.

I'm leaving the input format slightly open to interpretation. This is because some languages do better with certain small modifications to input. For example, in the default input below I assume that the restroom queue will simply continue until EOF; however, if you want to either require that the size of the queue be specified first, or that there should be some sentinel value at the end, or whatever... any of that is fine, but I want you to make clear exactly what your input format is.

You can also do minor tweaks to it if it will shorten your character count-- just let me know what you do. (Note: Minor tweaks are things like whitespace... not like changing characters or otherwise making the format look completely different when run through a whitespace-ignoring diff program.)

Here's the default input scheme:

• The input is newline delimited.
• The first line will contain the number of stalls for the restroom, in decimal numeric form.
• The second and later lines will contain two pieces of information: The character M or W (which signifies man or woman); and a number indicating how many time units the person will take.
• The end of input is here signified by EOF. (As I said, this can definitely be changed. Just tell me how you change it)

The task:

• Try to determine the optimal order for allowing women and men to use the restroom, such that everyone finishes in the minimum total amount of time.
• Print who goes in the restroom at what times, in order.
• Do this with the smallest amount of source code you can.

The output:

• Line-delimited output like the following: (12) woman uses stall 3 (time: 5)
• The first number denotes what zero-based time the person starts using the restroom; the gender is obviously important; and then the zero-based stall number and her use duration is printed according to the above format.
• In that case, the woman started at time 12, using stall 3; at time 17, the stall becomes available again. If the next person to enter is a woman, and assuming nobody finishes earlier than time 17, then that woman can use stall 3 at time 17. (If the next person is a man, then everyone else needs to finish first!)
• At the end, print something like (31) done.

Examples

(Note: For the first one, any order that obeys the main constraints is okay; this is because no matter what, this is a serial problem. Also, for any of these your mileage can vary... the goal is to have the shortest "done" time.)

Input:
1
W 5
M 2
W 10
M 4
M 10
Output:
(0) woman uses stall 0 (time: 5)
(5) man uses stall 0 (time: 2)
(7) woman uses stall 0 (time: 10)
(17) man uses stall 0 (time: 4)
(21) man uses stall 0 (time: 10)
(31) done.

Input:
3
M 4
M 10
W 2
M 3
W 3
M 3
M 2
W 5
W 2
Output:
(0) woman uses stall 0 (time: 2)
(0) woman uses stall 1 (time: 3)
(0) woman uses stall 2 (time: 5)
(2) woman uses stall 0 (time: 2)
(5) man uses stall 0 (time: 4)
(5) man uses stall 1 (time: 10)
(5) man uses stall 2 (time: 3)
(8) man uses stall 2 (time: 3)
(9) man uses stall 0 (time: 2)
(15) done.

Input:
2
M 10
W 1
M 2
M 2
M 3
W 6
M 2
W 4
M 2
M 1
W 2
Output:
(0) man enters stall 0 (time: 10)
(0) man enters stall 1 (time: 2)
(2) man enters stall 1 (time: 2)
(4) man enters stall 1 (time: 3)
(7) man enters stall 1 (time: 2)
(9) man enters stall 1 (time: 2)
(10) man enters stall 0 (time: 1)
(11) woman enters stall 0 (time: 1)
(11) woman enters stall 1 (time: 6)
(12) woman enters stall 0 (time: 4)
(16) woman enters stall 0 (time: 2)
(18) done.

Evaluation Metrics

The winner is the poster of the solution with the shortest amount of source code by character count.

Answer 1

Perl, 215 211 215 char

Last edit: fixed spelling mistake and display to relative stall time. Newlines are not significant.

sub Q{@q=map"$% $_",0..$n-1;for(grep s/$_[0]//,@n){($%,$s)=split$",pop@q;
$_+=0;$o.="($%) $@man enters stall $s (time: $_)\n";$%+=$_;
@q=sort{$b-$a}@q,"$% $s"}$%=$q[0]}
$n=(@n=<>)[0];Q M;$@=wo;Q W;print"$o($%) done.\n"

---

$ perl usbr.pl < usbr1
(0) man enters stall 2 (time: 4)
(0) man enters stall 1 (time: 10)
(0) man enters stall 0 (time: 3)
(3) man enters stall 0 (time: 3)
(4) man enters stall 2 (time: 2)
(10) woman enters stall 2 (time: 2)
(10) woman enters stall 1 (time: 3)
(10) woman enters stall 0 (time: 5)
(12) woman enters stall 2 (time: 2)
(15) done.

In subroutine Q, we initialize an array @q with elements that encode the current time and the available stalls. Then you iterate over the patrons, popping the first available stall from the top of @q and adding a new element to @q showing when that server will be available again.

THis solution uses the special perl variable $% to represent the "time". $% is always an integer, so it is safe and effective to make assignments like $%="14:3" and get $%=14.

Normally I'd say ladies first, but it turns out that letting the men go first saves about 6 strokes! :-)