Haskelling the Advent of Code 2020 - Day 4

hello again haskellings well there’s a few hours left before we start day four so let’s have a look at what we’ve done yesterday first i’d like to share with you something which i find really useful and it’s an online tool called hugel and it’s a search engine for haskell functions and not only can you search by function name but also you can search by type signature which is extremely useful if you don’t actually know the name of the function you’re looking for let’s have a look at this cycle function that we used yesterday we can see that it’s defined in the prelude and it turns a finite list into a circular one we can also click through to see the source code we can also have a closer look at this bang bang function that we used which takes a list and an int and returns us back an element from that list we’ve already seen that this function can cause the program to crash when the index is out of bounds but another problem is that lists are stored sequentially so when you index through a list it has to go through each element in turn to get to the index you’re looking for so today we’re going to look at another type of data structure called a vector which is very similar to an array in other programming languages and vectors allow us to actually index into the structure in what’s known as constant time and if you’re not familiar this is the big o of one notation there and that simply means that no matter how big our vector is it will always give us the result in the same amount of time on the other hand indexing into a list takes order n time or linear time and that just means that the time it takes is proportional to the number of elements in the list let’s convert our program to use vectors instead of lists we first import the module and we do this in a qualified way so we don’t clash with the prelude functions of similar names now i’m going to remove the cycle for now and we use the from list function to convert the list that we’re reading into a vector next we change our indexing operation to use the vector indexing operation even though it’s an operator we still use v dot to qualify it we still need to somehow extend the vectors infinitely but instead of doing that what we can actually do is create our own indexing function that indexes in a cyclic manner we’re going to call this bang pipe so the type signature of bang pipe will be the same as the index we’ve had before and it’s going to then take a vector of a’s and an int and return us an a it’s going to do the same indexing operation as before except this time we’re going to adjust the index and we’re going to adjust it by getting the remainder after division on the length of v interestingly haskell actually has two ways to get the remainder after division one is rem and the other is mod the difference between these two functions is when you’re handling negative numbers mod will take the sign of the second argument whereas rem takes the sign of the first argument in our particular example we’re only dealing with positive numbers so it doesn’t actually make much difference which we use here except that rem is actually slightly faster on most hardware okay so let’s take this function actually and put this into our advent of code module because i think this will be actually quite useful and we’re going to use vectors probably in the future as well i’m also going to import data dot vector unqualified but only bring in the vector type itself that means that we don’t have to use v dot vector everywhere because that doesn’t clash with the standard prelude another thing i’d like to do is try to avoid importing the data dot vector module in our code and i do that by creating an alias to the from list function called l to the list to vector so updating part two is now quite easy all we actually need to do is replace those two function calls and it works as expected so now let’s move on to day four all right now this puzzle involves processing a bunch of records and these are the fields we need to process so let’s copy and paste that into a new haskell file all right so we don’t need the comments here so we’re just going to remove them and we first import our advent of code module and we start using interact but this time we actually don’t want the lines so we’re going to create a new interact function without the lines and then we can parse the whole string as one string so we call this interact prime and we just remove the lines here but that also means that our normal interact function can just be defined in terms of interact prime we we just need to then compose f with lines and that will be the same as what we had before okay so we grab our input and you can see it’s actually the each record is separated by an extra line so this is a slightly weird format so we’re going to create a parser p that’s going to pass a whole file what we want at the end of the day is a list of list of fields and each of those fields is going to have some sort of field type and then the value is a string so because we want to grab many of these fields we use the many one parser combinator to grab many fields and then we just grab all of those by using many one outside the do as well okay so let’s create our field parser and for now let’s just create a field parser that simply returns a dummy value in the double dummy value we’re just going to create an enum so essentially just a data type where every single constructor has no parameters and that enum is going to be for the field type for now just ignore the deriving there let’s see if that compiles and yeah it looks like we have a problem with the interact function and we forgot that we because we’re not using lines anymore then we need to actually just take in the whole string in our function f okay back to our solution and we have a problem because actually the empty parser is not something that is liked when you’re using many so we need to fill out this field parser okay so first we’re going to have a field type parser and we pull in the field type from that and then there’s a colon character and then we use this many till parser combinator to grab any character until there’s a space character okay now we need to define our field type parser and we’re going to have a bunch of parsers strung together in some way of the form like this so we’re going to need something that parses this string and then returns a value and this is how we achieve that with this greater than greater than operator and that simply means that we parse what happens on the left and then we throw that away and we just return what’s on the right so we’re going to use the alternate operator here except because we’ve got quite a lot of choices we can actually avoid using this alternate operator and use choice on a list instead and because it’s going to be a little bit tedious having this whole string arrow return we’re going to create a little helper function and we’ll call this sr and sr is going to take in a string and a value of type ft and return us a parser of fft and it’s simply going to match that string and return that field type we’re going to need to then fill out our choice list with sr functions of this form using a macro in vim we’re going to create all the options here for our choice list and we can append all those together and then put them into the list this should be able to create the parser for us for our field types except we have a small problem there are more than one item with a common prefix in this list and when we use choice or alternatives some of that content can be consumed and then it won’t match the subsequent choice so we can use the try combinator to actually reset back to the unconsumed input from the previous alternative and that’s working so let’s return the actual field type in our field parser we still have a problem because at the end of the input we need to see if there’s a carriage return in between each record and we do that just by simply matching against the carriage return character however at the very last input we need to match against eof and because char returns a character an eof returns a unit we force char to just return unit okay so we are actually able to parse and let’s replace the dummy values with the actual string that we’ve passed and as you can see we’re actually parsing this correctly so now we can add in our f after the pars and the f is going to validate these passport records the first thing we’re going to do is make sure that we have got a correct pass if we don’t we get a left value back and our program crashes but that’s fine that’s what we want it to do okay so we’re going to use another type of data structure and it’s called data.map and this allows us to actually create a mapping from our field type to the value and when we do that we can actually assure ourselves that we’ve only got one of each field type in any given record and then we can simply delete the cid record and if we just use length on that record we can verify the ones with a length of seven have every field necessary okay so let’s check that and we have our correct answer part two is all about validating our records and we have to make sure that the passports adhere to the criteria as specified there so let’s uh just copy that out and we’re going to check each of these one by one we’re going to create a function called is valid and that’s going to give us a true or false and at the end of the day we will be counting the true values to ensure all the fields are present we then create a filter to make sure that we have all seven fields in each of our records then we’re going to map our is valid function across the records and that’s going to return us a true or false for each of the records so let’s create that function now we just create that as with a dummy true value and that should be a dot then that’s a dollar and yeah okay so we’ve got the same output as before okay so the isvalid function needs to test a bunch of things so first we need to fetch all of our values out of our map and we’re going to use a let statement to do that so we’re going to fetch the values using the let and we use the m dot exclamation mark operator again to fetch the value corresponding to that field and then we read it as an end and in the in clause of the let we have a list of conditions that we need to satisfy and we need to satisfy all of these conditions so if we and all those together then we can verify that we’re having we we have a correct record so we we test to see if each of these records are within the limits given to us the integer ones are easy enough and we have one more the expiration year the next one though is going to be tricky the the height parameter it requires us to actually parse the string that we’re given because the the string we’re given is an integer a string with the units so we’re going to create a little parser for the height and it’s going to return us a tuple with the height and the units as an internal string so first we’re going to get in the number and that’s just a mini one digit and the units will be a mini one in each r because we want to pass the units until the end of the string we simply read the integer height and return the units as is so we’re going to then parse that height after fetching it from the record and it’s going to return us either a left or a right value and we’re going to use a case statement now to determine whether we’re getting a right or a left value and if we get a left value then we’re going to return false it’s not a valid passport but if we get a right value then we check to see if the units are valid by putting another case statement based on the units and if the units are inches then we check to see if the height is within the given limits and similarly for centimeters if the units aren’t recognized we’re just going to return false we can then add that check to our list of criteria and we are now done with processing the height so now we should validate the hair color and this one is also a little bit tricky because it needs to contain a hash character and then be followed by six hexadecimal digits what we can do though is split off the first character when we actually fetch it from the record we’re going to then check to see that the first character is that hash character and then we’re going to test if the length is correct and then we can test if all of the characters in that string a number from zero to nine or a letter from a to f i’m sure there’s a better way to do this but this is a quick and dirty way for now okay so similarly for eye color we can just check if the eye color is an element of the list of those correct eye colors so we just make ourselves a little macro to put those in quotes so the a list of strings and we have ourselves a test for eye color the last check we need to do is for the passport id and the passport id is much simpler we just check to see the length of the digits and we make sure that each of them is indeed a digit we can use the is digit function for this which is in the data.jar module so let’s import data.jar and hopefully that should compile and we have an answer let’s check that and it looks like we have a second gold star happy haskelling goodbye for now .