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 #include "test/int.hh"
00035 #include <gecode/minimodel.hh>
00036
00037 namespace Test { namespace Int {
00038
00040 namespace Circuit {
00041
00047
00048 class Circuit : public Test {
00049 private:
00051 int offset;
00052 public:
00054 Circuit(int n, int min, int max, int off, Gecode::IntPropLevel ipl)
00055 : Test("Circuit::" + str(ipl) + "::" + str(n) + "::" + str(off),
00056 n,min,max,false,ipl), offset(off) {
00057 contest = CTL_NONE;
00058 testfix = false;
00059 }
00061 virtual bool solution(const Assignment& x) const {
00062 for (int i=x.size(); i--; )
00063 if ((x[i] < 0) || (x[i] > x.size()-1))
00064 return false;
00065 int reachable = 0;
00066 {
00067 int j=0;
00068 for (int i=x.size(); i--; ) {
00069 j=x[j]; reachable |= (1 << j);
00070 }
00071 }
00072 for (int i=x.size(); i--; )
00073 if (!(reachable & (1 << i)))
00074 return false;
00075 return true;
00076 }
00078 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00079 if (offset > 0) {
00080 Gecode::IntVarArgs xx(x.size());
00081 for (int i=x.size(); i--;)
00082 xx[i] = Gecode::expr(home, x[i]+offset);
00083 Gecode::circuit(home, offset, xx, ipl);
00084 } else {
00085 Gecode::circuit(home, x, ipl);
00086 }
00087 }
00088 };
00089
00091 class Path : public Test {
00092 private:
00094 int offset;
00095 public:
00097 Path(int n, int min, int max, int off, Gecode::IntPropLevel ipl)
00098 : Test("Path::" + str(ipl) + "::" + str(n) + "::" + str(off),
00099 n+2,min,max,false,ipl), offset(off) {
00100 contest = CTL_NONE;
00101 testfix = false;
00102 }
00104 virtual bool solution(const Assignment& x) const {
00105 int n = x.size() - 2;
00106 int s = x[n];
00107 int e = x[n+1];
00108 if ((s < 0) || (s > n) || (e < 0) || (e > n) || (x[e] != n))
00109 return false;
00110 for (int i=n; i--; )
00111 if ((i != e) && ((x[i] < 0) || (x[i] > n)))
00112 return false;
00113 int reachable = (1 << s);
00114 {
00115 int j=s;
00116 for (int i=n; i--; ) {
00117 j=x[j]; reachable |= (1 << j);
00118 }
00119 }
00120 for (int i=n; i--; )
00121 if (!(reachable & (1 << i)))
00122 return false;
00123 return true;
00124 }
00126 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00127 int n = x.size() - 2;
00128 Gecode::IntVarArgs xx(n);
00129 if (offset > 0) {
00130 for (int i=n; i--;)
00131 xx[i] = Gecode::expr(home, x[i]+offset);
00132 Gecode::path(home, offset, xx,
00133 Gecode::expr(home, x[n]+offset),
00134 Gecode::expr(home, x[n+1]+offset),ipl);
00135 } else {
00136 for (int i=n; i--;)
00137 xx[i] = x[i];
00138 Gecode::path(home, xx, x[n], x[n+1], ipl);
00139 }
00140 }
00141 };
00142
00144 class CircuitCost : public Test {
00145 private:
00147 int offset;
00148 public:
00150 CircuitCost(int n, int min, int max, int off, Gecode::IntPropLevel ipl)
00151 : Test("Circuit::Cost::"+str(ipl)+"::"+str(n)+"::"+str(off),
00152 n+1,min,max,false,ipl), offset(off) {
00153 contest = CTL_NONE;
00154 testfix = false;
00155 }
00157 virtual bool solution(const Assignment& x) const {
00158 int n=x.size()-1;
00159 for (int i=n; i--; )
00160 if ((x[i] < 0) || (x[i] > n-1))
00161 return false;
00162 int reachable = 0;
00163 {
00164 int j=0;
00165 for (int i=n; i--; ) {
00166 j=x[j]; reachable |= (1 << j);
00167 }
00168 }
00169 for (int i=n; i--; )
00170 if (!(reachable & (1 << i)))
00171 return false;
00172 int c=0;
00173 for (int i=n; i--; )
00174 c += x[i];
00175 return c == x[n];
00176 }
00178 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00179 using namespace Gecode;
00180 int n=x.size()-1;
00181 IntArgs c(n*n);
00182 for (int i=0; i<n; i++)
00183 for (int j=0; j<n; j++)
00184 c[i*n+j]=j;
00185 IntVarArgs y(n);
00186 if (offset > 0) {
00187 for (int i=n; i--;)
00188 y[i] = Gecode::expr(home, x[i]+offset);
00189 Gecode::circuit(home, c, offset, y, x[n], ipl);
00190 } else {
00191 for (int i=0; i<n; i++)
00192 y[i]=x[i];
00193 circuit(home, c, y, x[n], ipl);
00194 }
00195 }
00196 };
00197
00199 class PathCost : public Test {
00200 private:
00202 int offset;
00203 public:
00205 PathCost(int n, int min, int max, int off, Gecode::IntPropLevel ipl)
00206 : Test("Path::Cost::"+str(ipl)+"::"+str(n)+"::"+str(off),
00207 n+3,min,max,false,ipl), offset(off) {
00208 contest = CTL_NONE;
00209 testfix = false;
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], ipl);
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], ipl);
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::IntPropLevel ipl)
00269 : Test("Circuit::FullCost::" + str(ipl)+"::"+str(n)+"::"+str(off),
00270 2*n+1,min,max,false,ipl), offset(off) {
00271 contest = CTL_NONE;
00272 testfix = false;
00273 }
00275 virtual bool solution(const Assignment& x) const {
00276 int n=(x.size()-1) / 2;
00277 for (int i=n; i--; )
00278 if ((x[i] < 0) || (x[i] > n-1))
00279 return false;
00280 int reachable = 0;
00281 {
00282 int j=0;
00283 for (int i=n; i--; ) {
00284 j=x[j]; reachable |= (1 << j);
00285 }
00286 }
00287 for (int i=n; i--; )
00288 if (!(reachable & (1 << i)))
00289 return false;
00290 for (int i=n; i--; )
00291 if ((x[i]/2) != x[n+i])
00292 return false;
00293 int c=0;
00294 for (int i=n; i--; )
00295 c += x[n+i];
00296 return c == x[2*n];
00297 }
00299 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00300 using namespace Gecode;
00301 int n=(x.size()-1)/2;
00302 IntArgs c(n*n);
00303 for (int i=0; i<n; i++)
00304 for (int j=0; j<n; j++)
00305 c[i*n+j]=(j/2);
00306 IntVarArgs y(n), z(n);
00307 for (int i=0; i<n; i++) {
00308 z[i]=x[n+i];
00309 }
00310 if (offset > 0) {
00311 for (int i=n; i--;)
00312 y[i] = Gecode::expr(home, x[i]+offset);
00313 Gecode::circuit(home, c, offset, y, z, x[2*n], ipl);
00314 } else {
00315 for (int i=0; i<n; i++)
00316 y[i]=x[i];
00317 circuit(home, c, y, z, x[2*n], ipl);
00318 }
00319 }
00320 };
00321
00323 class Create {
00324 public:
00326 Create(void) {
00327 for (int i=1; i<=6; i++) {
00328 (void) new Circuit(i,0,i-1,0,Gecode::IPL_VAL);
00329 (void) new Circuit(i,0,i-1,0,Gecode::IPL_DOM);
00330 (void) new Circuit(i,0,i-1,5,Gecode::IPL_VAL);
00331 (void) new Circuit(i,0,i-1,5,Gecode::IPL_DOM);
00332 }
00333 for (int i=1; i<=4; i++) {
00334 (void) new Path(i,0,i-1,0,Gecode::IPL_VAL);
00335 (void) new Path(i,0,i-1,0,Gecode::IPL_DOM);
00336 (void) new Path(i,0,i-1,5,Gecode::IPL_VAL);
00337 (void) new Path(i,0,i-1,5,Gecode::IPL_DOM);
00338 }
00339 (void) new CircuitCost(4,0,9,0,Gecode::IPL_VAL);
00340 (void) new CircuitCost(4,0,9,0,Gecode::IPL_DOM);
00341 (void) new CircuitFullCost(3,0,3,0,Gecode::IPL_VAL);
00342 (void) new CircuitFullCost(3,0,3,0,Gecode::IPL_DOM);
00343 (void) new CircuitCost(4,0,9,5,Gecode::IPL_VAL);
00344 (void) new CircuitCost(4,0,9,5,Gecode::IPL_DOM);
00345 (void) new CircuitFullCost(3,0,3,5,Gecode::IPL_VAL);
00346 (void) new CircuitFullCost(3,0,3,5,Gecode::IPL_DOM);
00347 (void) new PathCost(3,0,5,0,Gecode::IPL_VAL);
00348 (void) new PathCost(3,0,5,0,Gecode::IPL_DOM);
00349 (void) new PathCost(3,0,5,5,Gecode::IPL_VAL);
00350 (void) new PathCost(3,0,5,5,Gecode::IPL_DOM);
00351 }
00352 };
00353
00354 Create c;
00356
00357 }
00358 }}
00359
00360