[davidtgoldblatt]

Looks good to me; that's essentially the solution I had in mind (though, I think you have a race on NintBucket::waiters in modify and append_cv). Using a custom two-mutex lock class and condition_variable_any is particularly clever, I hadn't thought of that.

I just published my solution, which uses a similar strategy: http://dgoldblatt.com/a-threading-riddle-solution.html

I don't think of this as violating the N^2 primitives rule; the solution is still linear in the size of the problem its facing (it only uses K condition variables for K threads, so even if K is bigger than N^2, it's still morally in the scope of the problem).

[sdab]

Ah, yep I see the race. Here is a fix: https://gist.github.com/sdab/d7ba036b2b7f4b5626cd

Thanks for the puzzle, its hard to find good concurrency problems.

Edit: Looked through your solution. You are right, we thought of similar things. I started out by wanting a multi condition variable, but didnt want to implement it :). I ended up getting something similar in a roundabout way.