3 ms·
Finished them all, and enjoyed it, but Day 23 part 2 (part 1 was trivial) was a real bugbear. In particular, Day 23 was pretty remarkable for the sheer number
by rst 8y ago
Finished them all, and enjoyed it, but Day 23 part 2 (part 1 was trivial) was a real bugbear.
In particular, Day 23 was pretty remarkable for the sheer number of "solutions" posted to the solutions board that worked for the person's own input, but only by luck -- they failed for other peoples'. The only possibly general solutions I've seen are the ones that set up external solvers -- either z3 or some integer programming package. (I wound up using the latter, and may have lucked out myself -- whether due to numerical instability or some fault in problem setup, I only got close enough to optimum to find it with a little local hill-climbing.) I'm not sure that's what Eric had in mind; everything else can be solved in Python or Ruby with no recourse to large external libraries.
For the most part, I had fun with this stuff -- even day 24, which I had to set aside for hours before a careful desk check found the reason why the answers I was getting weren't quite right. But rules that matter for some people, but not others, do take a bit of the shine off.
There were more minor problems along the same lines with some of the other problems -- day 15 and day 24 had a lot of fiddly rules which didn't matter at all for some peoples' inputs.
- tomsmeding 8y ago> Day 23 [...] I'm not sure that's what Eric had in mind There is an algorithm for finding a maximum clique in a graph, and some people on Reddit seem to have used it: the Born-Kerbosch algorithm [1]. Your graph has a connection between two nodes if their ranges overlap. It relies on the assumption that overlapping of manhattan regions is transitive; no-one on Reddit seemed to know whether that assumption is true, and I don't know either. :) [1]: https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorith...
- rst 8y agoIt's not -- the Reddit thread has a counterexample: https://www.reddit.com/r/adventofcode/comments/a8s17l/2018_day_23_solutions/ecdxr1u/ https://www.reddit.com/r/adventofcode/comments/a8s17l/2018_d... That said -- one visualization posted elsewhere showed that that person's particular input was a bunch of singletons, plus one colossal clique that all intersected at a single point. That may have been structure that people were meant to discover -- but it's not clear that anyone did until after the fact. (The person with the visualization identified the clique as all the "bot ranges" intersecting with a solution point that they'd already found by other means.)