Advent of Code 2020 solutions in Racket, I guess
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
Hazel Levine a273f1148f
lol
3 years ago
aux cheat 3 years ago
bin add get-challenge 3 years ago
data lol 3 years ago
day8 refactor w/out br/quicklang 3 years ago
day14 bv 3 years ago
lib wip day 20 -- not finishing with this soln 3 years ago
.gitignore viz 3 years ago
LICENSE pilfer haskal's submission code 3 years ago
README.org day 14 fucking finally 3 years ago
day1.rkt add final answer validators, regex part 4 for no reason 3 years ago
day2.rkt add final answer validators, regex part 4 for no reason 3 years ago
day3.rkt add final answer validators, regex part 4 for no reason 3 years ago
day4.rkt sigh 3 years ago
day5.rkt whatever 3 years ago
day6.rkt pilfered... 3 years ago
day7.rkt pilfered... 3 years ago
day9.rkt day 9 3 years ago
day10.rkt remove unnecessary require 3 years ago
day11.rkt day 11 3 years ago
day13.rkt day 13 3 years ago
day15.rkt typed racket 15 3 years ago
day16.rkt day 17 3 years ago
day17.rkt day 17 3 years ago
day18.rkt day18 3 years ago
day19.rkt cheat 3 years ago
day20.rkt lol 3 years ago
day21.rkt more day 20 bs, day 21 3 years ago
day22.rkt visceral pain 3 years ago
day23.rkt visceral pain 3 years ago
day24.rkt visceral pain 3 years ago
day25.rkt lol 3 years ago

README.org

Advent of Code 2020

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.