Home → Magazine Archive → April 2016 (Vol. 59, No. 4) → April 2016 (Vol. 59, No. 4) → Abstract

Upstart Puzzles: Sleep No More

By Dennis Shasha

Communications of the ACM, Vol. 59 No. 4, Page 96

[article image]

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.


No entries found