001: /***************************************************************************
002:                           prepare.cpp  -  description
003:                              -------------------
004:     begin                : Fri Mar 28 2003
005:     copyright            : (C) 2003 by Dominik Raddatz
006:     email                : dom@wtal.de
007:  ***************************************************************************/
008: 
009: #include "prepare.h"
010: #include <stdio.h>
011: 
012: unsigned long long turnedPieceArray[24];
013: int boundingBox[24][3];
014: int numberOfTurns;
015: 
016: void prepare()
017: {
018:   int i;
019:   initializePC();
020:   for(i=0; i<12; ++i)
021:   {
022:     int bb[3]={BoundingBox[i][0], BoundingBox[i][1], BoundingBox[i][2]};
023:     createTurns(pieceArray[i], bb);
024:     registerPositions(i);
025:   }
026:   for(i=0; i<60; ++i)
027:   {
028:     registerMasks(i);
029:   }
030: }
031: 
032: void registerMasks(const int index)
033: {
034:   int x, y, z;
035:   const long long indexMask=1ull<<index;
036:   long long andMask=indexMask;
037:   long long equalsMask=0;
038:   x=index%3;
039:   y=(index/3)%4;
040:   z=(index/12)%5;
041:   if(x>0)equalsMask|=indexMask>>1;
042:   if(x<2)equalsMask|=indexMask<<1;
043:   if(y>0)equalsMask|=indexMask>>3;
044:   if(y<3)equalsMask|=indexMask<<3;
045:   if(z>0)equalsMask|=indexMask>>12;
046:   if(z<4)equalsMask|=indexMask<<12;
047:   andMask|=equalsMask;
048:   insert(indexMask, andMask, equalsMask);
049: }
050: 
051: void registerPositions(int index)
052: {
053:   bool box[3][4][5], temp[4][4][4];
054:   int posCount=0;
055:   if(index!=10)       // hack for piece 11 will be done here, peace 10 later
056:   {
057:     for(int i=0; i<numberOfTurns; ++i)
058:     {
059:       convert(&turnedPieceArray[i], temp);
060:       for(int x=0; x<=3-boundingBox[i][0]; ++x)
061:       {
062:         for(int y=0; y<=4-boundingBox[i][1]; ++y)
063:         {
064:           for(int z=0; z<=(index!=11? 5: 3)-boundingBox[i][2]; ++z)  // Hack: do not use all z Positions
065:           {
066:             for(int a=0; a<3; ++a)
067:             {
068:               for(int b=0; b<4; ++b)
069:               {
070:                 for(int c=0; c<5; ++c)
071:                 {
072:                   box[a][b][c]=0;
073:                 }
074:               }
075:             }
076:             for(int a=0; a<boundingBox[i][0]; ++a)
077:             {
078:               for(int b=0; b<boundingBox[i][1]; ++b)
079:               {
080:                 for(int c=0; c<boundingBox[i][2]; ++c)
081:                 {
082:                   box[x+a][y+b][z+c]=temp[a][b][c];
083:                 }
084:               }
085:             }
086:             ++posCount;
087:             insert(box, index);
088:           }
089:         }
090:       }
091:     }
092:   }
093:   else   // hack for asymmetric 3x1x2 piece
094:   {
095:     for(int i=0; i<numberOfTurns; ++i)
096:     {
097:       if(boundingBox[i][1]!=2)
098:       {
099:         convert(&turnedPieceArray[i], temp);
100:         for(int x=0; x<=3-boundingBox[i][0]; ++x)
101:         {
102:           for(int y=0; y<=(boundingBox[i][1]==1? 1: 0); ++y)  // Depth==1=>2 layers
103:           {
104:             for(int z=0; z<=5-boundingBox[i][2]; ++z)
105:             {
106:               for(int a=0; a<3; ++a)
107:               {
108:                 for(int b=0; b<4; ++b)
109:                 {
110:                   for(int c=0; c<5; ++c)
111:                   {
112:                     box[a][b][c]=0;
113:                   }
114:                 }
115:               }
116:               for(int a=0; a<boundingBox[i][0]; ++a)
117:               {
118:                 for(int b=0; b<boundingBox[i][1]; ++b)
119:                 {
120:                   for(int c=0; c<boundingBox[i][2]; ++c)
121:                   {
122:                     box[x+a][y+b][z+c]=temp[a][b][c];
123:                   }
124:                 }
125:               }
126:               ++posCount;
127:               insert(box, index);
128:             }
129:           }
130:         }
131:       }
132:       else  // Problematic cases where boundingBox[i][1]==2
133:       {
134:         convert(&turnedPieceArray[i], temp);
135:         int y=0;
136:         for(int x=0; x<=3-boundingBox[i][0]; ++x)
137:         {
138:           for(int z=0; z<=5-boundingBox[i][2]; ++z)
139:           {
140:             for(int a=0; a<3; ++a)
141:             {
142:               for(int b=0; b<4; ++b)
143:               {
144:                 for(int c=0; c<5; ++c)
145:                 {
146:                   box[a][b][c]=0;
147:                 }
148:               }
149:             }
150:             for(int a=0; a<boundingBox[i][0]; ++a)
151:             {
152:               for(int b=0; b<boundingBox[i][1]; ++b)
153:               {
154:                 for(int c=0; c<boundingBox[i][2]; ++c)
155:                 {
156:                   box[x+a][y+b][z+c]=temp[a][b][c];
157:                 }
158:               }
159:             }
160:             ++posCount;
161:             insert(box, index);
162:           }
163:         }
164:         if(boundingBox[i][0]==1)  // First half of problematic cases
165:         {
166:           if(temp[0][1][0]==0        // Now the real hacks: the pieces in the middle must not have all orientations
167:            ||temp[0][1][2]==0)
168:           {
169:             y=1;
170:             for(int x=0; x<=2; ++x)
171:             {
172:               for(int z=0; z<=2; ++z)
173:               {
174:                 for(int a=0; a<3; ++a)
175:                 {
176:                   for(int b=0; b<4; ++b)
177:                   {
178:                     for(int c=0; c<5; ++c)
179:                     {
180:                       box[a][b][c]=0;
181:                     }
182:                   }
183:                 }
184:                 for(int a=0; a<boundingBox[i][0]; ++a)
185:                 {
186:                   for(int b=0; b<boundingBox[i][1]; ++b)
187:                   {
188:                     for(int c=0; c<boundingBox[i][2]; ++c)
189:                     {
190:                       box[x+a][y+b][z+c]=temp[a][b][c];
191:                     }
192:                   }
193:                 }
194:                 ++posCount;
195:                 insert(box, index);
196:               }
197:             }
198:           }
199:         }
200:         else //boundingBox[i][0]==3 means second half of problematic cases
201:         {
202:           if(temp[0][1][0]==0        // Now the 2nd real hack: the pieces in the middle must not have all orientations
203:            ||temp[2][1][0]==0)
204:           {
205:             int x=0;
206:             y=1;
207:             for(int z=0; z<5; ++z)
208:             {
209:               for(int a=0; a<3; ++a)
210:               {
211:                 for(int b=0; b<4; ++b)
212:                 {
213:                   for(int c=0; c<5; ++c)
214:                   {
215:                     box[a][b][c]=0;
216:                   }
217:                 }
218:               }
219:               for(int a=0; a<boundingBox[i][0]; ++a)
220:               {
221:                 for(int b=0; b<boundingBox[i][1]; ++b)
222:                 {
223:                   for(int c=0; c<boundingBox[i][2]; ++c)
224:                   {
225:                     box[x+a][y+b][z+c]=temp[a][b][c];
226:                   }
227:                 }
228:               }
229:               ++posCount;
230:               insert(box, index);
231:             }
232:           }
233:         }
234:       }
235:     }
236:   }
237:   printf("Positions: %d\n", posCount);
238: }
239: 
240: void createTurns(const bool piece[4][4][4], int bb[3])
241: {
242:   numberOfTurns=0;
243:   bool dub;
244:   unsigned long long currentTurn;
245:   convert(piece, &currentTurn);
246:   for(int i=0; i<3; ++i)
247:   {
248:     for(int j=0; j<4; ++j)
249:     {
250:       turnX(&currentTurn, bb);
251:       dub=false;
252:       int k=0;
253:       while((dub==false)&&(k<numberOfTurns))
254:       {
255:         dub=turnedPieceArray[k]==currentTurn;
256:         ++k;
257:       }
258:       if(dub==false)fillNextPlace(&currentTurn, bb);
259:     }
260:     turnY(&currentTurn, bb);
261:     for(int j=0; j<4; ++j)
262:     {
263:       turnX(&currentTurn, bb);
264:       dub=false;
265:       int k=0;
266:       while((dub==false)&&(k<numberOfTurns))
267:       {
268:         dub=turnedPieceArray[k]==currentTurn;
269:         ++k;
270:       }
271:       if(dub==false)fillNextPlace(&currentTurn, bb);
272:     }
273:     turnZ(&currentTurn, bb);  
274:   }  
275:   printf("Number of Turns:%d\n", numberOfTurns);
276: }
277: 
278: void fillNextPlace(unsigned long long *currentTurn, int bb[3])
279: {
280:   turnedPieceArray[numberOfTurns]=(*currentTurn);
281:   boundingBox[numberOfTurns][0]=bb[0];
282:   boundingBox[numberOfTurns][1]=bb[1];
283:   boundingBox[numberOfTurns][2]=bb[2];
284:   ++numberOfTurns;
285: }
286: 
287: void turnX(unsigned long long *currentTurn, int bb[3])
288: {
289:   bool temp1[4][4][4], temp2[4][4][4];
290:   convert(currentTurn, temp1);
291:   turnX(temp1, temp2, bb);
292:   convert(temp2, currentTurn);
293:   normalize(currentTurn);
294: }
295: 
296: void turnY(unsigned long long *currentTurn, int bb[3])
297: {
298:   bool temp1[4][4][4], temp2[4][4][4];
299:   convert(currentTurn, temp1);
300:   turnY(temp1, temp2, bb);
301:   convert(temp2, currentTurn);
302:   normalize(currentTurn);
303: }
304: 
305: void turnZ(unsigned long long *currentTurn, int bb[3])
306: {
307:   bool temp1[4][4][4], temp2[4][4][4];
308:   convert(currentTurn, temp1);
309:   turnZ(temp1, temp2, bb);
310:   convert(temp2, currentTurn);
311:   normalize(currentTurn);
312: }
313: 
314: void convert(unsigned long long *source, bool target[4][4][4])
315: {
316:   for(int i=0; i<64; ++i)
317:   {
318:     target[i>>4][(i>>2)%4][i%4]=(*source)&(1ull<<i);
319:   }
320: }
321: 
322: void convert(const bool source[4][4][4], unsigned long long *target)
323: {
324:   unsigned long long bitPos=1;
325:   *target=0ull;
326:   for(int x=0; x<4; ++x)
327:   {
328:     for(int y=0; y<4; ++y)
329:     {
330:       for(int z=0; z<4; ++z)
331:       {
332:         if(source[x][y][z]==1)
333:         {
334:           (*target)|=bitPos;
335:         }
336:         bitPos<<=1;
337:       }
338:     }
339:   }
340: }
341: 
342: void turnX(const bool source[4][4][4], bool target[4][4][4], int bb[3])
343: {
344:   for(int x=0; x<4; ++x)
345:   {
346:     for(int y=0; y<4; ++y)
347:     {
348:       for(int z=0; z<4; ++z)
349:       {
350:         target[x][3-z][y] = source[x][y][z];
351:       }
352:     }
353:   }
354:   int temp=bb[1];
355:   bb[1]=bb[2];
356:   bb[2]=temp;
357: }
358: 
359: void turnY(const bool source[4][4][4], bool target[4][4][4], int bb[3])
360: {
361:   for(int x=0; x<4; ++x)
362:   {
363:     for(int y=0; y<4; ++y)
364:     {
365:       for(int z=0; z<4; ++z)
366:       {
367:         target[3-z][y][x] = source[x][y][z];
368:       }
369:     }
370:   }
371:   int temp=bb[0];
372:   bb[0]=bb[2];
373:   bb[2]=temp;
374: }
375: 
376: void turnZ(const bool source[4][4][4], bool target[4][4][4], int bb[3])
377: {
378:   for(int x=0; x<4; ++x)
379:   {
380:     for(int y=0; y<4; ++y)
381:     {
382:       for(int z=0; z<4; ++z)
383:       {
384:         target[y][3-x][z] = source[x][y][z];
385:       }
386:     }
387:   }
388:   int temp=bb[0];
389:   bb[0]=bb[1];
390:   bb[1]=temp;
391: }
392: 
393: void normalize(unsigned long long *rawTurn)
394: {
395:   while((0x000000000000ffffull&(*rawTurn))==0)(*rawTurn)>>=16;
396:   while((0x1111111111111111ull&(*rawTurn))==0)(*rawTurn)>>=1;
397:   while((0x000f000f000f000full&(*rawTurn))==0)(*rawTurn)>>=4;
398: }