There exists a game, whose state is quantified by n boolean variables p_1, p_2, ..., p_n. Assume 0 <= n <= 10. The purpose of the game is to keep track of the state of as many variables as possible, and when they will change states (see below).
Only a subset of the variables may be observed at a time. We are always informed when the state of a variable changes from true to false, but only when the variable in question is being observed are we also informed which variable was changed.
If some p_i changes state from true to false at time t, then it will change state back from false to true at time t + 60.
Here are some example situations and the desired behavior. Assume that there are three variables, p_1, p_2, and p_3.
p_1. We know that p_1 will change state back at t + 60.p_1 and p_2 are observable. A variable changes state. It should be inferred that it was p_3. We know that p_3 will change state back at t + 60.p_1 is observable, and it is known that p_2 changed state to false at time t - 30. A variable changes state. It was not p_1 by observation and p_2 will only change state to true at t + 30, therefore it was p_3.p_1 changed state to false at time t - 30, p_2 changed state to false at t - 75, and p_3 changed state to false at t - 80. A variable changes state. At t + 1 p_2 is observed to have a value of true. Because p_1 is still false, and p_2 has been observed to be true, it should be inferred that p_3 is false, and will change state back to true at t + 60.p_1 and p_2 are observable. It is known that p_3 changed state to false at time t - 70. No variable changes state. It should be inferred that p_3 is true, since it would have changed from false to true at t - 10, and if it had changed from true to false, we would have been informed of a variable changing state.One approach I have tried involved iterating over each of the variables on each notification of a variable state change, and ruling out the possible matches based on:
then, for the leftover variables for which state is known, determining an upper and lower bound on their last variable change based on when the variable was last observed in a particular state, when the variable may have changed state (back, from false to true), etc. Then if there exists only one variable change event within that bounds, it should be the one corresponding to the variable. It ended up being too cumbersome and I didn't continue. Every line was a burden because it seemed as if the number of possible combinations of states was too large and I would not take something into account.
Is the above approach a reasonable one to take, given the problem statement? Is there a general way that problems like this are modeled that allows them to be solved more elegantly?
On the advice of @NicoSchertler, I have come up with a solution which handles the uncertainty by creating sets of states based on a sequence of Observations and Hypotheses. An observation is a known state for a particular (observed) variable, whereas a hypothesis is notification of a state, but with no information concerning which variable it applies to. We are able to make the assumption that a hypothesis cannot apply to a variable which is under observation. This solution does not handle the case where the start state is not known (yet).
There is a single starting state corresponding to the case where every variable is true. When provided a hypothesis, potentially multiple (n) successor states are generated by supposing that each unobserved variable is the subject of the hypothesis. Successor states that lead to contradiction are discarded. When provided an observation, a single successor state is generated for each current state. Any state that leads to contradiction is discarded. In this way the sequence of hypotheses and observations results in a set of possible states the variables may be in.
For my specific purpose, I wanted to know what could be known based on these states (as opposed to e.g. whether a valid solution exists). The states are combined and a result is returned that gives the state of each variable if that variable has the same state across all states.
Given n states and m notifications, the worst-case complexity is n^m which can be very limiting, but it should be fine for my limited application.
Here is the JavaScript implementation and test code.
solver.js
// Time for state to change back.
var STATE_CHANGE = 6e4;
// Possible notification lag.
var EPSILON = 2e3;
// Comparison operations.
function lt(a, b) {
return a - b < EPSILON;
}
function gt(a, b) {
return b - a < EPSILON;
}
function eq(a, b) {
return Math.abs(a - b) < EPSILON;
}
// Object clone.
function clone(obj) {
return JSON.parse(JSON.stringify(obj));
}
module.exports = Solver;
/**
* Solver solves boolean dynamic state.
* @param {Array<string>} variables - array of variable names.
*/
function Solver(variables) {
this.variables = {};
this.states = [];
this._time = null;
var state = {};
var time = Date.now();
var self = this;
// TODO: Handle unknown or variable start.
variables.forEach(function (variable) {
self.variables[variable] = {
observed: false
};
state[variable] = {
state: true,
intervals: [{
state: true,
start: time,
observed: false,
end: null
}]
};
});
this.states.push(state);
}
// Set subset of variables as observed, the rest assumed not.
Solver.prototype.setObserved = function(variables) {
var unobserved_variables = Object.keys(this.variables).filter(function (variable) {
return variables.indexOf(variable) === -1;
});
var self = this;
variables.forEach(function (variable) {
self.variables[variable].observed = true;
});
unobserved_variables.forEach(function (variable) {
self.variables[variable].observed = false;
});
};
// Hypothesis has time, state.
Solver.prototype.addHypothesis = function(h) {
this.updateVariables();
var states = [];
for (var i = 0; i < this.states.length; i++) {
var newStates = this.applyHypothesis(this.states[i], h);
if (newStates)
Array.prototype.push.apply(states, newStates);
}
this.states = states;
};
// Observation has time, state, variable.
Solver.prototype.addObservation = function(o) {
this.updateVariables();
var states = [];
for (var i = 0; i < this.states.length; i++) {
var newState = this.applyObservation(this.states[i], o);
if (newState)
states.push(newState);
}
this.states = states;
};
// Get set of possible states.
Solver.prototype.getStates = function() {
this.updateVariables();
return this.states.slice();
};
// Get consolidated state.
// Each variable has state (true|false|null), change (if false). change
// is number or array (if there is disagreement)
Solver.prototype.getState = function() {
this.updateVariables();
// Construct output.
var out = {};
var state = this.states[0];
for (var name in state) {
var variable = state[name];
if (variable.state) {
out[name] = {
state: variable.state
};
} else {
var time = variable.intervals[variable.intervals.length - 1].end;
out[name] = {
state: variable.state,
time: time
};
}
}
// Compare results across all states.
return this.states.slice(1).reduce(function (out, state) {
for (var name in out) {
var out_variable = out[name],
variable = state[name];
// Check for matching states.
if (out_variable.state === variable.state) {
// Falsy check time.
if (!out_variable.state) {
// TODO: check undefined in case interval not updated?
var change = variable.intervals[variable.intervals.length - 1].end;
if (out_variable.time instanceof Array) {
if (out_variable.time.indexOf(change) === -1) {
out_variable.push(change);
}
} else if (out_variable.time !== change) {
var times = [out_variable.time, change];
out_variable.time = times;
} // Else matches, so no problem.
}
} else {
// Conflicted states.
out_variable.state = null;
// In case it was set.
delete out_variable.time;
}
}
return out;
}, out);
};
// Update `false` state variables based on false end
// time, if present.
Solver.prototype.updateVariables = function() {
var time = this._time || Date.now();
for (var i = 0; i < this.states.length; i++) {
var state = this.states[i];
for (var name in state) {
var variable = state[name];
// Update changeback.
if (!variable.state) {
if (variable.intervals.length > 0) {
var last = variable.intervals[variable.intervals.length - 1];
if (last.end && last.end <= time) {
// update to true.
variable.state = true;
variable.intervals.push({
state: true,
start: time,
end: null
});
}
}
}
}
}
};
// Return state with observation applied or null if invalid.
Solver.prototype.applyObservation = function(state, observation) {
var variable = state[observation.variable];
if (variable.state && !observation.state) {
// Change in observed variable true -> false
variable.state = observation.state;
variable.intervals.push({
state: variable.state,
start: observation.time,
end: observation.time + STATE_CHANGE
});
return state;
} else if (variable.state && observation.state) {
// Expected state.
return state;
} else if (!variable.state && observation.state) {
// Potentially updating variable.
var time = variable.intervals[variable.intervals.length - 1];
if (eq(time, observation.time)) {
// update state.
variable.state = observation.state;
variable.intervals.push({
state: observation.state,
start: observation.time,
end: null
});
return state;
} else {
// Could not update this variable.
return null;
}
} else if (!variable.state && !observation.state) {
// Expected state.
return state;
}
};
// Returns multiple states or null if invalid
Solver.prototype.applyHypothesis = function(state, hypothesis) {
hypothesis = clone(hypothesis);
var states = [];
for (var name in state) {
// Skip observed variables, no guessing with them.
if (this.variables[name].observed)
continue;
var newState = clone(state);
var variable = newState[name];
// Hypothesis is always false.
if (variable.state) {
// Change in observed variable true -> false
variable.state = hypothesis.state;
variable.intervals.push({
state: variable.state,
start: hypothesis.time,
end: hypothesis.time + STATE_CHANGE
});
} else {
newState = null;
}
if (newState !== null) {
states.push(newState);
}
}
if (states.length === 0) {
return null;
} else {
return states;
}
};
test-solver.js
var Solver = require('./solver');
var p_1 = "p_1",
p_2 = "p_2",
p_3 = "p_3";
var solver = new Solver([p_1, p_2, p_3]);
var t = Date.now();
solver.setObserved([p_1, p_2, p_3]);
solver._time = t + 5e3;
solver.addObservation({
variable: p_1,
state: false,
time: t + 5e3
});
var result = solver.getState();
if (!result[p_1].state && result[p_1].time === t + 65e3 &&
result[p_2].state &&
result[p_3].state) {
console.log("PASS: Test 1.");
} else {
console.log("FAIL: Test 1.");
}
solver = new Solver([p_1, p_2, p_3]);
solver.setObserved([p_1, p_2]);
solver._time = t + 5e3;
solver.addHypothesis({
state: false,
time: t + 5e3
});
result = solver.getState();
if (result[p_1].state &&
result[p_2].state &&
!result[p_3].state && result[p_3].time === t + 65e3) {
console.log("PASS: Test 2.");
} else {
console.log("FAIL: Test 2.");
}
solver = new Solver([p_1, p_2, p_3]);
solver.setObserved([p_1]);
solver._time = t - 30e3;
solver.addObservation({
variable: p_2,
time: t - 30e3,
state: false
});
solver._time = t;
solver.addHypothesis({
state: false,
time: t
});
var result = solver.getState();
if (result[p_1].state &&
!result[p_2].state && result[p_2].time === t + 30e3 &&
!result[p_3].state && result[p_3].time === t + 60e3) {
console.log("PASS: Test 3.");
} else {
console.log("FAIL: Test 3.");
}
solver = new Solver([p_1, p_2, p_3]);
solver._time = t - 80e3;
solver.addObservation({
variable: p_3,
time: t - 80e3,
state: false
});
solver._time = t - 75e3;
solver.addObservation({
variable: p_2,
time: t - 75e3,
state: false
});
solver._time = t - 30e3;
solver.addObservation({
variable: p_1,
time: t - 30e3,
state: false
});
solver._time = t;
solver.addHypothesis({
state: false,
time: t
});
result = solver.getState();
if (!result[p_1].state && result[p_1].time === t + 30e3 &&
result[p_2].state === null &&
result[p_3].state === null) {
console.log("PASS: Test 4.");
} else {
console.log("FAIL: Test 4.");
}
solver._time = t + 1;
solver.addObservation({
variable: p_2,
time: t + 1,
state: true
});
var result = solver.getState();
if (!result[p_1].state && result[p_1].time === t + 30e3 &&
result[p_2].state &&
!result[p_3].state && result[p_3].time === t + 60e3) {
console.log("PASS: Test 5.");
} else {
console.log("FAIL: Test 5.");
}