*************************************
Example program outputs + source code
*************************************
Input map:
***y
*
*
x
maximum tiles = 2
One possible layout:
AAA*
B
B
B
Truth table with 2 variables:
xy [is max possible, with given squares removed]
00 1 //no squares removed (max always possible)
01 1
10 1
11 0
Input map:
***y
*
**x
maximum tiles = 2
One possible layout:
AAA*
*
BBB
Truth table with 2 variables:
xy [is max possible, with given squares removed]
00 1 //no squares removed (max always possible)
01 1
10 1
11 0
Input map:
x y
* *
* *
*****
*
***z
maximum tiles = 4
One possible layout:
A B
A B
A B
CCC**
*
DDD*
Truth table with 3 variables:
xyz [is max possible, with given squares removed]
000 1 //no squares removed (max always possible)
001 1
010 1
011 1
100 1
101 1
110 1
111 0
Input map:
*******
* *
* *
**** ***
* *
*** ****
* *
* *
* ******* *
* * * *
* * * *
*z*x* *****
* *
**** ****
* *
***
***
***
*
*
y
maximum tiles = 25
One possible layout:
AAABBBC
D C
D C
EEED FFF
* *
GGG HHHI
J I
J I
J KLLLMMM N
O K P N
O K P N
*OQQQ *PRRR
* *
SSST UVVV
T U
T*U
WWW
XXX
Y
Y
Y
Truth table with 3 variables:
xyz [is max possible, with given squares removed]
000 1 //no squares removed (max always possible)
001 0
010 0
011 0
100 0
101 0
110 0
111 0
Input map:
********** *******
* * * *
* *** *
*** *** ***
* *** *
**** * ****
* * *
* **** *
*** * ***
* *** *
**** * * ****
y * * * * x
* * * * * *
* **** *** **** *
*** *** ***
*************X*Y****************
maximum tiles = 46
One possible layout:
AAABBBCCCD EFFFGGG
H D E I
H D*E I
*HJ KKK LI*
J MMM L
NNNJ O LPPP
Q O R
Q SSSO R
*QT * UR*
T VVV U
WWWT X Y UZZZ
[ \ X Y ] ^
[ \ X Y ] ^
[ ___\ ``` ]aaa ^
bbb ccc ddd
eeefffggghhhiiijjjkkklllmmmnnn**
Truth table with 4 variables:
XYxy [is max possible, with given squares removed]
0000 1 //no squares removed (max always possible)
0001 0
0010 0
0011 0
0100 1
0101 0
0110 0
0111 0
1000 1
1001 0
1010 0
1011 0
1100 0
1101 0
1110 0
1111 0
*****************
**
** SOURCE CODE
**
*****************
// Dominoes helper -- by Tom Sirgedas
// Freeware
#include <iostream>
#include <string>
#include <vector>
#include <fstream>
#include <algorithm>
#include <map>
#include <sstream>
#define ARR_SIZE(x) int(sizeof(x)/sizeof((x)[0]))
using namespace std;
class Board
{
public:
Board() {}
Board( int sizeX, int sizeY ) { _m = vector<string>( sizeY, string( sizeX, ' ' ) ); }
Board( const string& filename ) { Load( filename ); }
void Clear() { _m.clear(); }
void Load( const string& filename )
{
Clear();
ifstream f( filename.c_str() );
if ( f.fail() )
{
cerr << "Error loading '" << filename << "'." << endl;
cerr << endl;
cerr << "Syntax Example: dominoes.exe mymap.txt" << endl;
exit( 1 );
}
char buf[1024];
int maxWidth = 0;
while ( f.getline( buf, sizeof(buf) ) )
{
_m.push_back( buf );
maxWidth = max( maxWidth, (int)_m.back().length() );
}
for ( int y = 0; y < SizeY(); y++ )
_m[y] = _m[y] + string( maxWidth - _m[y].length(), ' ' );
findTileVariables();
}
string Str() const
{
string ret;
for ( int y = 0; y < SizeY(); y++ )
ret += _m[y] + "\n";
return ret;
}
int SizeX() const { return _m.size() ? _m[0].length() : 0; }
int SizeY() const { return _m.size(); }
const string& operator[]( int row ) const { return _m[row]; }
string& operator[]( int row ) { return _m[row]; }
int Max1x3Tiles() const;
Board GenerateLayout() const;
int NumVariables() const { return (int)_TileVariables.size(); }
void SetVariables( int b ) // bitflags
{
int idx = NumVariables() - 1;
for ( map<char,pair<int,int> >::iterator it = _TileVariables.begin(); it != _TileVariables.end(); it++, idx-- )
{
int x = (*it).second.first;
int y = (*it).second.second;
_m[y][x] = b & (1<<idx) ? ' ' : '*';
}
}
string Num( int x ) const { stringstream ss; ss << x; return ss.str(); }
string TruthTable() const
{
if ( NumVariables() < 1 )
return "No truth table (no variables found!)";
if ( NumVariables() > 6 )
return "Too many variables for truth table";
int maxTiles = Max1x3Tiles();
Board board = *this;
string ret;
ret += "Truth table with " + Num( NumVariables() ) + " variables:\n";
for ( map<char,pair<int,int> >::const_iterator it = _TileVariables.begin(); it != _TileVariables.end(); it++ )
{
char c = (*it).first;
ret += c;
}
ret += " [is max possible, with given squares removed]\n";
// for each row of the table...
for ( int b = 0; b < (1<<NumVariables()); b++ )
{
board.SetVariables( b );
for ( int i = board.NumVariables()-1; i >= 0; i-- )
ret += b & (1<<i) ? "1" : "0";
int maxTilesForTheseVariables = board.Max1x3Tiles();
bool maxStillPossible = maxTilesForTheseVariables == maxTiles;
ret += string(" ") + ( maxStillPossible? "1" : "0" );
if ( b == 0 )
ret += " //no squares removed (max always possible)";
ret += "\n";
}
return ret;
}
private:
void findTileVariables()
{
_TileVariables.clear();
map<char, int> letterCount;
for ( int y = 0; y < SizeY(); y++ )
for ( int x = 0; x < SizeX(); x++ )
{
char c = _m[y][x];
letterCount[c]++;
_TileVariables[c] = pair<int,int>( x, y );
if ( letterCount[c] > 1 )
_TileVariables.erase( c );
}
}
private:
vector<string> _m;
map<char,pair<int,int> > _TileVariables; // advanced feature
};
class BitBoard
{
public:
typedef long long RowType;
struct ThreeRows
{
ThreeRows( RowType r0, RowType r1, RowType r2 ) : row0(r0), row1(r1), row2(r2) {}
bool operator<( const ThreeRows& rhs ) const { return row0 != rhs.row0 ? row0 < rhs.row0
: row1 != rhs.row1 ? row1 < rhs.row1
: row2 < rhs.row2; }
RowType row0, row1, row2;
};
BitBoard( const Board& b )
{
Init( b );
}
RowType toRowType( const string& row )
{
RowType r = 0;
for ( int x = 0; x < (int) row.length(); x++ )
r += RowType( row[x] != ' ' ) << x;
return r;
}
void Init( const Board& board )
{
_SizeX = board.SizeX();
if ( board.SizeX() > 64-3 )
return;
if ( board.SizeY() > 64-3 )
return;
for ( int y = 0; y < board.SizeY(); y++ )
_m.push_back( toRowType( board[y] ) );
}
int max1x3Tiles()
{
for ( int y = 0; y < ARR_SIZE( _Cache ); y++ )
for ( int x = 0; x < ARR_SIZE( _Cache[y] ); x++ )
_Cache[y][x].clear();
return max1x3Tiles( 0, 0, row(0), row(1), row(2) );
}
Board generateLayout()
{
Board outputBoard( _SizeX, _m.size() );
max1x3TilesPrint( 0, 0, row(0), row(1), row(2), outputBoard, 'A' );
return outputBoard;
}
private:
// recursive memoized function to find maximum layout starting at (x,y) (and going left-to-right, top-to-bottom)
// with the current and next two rows overridden to be (row0,row1,row2)
int max1x3Tiles( int x, int y, RowType row0, RowType row1, RowType row2 )
{
row0 &= ~((1LL<<x)-1); // clear out the part of the row we passed by already
// return cached result if found
ThreeRows tr(row0,row1,row2);
if ( _Cache[y][x].count(tr) )
return _Cache[y][x][tr];
if ( x >= _SizeX )
return max1x3Tiles( 0, y+1, row1, row2, row(y+3) ); // next row
if ( y >= (int)_m.size() )
return 0; // done
// option 1. don't cover (x,y)
int bestScore = max1x3Tiles( x+1, y, row0, row1, row2 );
// option 2. cover (x,y) horizontally
RowType horz = 7LL << x; // e.g. 000011100 in binary
bool canPlaceHorz = !( horz & ~row0 );
if ( canPlaceHorz )
bestScore = max( bestScore, 1+max1x3Tiles( x+3, y, row0 & ~horz, row1, row2 ) );
// option 3. cover (x,y) vertically
RowType vert = 1LL << x;
bool canPlaceVert = !( vert & ~row0 ) && !( vert & ~row1 ) && !( vert & ~row2 );
if ( canPlaceVert )
bestScore = max( bestScore, 1+max1x3Tiles( x+1, y, row0 & ~vert, row1 & ~vert, row2 & ~vert ) );
return _Cache[y][x][tr] = bestScore;
}
// code to generate an actual maximum tile layout (uses a lot of duplicated code:()
int max1x3TilesPrint( int x, int y, RowType row0, RowType row1, RowType row2, Board& outputBoard, char curLetter )
{
row0 &= ~((1LL<<x)-1); // clear out the part of the row we passed by already
if ( x >= _SizeX )
return max1x3TilesPrint( 0, y+1, row1, row2, row(y+3), outputBoard, curLetter ); // next row
if ( y >= (int)_m.size() )
return 0; // done
bool currentTileIsEmpty = !((1LL<<x)&row0);
if ( currentTileIsEmpty )
return max1x3TilesPrint( x+1, y, row0, row1, row2, outputBoard, curLetter );
// option 1. don't cover (x,y)
int option1Score = max1x3Tiles( x+1, y, row0, row1, row2 );
int option2Score = -1;
int option3Score = -1;
// option 2. cover (x,y) horizontally
RowType horz = 7LL << x; // e.g. 000011100 in binary
bool canPlaceHorz = !( horz & ~row0 );
if ( canPlaceHorz )
option2Score = 1+max1x3Tiles( x+3, y, row0 & ~horz, row1, row2 );
// option 3. cover (x,y) vertically
RowType vert = 1LL << x;
bool canPlaceVert = !( vert & ~row0 ) && !( vert & ~row1 ) && !( vert & ~row2 );
if ( canPlaceVert )
option3Score = 1+max1x3Tiles( x+1, y, row0 & ~vert, row1 & ~vert, row2 & ~vert );
int bestOption = option1Score > option2Score && option1Score > option3Score ? 1
: option2Score >= option3Score ? 2 : 3;
if ( bestOption == 1 )
{
outputBoard[y][x] = '*';
max1x3TilesPrint( x+1, y, row0, row1, row2, outputBoard, curLetter );
}
if ( bestOption == 2 )
{
outputBoard[y][x+0] = curLetter;
outputBoard[y][x+1] = curLetter;
outputBoard[y][x+2] = curLetter;
max1x3TilesPrint( x+3, y, row0 & ~horz, row1, row2, outputBoard, curLetter+1 );
}
if ( bestOption == 3 )
{
outputBoard[y+0][x] = curLetter;
outputBoard[y+1][x] = curLetter;
outputBoard[y+2][x] = curLetter;
max1x3TilesPrint( x+1, y, row0 & ~vert, row1 & ~vert, row2 & ~vert, outputBoard, curLetter+1 );
}
return max(option1Score,max(option2Score,option3Score));
}
private:
RowType row( int y ) const { return y < (int)_m.size() ? _m[y] : 0; }
private:
vector<RowType> _m;
int _SizeX;
map<ThreeRows, int> _Cache[64][64];
};
int Board::Max1x3Tiles() const
{
return BitBoard( *this ).max1x3Tiles();
}
Board Board::GenerateLayout() const
{
return BitBoard( *this ).generateLayout();
}
int main(int argc, char *argv[])
{
string mapFile = "../map.txt";
if ( argc == 2 )
mapFile = argv[1];
Board board( mapFile );
cout << "Input map: " << endl;
cout << board.Str() << endl;
cout << "maximum tiles = " << board.Max1x3Tiles() << endl;
cout << "One possible layout: " << endl;
cout << board.GenerateLayout().Str() << endl;
cout << board.TruthTable() << endl;
return 0;
}