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::IntPropLevel ipl)
00059 : Test("Circuit::" + str(ipl) + "::" + str(n) + "::" + str(off),
00060 n,min,max,false,ipl), offset(off) {
00061 contest = CTL_NONE;
00062 testfix = false;
00063 }
00065 virtual bool solution(const Assignment& x) const {
00066 for (int i=x.size(); i--; )
00067 if ((x[i] < 0) || (x[i] > x.size()-1))
00068 return false;
00069 int reachable = 0;
00070 {
00071 int j=0;
00072 for (int i=x.size(); i--; ) {
00073 j=x[j]; reachable |= (1 << j);
00074 }
00075 }
00076 for (int i=x.size(); i--; )
00077 if (!(reachable & (1 << i)))
00078 return false;
00079 return true;
00080 }
00082 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00083 if (offset > 0) {
00084 Gecode::IntVarArgs xx(x.size());
00085 for (int i=x.size(); i--;)
00086 xx[i] = Gecode::expr(home, x[i]+offset);
00087 Gecode::circuit(home, offset, xx, ipl);
00088 } else {
00089 Gecode::circuit(home, x, ipl);
00090 }
00091 }
00092 };
00093
00095 class Path : public Test {
00096 private:
00098 int offset;
00099 public:
00101 Path(int n, int min, int max, int off, Gecode::IntPropLevel ipl)
00102 : Test("Path::" + str(ipl) + "::" + str(n) + "::" + str(off),
00103 n+2,min,max,false,ipl), offset(off) {
00104 contest = CTL_NONE;
00105 testfix = false;
00106 }
00108 virtual bool solution(const Assignment& x) const {
00109 int n = x.size() - 2;
00110 int s = x[n];
00111 int e = x[n+1];
00112 if ((s < 0) || (s > n) || (e < 0) || (e > n) || (x[e] != n))
00113 return false;
00114 for (int i=n; i--; )
00115 if ((i != e) && ((x[i] < 0) || (x[i] > n)))
00116 return false;
00117 int reachable = (1 << s);
00118 {
00119 int j=s;
00120 for (int i=n; i--; ) {
00121 j=x[j]; reachable |= (1 << j);
00122 }
00123 }
00124 for (int i=n; i--; )
00125 if (!(reachable & (1 << i)))
00126 return false;
00127 return true;
00128 }
00130 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00131 int n = x.size() - 2;
00132 Gecode::IntVarArgs xx(n);
00133 if (offset > 0) {
00134 for (int i=n; i--;)
00135 xx[i] = Gecode::expr(home, x[i]+offset);
00136 Gecode::path(home, offset, xx,
00137 Gecode::expr(home, x[n]+offset),
00138 Gecode::expr(home, x[n+1]+offset),ipl);
00139 } else {
00140 for (int i=n; i--;)
00141 xx[i] = x[i];
00142 Gecode::path(home, xx, x[n], x[n+1], ipl);
00143 }
00144 }
00145 };
00146
00148 class CircuitCost : public Test {
00149 private:
00151 int offset;
00152 public:
00154 CircuitCost(int n, int min, int max, int off, Gecode::IntPropLevel ipl)
00155 : Test("Circuit::Cost::"+str(ipl)+"::"+str(n)+"::"+str(off),
00156 n+1,min,max,false,ipl), offset(off) {
00157 contest = CTL_NONE;
00158 testfix = false;
00159 }
00161 virtual bool solution(const Assignment& x) const {
00162 int n=x.size()-1;
00163 for (int i=n; i--; )
00164 if ((x[i] < 0) || (x[i] > n-1))
00165 return false;
00166 int reachable = 0;
00167 {
00168 int j=0;
00169 for (int i=n; i--; ) {
00170 j=x[j]; reachable |= (1 << j);
00171 }
00172 }
00173 for (int i=n; i--; )
00174 if (!(reachable & (1 << i)))
00175 return false;
00176 int c=0;
00177 for (int i=n; i--; )
00178 c += x[i];
00179 return c == x[n];
00180 }
00182 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00183 using namespace Gecode;
00184 int n=x.size()-1;
00185 IntArgs c(n*n);
00186 for (int i=0; i<n; i++)
00187 for (int j=0; j<n; j++)
00188 c[i*n+j]=j;
00189 IntVarArgs y(n);
00190 if (offset > 0) {
00191 for (int i=n; i--;)
00192 y[i] = Gecode::expr(home, x[i]+offset);
00193 Gecode::circuit(home, c, offset, y, x[n], ipl);
00194 } else {
00195 for (int i=0; i<n; i++)
00196 y[i]=x[i];
00197 circuit(home, c, y, x[n], ipl);
00198 }
00199 }
00200 };
00201
00203 class PathCost : public Test {
00204 private:
00206 int offset;
00207 public:
00209 PathCost(int n, int min, int max, int off, Gecode::IntPropLevel ipl)
00210 : Test("Path::Cost::"+str(ipl)+"::"+str(n)+"::"+str(off),
00211 n+3,min,max,false,ipl), offset(off) {
00212 contest = CTL_NONE;
00213 testfix = false;
00214 }
00216 virtual bool solution(const Assignment& x) const {
00217 int n = x.size() - 3;
00218 int s = x[n];
00219 int e = x[n+1];
00220 int c = x[n+2] + n;
00221 if ((s < 0) || (s > n) || (e < 0) || (e > n) || (x[e] != n))
00222 return false;
00223 for (int i=n; i--; )
00224 if ((i != e) && ((x[i] < 0) || (x[i] > n)))
00225 return false;
00226 int reachable = (1 << s);
00227 {
00228 int j=s;
00229 for (int i=n; i--; ) {
00230 j=x[j]; reachable |= (1 << j);
00231 }
00232 }
00233 for (int i=n; i--; )
00234 if (!(reachable & (1 << i)))
00235 return false;
00236 for (int i=n; i--; )
00237 c -= x[i];
00238 return c == 0;
00239 }
00241 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00242 using namespace Gecode;
00243 int n=x.size()-3;
00244 IntArgs c(n*n);
00245 for (int i=0; i<n; i++)
00246 for (int j=0; j<n; j++)
00247 c[i*n+j]=j;
00248 IntVarArgs y(n);
00249 if (offset > 0) {
00250 for (int i=n; i--;)
00251 y[i] = Gecode::expr(home, x[i]+offset);
00252 path(home, c, offset, y,
00253 expr(home, x[n]+offset),
00254 expr(home, x[n+1]+offset),
00255 x[n+2], ipl);
00256 } else {
00257 for (int i=0; i<n; i++)
00258 y[i]=x[i];
00259 path(home, c, y, x[n], x[n+1], x[n+2], ipl);
00260 }
00261 }
00262 };
00263
00265 class CircuitFullCost : public Test {
00266 private:
00268 int offset;
00269 public:
00271 CircuitFullCost(int n, int min, int max, int off,
00272 Gecode::IntPropLevel ipl)
00273 : Test("Circuit::FullCost::" + str(ipl)+"::"+str(n)+"::"+str(off),
00274 2*n+1,min,max,false,ipl), offset(off) {
00275 contest = CTL_NONE;
00276 testfix = false;
00277 }
00279 virtual bool solution(const Assignment& x) const {
00280 int n=(x.size()-1) / 2;
00281 for (int i=n; i--; )
00282 if ((x[i] < 0) || (x[i] > n-1))
00283 return false;
00284 int reachable = 0;
00285 {
00286 int j=0;
00287 for (int i=n; i--; ) {
00288 j=x[j]; reachable |= (1 << j);
00289 }
00290 }
00291 for (int i=n; i--; )
00292 if (!(reachable & (1 << i)))
00293 return false;
00294 for (int i=n; i--; )
00295 if ((x[i]/2) != x[n+i])
00296 return false;
00297 int c=0;
00298 for (int i=n; i--; )
00299 c += x[n+i];
00300 return c == x[2*n];
00301 }
00303 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00304 using namespace Gecode;
00305 int n=(x.size()-1)/2;
00306 IntArgs c(n*n);
00307 for (int i=0; i<n; i++)
00308 for (int j=0; j<n; j++)
00309 c[i*n+j]=(j/2);
00310 IntVarArgs y(n), z(n);
00311 for (int i=0; i<n; i++) {
00312 z[i]=x[n+i];
00313 }
00314 if (offset > 0) {
00315 for (int i=n; i--;)
00316 y[i] = Gecode::expr(home, x[i]+offset);
00317 Gecode::circuit(home, c, offset, y, z, x[2*n], ipl);
00318 } else {
00319 for (int i=0; i<n; i++)
00320 y[i]=x[i];
00321 circuit(home, c, y, z, x[2*n], ipl);
00322 }
00323 }
00324 };
00325
00327 class Create {
00328 public:
00330 Create(void) {
00331 for (int i=1; i<=6; i++) {
00332 (void) new Circuit(i,0,i-1,0,Gecode::IPL_VAL);
00333 (void) new Circuit(i,0,i-1,0,Gecode::IPL_DOM);
00334 (void) new Circuit(i,0,i-1,5,Gecode::IPL_VAL);
00335 (void) new Circuit(i,0,i-1,5,Gecode::IPL_DOM);
00336 }
00337 for (int i=1; i<=4; i++) {
00338 (void) new Path(i,0,i-1,0,Gecode::IPL_VAL);
00339 (void) new Path(i,0,i-1,0,Gecode::IPL_DOM);
00340 (void) new Path(i,0,i-1,5,Gecode::IPL_VAL);
00341 (void) new Path(i,0,i-1,5,Gecode::IPL_DOM);
00342 }
00343 (void) new CircuitCost(4,0,9,0,Gecode::IPL_VAL);
00344 (void) new CircuitCost(4,0,9,0,Gecode::IPL_DOM);
00345 (void) new CircuitFullCost(3,0,3,0,Gecode::IPL_VAL);
00346 (void) new CircuitFullCost(3,0,3,0,Gecode::IPL_DOM);
00347 (void) new CircuitCost(4,0,9,5,Gecode::IPL_VAL);
00348 (void) new CircuitCost(4,0,9,5,Gecode::IPL_DOM);
00349 (void) new CircuitFullCost(3,0,3,5,Gecode::IPL_VAL);
00350 (void) new CircuitFullCost(3,0,3,5,Gecode::IPL_DOM);
00351 (void) new PathCost(3,0,5,0,Gecode::IPL_VAL);
00352 (void) new PathCost(3,0,5,0,Gecode::IPL_DOM);
00353 (void) new PathCost(3,0,5,5,Gecode::IPL_VAL);
00354 (void) new PathCost(3,0,5,5,Gecode::IPL_DOM);
00355 }
00356 };
00357
00358 Create c;
00360
00361 }
00362 }}
00363
00364