/* Top This, Java version by Andy Harrington
Store grid (< 64 locations) as a bit field,
with [0][0] location corresponding to the
most significant bit used,
allowing shifting, checking for intersection,
adding, and testing order all as single
binary operations with long operands.
.
Recursively add shapes, disjoint from what is before.
After all in the first group added,
invert the grid, and the remaining group, following
the same rules as the first three, being disjoint from
what is set so far.
After the first group of shapes is put together,
the potential final accepted shape is known, and
the result from the first group can be compared to
the best so far, to see if it is worth continuing.
*/
import java.util.*;
import java.io.*;
public class top
{
static int L = 6, // output is LxL L < 8
GROUP_MAX = 3,
groupSize; //number of pieces in a group
// pAll[index in all 7 pieces][rotation] = L x L bitfield
static long[][] pAll = new long[7][4];
static int[] pieceIndex = new int[GROUP_MAX*2]; // pieces to use
static long best, B = 1L << (L*L-1); // bit for [r][c] = [0][0]
static long shift(long a, int r, int c) {
return a >> (L*r + c);
}
static boolean get(long a, int r, int c) {// get bit [r][c]
return (a & shift(B, r, c)) > 0;
}
static long set(long a, int r, int c) {// set bit [r][c]
return a | shift(B, r, c);
}
//assumes a shifted to upper left; return rotated, shifted up, left
static long rot90Shift(long a) {
long b=0;
int rMax = 0;
for (int r = 0; r < L; r++)
for (int c = 0; c < L; c++)
if (get(a, r, c))
rMax = r;
for (int r = 0; r <= rMax; r++)
for (int c = 0; c < L; c++)
if (get(a, r, c))
b = set(b, c, rMax-r);
return b;
}
static void print(long a) {
for (int r = 0; r < L; r++) {
for (int c = 0; c < L; c++)
System.out.print(get(a, r, c) ? '#' : '.');
System.out.println();
}
}
static void findSol(long a, int next, long shape){
if (next == 2*groupSize) {
if (shape > best)
best = shape;
return;
}
if (next == groupSize) {
if (a <= best)
return; // save lots of time to test if best here!
shape = a;
a = (B << 1) - 1 - a; //invert all bits
}
int pNum = pieceIndex[next];
int rows = 2, cols = 3;
if (pNum == 0) {
rows = 1;
cols = 4;
}
for (int rot = 0; rot < 4; rot++) {
for (int dr = 0; dr <= L-rows; dr++)
for (int dc = 0; dc <= L-cols; dc++) {
long shifted = shift(pAll[pNum][rot], dr, dc);
if ((a & shifted)== 0) // if disjoint
findSol(a | shifted, next+1, shape); //solve wih union
}
int temp = rows;
rows = cols;
cols = temp;
}
}
public static void main(String[] args) throws Exception {
String file = (args.length > 0) ? args[0] : "top.in";
Scanner in = new Scanner(new File(file));
String[][] ps = {{"####"}, //quick coding - next convert to array
{"###",
"#"},
{"###",
".#"},
{"###",
"..#"},
{"##",
".##"},
{"##",
"##"},
{".##",
"##"}};
for (int i=0; i < ps.length; i++) { // set up all 4x4 boolean arrays
for (int r = 0; r < ps[i].length; r++) //translate from String representation
for (int c = 0; c < ps[i][r].length(); c++)
if (ps[i][r].charAt(c) == '#')
pAll[i][0] = set(pAll[i][0], r, c);
for (int rot=0; rot<3; rot++) // record rotations, shift up left
pAll[i][rot+1] = rot90Shift(pAll[i][rot]);
}
int dataSets = in.nextInt();
for (int ds = 1; ds <= dataSets; ds++) {
System.out.println(ds);
groupSize = 3; // hardwired for this problem
for (int i=0; i<2; i++) {
String pieces = in.next();
for (int j=0; j < groupSize; j++)
pieceIndex[i*groupSize + j] = pieces.charAt(j) - 'A';
}
best = 0;
findSol(0, 0, 0);
if (best == 0) // array never replaced
System.out.println("No solution");
else
print(best);
}
}
}
|