import Control.Concurrent.STM
import Control.Monad
import Data.Vector
type VecInts = Vector (TVar Int)
newVecInts :: Int -> STM (VecInts)
newVecInts s = generateM s (\_ -> newTVar 0)
modifyVI :: VecInts -> Int -> Int -> STM ()
modifyVI vi pos val = do
writeTVar (vi ! pos) val
waitUntilEqual :: VecInts -> Int -> Int -> STM ()
waitUntilEqual vi p1 p2 = do
a <- readTVar (vi ! p1)
b <- readTVar (vi ! p2)
when (a /= b) retryYes. It only retries when one of the referenced values is updated.
This does violate the rule "only use mutexes and condition variables", and perhaps the rule added at the end "you can't read the values" (comparing memory without reading from memory seems like quite a trick!).
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.
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).
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.
More generally, when you discover a tricky problem that would make a good interview question, oftentimes there's an architectural decision that would eliminate the problem.
var a = [0, 0, 0];
// Accept input from user
function modify(i, v) {
a[i] = v;
// ...
}
// Trigger an event when two values are equal
function waitUntil(i, j) {
return new Promise(function(res, rej) {
// ?
});
} var EventEmitter = require('events').EventEmitter;
var Promise = require('promise');
function Answer() {
var values = [];
var emitters = [];
this.modify = function(index, value) {
values[index] = value;
if (emitters[index]) {
emitters[index].emit('modified');
}
};
this.waitUntilEqual = function(index1, index2) {
return new Promise(function(resolve) {
if (!emitters[index1]) {
emitters[index1] = new EventEmitter();
}
if (!emitters[index2]) {
emitters[index2] = new EventEmitter();
}
function compare() {
if (values[index1] === values[index2]) {
resolve();
}
}
emitters[index1].on('modified', compare);
emitters[index2].on('modified', compare);
});
};
}
var check = new Answer();
check.waitUntilEqual(0, 1).then(function () { console.log('equal'); });
check.modify(0, 'x');
check.modify(1, 'x');