[sdab]

My c++ solution: https://gist.github.com/anonymous/7e6cc8f58e9cde1b6fda

I believe it follows all of the requirements. There is one glaring flaw which is that it uses a condition variable per 'wait_until_equal' call, though it uses only N mutexes. So this doesn't fall under the N^2 primitives (in the case of many waits), though its unclear to me if thats an official rule.

Im happy to listen to feedback or if someone sees an error.

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