Sign In

Communications of the ACM

Last byte

Upstart Puzzles: Sleep No More


View as: Print Mobile App ACM Digital Library Full Text (PDF) In the Digital Edition Share: Send by email Share on reddit Share on StumbleUpon Share on Hacker News Share on Tweeter Share on Facebook
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.

Credit: Andrij Borys Associates / Shutterstock

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 = y - x 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

Author

Dennis Shasha (dennisshasha@yahoo.com) is a professor of computer science in the Computer Science Department of the Courant Institute at New York University, New York, as well as the chronicler of his good friend the omniheurist Dr. Ecco.

Back to Top

Footnotes

All are invited to submit their solutions to upstartpuzzles@cacm.acm.org; solutions to upstarts and discussion will be posted at http://cs.nyu.edu/cs/faculty/shasha/papers/cacmpuzzles.html

Back to Top

Figures

UF1Figure. 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


Copyright held by author.

The Digital Library is published by the Association for Computing Machinery. Copyright © 2016 ACM, Inc.


 

No entries found