Toilet Seat Algorithm

Question

Yes, there is a basic O(1) algorithm.

I start with the assumption both people start "ticking" at t=0. I believe the solution should generalize to different starting times, but it isn't hard to extend from one "free end" of the timeline to two ends.

Assume n <= m.

Then our timeline looks like this (an 'x' marks a 'move', not a visit)

  0     m    2m    ..              t-t%m  t
  +-----+-----+-----+-----+-----+-----+--o
W x     x     x     x     x     x     x 
M x  x    x    x       x     x    x     x?

So, the woman goes floor(t/m) times, and between each time the woman goes -- in the half-open interval (a*m,*m+m] -- the man goes at least once, thus flipping the seat once. for each time that she flips the seat in an interval, he also flips it once. However, he possibly will go once more after her last trip, depending on their relative timings, which you can calculate based on t modulo their respective periods.

total_moves = floor(t/m) * 2 + (t%m < t%n ? 1 : 0)

Now for the case n > m.

The roles of the woman and man are reversed... the half-open interval [an, an+n) will always involve two moves. The remainder of the line is [t-t%n, t), in which the man goes once at the beginning, (which is +1 move, but we counted +2 for both people's moves at t=0, which we should probably discard) and the woman goes if she has equal or less time left than he does

total_moves = floor(t/n) * 2 - 1 + (t%m >= t%n ? 1 : 0)

For 2, the answer is 2*floor(X/n). The man will always go to the bathroom with the toilet seat down and leave it down. The woman will never put it down, since it's only up when the man goes to the bathroom.

1 is a little more tricky.

EDIT: Duh. For 1, the answer is 2*floor(X/m). The toilet seat only transitions when the woman goes to the bathroom.

EDIT2: Plus or minus the initial state of the toilet.

EDIT3: My answer to 1 is only correct if m>=n. I'll figure out the rest later.

EDIT4: If n>=2m, then it's 2*floor(X/n), since the seat will only transition when the man goes pee. If n>m, I believe the answer is also 2*floor(X/n), but I need to work out the math.

EDIT5: So, for 2m>n>m, the seat transitions when the man goes pee after the woman and vice versa. The sequence of man/woman visits repeats every least_common_multiple(m, n) minutes, so we only need to concern ourselves with what happens in that time period. The only time the seat would not transition when the man uses it would be if he managed to visit it twice in a row. Given that the woman is visiting more often than the man, between every man visit there is at least one woman visit. (Twice at the beginning or end.)

Answer 1 then becomes: (n>m ? 2*floor(X/n) : 2*floor(X/m)) + (remainder(X/n) > remainder(X/m) ? 1 : 0). Or something like that.

Yes there is, at least when the implementation can assume that the cycle for a man and a woman is known in advance and that it doesn't change:

Start with the least common multiple of the man/woman cycle times (lcm). Precalculate the movements for this time period (lcm_movements). Now you only have to deal with your input time modulo lcm. For this you could simply set up a fixed length table containing the number of movements for every minute.

Given that time and lcm are integers in Java/C/C++/C# the actual calculation might be this:

return ( time / lcm ) * lcm_movements + movements[ time % lcm ];

Assumptions:

• we start at t=0 with the toilet seat down
• if man and woman arrive at the same time, then ladies first.

Let lastLadyTime := floor(X/m)*m and lastManTime := floor(X/n)*n. They represent the last time of toilet usage. The expression (lastLadyTime > lastManTime) is the same as (X%m < X%n) because by definition X%m = X - lastLadyTime and X%n = X - lastManTime.

Case: man leaves seat down
The lady never has to move the seat but he always needs to lift it up. Hence floor(X/n).

Case: man leaves seat up, n == m
He will always need to lift it up and she will always need to push it down except at the very first toilet usage when she doesn't have to do anything. Hence 2*floor(X/n) - (X < n ? 0 : 1)

Case: man leaves seat up, n > m
Every time he uses it, he needs to lift it up. She only needs to push it down once after he uses it. This happens all the time except at the end if time runs out before she gets to use the toilet after him. Therefore we must minus 1 if lastManTime >= lastLadyTime (remember, ladies first). Hence 2*floor(X/n) - (lastManTime >= lastLadyTime ? 1 : 0) = 2*floor(X/n) - (X%n <= X%m ? 1 : 0)

Case: man leaves seat up, n < m
Similar to n > m. Every time she uses it, she needs to push it down. He only needs to lift it up once after she uses it. This happens all the time except at the end if time runs out before he has to use the toilet after her. Therefore we must minus 1 if lastManTime < lastLadyTime. Also one difference is that he needs to lift the seat the first time around. Hence 2*floor(X/m) - (lastManTime < lastLadyTime ? 1 : 0) + (X < n ? 0 : 1) = 2*floor(X/m) - (X%n > X%m ? 1 : 0) + (X < n ? 0 : 1)

If all minute variables are integers then you could do it like this:

int toilet_seat_movements = 0;
bool seat_up = false;

for (i = 0; i <= total_minutes; i++)
{
    if (seat_up)
    {
        if (i % woman_minutes == 0)
            toilet_seat_movements++;
    }
    else
    {
        if (i % man_minutes == 0)
            toilet_seat_movements++;
    }
}

return toilet_seat_movements;