I was checking out the latest Google Code Jam round and came across a cute problem called Broken Clock and decided to try my hand at it (in Haskell, of course).
Then, I read the provided analysis and saw that it stopped one step short of introducing some basic number theory that could result in a pretty elegant solution. I thought this was a bit of a shame, so I decided to write up some thoughts here.
Analysis
First, let's formalize how to think about the problem. We're effectively looking for a number of nanoseconds after midnight that could lead to the angles given in the input. Once we have the number of nanoseconds, it's just about doing divisions and taking remainders to convert that into the H M S NS format required by the output. Let's call this number of nanoseconds value N. The problem statement tells us that the hours hand rotates by 1 tick each nanosecond, the minutes hand rotates by 12 ticks each nanosecond, and the seconds hand rotates by 720 ticks each nanosecond. Let's ignore the rotation part for now and assume the clock is oriented properly. If we let H, M, S be the number of ticks for each hand, we might write the following to relate N to H, M and S:
H = N
M = 12N
S = 720N
This is pretty close. If N = 10 (i.e., 10 nanoseconds after midnight), we expect the hour hand to be at 10 ticks, the minute hand at 120 ticks, and the second hand at 7200 ticks. However, these equations aren't quite what we want once we reach N = 60000000000 (i.e., 60 seconds after midnight). In this case, H = 60000000000 and M = 720000000000 are still what we expect, but S = 43200000000000. Of course, 60 seconds after midnight, we expect the second hand to have returned back to 0, and our equations don't currently capture that. We model this using modular arithmetic. Let D = 43200000000000, the number of ticks in one 360-degree revolution.
H mod D = N mod D
M mod D = 12N mod D
S mod D = 720N mod D
From here, it's just a small modification to account for arbitrary rotations of the clock. If the clock needs to be rotated by R ticks before being read, we can write the following:
H mod D = (N + R) mod D
M mod D = (12N + R) mod D
S mod D = (720N + R) mod D
What we've done so far is to construct a system of equations that relate the angles of the clock hands, the global rotation of the clock, and the number of nanoseconds after midnight. If we know how many nanoseconds have elapsed since midnight (N) and we know how the clock was rotated (R), these equations give us a way to determine the angles of all of the hands. More interestingly, we can also go the other way: if we know all of the angles, we may be able to solve for N and R, with N effectively being what we need to output.
So how do we go about solving this system of equations? The process is complicated by the fact that we're working in modular arithmetic, where the rules are slightly different than the algebra we learn in grade school. One of the things we can do, however, is subtract one equation from another. Let's subtract the first equation from the second and the second from the third to eliminate R.
(M - H) mod D = 11N mod D
(S - M) mod D = 708N mod D
It's worth stepping back here and looking at what these equations are now telling us. Every nanosecond that elapses, the minute hand gets ahead of the hour hand by 11 ticks, and the second hand gets ahead of the minute hand by 708 ticks. This happens irrespsective of how the clock is rotated, which makes intuitive sense. In the problem, we're given M and H, so we know how far apart they are. Focusing on the first difference equation, we only have one unknown. Surprisingly, just knowing how far apart the minute and hour hand are yields a lot of information, and we can extract that information by solving the first difference equation.
If we ignore the mod D momentarily, we see that we effectively want to divide (M - H) by 11 in order to obtain N. Fortunately, even under mod D, this division happens to be possible, using what's known as the modular multiplicative inverse. The basic idea is that multiplying by the multiplicative inverse is essentially some form of division. Note that the conditions for existence of the inverse are satisfied because 11 is a prime number, so that gcd(11, d) = 1. There's more number theory behind this that I don't have time to dive into, but here I'll just point out that the fact that the minute hand gets ahead of the hour hand by 11 ticks each nanosecond, combined with the fact that 11 doesn't share any prime factors with the number of ticks on the clock face means that any difference (i.e., any value for (M - H)) corresponds to some time. In other words, there always exists a solution to the first equation. Neat, huh?
At this point, we have a few options for finding multiplicative inverse of 11, a few of which are listed in the Wikipedia article. The extended Euclidean algorithm is a good option that is generally useful to know for these sorts of contests, so those who regularly participate likely already have it in their toolbox. However, under Code Jam rules, we have an additional option that takes even less effort. Since this problem only calls for the inverse of a single number, 11, we can hop over to our friend Wolfram Alpha and type in 11x = 1 mod D; it tells us the following:
x = 43200000000000n + 15709090909091 for integer n
Taking n=0, we conclude that dividing by 11 is the same as multiplying by 15709090909091 when we're working in mod D. If you're skeptical at this point, you can try a few examples to convince yourself. If (M - H) is 2, then "dividing" by 11 in this way gives 31418181818182. Sure enough, you can punch 31418181818182*11 into a calculator to get 345600000000002, which does indeed give a remainder of 2 under mod 43200000000000.
We've thus established that, if we know how far apart the minute and hour hand are, we can determine a candidate time in nanoseconds. Furthermore, if the hands are in a valid arrangement, this candidate time will also satisfy the second difference equation. If it does not satisfy the second difference equation as well, then this arrangement of hands is not valid.
So, if we knew which hand was which, solving the system of equations above yields a very simple algorithm for determining how many nanoseconds have elapsed since midnight.
- Compute (M - H) mod D
- Multiply by 15709090909091 in mod D to get a candidate N
- Check that 708N is equivalent to (S - M) in mod D. If so, N is a valid solution. Otherwise, no solution exists.
Of course, we don't know which hand is which, but this doesn't pose much of a problem. There are only three hands, and therefore only 3! = 6 possible arrangements. Our solution can simply try all 6 and pick the first one that yields a valid solution. We are guaranteed by the problem that at least one valid solution will exist.
Haskell Solution
Let's start with a very basic modular arithmetic function to help us "divide by 11". It uses the magic constant that we got from Wolfram Alpha above. We also define a constant ticksInHalfDay so that we don't need to keep typing out 43200000000000.
ticksInHalfDay :: Integer
ticksInHalfDay = 12 * 60 * 60 * 1000000000
divideBy11 :: Integer -> Integer
divideBy11 x = (x * 15709090909091) `mod` ticksInHalfDay
Then, we can write a fairly straightforward implementation of the algorithm for solving the system of difference equations for N. We leverage Haskell's Maybe functor to represent the fact that a proposed arrangement of hands may not have a solution. If it does, we return it. If it does not, we return Nothing.
getSatisfyingNanoseconds :: [Integer] -> Maybe Integer
getSatisfyingNanoseconds [ah, am, as] =
let minutesToHours = (am - ah + ticksInHalfDay) `mod` ticksInHalfDay
secondsToMinutes = (as - am + ticksInHalfDay) `mod` ticksInHalfDay
candidate = divideBy11 minutesToHours
in if (708 * candidate `mod` ticksInHalfDay == secondsToMinutes)
then Just candidate
else Nothing
Finally, we write one more function that takes the angles in an unknown order, as the problem specifies, and then uses this getSatisfyingNanoseconds function to try every permutation. Data.List has a permutations function that gives a list of all permutations of a list. In this case, it takes our list of angles ([Integer]) and returns all permutations of these angles ([[Integer]]). By mapping our getSatisfyingNanoseconds function over these permutations, we get a list of Maybe results ([Maybe Integer]). Since we are guaranteed that every test case has at least one valid solution, at least one of these results is guaranteed to be a Just, while the others might be Nothing. The very nice catMaybes function in Data.Maybe takes this [Maybe Integer] and squishes it down to a plain [Integer] by removing the Nothing values. We just need any valid answer, so we choose the head of the list (which, again, is guaranteed to exist).
findSolution :: [Integer] -> Integer
findSolution angles =
let ps = permutations angles
nanoseconds = catMaybes $ map getSatisfyingNanoseconds ps
in head nanoseconds
That's the bulk of it! Here's the complete solution, including the input and output part of it.
import Control.Monad
import Data.List
import Data.Maybe
ticksInHalfDay :: Integer
ticksInHalfDay = 12 * 60 * 60 * 1000000000
divideBy11 :: Integer -> Integer
divideBy11 x = (x * 15709090909091) `mod` ticksInHalfDay
getSatisfyingNanoseconds :: [Integer] -> Maybe Integer
getSatisfyingNanoseconds [ah, am, as] =
let minutesToHours = (am - ah + ticksInHalfDay) `mod` ticksInHalfDay
secondsToMinutes = (as - am + ticksInHalfDay) `mod` ticksInHalfDay
candidate = divideBy11 minutesToHours
in if (708 * candidate `mod` ticksInHalfDay == secondsToMinutes)
then Just candidate
else Nothing
findSolution :: [Integer] -> Integer
findSolution angles =
let ps = permutations angles
nanoseconds = catMaybes $ map getSatisfyingNanoseconds ps
in head nanoseconds
toHMSN :: Integer -> [Integer]
toHMSN n = [h, m, s, ns]
where h = n `div` (60 * 60 * 1000000000)
m = (n `mod` (60 * 60 * 1000000000)) `div` (60 * 1000000000)
s = (n `mod` (60 * 1000000000)) `div` (1000000000)
ns = n `mod` 1000000000
printCase :: Show a => Integer -> [a] -> IO ()
printCase c r = putStrLn ("Case #" ++ show c ++ ": " ++ showSpaces r)
where showSpaces = intercalate " " . map show
readInteger :: (String -> Integer)
readInteger = read
main :: IO ()
main = do
t <- readLn :: IO Integer
forM_ [1..t] $ \cas -> do
line <- getLine
let angles = map readInteger $ words line
answer = toHMSN $ findSolution angles
printCase cas answer