Day 2 is another parse-and-compute problem. I opted for a simple lazy list processing parser, with a couple of neat tricks thanks to Arrow combinators.
On a hunch, I wrote the first part in the form of a higher order function. It payed up: the second part was trivial to write.
The Problem
We are given a dataset of unknown length, with the following
structure. The explicit newlines (\n) are there to make
the explanation easier to follow.
A Y\n
B X\n
C Z\n
...Each line correspons to a round of Rock-Paper-Scissors.
The first column will always contain A, B, or C, which
correspond to Paper, Rock, and Scissors, as played by your
opponent. The second column will always contain X, Y, or Z.
For the first part, they represent a «cheat code» of what we
should play, meaning Rock, Paper, and Scissors, respectively.
Each round is scored depending on its outcome, and what you play. The scoring should be obvious from the code below.
Part A wants the total score for all the games.
Main Program
The main program is pretty much the same as Day 1.
Playing the game
The solution for Part A has the signature
partA :: String -> Intand we can break its implementation in three parts:
Parse the input String into a list of «turns»
turns :: String -> [Turn]Have a way to «score» each turn, and
mapit over the list.score :: Turn -> IntAdd the list.
This leads to a high level implemenation like so
partA = sum . map score . turnsYou’ll notice I’m using Int instead of Integer. This has to do
with my wanting to illustrate the use of the Enum typeclass for scoring.
Strong static typing go brrr
Let’s create a simple model for Rock-Paper-Scissors using
Haskell types. I’ve already mentioned the notion of Turn
to represent each line to process. And every Turn is actually
comprised of what the opponent and we will Play.
This suggest the following sum type to model each player’s action
data Play = Rock | Paper | Scissors
deriving (Show,Eq,Enum)with the natural relation
beats :: Play -> Play -> Bool
Rock `beats` Scissors = True
Scissors `beats` Paper = True
Paper `beats` Rock = True
_ `beats` _ = FalseAs mentioned before, the scoring rules given in the problem’s
description assign specific values to each Play. When a Haskell
sum type has an Enum instance, a bijection with the Int datatype
is created, counting from 0. So, for scoring as per the problems
description we write
valueOf :: Play -> Int
valueOf = succ . fromEnumA Turn is nothing more than a pair with Plays from the opponent
and ourselves. Instead of using a plain tuple, I chose a product
type with record notation for simplicity
data Turn = Turn { they :: Play
, we :: Play
}
deriving (Show)I was able to complete the scoring rules by writing
score :: Turn -> Int
score turn | they turn == we turn = valueOf (we turn) + 3
score turn | they turn `beats` we turn = valueOf (we turn)
score turn | we turn `beats` they turn = valueOf (we turn) + 6This combines the valueOf our Play for the Turn, with the offset
depending on the outcome of the turn, thus solving (2)
Parsing the input
I built my parser using pure list manipulation functions, step by step using the REPL. It went like this
ghci> f <- readFile "input.txt"
f :: String
ghci> take 3 $ lines f
["A Y","B Y","B Z"]Using lines gives us a list with each line; I always use take so I can
look at the beginning instead of the whole thing. Now I need to
get the first and third letters. Here’s how knowing about
Arrows makes it easy to write.
Granted operator
(&&&) :: Arrow a => a b c -> a b c' -> a b (c,c')has a strange signature when you look at it. Regular functions happen to be arrows, so the above operator, in the context of plain functions can be thought of as
(&&&) :: (b -> c) -> (b -> c') -> b -> (c,c')That is, if you have two functions that can work on the same domain type, this operator gives you a new function that operates on a single argument producing a tuple with both results, e.g.
ghci> ((*2) &&& even) 21
(42,False)Back to our parsing problem, I need the first and third character from each line. So I write
ghci> take 3 $ map ((!! 0) &&& (!! 2)) $ lines f
[('A','Y'),('B','Y'),('B','Z')]Neat!
The last step is to actually use our Turn type. At this point
I was about to write a simple helper function with signature
(Char,Char) -> (Play,Play)or even
(Char,Char) -> Turnbut my laziness kicked in.
Recall that you don’t know about Part B until you’ve successfully completed Part A. While reading the latter, I had a hunch that the «meaning» of the second column was going to change for Part B. Instead of «hardcoding» transformations inside the parsing code, I decided to abstract it in the form of a higher order function:
playWith :: ((Char,Char) -> (Play,Play))
-> String
-> [Turn]
playWith style = map (tupleToTurn . style . (!! 0) &&& (!! 2)) . lines
where
tupleToTurn (t,m) = Turn t mso I could pass any function style able to «change the meaning» of
the second column, before turning it into an actual Turn.
Back to solving Part A
For Part A, we’re told to interpret A, B, and C, as
Rock, Paper, and Scissors, respectively, and to interpret
X, Y, or Z, as Rock, Paper, and Scissors, respectively.
This results in
charToPlay :: Char -> Play
charToPlay c | c == 'A' || c == 'X' = Rock
charToPlay c | c == 'B' || c == 'Y' = Paper
charToPlay c | c == 'C' || c == 'Z' = ScissorsRecall the function
playWith :: ((Char,Char) -> (Play,Play))
-> String
-> [Turn]where the first argument is the transformation we want from our
source tuple to the actual Play interpretation. That is, we
need to write a function with type
(Char,Char) -> (Play,Play)But we already have charToPlay! We would need to apply it to
each argument of the tuple, and produce the result as a tuple.
That is something that you can definitely do via pattern-matching,
and that’s left as an exercise to the reader. Arrow makes it
very easy, thanks to operator
(***) :: Arrow a => a b c -> a b' c' -> a (b, b') (c, c')which, in the context of functions, can be thought of as
(***) :: (b -> c) -> (b' -> c') -> (b, b') -> (c, c')This allows us to write
turns :: String -> [Turn]
turns = playWith (charToPlay *** charToPlay)and now partA is complete!
How does that help with Part B?
Once Part A was solved using the preceding implementation, the
specification for Part B became available. We’re told to keep
interpreting A, B, and C as they were in Part A, but the meanings
for X, Y, and Z have now changed. Instead of being interpreted
as what to play, they are to be interpreted as the desired outcome
for each round: an X means «play to lose», Y means «play to draw»,
and Z means «play to win».
So I wrote a couple of helper functions for figuring out how
to win or lose to a particular Play,
toBeat :: Play -> Play
toBeat Rock = Paper
toBeat Paper = Scissors
toBeat Scissors = Rock
toLose :: Play -> Play
toLose Rock = Scissors
toLose Paper = Rock
toLose Scissors = PaperNow, the solution for partB becomes
partB = sum . map score . predict
where
predict :: String -> [Turn]
predict = playWith fix
where
fix :: (Char,Char) -> (Play,Play)
fix (t,c) = let they = charToPlay t
in case c of
'X' -> (they, toLose they)
'Y' -> (they, they)
'Z' -> (they, toBeat they)passing to playWith a helper function that «fixes» the Turn
to have the desired outcome.
Conclusion
There are many Haskell standard type-classes that have somewhat
obscure names. Instead of focusing on their names, or trying to
fathom their arcane origins in
Category Theory,
it’s way better
to know their practical use cases. fmap over Functor, bimap
over Bifunctor, mconcat on Monoid, and Arrow combinators in
function contexts are some of the more useful ones. You find
them everywhere and anywhere…
The use of higher-order functions, such as playWith, is pervasive
in functional programming (think of map, foldr, etc.). It’s one
of the basic techniques that help build reusable components.
Instead of hard-coding functionality to an unrelated process,
try abstracting it out and creating higher-order functions.
Granted, I did this «on a hunch» before knowing what Part B was about, but then again, this is not my first rodeo.