Sleep No More
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.
All are invited to submit their solutions to
firstname.lastname@example.org; solutions to upstarts
and discussion will be posted at http://cs.nyu.edu/cs/
Dennis Shasha ( email@example.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.
Copyright held by author.
amount, else advance the alarm by
60 – timeadvance(A, T, m). End of
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.
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-neg-ative 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:
timeadvance(A, T, m) = (A – (T+m))
If timeadvance(A, T, m) <=
30, then advance the time by that
DOI: 10.1145/2892635 Dennis Shasha
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.