001:
002:
003:
004:
005:
006: #include <iostream>
007: #include <fstream>
008: #include <vector>
009: #include "cbitpart.h"
010:
011: using namespace std;
012:
013: const int N = 12;
014: const int maxR = 24;
015: const int maxP = 576;
016: const int PAT = 15;
017:
018: CBitPart Parts[N];
019: vector<CBitPart> BPartsR[N];
020: vector<CBitPart> BPartsP[N];
021:
022: vector<CBitPart> BPartsS[BITS][PAT+1][N];
023: int **BV[60][PAT+1];
024: int **BV1[32][PAT+1];
025:
026: int *FourElim[60][PAT+1];
027: vector<CBitPart> TenFront, TenSym, FourElimV;
028:
029: int next[N+1];
030:
031: int bitworld0 = 0, bitworld1 = 0;
032:
033: int Permutations = 0;
034: int Solutions = 0, sol;
035:
036:
037: struct CDupe {
038: int bw0, bw1;
039: int dps;
040: CDupe *next;
041: };
042:
043: const int BigNumber = 3497867;
044: int MaxDepth = 4;
045: CDupe* Table[BigNumber];
046: int k[N];
047: CDupe* head;
048: int dupe_parts = 0;
049:
050:
051: void InitHashTable()
052: {
053: CDupe *z = new CDupe;
054: z->next = 0;
055:
056: for (int i = 0; i < BigNumber; ++i)
057: Table[i] = z;
058: }
059:
060: void DestructHashTable()
061: {
062: CDupe *t;
063:
064: for (int i = 0; i < BigNumber; ++i)
065: while (Table[i]->next) {
066: t = Table[i];
067: Table[i] = Table[i]->next;
068: delete t;
069: }
070: }
071:
072: inline bool isInVector(vector<CBitPart>& vec, CBitPart& bp)
073: {
074: for (int i = vec.size()-1; i >= 0; --i)
075: if (vec[i] == bp) return true;
076: return false;
077: }
078:
079: void RotatePart(vector<CBitPart>& vec, CBitPart bp)
080: {
081: vec.push_back(bp);
082:
083: for (int i = 0; i < vec.size(); ++i) {
084: if ( (bp = vec[i]).RotateLocalF90() )
085: if (!isInVector(vec, bp)) vec.push_back(bp);
086:
087: if ( (bp = vec[i]).RotateLocalT90() )
088: if (!isInVector(vec, bp)) vec.push_back(bp);
089:
090: if ( (bp = vec[i]).RotateLocalS90() )
091: if (!isInVector(vec, bp)) vec.push_back(bp);
092:
093: if ( (bp = vec[i]).RotateLocalF180() )
094: if (!isInVector(vec, bp)) vec.push_back(bp);
095:
096: if ( (bp = vec[i]).RotateLocalT180() )
097: if (!isInVector(vec, bp)) vec.push_back(bp);
098:
099: if ( (bp = vec[i]).RotateLocalS180() )
100: if (!isInVector(vec, bp)) vec.push_back(bp);
101: }
102: }
103:
104: void PermutePart(vector<CBitPart>& vec, CBitPart bp)
105: {
106: int max_x, max_y, max_z;
107: CBitPart bp2;
108:
109: bp.GetMaxima(max_x, max_y, max_z);
110:
111: for (int mz = 0; mz < (Z-max_z); ++mz)
112: for (int my = 0; my < (Y-max_y); ++my)
113: for (int mx = 0; mx < (X-max_x); ++mx)
114: vec.push_back( (bp2 = bp).Move(mx, my, mz) );
115:
116: }
117:
118: void HackPart(vector<CBitPart>& vec)
119: {
120: vector<CBitPart> BestParts;
121: CBitPart bp[4];
122: int best_i, i;
123:
124: while (!vec.empty()) {
125: bp[0] = bp[1] = bp[2] = bp[3] = vec[0];
126:
127: bp[1].RotateCubeF180();
128: bp[2].RotateCubeT180();
129: bp[3].RotateCubeS180();
130:
131: for (i = 1, best_i = 0; i < 4; ++i)
132: if (bp[i].NextSetBit(0) > bp[best_i].NextSetBit(0))
133: best_i = i;
134: else if (bp[i].NextSetBit(0) == bp[best_i].NextSetBit(0))
135: if (bp[i].Density() < bp[best_i].Density())
136: best_i = i;
137:
138: BestParts.push_back(bp[best_i]);
139:
140: for (i = vec.size()-1; i >= 0; --i)
141: if (vec[i]==bp[0] || vec[i]==bp[1] || vec[i]==bp[2] || vec[i]==bp[3])
142: vec.erase(vec.begin()+i);
143: }
144:
145: for (i = 0; i < BestParts.size(); ++i)
146: vec.push_back(BestParts[i]);
147: }
148:
149: void HackPartX()
150: {
151: vector<CBitPart>& vec = BPartsP[10];
152: CBitPart bp[4];
153: int best_i, i;
154:
155: while (!vec.empty()) {
156: bp[0] = bp[1] = bp[2] = bp[3] = vec[0];
157:
158: bp[1].RotateCubeT180();
159: bp[2].RotateCubeF180();
160: bp[3].RotateCubeS180();
161:
162: if (bp[1] != vec[0]) {
163: for (i = 1, best_i = 0; i < 4; ++i)
164: if (bp[i].NextSetBit(0) < bp[best_i].NextSetBit(0))
165: best_i = i;
166: else if (bp[i].NextSetBit(0) == bp[best_i].NextSetBit(0))
167: if (bp[i].Density() < bp[best_i].Density())
168: best_i = i;
169:
170: TenFront.push_back(bp[best_i]);
171: }
172: else {
173: TenSym.push_back(vec[0]);
174: if (bp[2] != vec[0]) TenSym.push_back(bp[2]);
175: if (bp[3] != vec[0] && bp[2] != bp[3]) TenSym.push_back(bp[3]);
176: }
177:
178: for (i = vec.size()-1; i >= 0; --i)
179: if (vec[i]==bp[0] || vec[i]==bp[1] || vec[i]==bp[2] || vec[i]==bp[3])
180: vec.erase(vec.begin()+i);
181: }
182:
183:
184:
185: }
186:
187: void ConstructArrays()
188: {
189: int first, pattern;
190:
191: for (int i = 0; i < N; ++i)
192: for (int j = 0; j < BPartsP[i].size(); ++j) {
193: first = BPartsP[i][j].NextSetBit(0);
194: pattern = (BPartsP[i][j].bits >> (first+1)) & PAT;
195:
196: for (int p = 0; p <= PAT; ++p)
197: if ( !(pattern & p) )
198: BPartsS[first][p][i].push_back(BPartsP[i][j]);
199: }
200:
201: for (int i = 0; i < BITS; ++i)
202: for (int j = 0; j <= PAT; ++j)
203: BV[i][j] = new int*[N];
204:
205: for (int i = 0; i < BITS; ++i)
206: for (int j = 0; j <= PAT; ++j)
207: for (int k = 0; k < N; ++k) {
208: BV[i][j][k] = new int[2*(BPartsS[i][j][k].size()+1)];
209:
210: for (int m = BPartsS[i][j][k].size()-1; m >= 0; --m) {
211: BV[i][j][k][2*m] = BPartsS[i][j][k][m].bits & (~(15 << 28));
212: BV[i][j][k][2*m+1] = BPartsS[i][j][k][m].bits >> 28;
213: }
214:
215: BV[i][j][k][2*BPartsS[i][j][k].size()] = 0;
216: BV[i][j][k][2*BPartsS[i][j][k].size()+1] = 0;
217:
218: if (i >= 28) BV1[i-28][j] = BV[i][j];
219: }
220:
221:
222:
223:
224: for (int i = 0; i < BITS; ++i)
225: for (int j = 0; j <= PAT; ++j)
226: BPartsS[i][j][4].clear();
227:
228: for (int j = 0; j < FourElimV.size(); ++j) {
229: first = FourElimV[j].NextSetBit(0);
230: pattern = (FourElimV[j].bits >> (first+1)) & PAT;
231:
232: for (int p = 0; p <= PAT; ++p)
233: if ( !(pattern & p) )
234: BPartsS[first][p][4].push_back(FourElimV[j]);
235: }
236:
237: for (int i = 0; i < BITS; ++i)
238: for (int j = 0; j <= PAT; ++j) {
239: FourElim[i][j] = new int[2*(BPartsS[i][j][4].size()+1)];
240:
241: for (int m = BPartsS[i][j][4].size()-1; m >= 0; --m) {
242: FourElim[i][j][2*m] = BPartsS[i][j][4][m].FirstHalf();
243: FourElim[i][j][2*m+1] = BPartsS[i][j][4][m].SecondHalf();
244: }
245:
246: FourElim[i][j][2*BPartsS[i][j][4].size()] = 0;
247: FourElim[i][j][2*BPartsS[i][j][4].size()+1] = 0;
248: }
249: }
250:
251:
252:
253:
254:
255:
256:
257:
258:
259:
260:
261:
262: void MakeItSoBV1()
263: {
264: if (next[12] == -1) {
265: ++sol;
266: return;
267: }
268:
269: int b;
270:
271: __asm__ ("bsfl %1,%0" : "=r" (b) : "r" (~bitworld1));
272:
273: int k;
274: int **p = BV1[b][(bitworld1 >> (b+1)) & PAT];
275:
276: for (int i = 12; next[i] >= 0; i = next[i]) {
277: k = next[i];
278: next[i] = next[next[i]];
279:
280: for (int *j = p[k]+1; *j; j += 2)
281: if ( !(bitworld1 & *j) ) {
282: bitworld1 |= *j;
283: MakeItSoBV1();
284: bitworld1 ^= *j;
285: }
286:
287: next[i] = k;
288: }
289: }
290:
291: void MakeItSo()
292: {
293: int b;
294:
295: __asm__ ("bsfl %1,%0" : "=r" (b) : "r" (~bitworld0));
296:
297: if (b == 28) {
298: MakeItSoBV1();
299: return;
300: }
301:
302: int k;
303: int **p = BV[b][(bitworld0 >> (b+1)) & PAT];
304:
305: for (int i = 12; next[i] >= 0; i = next[i]) {
306: k = next[i];
307: next[i] = next[next[i]];
308:
309: for (int *j = p[k]; *j; j += 2)
310: if ( !(bitworld0 & *j) && !(bitworld1 & *(j+1)) ) {
311: bitworld0 |= *j;
312: bitworld1 |= *(j+1);
313: MakeItSo();
314: bitworld0 ^= *j;
315: bitworld1 ^= *(j+1);
316: }
317:
318: next[i] = k;
319: }
320: }
321:
322: int MakeItSoHASH(int d)
323: {
324: if (d > MaxDepth) {
325: sol = 0;
326: MakeItSo();
327: return sol;
328: }
329:
330: int b;
331:
332: __asm__ ("bsfl %1,%0" : "=r" (b) : "r" (~bitworld0));
333:
334: int h = (((bitworld0 ^ dupe_parts) ^ bitworld1) & ~(1 << 31)) % BigNumber;
335:
336: for (CDupe *i = Table[h]; i->next; i = i->next)
337: if ( (i->bw0 == bitworld0) && (dupe_parts == (i->dps & 4095)) && (i->bw1 == bitworld1) )
338: return (i->dps >> 12);
339:
340: int solu = 0;
341: int **p = BV[b][(bitworld0 >> (b+1)) & PAT];
342:
343: for (int i = 12; next[i] >= 0; i = next[i]) {
344: k[d] = next[i];
345: dupe_parts |= (1 << k[d]);
346: next[i] = next[next[i]];
347:
348: for (int *j = p[k[d]]; *j; j += 2)
349: if ( !(bitworld0 & *j) && !(bitworld1 & *(j+1)) ) {
350: bitworld0 |= *j;
351: bitworld1 |= *(j+1);
352: solu += MakeItSoHASH(d+1);
353: bitworld0 ^= *j;
354: bitworld1 ^= *(j+1);
355: }
356:
357: next[i] = k[d];
358: dupe_parts ^= (1 << k[d]);
359: }
360:
361: CDupe *nd = new CDupe;
362: nd->dps = dupe_parts | (solu << 12);
363: nd->bw0 = bitworld0;
364: nd->bw1 = bitworld1;
365: nd->next = Table[h];
366: Table[h] = nd;
367:
368: return solu;
369: }
370:
371:
372:
373:
374:
375:
376:
377:
378:
379:
380:
381:
382: int main()
383: {
384: ifstream ifs("ct.parts.3.4.1");
385: cout << "Loading..." << endl;
386:
387: for (int i = 0; i < N; ++i)
388: Parts[i].FromStream(ifs);
389:
390: cout << "Orientating..." << endl;
391:
392: for (int i = 0; i < N; ++i) {
393: RotatePart(BPartsR[i], Parts[i]);
394: cout << "Orientations of Part " << i << ": " << BPartsR[i].size() << endl;
395: }
396:
397: cout << "\nPermuting..." << endl;
398:
399: for (int i = 0; i < N; ++i) {
400: for (int j = 0; j < BPartsR[i].size(); ++j)
401: PermutePart(BPartsP[i], BPartsR[i][j]);
402: cout << "Permutations of Part " << i << ": " << BPartsP[i].size() << endl;
403: }
404:
405: for (int i = 0; i < N; ++i) BPartsR[i].clear();
406:
407: HackPartX();
408:
409: cout << "Symmetric Part 10 List Size: " << TenSym.size() << endl;
410: cout << "Minimized Part 10 List Size: " << TenFront.size() << endl;
411:
412: for (int i = BPartsP[4].size()-1; i >= 0; --i)
413: FourElimV.push_back(BPartsP[4][i]);
414:
415: HackPart(FourElimV);
416:
417: cout << "Permutations of Hacked Part 4: " << FourElimV.size() << endl;
418:
419: ConstructArrays();
420:
421: cout << "Minimized: " << endl;
422: for (int i = TenFront.size()-1; i >= 0; --i) {
423: TenFront[i].Print(); cout << endl;
424: }
425:
426: cout << "\nSymmetrics: " << endl;
427: for (int i = TenSym.size()-1; i >= 0; --i) {
428: TenSym[i].Print(); cout << endl;
429: }
430:
431:
432: for (int i = N; i >= 0; --i) next[i] = i-1;
433: next[11] = 9;
434:
435: InitHashTable();
436:
437:
438: cout << "\nCalculating..." << endl;
439:
440: cout << "\nMinimized Part: " << endl;
441:
442: for (int i = TenFront.size()-1; i >= 0; --i) {
443: bitworld0 = TenFront[i].FirstHalf();
444: bitworld1 = TenFront[i].SecondHalf();
445:
446: int usol = MakeItSoHASH(0);
447:
448: cout << "Sol: " << usol << endl << endl;
449: Solutions += usol;
450: }
451:
452:
453: for (int i = 0; i < BITS; ++i)
454: for (int j = 0; j <= PAT; ++j) {
455: BV[i][j][4] = FourElim[i][j];
456: if (i >= 28) BV1[i-28][j][4] = FourElim[i][j];
457: }
458:
459: DestructHashTable();
460: MaxDepth = 3;
461:
462: cout << "\nSymmetric Part: " << endl;
463:
464: for (int i = TenSym.size()-1; i >= 0; --i) {
465: bitworld0 = TenSym[i].FirstHalf();
466: bitworld1 = TenSym[i].SecondHalf();
467:
468: int usol = MakeItSoHASH(0);
469:
470: cout << "Sol: " << usol << endl << endl;
471: Solutions += usol;
472: }
473:
474: cout << "\nSolutions: " << Solutions << endl;
475:
476: return 0;
477: }