Brandon.Si(mmons)

code / art / projects

Some Haskell Boilerplate for Google CodeJam

I put together a skeleton module which should be usable for any of the problems in this year’s Google CodeJam Programming Contest (as long as they don’t adopt a new format/pattern for the problems this year). The module includes some useful parsing functions which should in the worst case be useful as a cheatsheet for those not too experienced with Parsec (*cough me). I hope it will encourage people to sign up and use Haskell in the contest!

To adapt the module to a problem, one defines the following:

  1. a type Case into which we will parse a test case (i.e. problem)

  2. a type SolvedCase, representing a solution to a test case

  3. our algorithm :: Case -> SolvedCase

  4. a Parser caseParser which can parse a single test case (n.b. not the whole file) into the Case type

  5. a function formatCase :: SolvedCase -> String which brings the solution to the state where it can be prepended with the standard “Case #1: ” string

Here is the module, filled in to solve the Minimum Scalar Product practice problem. You can download the code here:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
module Main
where

import Text.ParserCombinators.Parsec
import IO hiding (try)
import System.Environment

-- PROBLEM-SPECIFIC IMPORTS --  
import Data.List (sort)
import Control.Arrow

------------------------------  

-- the input file will be parsed into a list of some type representing  
-- individual cases to be solved by our algorithm:  
type Input = [Case]

-- our algorithms will produce a list of some type SolutionCase:  
type Solution = [SolvedCase]

-- we convert each solved case into a String, which is zipped with  
-- the standard "Case #x: " strings for the final output  
type Output = [String]

-- --------------- BEGIN EDITING --------------- --  

-- DEFINE A TYPE TO REPRESENT A SINGLE UNSOLVED TEST CASE: --  
type Case =
    -- EXAMPLE: a pair of lists of Ints (our "vectors"):  
    ([Int],[Int])


-- DEFINE A TYPE TO REPRESENT A SINGLE SOLVED TEST CASE: --  
type SolvedCase =
    -- EXAMPLE: our Minimum Scalar Product as an Int:  
    Int


-- -- -- ALGORITHMS -- -- --  


-- SOLVE A TEST CASE HERE:  
algorithm :: Case -> SolvedCase
algorithm =
    -- EXAMPLE: simply sort both lists, reverse one, and combine:  
    sum . uncurry (zipWith (*)) . (reverse . sort *** sort)



-- -- -- PARSING INPUT -- -- --  


-- DEFINE PARSER FOR A TEST CASE: --  
caseParser :: Parser Case
caseParser = do
    -- EXAMPLE: parses a case consisting of 3 lines: the first describes the   
    -- number n of elements in the following two lines, the next two lines   
    -- have n space-separated elements:  
    w <- word
    let n = read w
    as <- count n word
    bs <- count n word
    return (map read as, map read bs)


-- -- -- FORMAT OUTPUT -- -- --  

-- DEFINE A FUNCTION FROM AN INDIVIDUAL SolvedCase -> String.   
formatCase :: SolvedCase -> String
formatCase sol =
    -- EXAMPLE: nothing to speak of here:  
    show sol



-- --------------- STOP EDITING --------------- --  


--------------------  
-- IO BOILERPLATE --  
--------------------  


main = do
    -- pass the input file name to our program:  
    (f:_) <- getArgs
    file <- readFile f

    -- start parsing, solve problem, and prepare output:   
    let inp = parseWith mainParser file
    solution = map algorithm inp
    solutionStrings = map formatCase solution
    outp = zipWith (++) prefixes solutionStrings

    -- write the prepared output to screen:  
    putStr $ unlines outp


-- dies with error, or returns some datatype with our parsed data:  
parseWith p = either (error . show) id . parse p ""

-- to begin parsing, we read in a line containing the number of test cases   
-- to follow. We parse them with caseParser, returning a list:  
mainParser :: Parser Input
mainParser = do
    n <- word
    ms <- count (read n) caseParser
    return ms
   <?> "mainParser"

-- strings to prepend to output:  
prefixes = [ "Case #" ++ show n ++ ": " | n <- [1..]]



---------------------  
-- VARIOUS PARSERS --  
---------------------  


-- -- LINE PARSERS -- --  


-- a single line String, up to the newline:  
wholeLine :: Parser String
wholeLine = manyTill anyChar (try newline) <?> "wholeLine"

-- parse a String with whitespace-separated values into [String]  
whiteSepLine = manyTill spaceSepWord newline <?> "whiteSepLine"


-- -- WORD PARSERS -- --   

-- a single word followed by whitespace (space, newline, etc.):  
word = do
    w <- many1 nonWhite
    spaces
    return w
   <?> "word"

-- a single word followed by one or more ' ' characters (won't consume '\n')  
spaceSepWord = do
    w <- many1 nonWhite
    many (char ' ')
    return w
   <?> "spaceSepWord"


-- e.g. "hello:world" ---> ("hello","world")  
-- won't consume newlines  
    twoWordsSepBy c = do
    x <- manyTill nonWhite (try$ char c)
    y <- many1 nonWhite
    many (char ' ')
    return (x,y)
   <?> "twoWordsSepBy"


-- -- CHARACTER PARSERS -- --  

-- nonWhitespace character:  
nonWhite = noneOf " \v\f\t\r\n" <?> "nonWhite"

Comments