I think this is poorly worded: “Counting the number of times any of these ingredients appear in any ingredients list produces 5” - I originally read that as “count the number of ingredients lists where any of the "can’t possibly” ingredients appears". Since there are only 4 lists in the sample, that would be the maximum. I think they meant “sum the number of times each of these ingredients appears in an ingredients list”
Sheesh, I accidentally pasted the answer with surrounding quotes i.e. "foo,bar,baz"
and thought how can this possibly be wrong?!?! :)
Yes, it was nice to re-use maximum-bipartite-matching
after learning about it on Day 16. However, I learned something new - apparently the result can swap the tuples !! I didn’t realize that at first and just blindly pasted the answer, and then I realized I’d pasted allergens, not ingredients because graph
had swapped my tuples for the real data, but not for the sample data.
Did you experience that @haskal ?
on the test data, yes i think so. but on the real data it was in the expected order. maybe there should be some way to denote which order you want the matching in, but i guess you can also just test one of the values and adjust accordingly
I think it’s a bad user experience to have the order be unstable. Having to test one of the values seems hacky IMO.
it should take an optional parameter for a vertex property that defines the “first” bipartite set, and the rest are considered the “second” maybe
@yfangzhe good hint; I had been thinking about something similar. In the end I modified my generated parsers to count the rules applied, and then sub’d in a parser for 0
that does 42+31+
. To “validate” I checked the number of each (42 > 31)
A friend of mine (not the author) sent me this <https://paste.factorcode.org/paste?id=4205|Factor solution to Day 20 Part 1> . I don’t quite understand it, due to lack of familiarity with Factor, but it seems pretty concise!
Hmm… after looking at <https://github.com/DearRude/aoc–2020/blob/main/solutions/day–20/part–1.jl|this Julia version> , it appears that both of them may have taken a shortcut that works well for Part 1, but doesn’t help w/ Part 2. And, coincidentally, neither of them have a part 2 ! :)
i have a 17–19 second part 2 and i’m wondering how to optimize it got no ideas though…
Mine was taking about the same amount of time, then i just hit it with define/memo
and got it down to 12 seconds
not a huge improvement, but far easier than anything else
yeah so turns out i can cut down the time to like 10 seconds by slapping global memoization on the function still, the whole thing is basically just appending lists every turn which can’t be that efficient… problem is when i tried to write a data/queue solution it was actually slower
Interesting. I have a feeling that it would benefit most from a vector queue so that the copy operation when starting a subgame can be far more efficient. I’m not sure how to do that kind of thing with managing memory in racket though.
Ugh. I originally overlooked the rule where you only copy the number of cards equal to the card you just dealt and wondered why my program wouldn’t terminate.
Now that I actually read the instructions correctly mine runs in about 7 seconds. I’m using imperative queues, but I have to copy them a lot anyhow to implement the history-checking rule.
Also, no memoization.