source code
// The Computer Language Benchmarks Game
// http://benchmarksgame.alioth.debian.org/
// contributed by Ben St. John
// some ideas taken from Kevin Barnes' implementation
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <string>
#include <memory.h>
using namespace std;
#define getMask(iPos) (1 << iPos)
enum {X, Y, N_DIM};
enum {EVEN, ODD, N_PARITY};
typedef unsigned int TUInt32;
typedef unsigned long long TUInt64;
typedef signed char TInt8;
typedef TUInt32 BitVec;
static const int N_COL = 5;
static const int N_ROW = 10;
static const int N_CELL = N_COL * N_ROW;
static const int N_PIECE_TYPE = 10;
class Piece;
struct Solution
{
static const int NO_PIECE = -1;
void setCells(void);
bool lessThan(Solution & r);
string toString(void) const;
void fill(int val);
void spin(Solution & spun);
bool isEmpty(void) {return (m_nPiece == 0);}
void removeLastPiece(void) {m_nPiece--; m_synched = false;}
void addPiece(const BitVec & vec, int iPiece, int row) {
SPiece & p = m_pieces[m_nPiece++];
p.vec = vec;
p.iPiece = (short)iPiece;
p.row = (short)row;
}
Solution(int fillVal);
Solution() : m_synched(false), m_nPiece(0) {}
struct SPiece {
BitVec vec;
short iPiece;
short row;
SPiece() {}
SPiece(BitVec avec, TUInt32 apiece, TUInt32 arow) :
vec(avec), iPiece(short(apiece)), row(short(arow))
{}
};
SPiece m_pieces[N_PIECE_TYPE];
TUInt32 m_nPiece;
TInt8 m_cells[N_ROW][N_COL];
bool m_synched;
};
//------------------------------------
struct Board
{
static const BitVec L_EDGE_MASK =
(1LL << 0) | (1LL << 5) | (1LL << 10) | (1LL << 15) |
(1LL << 20) | (1LL << 25) | (1LL << 30);
static const BitVec R_EDGE_MASK = L_EDGE_MASK << 4;
static const BitVec TOP_ROW = (1 << N_COL) - 1;
static const BitVec ROW_0_MASK =
TOP_ROW | (TOP_ROW << 10) | (TOP_ROW << 20) | (TOP_ROW << 30);
static const BitVec ROW_1_MASK = ROW_0_MASK << 5;
static const BitVec BOARD_MASK = (1 << 30) - 1;
Board();
static TUInt32 getIndex(TUInt32 x, TUInt32 y) { return y * N_COL + x; }
static bool hasBadFirstRegion(BitVec & toFill, BitVec rNew);
static bool hasBadIslands(BitVec boardVec, int row);
static bool calcBadIslands(const BitVec boardVec, int row);
static bool hasBadIslandsSingle(const BitVec & boardVec, int row);
void genAllSolutions(BitVec boardVec, TUInt32 placedPieces, TUInt32 iNextFill);
void recordSolution(Solution & s);
Solution m_curSolution;
Solution m_minSolution;
Solution m_maxSolution;
TUInt32 m_nSolutionFound;
};
//------------------------------------
class Piece
{
public:
struct Instance {
TUInt64 m_allowed;
BitVec m_vec;
int m_offset;
int m_w;
int m_h;
};
static const int N_ELEM = 5;
static const int N_ORIENT = 12;
static const int ALL_PIECE_MASK = (1 << N_PIECE_TYPE) - 1;
static const TUInt32 SKIP_PIECE = 5; // it's magic!
typedef int TCoordList[N_ELEM][N_DIM];
static const BitVec BaseDefinitions[N_PIECE_TYPE];
static Piece s_basePiece[N_PIECE_TYPE][N_ORIENT];
static const Instance & getPiece(TUInt32 iPiece, TUInt32 iOrient, TUInt32 iParity);
static bool checkBaseDefinitions(void);
static BitVec toBitVector(const TCoordList & coords);
static void genOrientation(const BitVec & vec, TUInt32 iOrient, Piece & target);
static void setCoordList(const BitVec & vec, TCoordList & coords);
static void shiftUpLines(TCoordList & coords, int shift);
static void shiftToX0(TCoordList & coords, Instance & instance, int offsetRow);
void setAllowedPositions(TUInt32 isOdd);
static void genAllOrientations(void);
Instance m_instance[N_PARITY];
};
struct AllowedPieces {
signed char nPieces[N_PIECE_TYPE];
// DEVNOTE: could be done more efficiently (space-wise)
TUInt32 pieceVec[N_PIECE_TYPE][Piece::N_ORIENT];
};
AllowedPieces g_allowedPieces[N_ROW][N_COL] = {{0}};
// should be moved in Board, but I'm lazy
enum {CLOSED, OPEN, N_FIXED};
#define MAX_ISLAND_OFFSET 1024
struct IslandInfo {
TUInt32 hasBadIslands[N_FIXED][N_PARITY];
TUInt32 isKnown[N_FIXED][N_PARITY];
};
IslandInfo g_islandInfo[MAX_ISLAND_OFFSET] = {0};
int g_nIslandInfo = 0;
//------------------------------------
Solution::Solution(int fillVal) :
m_nPiece(0) {
fill(fillVal);
}
void Solution::fill(int val)
{
m_synched = false;
memset(&m_cells[0][0], val, N_CELL);
}
string Solution::toString(void) const
{
string result;
result.reserve(N_CELL * 2);
for (int y = 0; y < N_ROW; y++) {
for (int x = 0; x < N_COL; x++) {
int val = m_cells[y][x];
result += ((val == NO_PIECE) ? '.' : char('0' + val));
result += ' ';
}
result += '\n';
// indent every second line
if (y % 2 == 0)
result += " ";
}
return result; // copies result. Oh well
}
void Solution::setCells(void)
{
if (m_synched)
return;
fill(NO_PIECE);
// could be more efficient
for (TUInt32 iPiece = 0; iPiece < m_nPiece; iPiece++) {
const SPiece & p = m_pieces[iPiece];
BitVec vec = p.vec;
TInt8 pID = (TInt8)p.iPiece;
int rowOffset = p.row;
int nNewCells = 0;
for (int y = rowOffset; y < N_ROW; y++) {
for (int x = 0; x < N_COL; x++) {
if (vec & 1) {
m_cells[y][x] = pID;
nNewCells++;
}
vec >>= 1;
}
if (nNewCells == Piece::N_ELEM)
break;
}
}
m_synched = true;
}
bool Solution::lessThan(Solution & r)
{
if (m_pieces[0].iPiece != r.m_pieces[0].iPiece) {
return m_pieces[0].iPiece < r.m_pieces[0].iPiece;
}
setCells();
r.setCells();
int y;
for (y = 0; y < N_ROW; y++) {
for (int x = 0; x < N_COL; x++) {
int lval = m_cells[y][x];
int rval = r.m_cells[y][x];
if (lval != rval)
return (lval < rval);
}
}
return false; // solutions are equal
}
void Solution::spin(Solution & spun)
{
setCells();
// swap cells
for (int y = 0; y < N_ROW; y++) {
for (int x = 0; x < N_COL; x++) {
TInt8 flipped = m_cells[N_ROW - y - 1][N_COL - x - 1];
spun.m_cells[y][x] = flipped;
}
}
// swap first and last pieces (the rest aren't used)
spun.m_pieces[0].iPiece = m_pieces[N_PIECE_TYPE - 1].iPiece;
spun.m_synched = true;
}
//------------------------------------
Piece Piece::s_basePiece[N_PIECE_TYPE][N_ORIENT];
const BitVec Piece::BaseDefinitions[] = {
0x010f, 0x00cb, 0x1087, 0x0427, 0x0465,
0x00c7, 0x08423, 0x00a7, 0x0187, 0x008f
};
int floor(int top, int bot) {
int toZero = top / bot;
// negative numbers should be rounded down, not towards zero
if ((toZero * bot != top) && ((top < 0) != (bot <= 0)))
toZero--;
return toZero;
}
static const TUInt32 s_firstOne[32] = {
0, 0, 1, 0,
2, 0, 1, 0,
3, 0, 1, 0,
2, 0, 1, 0,
4, 0, 1, 0,
2, 0, 1, 0,
3, 0, 1, 0,
2, 0, 1, 0,
};
TUInt32 getFirstOne(const BitVec & v, TUInt32 startPos = 0) {
if (v == (BitVec)0)
return 0;
TUInt32 iPos = startPos;
BitVec mask = 0xff << startPos;
while ((mask & v) == 0) {
mask <<= 8;
iPos += 8;
}
TUInt32 result = TUInt32((mask & v) >> iPos);
TUInt32 resultLow = result & 0x0f;
if (resultLow != 0)
iPos += s_firstOne[resultLow];
else
iPos += 4 + s_firstOne[result >> 4];
return iPos;
}
TUInt32 countOnes(BitVec v) {
TUInt32 n = 0;
while (v) {
n++;
v = v & (v - 1);
}
return n;
}
void Piece::setCoordList(const BitVec & vec, TCoordList & coords) {
int iCoord = 0;
BitVec mask = 1;
for (int y = 0; y < N_ROW; y++) {
for (int x = 0; x < N_COL; x++) {
if (mask & vec) {
coords[iCoord][X] = x;
coords[iCoord][Y] = y;
iCoord++;
}
mask <<= 1;
}
}
}
BitVec Piece::toBitVector(const TCoordList & coords) {
int y, x;
BitVec result = 0;
for (int iCoord = 0; iCoord < N_ELEM; iCoord++) {
x = coords[iCoord][X];
y = coords[iCoord][Y];
int pos = Board::getIndex(x, y);
result |= (1 << pos);
}
return result;
}
void Piece::shiftUpLines(TCoordList & coords, int shift) {
// shifts are not so simple in the vertical direction
for (int iCoord = 0; iCoord < N_ELEM; iCoord++) {
int & rx = coords[iCoord][X];
int & ry = coords[iCoord][Y];
if (ry & shift & 0x1)
rx++;
ry -= shift;
}
}
void Piece::shiftToX0(TCoordList & coords, Piece::Instance & instance, int offsetRow)
{
// .. determine shift
int x, y;
int xMin = coords[0][X];
int xMax = xMin;
int iCoord;
for (iCoord = 1; iCoord < N_ELEM; iCoord++) {
x = coords[iCoord][X];
y = coords[iCoord][Y];
if (x < xMin)
xMin = x;
else if (x > xMax)
xMax = x;
}
// I'm dying for a 'foreach' here
int offset = N_ELEM;
for (iCoord = 0; iCoord < N_ELEM; iCoord++) {
int & rx = coords[iCoord][X];
int & ry = coords[iCoord][Y];
rx -= xMin;
// check offset -- leftmost cell on top line
if ((ry == offsetRow) && (rx < offset))
offset = rx;
}
instance.m_w = xMax - xMin;
instance.m_offset = offset;
instance.m_vec = toBitVector(coords);
}
void Piece::setAllowedPositions(TUInt32 isOdd)
{
Piece::Instance & p = m_instance[isOdd];
TUInt64 & allowed = p.m_allowed = 0;
TUInt64 posMask = 1LL << (isOdd * N_COL);
for (int y = isOdd; y < N_ROW - p.m_h; y+=2, posMask <<= N_COL) {
if (p.m_offset)
posMask <<= p.m_offset;
for (int xPos = 0; xPos < N_COL - p.m_offset; xPos++, posMask <<= 1){
// check if the new position is on the board
if (xPos >= N_COL - p.m_w)
continue;
// move it to the desired location
BitVec pieceVec = p.m_vec << xPos;
if (Board::hasBadIslandsSingle(pieceVec, y))
continue;
// position is allowed
allowed |= posMask;
}
}
}
void Piece::genOrientation(const BitVec & vec, TUInt32 iOrient, Piece & target)
{
// get (x,y) coordinates
TCoordList coords;
setCoordList(vec, coords);
int y, x;
int iCoord = 0;
int rot = iOrient % 6;
int flip = iOrient >= 6;
if (flip) {
for (iCoord = 0; iCoord < N_ELEM; iCoord++)
coords[iCoord][Y] = -coords[iCoord][Y];
}
// rotate (if necessary)
while (rot--) {
for (iCoord = 0; iCoord < N_ELEM; iCoord++) {
x = coords[iCoord][X];
y = coords[iCoord][Y];
// I just worked this out by hand. Took a while.
int xNew = floor((2 * x - 3 * y + 1), 4);
int yNew = floor((2 * x + y + 1), 2);
coords[iCoord][X] = xNew;
coords[iCoord][Y] = yNew;
}
}
// shift vertically
// .. determine shift
int yMin = coords[0][Y];
int yMax = yMin;
for (iCoord = 1; iCoord < N_ELEM; iCoord++) {
y = coords[iCoord][Y];
if (y < yMin)
yMin = y;
else if (y > yMax)
yMax = y;
}
TUInt32 h = yMax - yMin;
Instance & even = target.m_instance[EVEN];
Instance & odd = target.m_instance[ODD];
even.m_h = h;
odd.m_h = h;
shiftUpLines(coords, yMin);
shiftToX0(coords, even, 0);
target.setAllowedPositions(EVEN);
even.m_vec >>= even.m_offset;
// shift down one line
shiftUpLines(coords, -1);
shiftToX0(coords, odd, 1);
// shift the bitmask back one line
odd.m_vec >>= N_COL;
target.setAllowedPositions(ODD);
odd.m_vec >>= odd.m_offset;
}
void Piece::genAllOrientations(void) {
for (int iPiece = 0; iPiece < N_PIECE_TYPE; iPiece++) {
const BitVec & refPiece = BaseDefinitions[iPiece];
for (int iOrient = 0; iOrient < N_ORIENT; iOrient++) {
Piece & p = s_basePiece[iPiece][iOrient];
genOrientation(refPiece, iOrient, p);
if ((iPiece == SKIP_PIECE) && ((iOrient / 3) & 1))
p.m_instance[0].m_allowed = p.m_instance[1].m_allowed = 0;
}
}
for (int iPiece = 0; iPiece < N_PIECE_TYPE; iPiece++) {
for (int iOrient = 0; iOrient < N_ORIENT; iOrient++) {
TUInt64 mask = 1;
for (int iRow = 0; iRow < N_ROW; iRow++) {
const Piece::Instance & p = getPiece(iPiece, iOrient, (iRow & 1));
for (int iCol = 0; iCol < N_COL; iCol++) {
AllowedPieces & allowed = g_allowedPieces[iRow][iCol];
if (p.m_allowed & mask) {
signed char & nPiece = allowed.nPieces[iPiece];
allowed.pieceVec[iPiece][nPiece] = p.m_vec << iCol;
nPiece++;
}
mask <<= 1;
}
}
}
}
}
const Piece::Instance & Piece::getPiece(TUInt32 iPiece, TUInt32 iOrient, TUInt32 iParity) {
return s_basePiece[iPiece][iOrient].m_instance[iParity];
}
// ------------------------------------
Board::Board() :
m_curSolution(Solution::NO_PIECE), m_minSolution(N_PIECE_TYPE),
m_maxSolution(Solution::NO_PIECE), m_nSolutionFound(0)
{
}
bool Board::hasBadFirstRegion(BitVec & toFill, BitVec rNew)
{
// grow empty region, until it doesn't change any more
BitVec region;
do {
region = rNew;
// grow right/left
rNew |= (region & ~L_EDGE_MASK) >> 1;
rNew |= (region & ~R_EDGE_MASK) << 1;
// simple grow up/down
rNew |= (region >> N_COL);
rNew |= (region << N_COL);
// tricky growth
BitVec evenRegion = region & (ROW_0_MASK & ~L_EDGE_MASK);
rNew |= evenRegion >> (N_COL + 1);
rNew |= evenRegion << (N_COL - 1);
BitVec oddRegion = region & (ROW_1_MASK & ~R_EDGE_MASK);
rNew |= oddRegion >> (N_COL - 1);
rNew |= oddRegion << (N_COL + 1);
// clamp against existing pieces
rNew &= toFill;
}
while ((rNew != toFill) && (rNew != region));
// subtract empty region from board
toFill ^= rNew;
TUInt32 nEmptyCells = countOnes(toFill);
if (nEmptyCells % Piece::N_ELEM != 0)
return true;
return false;
}
bool Board::hasBadIslands(BitVec boardVec, int row)
{
// skip over any filled rows
while ((boardVec & TOP_ROW) == TOP_ROW) {
boardVec >>= N_COL;
row++;
}
if (boardVec == 0)
return false;
if (boardVec & (TOP_ROW << N_COL * 3))
return calcBadIslands(boardVec, row);
int isOdd = row & 1;
TUInt32 iInfo = boardVec & ((1 << 2 * N_COL) - 1);
TUInt32 lastRow = (boardVec >> (2 * N_COL)) & TOP_ROW;
int isClosed = row > 6;
IslandInfo & islandInfo = g_islandInfo[iInfo];
TUInt32 mask = getMask(lastRow);
TUInt32 & isKnownVector = islandInfo.isKnown[isOdd][isClosed];
TUInt32 & badIsleVector = islandInfo.hasBadIslands[isOdd][isClosed];
if (isKnownVector & mask)
return ((badIsleVector & mask) != 0);
isKnownVector |= mask;
// calc island info
bool hasBad = calcBadIslands(boardVec, row);
// set it
if (hasBad)
badIsleVector |= mask;
return hasBad;
}
bool Board::calcBadIslands(const BitVec boardVec, int row)
{
BitVec toFill = ~boardVec;
if (row & 1) {
row--;
toFill <<= N_COL;
}
BitVec boardMask = BOARD_MASK; // all but the first two bits
if (row > 4) {
int boardMaskShift = (row - 4) * N_COL;
boardMask >>= boardMaskShift;
}
toFill &= boardMask;
// a little pre-work to speed things up
BitVec bottom = (TOP_ROW << (5 * N_COL));
bool filled = ((bottom & toFill) == bottom);
while ((bottom & toFill) == bottom) {
toFill ^= bottom;
bottom >>= N_COL;
}
BitVec startRegion;
int iPos;
if (filled || (row < 4)) {
startRegion = bottom & toFill;
} else {
iPos = getFirstOne(toFill);
startRegion = 1 << iPos;
// startRegion |= ((startRegion & ~R_EDGE_MASK) << 1) & toFill;
startRegion |= (startRegion << N_COL) & toFill;
}
while (toFill) {
if (hasBadFirstRegion(toFill, startRegion))
return true;
iPos = getFirstOne(toFill);
startRegion = 1 << iPos;
}
return false;
}
bool Board::hasBadIslandsSingle(const BitVec & boardVec, int row)
{
BitVec toFill = ~boardVec;
bool isOdd = (row & 1);
if (isOdd) {
row--;
toFill <<= N_COL; // shift to even aligned
toFill |= TOP_ROW;
}
BitVec startRegion = TOP_ROW;
BitVec lastRow = TOP_ROW << (5 * N_COL);
BitVec boardMask = BOARD_MASK; // all but the first two bits
if (row >= 4) {
int boardMaskShift = (row - 4) * N_COL;
boardMask >>= boardMaskShift;
}
else if ( isOdd || (row == 0) /* || (boardVec & lastRow) */) {
startRegion = lastRow;
}
toFill &= boardMask;
startRegion &= toFill;
while (toFill) {
if (hasBadFirstRegion(toFill, startRegion))
return true;
int iPos = getFirstOne(toFill);
startRegion = 1 << iPos;
}
return false;
}
// recursive vs iterative?
void Board::genAllSolutions(BitVec boardVec, TUInt32 placedPieces, TUInt32 row)
{
while ((boardVec & TOP_ROW) == TOP_ROW) {
boardVec >>= N_COL;
row++;
}
TUInt32 iNextFill = s_firstOne[~boardVec & TOP_ROW];
int pieceMask = 1;
for (int iPiece = 0; iPiece < N_PIECE_TYPE; iPiece++, pieceMask <<= 1)
{
// skip if we've already used this piece
if (pieceMask & placedPieces)
continue;
const AllowedPieces & allowed = g_allowedPieces[row][iNextFill];
for (int iOrient = 0; iOrient < allowed.nPieces[iPiece]; iOrient++)
{
BitVec pieceVec = allowed.pieceVec[iPiece][iOrient];
// check if piece conflicts with other pieces
if (pieceVec & boardVec)
continue;
// add the piece to the board
boardVec |= pieceVec;
if (hasBadIslands(boardVec, row)) {
// remove the piece from the board vector
boardVec ^= pieceVec;
continue;
}
// mark piece as placed
placedPieces |= pieceMask;
m_curSolution.addPiece(pieceVec, iPiece, row);
// recur if not done
if (placedPieces != Piece::ALL_PIECE_MASK)
genAllSolutions(boardVec, placedPieces, row);
else
recordSolution(m_curSolution);
// remove the piece before continuing with a new piece
boardVec ^= pieceVec;
m_curSolution.removeLastPiece();
}
placedPieces &= ~pieceMask;
}
}
void Board::recordSolution(Solution & s)
{
m_nSolutionFound += 2; // we add the solution and its rotation
if (m_minSolution.isEmpty()) {
m_minSolution = m_maxSolution = s;
return;
}
if (s.lessThan(m_minSolution))
m_minSolution = s;
else if (m_maxSolution.lessThan(s))
m_maxSolution = s;
Solution spun;
s.spin(spun);
if (spun.lessThan(m_minSolution))
m_minSolution = spun;
else if (m_maxSolution.lessThan(spun))
m_maxSolution = spun;
}
int main(int argc, char *[])
{
const int N_SOLUTION = 2098;
if (argc > 2)
return 1; // spec says this is an error
Board board;
Piece::genAllOrientations();
board.genAllSolutions(0, 0, 0);
int nFound = board.m_nSolutionFound;
cout << nFound << " solutions found\n\n";
cout << board.m_minSolution.toString() << '\n';
cout << board.m_maxSolution.toString() << endl;
if (nFound != N_SOLUTION)
return 1;
return 0;
}