Communications of the ACM
Last byte
Upstart Puzzles: Sleep No More
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:
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.
Footnotes
All are invited to submit their solutions to [email protected]; solutions to upstarts and discussion will be posted at http://cs.nyu.edu/cs/faculty/shasha/papers/cacmpuzzles.html
Figures
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.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2016 ACM, Inc.
No entries found