Skip to content

Instantly share code, notes, and snippets.

@zdavkeos
Created April 30, 2013 23:14
Show Gist options
  • Save zdavkeos/5492644 to your computer and use it in GitHub Desktop.
Save zdavkeos/5492644 to your computer and use it in GitHub Desktop.
Haskell solution to the ACM North Central North America Regional Programming Contest Problem 5: Clock Repair
-- Problem 5: Clock Repair
--
-- November 3, 2007
-- ACM North Central North America Regional Programming Contest Problem 5
-- acm.org
--
-- Mr. Horologia's House of Clocks contains various cuckoo clocks that
-- customers have brought in for repair. Since they are in the clock
-- shop, one might rightly assume that these clocks don't quite run as
-- they should. In fact, a fast clock may take 3500 seconds to advance
-- one hour, instead of 3600 seconds. A slow clock might take 3750
-- seconds. Each clock makes a sound like a cuckoo once each hour,
-- precisely on the hour. That is, a clock will "cuckoo" when it
-- displays 12:00, 1:00, 2:00, and so forth. Of course, the displayed
-- time when it cuckoos will not necessarily correspond to the real
-- time, since the clock may be running fast or slow. Every midnight on
-- Sunday morning, Mr. Horologia sets all clocks to exactly 12:00. He has
-- sufficient assistants awake at that hour that all clocks can be set
-- simultaneously. Some time later, possibly that same day but quite
-- possibly several days later, all clocks in the room will cuckoo at
-- precisely the same instant in time. (All clocks initially would chime
-- when they are set at midnight on Sunday, but the initial cuckooing
-- does not count.) What is the first day, hour, minute, and second when
-- all clocks simultaneously go off? The time might be several days in
-- the future; also, midnight on the next Sunday morning might come
-- around again before they ever cuckoo simultaneously. In this latter
-- case, Mr. Horologia will set them all again, and the correct answer
-- would be "Never".
--
-- Example
--
-- An easy example involves two clocks, one that advances an hour every
-- 3000 seconds, and a second clock that advances an hour every 4500
-- seconds. For simplicity, note that these represent 50 minutes and 75
-- minutes, respectively. The first clock would reach 1:00 AM after 50
-- minutes, then 2:00 AM after 100 minutes, and 3:00 AM after 150
-- minutes. The second clock would reach 1:00 at 75 minutes and 2:00 at
-- 150 minutes. Thus, 150 minutes after midnight, clock number one and
-- clock number two both cuckoo. The correct answer is thus "Sunday at
-- 2:30:00 AM". A second example might involve four clocks, all of which
-- are extremely fast. They advance at 600, 1200, 1800, and 600
-- seconds. After 30 minutes, all of them cuckoo except for the second
-- clock. After 60 minutes, all will cuckoo. Thus the answer here is
-- "Sunday at 1:00:00 AM". Finally, suppose we have four clocks with
-- speed s of 3601, 3559, 3600, and 3700. The answer in this case is
-- "Never" -- the next Sunday will occur before all clocks cuckoo.
--
-- Input
--
-- There will be multiple cases, sequentially numbered starting with
-- 1. The input for each case is a single line that contains integers
-- giving the number of clocks N, followed by N "seconds" measurements. A
-- line containing the integer 0 follows the last case. Because the
-- repair shop is limited, N will never be larger than 10.
--
-- Output
--
-- For each case, display the case number and either the first date and
-- time when all clocks will cuckoo simultaneously, or the word "Never"
-- as described above. Display a blank line after the output for each
-- case.
--
-- Sample Input
--
-- 2 3000 4500
-- 4 600 1200 1800 600
-- 3 3550 3650 3655
-- 2 3525 3625
-- 0
--
-- Output for the Sample Input
--
-- Case 1: Sunday at 2:30:00 AM
-- Case 2: Sunday at 1:00:00 AM
-- Case 3: Never
-- Case 4: Friday at 9:58:45 PM
--
-- Solution: The number we want it the least common multiple of all
-- the clock periods. To do this, we construct a list of the times
-- that each clock will chime (cuckoo) in the coming week. From these
-- lists we take the first time that is similar to all of them (set
-- intersection). This time is the nubmer of seconds since midnight
-- Sunday.
import Data.List
import Data.Maybe
import Text.Printf
-- all chimes in a week's time
chimes :: Int -> [Int]
chimes prd = takeWhile ((3600 * 24 * 7) >=) $ map (*prd) [1..]
-- lcm(list of periods)
solve :: [Int] -> Maybe Int
solve prds = case take 1 $ foldl1 intersect $ map chimes prds of
[] -> Nothing
[r] -> Just r
solveLine :: String -> Maybe Int
solveLine "0" = Nothing
solveLine l = solve $ map read $ tail $ words l
secToDate :: Maybe Int -> String
secToDate Nothing = "Never"
secToDate (Just t) = day t ++ " at " ++ hms t
day :: Int -> String
day t = case t `div` (3600 * 24) of
0 -> "Sunday"; 1 -> "Monday"
2 -> "Tuesday"; 3 -> "Wednesday"
4 -> "Thursday"; 5 -> "Friday"
6 -> "Saturday"
-- seconds -> hh:mm:ss am/pm
hms :: Int -> String
hms t = let t' = t `mod` (3600 * 24) -- seconds since midnight
(h, t'') = t' `divMod` 3600 -- seconds since the hour
(m, s) = t'' `divMod` 60
ampm = if h >= 12 then "PM" else "AM"
in printf "%d:%02d:%02d %s" (h `mod` 12) m s ampm
-- run like:
-- > echo -e "2 3000 4500\n4 600 1200 1800 600\n3 3550 3650 3655\n2 3525 3625" | runhaskell clock_repair.hs
main :: IO ()
main =
interact (unlines . map (secToDate . solveLine) . lines) >>
putStr "\n"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment