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 3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago

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.

### 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.

Poke me later.