Toilet Seat Algorithm

Question

Let's take some regular house with a man, which has to go to the toilet every n minutes, requiring the seat to be up, and a woman, which has to do it every m minutes, requiring a seat to be down. Is there a possibility to create a O(1) algorithm which will output the exact number of toilet seat movements for a given period of X minutes? There are two different additional inputs:
1. The man always leaves the seat up after a visit.
2. The man always puts the seat down after a visit.

Conclusion: in the real life (which involves n being much more than m, with X->infinity), it is proven that there is no difference in a number of seat movements.
But if a man does it more often, then a woman, it will prolong the seat life if he will just leave the seat up, but is this case one of them (or both) should probably see a doctor.
Now I know what is the best for the seat itself, but which person makes more movements - is another question (which should not be asked anyways).

Answer 1

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 ];

Answer 2

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;

Answer 3

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.

Answer 4

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 [a*n, a*n+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)