Opinion
Computing Applications Last byte

Upstart Puzzles: Sleep No More

Posted
  1. Article
  2. Author
  3. Footnotes
  4. Figures
Sleep No More, illustration
As with every alarm clock, this one can hardly wait to ring, and you must figure out how to set it to wake you when your nap is over, making as few button pushes as possible.

We begin simply, with a 60-minute clock that counts only minutes, from 0 to 59. The alarm can also be set from 0 to 59 and will go off when the clock reaches the same value. Say you want the alarm to go off in m (m < 60) minutes, the time value now is x, and the alarm value is y. You want to move the time value or alarm value forward as little as possible so the alarm goes off m minutes from now.

Warm-up. The time is at 20 minutes, and the alarm is at 5 minutes. You want the alarm to go off in 35 minutes. One option is to move the alarm forward (the only allowable direction) to 55. Another is to move the time value ahead to 30. The second is less expensive, requiring only 10 pushes, so you prefer that.

In general, for this 60-minute clock, if T is the time value and A is the alarm value and you want to wake up in m (< 60) minutes, which value do you move and at what cost in terms of number of minutes ahead you must push that value?

Solution. Recall (y-x) mod 60 = yx if x < y or (y+60) – x, otherwise; for example, (14-4) mod 60 = 10, but (4-14) mod 60 = 50; (y-x) mod 60 is thus the number of minutes on the 60-minute clock value y is ahead of x.

Let L2 be the minimum non-negative value having the property m = (A – (T+L2)) mod 60. L2 is the number of minutes we would have to advance the time to achieve our goal of waking up in m minutes. We call it timeadvance and solve for it as follows:

ueq01.gif

If timeadvance(A, T, m) <= 30, then advance the time by that amount, else advance the alarm by 60 – timeadvance(A, T, m). End of solution.

Now imagine you have a 24-hour clock for both alarm and time. You are faced with the same problem. You want the alarm to go off in m minutes, where m can now be any number up to (24 x 60) – 1 minutes.

You can move the hour value (between 0 and 23) for both time and alarm separately from the minute value (between 0 and 59). Each move forward by one of any hour or minute counter costs one unit of effort. (Moving the minute value past 59 to 0 does not affect the hour value.)

Is it ever an advantage to move both a time value and an alarm value, as opposed to just one?

Solution. Yes. Suppose the time is set at 15:18 and the alarm is 14:50. You want the alarm to go off in 30 minutes. The best thing is to move the alarm forward by one hour and the time to 15:20, costing a total of three units of effort.

Can you now find an elegant, cost-minimizing algorithm for the problem? The alarm clock will still have the pleasure of waking you up, but you will have the satisfaction of knowing the clock will never know what time it really is.

Back to Top

Back to Top

Back to Top

Figures

UF1 Figure. As with every alarm clock, this one can hardly wait to ring, and you must figure out how to set it to wake you when your nap is over, making as few button pushes as possible.

Back to top

Join the Discussion (0)

Become a Member or Sign In to Post a Comment

The Latest from CACM

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

Learn More