Haskelling the Advent of Code 2020 - Day 5

the first thing we’re going to do today is clean up our parser from yesterday we can start by replacing our many1 here with sepBy1 which is a parser combinator that takes in two parsers as parameters the first is the parser that we are interested in and the second is the character that separates those and that will then pass many of those fields separated by that other character i think it should be called in an infix way so it’s parsing many fields separated by a carriage return we also need to make sure that we’re parsing the whole input so we use <* eof to ensure that we are followed by an eof however the <* means we throw away the eof result and just return the result of the left hand side i’m going to up the ante a little bit now and generalise this fieldtype parser to be able to parse any enumeration i’d like to be able to parse case insensitive strings and match them against the enumeration constructor names so i’m going to create a parser that can parse a character in a case insensitive way and we do that by using oneOf and then the Data.Char functions toLower and toUpper to ensure we’re matching one of those cases we can then use that to create a case insensitive string parser by simply using mapM on our char parser now this mapM function is quite interesting because it allows us to take a function from a to something b and a list of as and convert that to a something of list of bs and that something in our case is a Parser but it works just the same for a Maybe type so let’s say we have a [Maybe Int] we can use mapM and then just the id function to then create a Maybe [Int] in the Maybe case it will just give us Nothing if any of them are Nothing or a Just value if they’re all Just values and in the Parser case it actually just combines those Parsers by sequencing them one after the other okay so after importing Data.Char this works as expected now we’re ready to create our enumeration parser and we’re going to base this on the fieldtype parser so we’re going to choose between a list of the values except this time we’re going to create the list by mapping our sr function across the whole range of our enumeration unfortunately that [..] syntax is not valid Haskell but we’ll deal with that in a second okay so we change our sr function to take in any showable value and create a Parser for it and we’re going to parse in a case insensitive way so we need to work out a way to cover the range of values in our enumeration and fortunately Haskell has a typeclass called Bounded and that provides us a minBound and a maxBound for any type and then the fieldtype is just enump but this still doesn’t work for a few reasons we haven’t given the type of minBound and maxBound but using a type variable within the scope of a function requires us to use this forall notation and the ScopedTypeVariables language extension to ghc now we just need to make sure our enumeration has the Bounded and Enum type classes by adding them to the deriving clause now fieldtype doesn’t need to be its own function so we can just use enump directly in our field parser let’s take those functions out and put them into our AOC.hs file we need to put the language extension at the top, the import with the other imports and our functions can go alongside our parse function the last thing to note for part one is that instead of length we should have used Data.Map.

size here because that is a more efficient operation 04:37 - because length will actually traverse through the Map to count the elements now i’ve applied all those same changes to part two that we did already and we’re going to look now at the height parser and i’m going to show you how you can condense a do notation into an expression now firstly i hope you understand that you can take the read out here and use <$> to read in the value directly into h now that we have just a simple return type we can use a tuple section with <$> and <*> to bring in those values and we have then the equivalent function if you haven’t seen these before tuple sections are just a function that allows us to construct a tuple so let’s move on to day five and we have this really long complicated explanation of essentially how binary numbers work so our task is just to read in each of these letters and interpret that in the correct way as a binary number so let’s get our input and we have a quick look at it and we see that we’ve just got these letters and each of those is a 0 or a 1 in our binary number so we’re going to use our interact function again which remember pulls in everything line by line so we’re going to map our function f over each of those lines and that’s in turn going to map a function bin over each character in the line and we’re going to interpret each of the characters in the appropriate way as a 0 or a 1 in our binary number once we’ve done that we need some way to combine those to get our Int at the end so we’re going to use a function called fold and a particular type of fold called foldl’ and this is a left fold and the dash here means it’s a variant of fold which uses strict evaluation we’re going to fold by taking the number we have already - that’s the x - and then the next number we add is the y so we need to multiply the existing number we have by two and then add the next digit y the 0 is the initial value for x and this then steps through the list and brings in all of the values by putting them through that accumulating function foldl’ is defined in Data.List so we need to make sure we import that and we can see now then we’ve read in all of the numbers as Int now we just simply have to find the maximum all right let’s check our answer and we have our first gold star for today nice and simple all right part two is a little bit more complicated and we need to find the missing value i’m sure there’s some really easy way to do this that i just can’t think of right now but the way i’m thinking of is to create a combination of the list and its tail and we’re going to use a function called zip to do this okay so we just read in the file that we had from before and the first thing we’re going to do is actually sort the list let’s have a look at our sorted list and we have a bunch of numbers in order we’re going to use a function called g then and g is just going to zip the list with its tail we’re then going to use a list comprehension to extract out each of the elements of the original list with its following element and we’re going to call those x and y and then all we need to do is check for which pair of values x + 1 /= y another way to say x + 1 is simply succ x - or successor of x - and that returns us the only tuple where y is 2 greater than x we can then simply return the successor of x because that will be the element in the middle and now we should be able to check our answer and we have our second gold star for today before i go i just wanted to give a quick shoutout to rs232boy who sent me this amazing solution to the last puzzle it uses the split function from Data.String.Util instead of using parsers and i think the solution is quite elegant and nice so until next time happy haskelling .