00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038 #include "test/int.hh"
00039 #include <gecode/minimodel.hh>
00040
00041 namespace Test { namespace Int {
00042
00044 namespace Circuit {
00045
00051
00052 class Circuit : public Test {
00053 private:
00055 int offset;
00056 public:
00058 Circuit(int n, int min, int max, int off, Gecode::IntConLevel icl)
00059 : Test("Circuit::" + str(icl) + "::" + str(n) + "::" + str(off),
00060 n,min,max,false,icl), offset(off) {
00061 contest = CTL_NONE;
00062 }
00064 virtual bool solution(const Assignment& x) const {
00065 for (int i=x.size(); i--; )
00066 if ((x[i] < 0) || (x[i] > x.size()-1))
00067 return false;
00068 int reachable = 0;
00069 {
00070 int j=0;
00071 for (int i=x.size(); i--; ) {
00072 j=x[j]; reachable |= (1 << j);
00073 }
00074 }
00075 for (int i=x.size(); i--; )
00076 if (!(reachable & (1 << i)))
00077 return false;
00078 return true;
00079 }
00081 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00082 if (offset > 0) {
00083 Gecode::IntVarArgs xx(x.size());
00084 for (int i=x.size(); i--;)
00085 xx[i] = Gecode::expr(home, x[i]+offset);
00086 Gecode::circuit(home, offset, xx, icl);
00087 } else {
00088 Gecode::circuit(home, x, icl);
00089 }
00090 }
00091 };
00092
00094 class Path : public Test {
00095 private:
00097 int offset;
00098 public:
00100 Path(int n, int min, int max, int off, Gecode::IntConLevel icl)
00101 : Test("Path::" + str(icl) + "::" + str(n) + "::" + str(off),
00102 n+2,min,max,false,icl), offset(off) {
00103 contest = CTL_NONE;
00104 }
00106 virtual bool solution(const Assignment& x) const {
00107 int n = x.size() - 2;
00108 int s = x[n];
00109 int e = x[n+1];
00110 if ((s < 0) || (s > n) || (e < 0) || (e > n) || (x[e] != n))
00111 return false;
00112 for (int i=n; i--; )
00113 if ((i != e) && ((x[i] < 0) || (x[i] > n)))
00114 return false;
00115 int reachable = (1 << s);
00116 {
00117 int j=s;
00118 for (int i=n; i--; ) {
00119 j=x[j]; reachable |= (1 << j);
00120 }
00121 }
00122 for (int i=n; i--; )
00123 if (!(reachable & (1 << i)))
00124 return false;
00125 return true;
00126 }
00128 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00129 int n = x.size() - 2;
00130 Gecode::IntVarArgs xx(n);
00131 if (offset > 0) {
00132 for (int i=n; i--;)
00133 xx[i] = Gecode::expr(home, x[i]+offset);
00134 Gecode::path(home, offset, xx,
00135 Gecode::expr(home, x[n]+offset),
00136 Gecode::expr(home, x[n+1]+offset),icl);
00137 } else {
00138 for (int i=n; i--;)
00139 xx[i] = x[i];
00140 Gecode::path(home, xx, x[n], x[n+1], icl);
00141 }
00142 }
00143 };
00144
00146 class CircuitCost : public Test {
00147 private:
00149 int offset;
00150 public:
00152 CircuitCost(int n, int min, int max, int off, Gecode::IntConLevel icl)
00153 : Test("Circuit::Cost::"+str(icl)+"::"+str(n)+"::"+str(off),
00154 n+1,min,max,false,icl), offset(off) {
00155 contest = CTL_NONE;
00156 }
00158 virtual bool solution(const Assignment& x) const {
00159 int n=x.size()-1;
00160 for (int i=n; i--; )
00161 if ((x[i] < 0) || (x[i] > n-1))
00162 return false;
00163 int reachable = 0;
00164 {
00165 int j=0;
00166 for (int i=n; i--; ) {
00167 j=x[j]; reachable |= (1 << j);
00168 }
00169 }
00170 for (int i=n; i--; )
00171 if (!(reachable & (1 << i)))
00172 return false;
00173 int c=0;
00174 for (int i=n; i--; )
00175 c += x[i];
00176 return c == x[n];
00177 }
00179 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00180 using namespace Gecode;
00181 int n=x.size()-1;
00182 IntArgs c(n*n);
00183 for (int i=0; i<n; i++)
00184 for (int j=0; j<n; j++)
00185 c[i*n+j]=j;
00186 IntVarArgs y(n);
00187 if (offset > 0) {
00188 for (int i=n; i--;)
00189 y[i] = Gecode::expr(home, x[i]+offset);
00190 Gecode::circuit(home, c, offset, y, x[n], icl);
00191 } else {
00192 for (int i=0; i<n; i++)
00193 y[i]=x[i];
00194 circuit(home, c, y, x[n], icl);
00195 }
00196 }
00197 };
00198
00200 class PathCost : public Test {
00201 private:
00203 int offset;
00204 public:
00206 PathCost(int n, int min, int max, int off, Gecode::IntConLevel icl)
00207 : Test("Path::Cost::"+str(icl)+"::"+str(n)+"::"+str(off),
00208 n+3,min,max,false,icl), offset(off) {
00209 contest = CTL_NONE;
00210 }
00212 virtual bool solution(const Assignment& x) const {
00213 int n = x.size() - 3;
00214 int s = x[n];
00215 int e = x[n+1];
00216 int c = x[n+2] + n;
00217 if ((s < 0) || (s > n) || (e < 0) || (e > n) || (x[e] != n))
00218 return false;
00219 for (int i=n; i--; )
00220 if ((i != e) && ((x[i] < 0) || (x[i] > n)))
00221 return false;
00222 int reachable = (1 << s);
00223 {
00224 int j=s;
00225 for (int i=n; i--; ) {
00226 j=x[j]; reachable |= (1 << j);
00227 }
00228 }
00229 for (int i=n; i--; )
00230 if (!(reachable & (1 << i)))
00231 return false;
00232 for (int i=n; i--; )
00233 c -= x[i];
00234 return c == 0;
00235 }
00237 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00238 using namespace Gecode;
00239 int n=x.size()-3;
00240 IntArgs c(n*n);
00241 for (int i=0; i<n; i++)
00242 for (int j=0; j<n; j++)
00243 c[i*n+j]=j;
00244 IntVarArgs y(n);
00245 if (offset > 0) {
00246 for (int i=n; i--;)
00247 y[i] = Gecode::expr(home, x[i]+offset);
00248 path(home, c, offset, y,
00249 expr(home, x[n]+offset),
00250 expr(home, x[n+1]+offset),
00251 x[n+2], icl);
00252 } else {
00253 for (int i=0; i<n; i++)
00254 y[i]=x[i];
00255 path(home, c, y, x[n], x[n+1], x[n+2], icl);
00256 }
00257 }
00258 };
00259
00261 class CircuitFullCost : public Test {
00262 private:
00264 int offset;
00265 public:
00267 CircuitFullCost(int n, int min, int max, int off,
00268 Gecode::IntConLevel icl)
00269 : Test("Circuit::FullCost::" + str(icl)+"::"+str(n)+"::"+str(off),
00270 2*n+1,min,max,false,icl), offset(off) {
00271 contest = CTL_NONE;
00272 }
00274 virtual bool solution(const Assignment& x) const {
00275 int n=(x.size()-1) / 2;
00276 for (int i=n; i--; )
00277 if ((x[i] < 0) || (x[i] > n-1))
00278 return false;
00279 int reachable = 0;
00280 {
00281 int j=0;
00282 for (int i=n; i--; ) {
00283 j=x[j]; reachable |= (1 << j);
00284 }
00285 }
00286 for (int i=n; i--; )
00287 if (!(reachable & (1 << i)))
00288 return false;
00289 for (int i=n; i--; )
00290 if ((x[i]/2) != x[n+i])
00291 return false;
00292 int c=0;
00293 for (int i=n; i--; )
00294 c += x[n+i];
00295 return c == x[2*n];
00296 }
00298 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00299 using namespace Gecode;
00300 int n=(x.size()-1)/2;
00301 IntArgs c(n*n);
00302 for (int i=0; i<n; i++)
00303 for (int j=0; j<n; j++)
00304 c[i*n+j]=(j/2);
00305 IntVarArgs y(n), z(n);
00306 for (int i=0; i<n; i++) {
00307 z[i]=x[n+i];
00308 }
00309 if (offset > 0) {
00310 for (int i=n; i--;)
00311 y[i] = Gecode::expr(home, x[i]+offset);
00312 Gecode::circuit(home, c, offset, y, z, x[2*n], icl);
00313 } else {
00314 for (int i=0; i<n; i++)
00315 y[i]=x[i];
00316 circuit(home, c, y, z, x[2*n], icl);
00317 }
00318 }
00319 };
00320
00322 class Create {
00323 public:
00325 Create(void) {
00326 for (int i=1; i<=6; i++) {
00327 (void) new Circuit(i,0,i-1,0,Gecode::ICL_VAL);
00328 (void) new Circuit(i,0,i-1,0,Gecode::ICL_DOM);
00329 (void) new Circuit(i,0,i-1,5,Gecode::ICL_VAL);
00330 (void) new Circuit(i,0,i-1,5,Gecode::ICL_DOM);
00331 }
00332 for (int i=1; i<=4; i++) {
00333 (void) new Path(i,0,i-1,0,Gecode::ICL_VAL);
00334 (void) new Path(i,0,i-1,0,Gecode::ICL_DOM);
00335 (void) new Path(i,0,i-1,5,Gecode::ICL_VAL);
00336 (void) new Path(i,0,i-1,5,Gecode::ICL_DOM);
00337 }
00338 (void) new CircuitCost(4,0,9,0,Gecode::ICL_VAL);
00339 (void) new CircuitCost(4,0,9,0,Gecode::ICL_DOM);
00340 (void) new CircuitFullCost(3,0,3,0,Gecode::ICL_VAL);
00341 (void) new CircuitFullCost(3,0,3,0,Gecode::ICL_DOM);
00342 (void) new CircuitCost(4,0,9,5,Gecode::ICL_VAL);
00343 (void) new CircuitCost(4,0,9,5,Gecode::ICL_DOM);
00344 (void) new CircuitFullCost(3,0,3,5,Gecode::ICL_VAL);
00345 (void) new CircuitFullCost(3,0,3,5,Gecode::ICL_DOM);
00346 (void) new PathCost(3,0,5,0,Gecode::ICL_VAL);
00347 (void) new PathCost(3,0,5,0,Gecode::ICL_DOM);
00348 (void) new PathCost(3,0,5,5,Gecode::ICL_VAL);
00349 (void) new PathCost(3,0,5,5,Gecode::ICL_DOM);
00350 }
00351 };
00352
00353 Create c;
00355
00356 }
00357 }}
00358
00359