So on Hacker News, I came across something awesome.  Advent of Code (http://adventofcode.com/)

A programming challenge that takes 25 2-part challenges, one  a day until Christmas.  I’ve been looking for a side project to hone my code, and this was perfect.  Especially after dragging my feet on board game bots, Alexa skills, general programs, and so on and so forth.  I’ve been having a bit of trouble lately because I haven’t felt like I was advancing my technical skills in a bit, and this will help.

I’ve done plenty of coding challenge sites before, with the most notable being Project Euler, so i wanted a nice challenge this time.  I knew I wasn’t going to be the fastest on the site, so speed wasn’t going to be an option.  Instead, I want to work on being a polyglot.  Let’s work in a few different programming languages.  The goal then, 25 languages in 25 days.  Am I going to be successful?  Probably not.  I have a hackathon week at work.  I have Christmas shopping to do.  I make dinner every night and have a wife and son to tend to.  But, once everyone goes to bed and the house is quiet, it’s my time to shine.

Let’s look at how the first day went……

Day 1

Start: 12/4/2016

Finish 12/4/2016

Language: Haskell

SPOILER ALERT: If you have any inkling, any whatsoever, to work on the Advent of Code…. DO NOT READ THIS BLOG POST.  DO NOT LOOK AT MY GITHUB PROJECT.  It is no fun if you’re not solving it yourself, and you’ll feel so much better about yourself if you can figure it out without looking up an answer.  This blog post is not to give away the answer, but instead, is there for people to learn from.

Problem Statement

So the first day was pretty much the Rover Problem, and I’ve done it as part of Scala for the 7 Languages in 7 Weeks book by Pragmatic Programmers (An excellent resources if you are a budding polyglot.)  So I had a good handle on how to write the problem.  But I’m trying to play around with a bunch of languages, so what to use?  Well, I’ve been meaning to learn Haskell, so I figured that’d be my first language to try.

Pretty much you need to navigate a rectangular grid where you start at some origin pointing north, and then either turn right or left and make movements.  So R3, R2, L3 would mean turn right, go forward 3, turn right, go forward 2, and turn left, and go forward 3.  This would put you 6 blocks east and 2 blocks south of your original starting position.  The goal is to find the taxicab distance to your origin (if your points are x,y, then your taxicab distance is abs(x) + abs(y).

So let’s look at my Haskell (all code can be found on my GitHub -> https://github.com/pviafore/AdventOfCode2016

So let’s look at what I wrote

import Data.List.Split

data Turn = R | L
    deriving (Show)
data Move = Move { turn :: Turn, distance :: Int }
    deriving (Show)
data Direction = North | East | West | South
    deriving (Show, Eq)
data Coords = Coords { dir :: Direction, x :: Int, y :: Int}
    deriving (Show)

main =  do
    input  Coords
processInput input = foldl applyMove initial (makeMoves input)
    
makeMoves :: String -> [Move]
makeMoves input = map makeMove (splitOnComma input)

initial :: Coords
initial = Coords North 0 0  

makeMove :: String -> Move
makeMove str = Move (makeTurn (head str)) (read (tail str))

makeTurn :: Char -> Turn
makeTurn 'R' = R
makeTurn 'L' = L
makeTurn _ = R

applyMove :: Coords -> Move -> Coords
applyMove (Coords dir x y) (Move t d) = applyDistance (Coords dir x y) (rotate dir t) d

applyDistance :: Coords -> Direction -> Int -> Coords
applyDistance (Coords _ x y) dir dist | dir == North = Coords North x (y+dist)
                                      | dir == East  = Coords East (x+dist) y
                                      | dir == South = Coords South x (y-dist)
                                      | dir == West  = Coords West (x-dist) y                         

rotate :: Direction -> Turn -> Direction
rotate North R = East
rotate East R = South
rotate South R = West
rotate West R = North
rotate North L = West
rotate West L = South
rotate South L = East
rotate East L = North

getDistance :: Coords -> Int
getDistance (Coords _ x y) = abs(x) + abs(y)

That’s a handful, so let’s break it down piece by piece:
First, I wanted to convert the text from the file (which is like “R1, R3, L2”) into some data type of my own.

So I created the following:

import Data.List.Split

data Turn = R | L
    deriving (Show)
data Move = Move { turn :: Turn, distance :: Int }
    deriving (Show)

readInput :: IO String
readInput = readFile "day1.txt"

splitOnComma = splitOn ", "
    
makeMoves :: String -> [Move]
makeMoves input = map makeMove (splitOnComma input)

makeMove :: String -> Move
makeMove str = Move (makeTurn (head str)) (read (tail str))

makeTurn :: Char -> Turn
makeTurn 'R' = R
makeTurn 'L' = L
makeTurn _ = R

This is nice and easy. I have some data types for a Move, which is a turn and a distance.

I have a readInput file, as well as a function to help me out with splitting on a comma. Then I map a make move function over my splitstring.
The make move simply takes the first character, turns it into a Turn type, and then uses the rest of the characters for the distance.

There is a hole here (un-haskell of me) in makeTurn. If the character is not a L or an R, I simply default it to a right turn. I should be returning an option, or validating the input beforehand, but with fixed input, there wasn’t as much as a worry. Now, I could get a list of moves with the following:

input <- readInput
let moves = makeMoves input

Now, Once I have the moves, I have to apply them to some coordinate system. The problem states that we are at the origin facing north, so:

data Direction = North | East | West | South
    deriving (Show, Eq)
data Coords = Coords { dir :: Direction, x :: Int, y :: Int}
    deriving (Show)

initial :: Coords
initial = Coords North 0 0  

So I have an initial position. What I want to do next is fold all those moves on top my position, updating the position each time:

processInput :: String -> Coords
processInput input = foldl applyMove initial (makeMoves input)

That takes my string input, makes moves out of them, and applies them using a fold left. So let’s look at what apply move should be doing:
It should rotate the direction, and take that many paces ->

applyMove :: Coords -> Move -> Coords
applyMove (Coords dir x y) (Move t d) = applyDistance (Coords dir x y) (rotate dir t) d

applyDistance :: Coords -> Direction -> Int -> Coords
applyDistance (Coords _ x y) dir dist | dir == North = Coords North x (y+dist)
                                      | dir == East  = Coords East (x+dist) y
                                      | dir == South = Coords South x (y-dist)
                                      | dir == West  = Coords West (x-dist) y                         

rotate :: Direction -> Turn -> Direction
rotate North R = East
rotate East R = South
rotate South R = West
rotate West R = North
rotate North L = West
rotate West L = South
rotate South L = East
rotate East L = North

This was the toughest part for me. I fought the type system quite a bit with this. But, as they say with Haskell, once you compile, it generally just works. So applyMove rotates the direction, then calls applyDistance to actually move it. The rotate function is pretty self explanatory.

Now, our processInput gives us the final position. Hooray! Now to just get the distance function

getDistance :: Coords -> Int
getDistance (Coords _ x y) = abs(x) + abs(y)

Well that was straight forward. Chaining them all together gives us our answer:

main =  do
    input <- readInput
    let final = processInput input
    let output = show (getDistance final)
    putStrLn output

Hooray!

Now on to part 2 of the day’s challenge:

Part 2

Well, now we have to find the first coordinate that we visit twice. Uh-oh, this means keeping track of state in a FP language. This should be interesting.

So I knew that I wanted to kep track of where I’d been. So I added a Position Data Type ->

data Position = Pos {coords :: Coords, path :: [Coords]}
    deriving (Show)

I then changed my functions that dealt with coordinates to deal with positions

processInput :: String -> Position
processInput input = foldl applyMove initial (makeMoves input)
  
initial :: Position
initial = Pos (Coords North 0 0) [(Coords North 0 0)]  
  
applyMove :: Position -> Move -> Position
applyMove (Pos (Coords dir x y) p) (Move t d) = 
    let newCoord = (applyDistance (Coords dir x y) (rotate dir t) d)
    in (Pos newCoord (p ++ (makePath (Coords dir x y) newCoord)))

applyMove is the big one that changed. It keeps track of every coord that we go through by concatenating the path so far (p) with a function called makePath.

makePath looks like:

makePath :: Coords -> Coords -> [Coords]
makePath (Coords d1 x1 y1) (Coords d2 x2 y2)   | x1 < x2 = [Coords d2 x y2 | x <- [x1+1 .. x2]]
                                               | x2 < x1 = reverse ([Coords d2 x y2 | x <- [x2 .. x1-1]])
                                               | y1 < y2 = [Coords d2 x2 y | y <- [y1+1 .. y2]]
                                               | y2 < y1 = reverse ([Coords d2 x2 y | y <- [y2 .. y1-1]])
                                               | otherwise = [Coords d2 x2 y2]   

Given two coordinates, it uses a list comprehension to generate all the points from the starting point to the end point (start point exclusive). I assumed the directions would always be the same.

Now, at the end of the program, I have the full path taken passed back as part of my position. I need to find the headquarters now:

findHeadquarters :: Position -> Coords
findHeadquarters (Pos _ path) = findFirstDuplicate [] path

findFirstDuplicate :: [Coords] -> [Coords] -> Coords
findFirstDuplicate _ [] = Coords North 0 0
findFirstDuplicate seen (x:xs) | elem x seen == True = x
                               | otherwise = findFirstDuplicate (seen++[x]) xs 

   

findFirstDuplicate keeps track of what we’ve seen before, and the first time we hit a coordinate we’ve seen before, we’re good, and return it. Otherwise recurse.

Our new main looks like this :

main =  do
    input <- readInput
    let position = processInput input
    let hq = findHeadquarters position
    let output = show (getDistance hq)
    putStrLn output

and that’s it. I solved it!

Closing Thoughts

Well, I did better with Haskell then I thought I would. I got the answer correct on the first try each time, and most of my time was spent googling and fighting the type checker. I felt I used the type system decently, but I’m sure there were a lot of Haskell Idioms I didn’t understand. I glazed over Monads, so I didn’t get too deep into it.

I would not have been able to do this had I not done some Elixir (to help with Pattern Matching and declarative functions) and Rust (to help with a static type system a bit better than C++ or Java).

Overall I’d grade this one a solid B. I took a lot of time Googling how to do things (especially dealing with types) but once I got it, I was fine with it. I could understand type system errors pretty quickly. Like I said, the first answer I submitted was correct each time, so that’s pretty good. This was also the first Haskell project I’ve done from scratch. My only experience was a brief project for a programming languages class in my undergrad (Which I got a 20 on 😦 ) and the exercises in 7 languages in 7 weeks.

My code was readable, but I felt that you had to be able to read Haskell to do so. I feel like this is a big difference from some of the other languages I know, where they are very easy to read without knowing the syntax. But that’s probably because I grew up with those syntaxes, and not Haskell.

So, onto the next problem, Day 2 … in Python 3!