Haskelling the Advent of Code 2020 - Day 3

Well, Haskellings, I can’t believe it’s day three already! We’re just going to do a very quick retrospective from yesterday and I’ve already gone ahead and actually refactored the code a little bit and put some useful functions into our advent of code module. So, we’re importing Parsec in this module in the same way as we did with the Prelude and we’re hiding “count” and “parse”. I’ve added this type called Parser and this is actually just a type synonym. This “type” keyword introduces a synonym and we’re just removing the two parameters that we’re always going to use for Advent of Code, so “Parser” is just the same as “Parsec String ()”. I’m also replacing the “parse” function with one that already has the filename parameter filled in with an empty filename because we’ll never use that in Advent of Code.

I’ve put in the “count” function as well that we had from before and 01:09 - because I’m hiding the “count” in Parsec we can actually now use “count” instead of “countelems”. The last thing that I’ve done is added “lines” to our “interact” function. Okay, so let’s have a look at the solution code and not a lot has changed apart from removing the calls to “lines” and changing the type signature of the parser and renaming “countelems” to “count”. The last thing I’m going to do which I’m going to do now is put the “rights” function into our Advent of Code module. I’m going to do that by just removing those from our solution files and putting those into the Advent of Code module.

02:01 - It’s as simple as that, but I’m also going to add a type signature just for good measure. In Haskell you don’t have to put in type signatures but it’s good to be explicit so the compiler can actually help you know when you do something that you didn’t intend to do. And so on to day three we go! Let’s get our input and have a look at it. We have a map with “#” characters representing trees. Let’s see how we can pull that data into a structure and we need to think about what sort of structure we would like this data to be in.

I’m going to choose a [[Bool]] values 02:52 - in which case we need to map over our data - and remember our custom “interact” function is already grabbing the lines into a [String] so we’re mapping a function over that [String] and a String is just a [Char] so we can map an equality test with the “#” character to get us back a [[Bool]]. The next thing we’re going to do is we’re going to create a function that will traverse that list in a special way, so we need to (for each line in that list) add 3 to the x value that we’re grabbing out of it. We’re going to create a function “f” that’s going to take in that [[Bool]]. We’re going to call it “m” for “map”, which is because it’s a map of the trees and then we’re going to create a helper function f’ which goes through this [[Bool]] and takes in a velocity argument and an x value and we’re going to grab out of the first line the boolean value at the position of that x value using this evil “!!” operator and then we’re going to use recursion to follow the rest of the list adding the velocity to x every time. The second line of f’ is just a catch-all that says if the list is [] or there’s some other case that we haven’t already handled then we just return [].

04:44 - Next we call f’ with the map and our velocity and our starting x value and this should give us back the list of boolean values corresponding to the path that we need to follow. Now, we get an error here because we forgot to extend the map outwards and we can do this fairly easily in Haskell by using the “cycle” function - which we do on each line - which essentially repeats that list over and over again. There we have our path representing where the trees are along that path and the only thing we have left to do then is to count the number of trees in that path. We can use our “count” function that we made last time. Let’s check to see if we’ve got the right answer - and we have and we’ve earned ourselves a gold star! Let’s have a look at part two and it requires us to do the same thing except we need to step a different amount each time, but one of the cases requires us to step in the y direction as well.

06:05 - That means we’ll have to skip rows but the way we’ve implemented our function is to actually go through row by row! So let’s add a velocity in the y direction. We’re going to call that “w”. Let’s first update all the places where we’re calling f’ to add the y-direction velocity. We have to skip some rows and we’re going to do that by just ignoring that first element and just recurring without doing anything with that row. But we need to have a case where we’re going to do that. So we’re going to do that if our extra parameter - we’re going to call this “j” - is non-zero in which case we skip a row but if it’s zero we process the row and then reset “j” to “w”.

07:00 - When we do skip a row we subtract one from “j” in the recursive call. Now this should return us the same result as we had before, but it doesn’t because we’re actually skipping one too many rows. We should set “w” to 0 because we actually don’t want to skip any rows! Because our function is going to need to actually calculate the product of the solutions, we’re going to create another helper function to actually do the counting. That’s going to take in the x and y velocities, v and w, and then call f’ on v and (w - 1) to account for the extra row skipping issue. f can then calculate the product of all of the counts from the solutions.

Once we’ve done that we should get a result that we can test. It looks like we’ve done something wrong here so let’s check this once more. After some debugging, I’ve worked it out: we have a typical copy paste error and we’ve added the velocity to x when we didn’t need to in the skipped a row case. This just goes to show you that just because your Haskell program compiles it doesn’t mean that it’s correct!! Let’s check this answer and we have our second gold star! Until tomorrow, happy Haskelling! .