Kattis, Speed limit; read irregular input

Question

I am able to solve this challenge but when look at my code I know it is not good.

The challenge:

Bill and Ted are taking a road trip. But the odometer in their car is broken, so they don’t know how many miles they have driven. Fortunately, Bill has a working stopwatch, so they can record their speed and the total time they have driven. Unfortunately, their record keeping strategy is a little odd, so they need help computing the total distance driven. You are to write a program to do this computation.

For example, if their log shows

Speed in miles per hour | Total elapsed time in hours

20 | 2

30 | 6

10 | 7

this means they drove 2 hours at 20 miles per hour, then 6−2=4 hours at 30 miles per hour, then 7−6=1 hour at 10 miles per hour. The distance driven is then 2⋅20+4⋅30+1⋅10=40+120+10=170 miles. Note that the total elapsed time is always since the beginning of the trip, not since the previous entry in their log.

Input:

The input consists of one or more data sets. Each set starts with a line containing an integer n, 1≤n≤10, followed by n pairs of values, one pair per line. The first value in a pair, s, is the speed in miles per hour and the second value, t, is the total elapsed time. Both s and t are integers, 1≤s≤90 and 1≤t≤12. The values for t are always in strictly increasing order. A value of −1 for nsignals the end of the input.

Output:

For each input set, print the distance driven, followed by a space, followed by the word "miles".

Sample input:

3
20 2
30 6
10 7
2
60 1
30 5
4
15 1
25 2
30 3
10 5
-1

Sample output:

170 miles
180 miles
90 miles

I try to split the input to case-by-case group and solve it using calculate but end-up with deep nested list.

import Data.List.Split
main :: IO ()
main = do
 as <- map words . lines <$> getContents
 let bs = filter (not.null) $ splitWhen ((==1).length) as
 let cs = map (map (map (read :: String -> Int))) bs
 let ds = map calculate cs
 mapM_ putStrLn ds
calculate :: [[Int]] -> String
calculate xs = z
 where as = map head xs
 bs = map last xs
 cs = head bs : zipWith (flip (-)) bs (tail bs)
 ds = zipWith (*) as cs
 z = show (sum ds) ++ " miles"

The code is ugly especially on line 7: map (map (map (read :: String -> Int)))

There are lot of let and meaningless bindings (as, bs, ...) because I need to insert print xs to see what the list is look like after each step.

Reading code again without print output, I hardly get the picture what the list structure is. This can't be good.

How should I make it better?

• wizzup: Please forgive bad problem formatting, I am not good at markdown.

Answer 1

Your approach to the problem seems very imperative and whole-problem focused. Thinking in Haskell generally benefits from considering more bottom-up strategies, using smaller, easily tested, reusable pieces.

Right off the bat, your representation of the core datatype (a log of speeds and timestamps) seems ill-fitted. A list of list of Ints doesn't capture the fact that you know you will only be receiving pairs of numbers at a time.

type Speed = Int
type Timestamp = Int
type LogLine = (Speed, Timestamp)
type Log = [LogLine]
-- Less vitally...
type Logs = [Log]

Type aliases help provide documentation to readers of your code (including you as you write it, or come back to it after any significant stretch of time), use them liberally when working with the basic datatypes. The above set of aliases captures the input as it will be given to you (post- the act of parsing). Lists of pairs of numbers in the string input become []s of (,)s of Ints in Haskell.

Next we have to determine what sort of format we want to transform the data into in order to calculate an answer from it. The problem would be simple if we could replace those timestamps with durations, so we'll figure out a way to do that.

type Duration = Int
durations :: [Timestamp] -> [Duration]

Note that speeds won't be relevant when converting timestamps to durations, but we will need all of the timestamps in a log in order.

Once we have speed and duration pairs, solving for the solution should be easy.

type Distance = Int
calculate :: [(Speed, Duration)] -> Distance
calculate = sum . map (uncurry (*))

And if we hop in GHCi and test that definition with some hand-crafted data (i.e., the worked example given in the problem statement)—

λ sum . map (uncurry (*)) $ [(20, 2), (30, 4), (10, 1)]
170

Looks good. Now we work backward, filling in the pieces we left undefined, and combining them together as appropriate.

durations :: [Timestamp] -> [Duration]
durations ts = zipWith (-) ts (0:ts)
solve :: Log -> Distance
solve ls =
 let (speeds, timestamps) = unzip ls
 in calculate $ zip speeds (durations timestamps)

With a little more consideration (and certainly if we were willing to pull in the lens library) we could code golf the unzip/zip away and end up with a pithy one liner for solve, but often the most straightforward solution is more than adequate.

Now we need only deal with the parsing and pretty-printing aspects of the problem. Given that all of these code challenge tasks are similar, much of this is boilerplate you reuse from problem to problem, just make sure you're familiar with the contents of the Control.Monad module.

main :: IO ()
main = do
 n <- readLn
 if n == -1
 then return () -- End flag, don't recurse
 else do
 log <- replicateM n $ do
 [speed, timestamp] <- map read . words <$> getLine
 return (speed, timestamp)
 let distance = solve log
 putStrLn $ (show distance) ++ " miles"
 main -- recurse, look for the next trip

• wizzup: I made a mistake thinking that problem this level (easy) should easily solve by hacking it along the way, and it would wasteful to make any data type. Obviously your approach is way better.
• Zeta: @wizzup Rowan didn't create any data type. He only defined aliases. The important part is that he used [(Int, Int)] instead of [[Int]], which makes working a lot easier. I would have used sum $ zipWith (\(_,a) (x,b) -> x * (b - a)) ((0,0) : xs) xs for a "quickly hacked solution".