3 ms·

I actually finished them all, most on the day on which they were published (I had the entire day, since the problems open at 06:00 in my timezone; I didn't try

I actually finished them all, most on the day on which they were published (I had the entire day, since the problems open at 06:00 in my timezone; I didn't try for any leaderboards :p). Some problems took me far too much time (day 15 with its huge simulation!), and overall I agree with the general sentiment that the problems were too finicky, with a lot of details to implement without much real thought. Day 23 part 2 (teleportation nanobots one) was fairly difficult as well; I tried to implement an actual solution, but failed because of wrong assumptions about its correctness. (I tried to represent the intersection of a number of octahedrons with the bounded volume of 8 planes, but it seems that representation is redundant, so there are invalid configurations. I didn't feel like fixing that anymore after 8+ hours.) Looking at the solutions board on reddit, I wrote a smtlib2 script for Z3 that solves it; it works, but isn't all that satisfying. The sheer amount of pathfinding amazed me; some of the plain pathfinding problems were good (day 22 with its pathfinding in the implicit graph where you split nodes up into the various combinations of tools), and I was happy to see that day 25 was just an unordered graph component analysis (i.e. a few floodfills). I liked yesteryear more, and in general I'd like to see smaller problem statements (and thereby also less details to implement!), and possibly slightly more of an algorithmic challenge, though the latter is definitely not necessary (this is not a competitive programming competition, it's an advent calendar of all things!). Still, big thanks to Eric for giving us this! (I did the problems in Rust, to become more familiar with the language. See my implementations here[1].) [1]: https://git.tomsmeding.com/AOC/tree/2018/src https://git.tomsmeding.com/AOC/tree/2018/src

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 ago
    It'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.)

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 ago
  It'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.)