Maximum Density Still Life:StillCell
From CometPublic
This is the implementation of the still-cell constraint in the Maximum Density Still Life problem.
/**
* Constraint applying on a still cell: a cell that will not change it's state if it's neighbours don't change
*/
class StillCell implements Constraint
{
/** The local solver associated with the cell and it's neighbours */
LocalSolver _s;
/** Indicates whether the constraint has been posted */
bool _posted;
/** The main cell (0 = dead, 1 = alive) */
var{int} _cell;
/** The cell's neighbours (0 = dead, 1 = alive) */
var{int}[] _neighb;
/** The range of neighbours that might be alive */
range _numNeighb;
/** The range of indexes in _neighb */
range _R;
/** The number of alive neighbours */
var{int} _numAliveNeighb;
/** The list of all variables on which this constraint applies */
var{int}[] _variables;
/**
* An 2D-array for computing the number violations:
* _violations[_cell,_numAliveNeighb]
* indicates the violations of this constraint from the state of
* the main cell and the number of alive neighbours.
* (this array might be better defined as static but how ?)
*/
int[,] _violations;
/** The number of violations of this constraint */
var{int} _violation;
/**
* Defines the violations of a neighbour in function of it's value,
* the number of alive neighbours and the center cell's value
* (this array might be better defined as static but how ?)
*/
int[,,] _neighb_violations; /* _cell, _neighb[i], _numAliveNeigb */
/**
* The correspondance between each cell covered by this constraint
* and it's index in _vv (and _variables)
* (similar to the technique that was used for AllDistinct,
* see Constraint-Based Local Search p.118-121)
*/
dict{var{int} -> int} _map;
/** The number of violations for each variable */
var{int}[] _vv;
/** Indicates whether this constraint is satisfied */
var{boolean} _isTrue;
/** Indicates whether this constraint is unsatisfied (=1) or satisfied (=0) */
var{int} _intIsFalse;
/**
* Builds a new StillCell constraint
* @param cell The main (center) cell that we want to be still
* @param neighb The list of neighbours of cell
*/
StillCell(var{int} cell, var{int}[] neighb)
{
_cell = cell;
_s = neighb.getLocalSolver();
_numNeighb = 0..neighb.sz();
_posted = false;
_neighb = neighb;
_R = _neighb.getRange();
_isTrue = new var{boolean}(_s);
_numAliveNeighb = new var{int}(_s);
_violation = new var{int}(_s);
_map = new dict{var{int} -> int}();
forall (i in _R)
{
_map{_neighb[i]} = i;
}
_map{_cell} = _neighb.sz();
_vv = new var{int}[_numNeighb](_s);
_intIsFalse = new var{int}(_s, 0..1) <- !_isTrue;
_variables = new var{int}[0.._neighb.sz()](_s);
}
/**
* Called when the constraint is posted
*/
void post()
{
if (!_posted)
{
_posted = true;
_numAliveNeighb <- sum(i in _R) _neighb[i];
_violations = new int[j in 0..1, i in _numNeighb] = (j == 1 ? (i <= 2 ? 2 - i : i - 3) : (i == 3 ? 1 : 0));
_violation <- _violations[_cell, _numAliveNeighb];
_neighb_violations = new int[0..1, 0..1, _numNeighb];
forall (i in _numNeighb)
{
// _cell alive and given neighbour alive
_neighb_violations[1,1,i] = (i > 3 ? 1 : 0);
// _cell alive but given neighbour dead
_neighb_violations[1,0,i] = (i < 2 ? 1 : 0);
// NB.: if _cell is dead and numAliveNeighb == 3,
// then flipping any neighbour solves the violation
// thus we count 1 violation for each neighbour
// _cell dead but given neighbour alive
_neighb_violations[0,1,i] = (i == 3 ? 1 : 0);
// _cell dead and given neighbour dead
_neighb_violations[0,0,i] = (i == 3 ? 1 : 0);
}
forall (i in _R)
{
_vv[i] <- _neighb_violations[_cell, _neighb[i], _numAliveNeighb];
}
_vv[_neighb.sz()] = _intIsFalse;
_isTrue <- _violation == 0;
forall (i in _R)
_variables[i] = _neighb[i];
_variables[_neighb.sz()] = _cell;
}
}
/**
* @return a variable that is true if the constraint is satsified (the cell is still)
*/
var{boolean} isTrue()
{
_isTrue;
}
/**
* @return a variable associated with the number of violations for this constraint
*/
var{int} violations()
{
return _violation;
}
/**
* @param x a variable on which applies this constraint (one of variables())
* @return a variable associated with the number of violations for x
*/
var{int} violations(var{int} x)
{
return _vv[_map{x}];
}
/**
* @return a variable that is associated with the number of violations that x might decrease for this constraint.
*/
var{int} decrease(var{int} x)
{
if (x.getId() == _cell.getId())
{
return violations();
}
else
{
return violations(x);
}
}
/**
* @return The variation in the number of violations applying on this constraint if the value v was assigned to x
*/
int getAssignDelta(var{int} x,int v)
{
if (x == v) return 0;
if (x.getId() == _cell.getId())
{
return _violations[v,_numAliveNeighb] - violations();
}
else
{
// if v == 0, _numAliveNeighb will decrement, else it will increment
return _violations[_cell,_numAliveNeighb - 1 + 2 * v] - violations();
}
}
/**
* @return The variation in the number of violations applying on this constraint if the values of x and y were swapped
*/
int getSwapDelta(var{int} x, var{int} y)
{
if (x == y) return 0;
var{int} a; var{int} b;
if (y.getId() == _cell.getId())
{
a = y; b = x;
}
else
{
a = x; b = y;
}
if (a.getId() == _cell.getId())
{
return _violations[b,_numAliveNeighb - 1 + 2 * a] - violations(); // swap the roles of a and b
}
return 0;
}
/**
* @return The list of variables on which applies this constraint
*/
var{int}[] getVariables()
{
return _variables;
}
/**
* @return The local solver associated with this constraint's variables
*/
LocalSolver getLocalSolver()
{
return _s;
}
// Unimplemented methods (TODO ?)
void initialize() {}
int getAssignDelta(var{int}[] x,int[] v) {}
int getSwapDelta(var{int} a, var{int} b, var{int} c, var{int} d) {}
int getAssignDelta(var{int} x, int v, var{int} y, int w) {}
ConstraintType getType() {}
}
