/*

Magic sequence in Comet.

From CSPLib problem 19:
http://www.csplib.org/Problems/prob019
"""
A magic sequence of length n is a sequence of integers x0 . . xn-1 between
0 and n-1, such that for all i in 0 to n-1, the number i occurs exactly
xi times in the sequence. For instance, 6,2,1,0,0,0,1,0,0,0 is a magic
sequence since 0 occurs 6 times in it, 1 occurs twice, ...
"""

This model is not very unlike the OPL models magic1.mod, magic2.mod,
and magic3.mod in
Pascal Van Hentenryck "The OPL Optimization Programming Language", page 39ff.

The problem n = 50 is solved in about 1 second, n = 500 is solved in about 18 seconds.

This Comet model was created by Hakan Kjellerstrand (hakank@gmail.com)
Also, see my Comet page: http://www.hakank.org/comet

*/

// Licenced under CC-BY-4.0 : http://creativecommons.org/licenses/by/4.0/

import cotfd;

int t0 = System.getCPUTime();

int n = 50;
range Range = 0..n-1;
range Domain = 0..n;

int value[i in Range] = i;

Solver<CP> m();
var<CP>{int} s[Range](m, Domain);

Integer num_solutions(0);

//
// distribute
//
// Imitates the OPL constraint distribute.
//
class distribute extends UserConstraint<CP> {
var<CP>{int}[] _occurrence;
int[] _value;
var<CP>{int}[] _element;
int _n;

distribute(var<CP>{int}[] occurrence,
int[] value,
var<CP>{int}[] element) : UserConstraint<CP>() {
_occurrence = occurrence;
_value = value;
_element = element;
_n = _occurrence.getSize();
}

Outcome<CP> post(Consistency<CP> cl) {
Solver<CP> cp = _occurrence[1].getSolver();
range Range = _occurrence.getRange();
forall(i in Range)
cp.post(sum(j in Range) (_occurrence[j] == _value[i]) == _element[i]);

return Suspend;
}

Outcome<CP> propagate() {
return Suspend;
}

}

explore<m> {

/*
// original constraint
forall(i in Range)
m.post(s[i] == sum(j in Range) (s[j] == i));
*/

// added in the OPL model magic2.mod
m.post(sum(i in Range) s[i] == n);
m.post(sum(i in Range) s[i]*i == n);

// added in the OPL model magic3.mod
m.post(distribute(s, value, s));

} using {

labelFF(m);

num_solutions++;

cout << s << endl;

}

cout << "\nnum_solutions: " << num_solutions << endl;

int t1 = System.getCPUTime();
cout << "time:      " << (t1-t0) << endl;
cout << "#choices = " << m.getNChoice() << endl;
cout << "#fail    = " << m.getNFail() << endl;
cout << "#propag  = " << m.getNPropag() << endl;