3 ms·

> 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

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