Dominoes

*************************************
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;
}