Advent of Code 2020

• Day 1: Report Repair
  • Part 1
  • Part 2
• Day 2: Password Philosophy
  • Part 1
  • Part 2
  • Revisions
• Day 3: Toboggan Trajectory
  • Part 1
  • Part 2
• Day 4: Passport Processing
  • Part 1
  • Part 2
  • Revisions
• Day 5: Binary Boarding
  • Part 1
  • Part 2
  • Revisions
• Day 6: Custom Customs
  • Part 1
  • Part 2
  • Revisions
• Day 7: Handy Haversacks
  • Part 1
  • Part 2
  • Revisions
• Day 8

I'm doing all of these in Racket in an attempt to learn the language itself better. I have a tendency to write Racket like it's Scheme, and I'm deliberately trying to avoid that.

This coincides with final exam season, so I might fall behind.

NOTE: I stopped writing these up because I got tired.

Day 1: Report Repair

Part 1

The naive solution here is to do a double for loop. I didn't want to do that, since that's O(n^2), which is gross. The input list is only like 100 elements, so it'd be passable, but I wanted to see if I could do better.

My solution:

• Sort the input list of numbers and store it, O(n*log(n))
• Reverse the sorted list and store it, O(n)

• Check the sum of the first elements of the sorted list and the reversed sorted list:

  • = 2020? Return the product
  • Greater than 2020? Drop the first element of the reversed list
  • Less than 2020? Drop the first element of the sorted list

This results in the answer 542619 for my input data.

Part 2

This isn't compatible with my solution for (1). The naive solution here is to do a triple for loop, which I think is gross. Again, it'd work though. I used a hash table here.

I first created a function using a immutable hash as an accumulator, taking a list, a hash, and a number. If the list is empty, we dump out the hash table. Otherwise, we create the key 2020 - i - j, because the corresponding third element would result in a sum to 2020 anyway. This key is the third number we need. We assign the value to the list [i, j, key], and recurse on the rest of the list.

We then want to check if the hash table has the number we want. We use a hash as an accumulator again here. We run the previous function using the first element as the number and the rest of the list as the input list. If the hash table has the key corresponding to the first element of the list, we have our triple, so we grab it from the hash and multiply the elements. Otherwise, we iterate on the rest of the list, but we keep the hash we used for the previous iteration.

We start with an empty hash and the input list, and end up with the answer 32858450.

Is this egregious overkill? Yes. I enjoyed doing it, though.

Day 2: Password Philosophy

Part 1

This is a pretty simple parsing problem. I created a struct holding a minimum number, maximum number, character, and the actual password.

To validate this struct (ignoring parsing for now), we check how many characters in the password content are equal to the stored char. This is easy with Racket's count function. We then check whether that number is greater than or equal to the min, and less than or equal to the max. This is the first time I used Racket's curry, which is… neat.

To actually parse the line, I just did a bunch of string splits and created the struct. Not pretty, but it works. I defined a function list->values (and a corresponding macro values->list that is unused) to be able to define-values on a string-split, which was a bit cleaner. I'd end up rewriting this later anyway.

We then run count with the validation function and the parsed lines, and get the answer 572.

Part 2

This is probably easier than part 1, honestly. I created a function that checks whether the character at a given index n (starting at 1) is equal to the stored character in the password struct. Then I just did xor for both the former "min" and "max" stored in the password struct.

Run count with this new validation function and get the answer 306.

Revisions

I didn't like my hacked together string split function. I looked at haskal's solution and they used match and pregexp, so I changed it to do that. match is a construct I use far too little. The regex in question was ^([0-9]+)\\-([0-9]+) (.): (.*?)$.

I didn't know string-ref existed, so I used that instead of list-ref and string->list. I don't know how Racket internally stores strings, but it's probably better than list-ref's O(n).

I didn't know that (module+ main ...) was special in Racket, and was getting annoyed when loading the file in the Racket REPL, so I ended up changing both this and Day 1 to use that. This will probably be useful when I need tests, and can use (module+ test ...), which is unnecessary for now.

I also didn't know that curry took arguments to the curried function, so instead of ((curry char=?) (password-char pwd)), I could just (curry char=? (password-char pwd)). Not really important, but alright.

Day 3: Toboggan Trajectory

Part 1

Are they going to stop giving us warm-up problems?

