12
votes
Day 7: Handy Haversacks
Today's problem description: https://adventofcode.com/2020/day/7
Join the Tildes private leaderboard! You can do that on this page, by entering join code 730956-de85ce0c
.
Please post your solutions in your own top-level comment. Here's a template you can copy-paste into your comment to format it nicely, with the code collapsed by default inside an expandable section with syntax highlighting (you can replace python
with any of the "short names" listed in this page of supported languages):
<details>
<summary>Part 1</summary>
```python
Your code here.
```
</details>
ok, part 2 is finally done!
Part 2
Basically, I'm pulling everything apart and categorizing it in its source bag. I then create another array that is stacked below this that is all bags with the value of 0.
From here I run this sloppy bullshit that is a tweak on a formula I saw on reddit.
I hate everything about this, but I really think it is the only way to get the value we're looking for. You need to drag fill it across 14 columns.
I tried to run a copy of the sheet I got off of reddit, but after about twenty minutes, Sheets basically came to a halt and refused to work. Essentially it's the same idea, but with a few thousand fewer formulas.
Using python, this ended up being the least clean solution to the problems so far. I ended up reversing the mapping between bags and contents in the two parts (just to make the later traversal easier).
Part 1
Part 2
Python
Repo link
Part 1
For the first part, my approach was to use regular expressions to parse the input into an adjacency list graph representation and then just traverse the graph (BFS/DFS) to check if any source bag eventually reached the target "shiny gold" bag.
Part 2
For the second part, my solution just recursively counts the number of bags that can be reached from the "shiny gold" source bag.
Swift!
Repo link
Part 1
Part Duex
Late to the party, but this was actually quite fun, even with POSIX AWK's lack of array stuff (from nice-to-haves like arrays of arrays to basics like
length()
). I tried including some comments in my solution for once.Part 1
Part 2
I'm not especially proud of my solutions for today, it shows my vast ignorance of core Python built-ins I think. Some stuff like defaultdict would have helped me a lot here.
I can't help but wonder, who out there is using Prolog (or other declarative languages)? I'd love to see what it looks like in one of those, that is probably the simplest language possible to work one of these problems.
part 1
part 2
Welcome to Tildes! :)
p.s. BTW, you can wrap your code blocks in the <details> and <summary> HTML elements to make your comment take up a lot less space. E.g. Here it is using your code. Click "More..." then "View Markdown" below my comment to see the implementation. Note: The spacing between the elements is required.
Part 1
Part 2
Thanks! very helpful and thanks for the welcome~
I was really unhappy with my original solution, so this is a refactored solution after thinking about it more clearly and taking some inspiration from Sophie Alpert.
JS
Parts 1+2
Quite a novice at programming in general, having lots of fun doing this so far! This one was definitely a lot more challenging to me than previous days so far. I should start using
defaultdict
, haha.Python
Repo link
Part 1
Part 2
Part 1
I used
defaultdict
to store a two-level mapping ofouter bag -> inner bag -> count
.@pork, @Nuolong, since you mentioned wanting to use
defaultdict
- here's a working exampleAnother neat Python trick that some people may not know about is the
pprint
module. It's very useful for debug logging, especially when dealing with complicated nested datastructures like this.For example, on line 2 of my
main()
function, my script prints this (truncated due to length):Prettyprint Output
If you just
print()
it instead, you get the entire thing on one line, which is pretty much completely unreadable.For part 1, I did the recursive part of the algorithm using an iterative method. If you're one of the people who struggled with recursion on this question (because everyone struggles with recursion to some degree when they first encounter it) this way of doing it might make more sense to you.
I have a list of
pending
bags to check. At first I only add my target bag (shiny gold) to the list. Then I get the set of bags that can contain shiny gold bags. Each one of those I add to my set of matching bags, as well as to my pending list. I keep doing that until I run out of pending bags. At that point I know I've checked every bag that can contain shiny gold, as well as every bag that can contain one of those bags, and so on.Part 2
For part 2, I had to fix a bug in my parsing logic and actually convert the counts to integers. Since I never used them in part 1 I never noticed that bug.
I used an actual recursive function for this one. Part 1 felt more natural to me as a "pending" queue of items, this felt more natural as a function.
Base case for the recursion is if a bag isn't allowed to contain any other bags, its count is obviously 0.
Recursive case is if a bag is allowed to have child bags, we need to count each of those bags, as well as the count of child bags for each of those bags. I was initially missing that
count *
and it was the final head-scratcher bug I had to track down.I missed the release last night because I was busy playing late night board games. So I took this one casually and decided to have some fun and go way overboard. Because of how I did it, part A actually ended up being slightly longer than part B
Day 7 Part A – Python
I went ahead and built an actual tree. First I constructed the nodes individually, noting the relationships between them via their bag name. Then, once all the nodes were built I actually made real references between them, so that each node could see its children. From there I built a recursive algorithm to check if a bag contains gold anywhere among its children.
Day 7 Part B – Python
I had already done the heavy lifting when I built my tree, so I just swapped out my first recursive algorithm that checked for gold for one that instead checked how many bags fit inside a given bag.
Tips for Beginners
For this problem, thinking about how you store your data is very important. I built an actual data structure, which is a more elaborate way of storing data than your average array or dict. Mine is a tree which stores information about the relationships between different bags. You don't HAVE to do something like this, but it might be a fun learning exercise. And it can make your data much easier to navigate if you aren't sure what you're going to need to do with it.
My tree structure allowed me to use recursion which is a computer science technique where your build a process that needs to be able to use itself. For example, if I want to know how many bags a shiny gold bag, I need to know what bags are in it directly. Then I need to look at each of THOSE bags and see what's in THEM directly. Then I need to look at THOSE bag... and so on an so on. It can get quite tedious until you make it to the bottom of your pile of bags. Recursion helps simplify the behavior you want the computer to repeat by saying 'for every bag, look inside it' until you get to empty bags'
As usually, there are many ways to solve this problem
Ugh. I stayed up until 4am coding this solution last night. I got stuck in "recursive debugging hell" in Part 2. I left all my debug in to inflame my shame below, but I'm still amazed the totaling worked. I wasn't even trying to return the total, my original idea was to have the result of the recursive function be a one-dimensional array of type/amount pairs of contents, so I could map/reduce that result to get the total after-the-fact. I added the total as a return value to the recursive function as a debug tool. Finally, after much frustration, I tried it on my input and it was apparently the correct answer. I'd like to figure out how to do what I was originally trying to do at some point; maybe I'll flag this one to revisit for a refactor after the event.
Part 1
Part 2
I thought this one was really satisfying! Took basically all my free time today though! I thought I might need reference counting or cells to do this one but actually recursing HashMaps was good enough!
Rust
lib.rs
main.rs
Ruby
A little slow getting started on this one, but I got there in the end. Not thrilled with my rule parsing, but it works.
Part 1
Part 2
Rust
This one seemed much harder than the previous days. I spent a while fighting the borrow checker/learning how to use rc + refcell to get the compiler to be happy.
Repo link
Solution to both parts
MIT scheme
Part 1 & 2
Part one is very inefficient but it works. I guess the way to improve it would be to memoize or make an association of bags to their containing bags.Part 1 memoized
Went ahead and memoized part one with a hash table and a closure. Went from .5sec to 0secThis one was kind of gross to look it to start, but was actually not too bad in the end. I used some recursive-ish functions, they don't really look like the textbook idea of recursion but that is how they work for the most part. I was also pleased to find, since I am still pretty new to Julia, that a function for accessing dictionaries with a default response to a missing keys was present by default, which made my life a little easier.
Part 1
Part 2 diff
Also, I decided to do some performance comparison between my PC and my Pi using the different optimization levels of the Julia compiler. I just tested 0, which is no optimization, and 3, which is the highest level of optimization. I believe 2 is the default.
Ryzen 5 2600 vs Raspberry Pi, 0 Optimization
Ryzen 5 2600 vs Raspberry Pi, 3 Optimization
Performance is helped a little with the higher levels of optimization, but I have a feeling I'm doing some things in this challenge that are not great practice in Julia, leading to slowdowns.
Rust
Spoilers
Recursion hurts my brain.Updated for my cleaned up solution.
Rust solution (cleaned up)
Rust solution (original)