Anyway, this is pretty simple. I defined a function that does a "looping string-ref" (so modulo-ing the index with the length). I then used Racket's for/sum to run on the range 0 to infinity (stepping by 3) and 0 to the length of the vector. If the character's (#), add 1. Otherwise, don't.

Part 2

Pretty trivial modification. I abstracted away from my Part 1 solution to add variables dx and dy for how much to step, and then mapped that to the input slopes and calculated the product.

Day 4: Passport Processing

Part 1

I… over-complicated this, because I didn't want to write spaghetti. Depending on who you ask, I ended up writing more spaghetti.

To make a generalized parser for this format, I first defined a struct containing each field. I then made a function parse-passport, which trims a single password string, splits it, and iterates over each key:value pair. The problem arised when reading this key:value pair into the struct. The naive, 211-y solution would be to do something like:

(passport val
          (passport-iyr new-passport)
          (passport-eyr new-passport)
          ...)

but this is long and requires doing a match on the key string, then doing this for each possible key!

Racket defines a function struct-copy that allows for updating of a single field immutably. However, struct-copy takes a syntax identifier, and can't take a string, so I would still have to match on the key string and do this for each case. This is, suffice it to say, not pretty.

This ended up taking me down Racket macro hell, but I'm glad I did it; it resulted in a better understanding of the Racket macro system, and my first non-trivial Racket macro outside of the context of a tutorial.

My first instinct was to create a macro like this one, which took a string as a field name:

(define-simple-macro (struct-insert strct:id name:id fld:str val:expr)
  #:with fld-name (format-id #'fld "~a" (syntax-e #'fld))
  (struct-copy strct name
               [fld-name val]))

This doesn't work because it results in the same issue: we have to match on the key. Macro expansion and runtime are two separate phases in Racket, so macros can't dereference a runtime variable. I could have done something nasty with nonhygenic macros here, but that wouldn't be general enough for my tastes.

To solve this, I did something either clever or gross depending on how you look at it: make a hash in tandem with the struct (called <struct-name>-insert-table), with the key being the field and the value being a lambda taking an instance of the struct and a value. I spent a while trying to figure out how to iterate in a Racket macro, before realizing ... was more powerful than I made it out to be. This was defined as a macro struct+, which creates a struct and its insert table in tandem.

After that, I wrote the iteration, tentatively storing each value in the struct as false and updating it using the insert table.

As for validation, Racket contracts are great for this. Namely, struct/c is pretty much exactly what I want. Just do string? on everything, except for cid, which can be any/c.

Then just run count with this validator on the parsed input data and we're done.

Part 2

This is where my hard work creating a generalized solution paid off. It's pretty much the same thing as the old validator, except with new contracts. I defined a few:

• string-length/c, which checks the string length
• string-integer-in, which determines if the string converted to a number is an integer in the range
• height/c, which uses a regex to match the height criteria
• color/c, which uses a regex to match the color criteria

After that, the following contracts were used for each field, along with passing the Part 1 criteria:

• byr: (and/c (string-length/c 4) (string-integer-in 1920 2002))
• iyr: (and/c (string-length/c 4) (string-integer-in 2010 2020))
• eyr: (and/c (string-length/c 4) (string-integer-in 2020 2030))
• hgt: height/c
• hcl: color/c
• ecl: (or/c "amb" "blu" "brn" "gry" "grn" "hzl" "oth")
• pid: (and/c (string-length/c 9) (string-integer-in 0 999999999))
• cid: any/c

Again, run count with this validator on the parsed input data.

Revisions

I wanted to see if I could do the Part 2 validator with almost nothing but regex, so I did that.

Day 5: Binary Boarding

Part 1

Each boarding pass can actually be treated as a binary number. F and L are zero digits, B and R are one digits. The ID is row * 8 + column, and the column part is 3 digits, so… uh… yeah.

Convert them all to IDs, maximize 'em.

Part 2

Find the first ID that's missing but doesn't have neighbors. This is just (first (memf ...)).

Revisions

I re-did this with manual BSP, since I tried and failed at that for a while before realizing the binary string method.

Day 6: Custom Customs

Part 1

Is it just me, or are these getting easier?

I wrote a function to remove all the unique elements from a string and return it as a string, so "aaabbbccdc" -> "abcd". I then applied that to each input split on double newline and got the string length, then summed it up.

Part 2

This was slightly harder. I changed each line in each group to a list, then to a set. Then I folded with the set intersection of each set, counted the results, and summed them.

This is the first time I've solved the problem in <10 min.

Revisions

I redid Part 1 with sets because I forgot they existed for a hot sec.

Day 7: Handy Haversacks

Part 1

The difficulty went off a fucking cliff with this one.

I used the Racket graph library. In retrospect, I shouldn't have, since the documentation is somewhat garbage. do-dfs is an extremely powerful function, and now that I understand it, I'm grateful. I will probably never use this again.

Anyway, to parse the input, I first splitted it on the phrase " bags contain " (including spaces), and applied that to a helper function. The helper function determined if the phrase contained the word "no", in which case it returned an empty list. Otherwise, it splitted based on the regex bag(s)?(,|.), and then constructed a list of the form (list weight from to), and applied that to every rule.

Then, I just applied that to every line, and appended the results.

As for the actual logic, the reasoning for the specific edge order is to pass as an argument to the constructor weighted-graph/directed, which does exactly what you think it does. I then generated a graph for the input,p and defined a vertex property has-wanted with an initial value of false.

Then I ran do-dfs. I visited every node if $to was not already marked (eliminating redundancy), and if it was I marked $from and stopped visiting. After each visit, if the child has the wanted string "shiny gold" or if it is marked with has-wanted, and we are not at the root of the tree, I set has-wanted for the given tree. This propagates the state of has-wanted up the tree, meaning that the parent of a bag containing a shiny gold bag contains a shiny gold bag.

I then summed up the number of values in the resultant hash of the vertex property that were true.

Part 2

For this DFS, we want to always check nodes we've already visited. Once we finish visiting a node, we want to add the already-visited node to the total. A function increment was defined for this purpose. We also want to always get our target as our first node.

The increment function determines that when we are not at the root, we should set the weight of the node we came from to the total weight thus far plus the multiple of the weight of the current edge and the weight of where we're going. This makes sense because each bag contains the number of bags within it times the number of bags within it, etc…

Revisions

I want to redo this without do-dfs. I'll get to it when I have time, was busy with an essay today.

Day 8

Poke me later.