This week only. Pastebin PRO Accounts Christmas Special! Don't miss out!Want more features on Pastebin? Sign Up, it's FREE!
Guest

Dominoes

By: a guest on Sep 10th, 2011  |  syntax: C++  |  size: 12.80 KB  |  views: 144  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1.  
  2. *************************************
  3. Example program outputs + source code
  4. *************************************
  5.  
  6.  
  7. Input map:
  8. ***y
  9. *
  10. *
  11. x
  12.  
  13. maximum tiles = 2
  14. One possible layout:
  15. AAA*
  16. B
  17. B
  18. B
  19.  
  20. Truth table with 2 variables:
  21. xy [is max possible, with given squares removed]
  22. 00 1 //no squares removed (max always possible)
  23. 01 1
  24. 10 1
  25. 11 0
  26.  
  27.  
  28.  
  29.  
  30. Input map:
  31.  ***y
  32.  *
  33. **x
  34.  
  35. maximum tiles = 2
  36. One possible layout:
  37.  AAA*
  38.  *
  39. BBB
  40.  
  41. Truth table with 2 variables:
  42. xy [is max possible, with given squares removed]
  43. 00 1 //no squares removed (max always possible)
  44. 01 1
  45. 10 1
  46. 11 0
  47.  
  48.  
  49.  
  50. Input map:
  51.  x y
  52.  * *
  53.  * *
  54. *****
  55.   *
  56.   ***z
  57.  
  58. maximum tiles = 4
  59. One possible layout:
  60.  A B
  61.  A B
  62.  A B
  63. CCC**
  64.   *
  65.   DDD*
  66.  
  67. Truth table with 3 variables:
  68. xyz [is max possible, with given squares removed]
  69. 000 1 //no squares removed (max always possible)
  70. 001 1
  71. 010 1
  72. 011 1
  73. 100 1
  74. 101 1
  75. 110 1
  76. 111 0
  77.  
  78.  
  79.  
  80. Input map:
  81.     *******
  82.     *     *
  83.     *     *
  84.  ****   ***
  85.  *       *
  86. ***      ****
  87.   *         *
  88.   *         *
  89.   * ******* *
  90.   * *     * *
  91.   * *     * *
  92.  *z*x*   *****
  93.    *       *
  94.    **** ****
  95.       * *
  96.       ***
  97.       ***
  98.       ***
  99.        *
  100.        *
  101.        y
  102.  
  103. maximum tiles = 25
  104. One possible layout:
  105.     AAABBBC
  106.     D     C
  107.     D     C
  108.  EEED   FFF
  109.  *       *
  110. GGG      HHHI
  111.   J         I
  112.   J         I
  113.   J KLLLMMM N
  114.   O K     P N
  115.   O K     P N
  116.  *OQQQ   *PRRR
  117.    *       *
  118.    SSST UVVV
  119.       T U
  120.       T*U
  121.       WWW
  122.       XXX
  123.        Y
  124.        Y
  125.        Y
  126.  
  127. Truth table with 3 variables:
  128. xyz [is max possible, with given squares removed]
  129. 000 1 //no squares removed (max always possible)
  130. 001 0
  131. 010 0
  132. 011 0
  133. 100 0
  134. 101 0
  135. 110 0
  136. 111 0
  137.  
  138.  
  139.  
  140. Input map:
  141.              ********** *******
  142.              *        * *     *
  143.              *        ***     *
  144.             ***       ***    ***
  145.               *       ***    *
  146.            ****        *     ****
  147.            *           *        *
  148.            *        ****        *
  149.           ***       *          ***
  150.             *      ***         *
  151.          ****      * *         ****
  152.     y    *         * *            *    x
  153.     *    *         * *            *    *
  154.     * ****         ***            **** *
  155.     ***            ***               ***
  156.       *************X*Y****************
  157.  
  158. maximum tiles = 46
  159. One possible layout:
  160.              AAABBBCCCD EFFFGGG
  161.              H        D E     I
  162.              H        D*E     I
  163.             *HJ       KKK    LI*
  164.               J       MMM    L
  165.            NNNJ        O     LPPP
  166.            Q           O        R
  167.            Q        SSSO        R
  168.           *QT       *          UR*
  169.             T      VVV         U
  170.          WWWT      X Y         UZZZ
  171.     [    \         X Y            ]    ^
  172.     [    \         X Y            ]    ^
  173.     [ ___\         ```            ]aaa ^
  174.     bbb            ccc               ddd
  175.       eeefffggghhhiiijjjkkklllmmmnnn**
  176.  
  177. Truth table with 4 variables:
  178. XYxy [is max possible, with given squares removed]
  179. 0000 1 //no squares removed (max always possible)
  180. 0001 0
  181. 0010 0
  182. 0011 0
  183. 0100 1
  184. 0101 0
  185. 0110 0
  186. 0111 0
  187. 1000 1
  188. 1001 0
  189. 1010 0
  190. 1011 0
  191. 1100 0
  192. 1101 0
  193. 1110 0
  194. 1111 0
  195.  
  196.  
  197. *****************
  198. **
  199. **  SOURCE CODE
  200. **
  201. *****************
  202.  
  203. // Dominoes helper -- by Tom Sirgedas
  204. // Freeware
  205. #include <iostream>
  206. #include <string>
  207. #include <vector>
  208. #include <fstream>
  209. #include <algorithm>
  210. #include <map>
  211. #include <sstream>
  212.  
  213. #define ARR_SIZE(x) int(sizeof(x)/sizeof((x)[0]))
  214.  
  215. using namespace std;
  216.  
  217. class Board
  218. {
  219. public:
  220.    Board() {}
  221.    Board( int sizeX, int sizeY ) { _m = vector<string>( sizeY, string( sizeX, ' ' ) ); }
  222.    Board( const string& filename ) { Load( filename ); }
  223.    void Clear() { _m.clear(); }
  224.    void Load( const string& filename )
  225.    {
  226.       Clear();
  227.  
  228.       ifstream f( filename.c_str() );
  229.       if ( f.fail() )
  230.       {
  231.          cerr << "Error loading '" << filename << "'." << endl;
  232.          cerr << endl;
  233.          cerr << "Syntax Example:  dominoes.exe mymap.txt" << endl;
  234.          exit( 1 );
  235.       }
  236.       char buf[1024];
  237.       int maxWidth = 0;
  238.       while ( f.getline( buf, sizeof(buf) ) )
  239.       {
  240.          _m.push_back( buf );
  241.          maxWidth = max( maxWidth, (int)_m.back().length() );
  242.       }
  243.       for ( int y = 0; y < SizeY(); y++ )
  244.          _m[y] = _m[y] + string( maxWidth - _m[y].length(), ' ' );
  245.  
  246.       findTileVariables();
  247.    }
  248.    string Str() const
  249.    {
  250.       string ret;
  251.       for ( int y = 0; y < SizeY(); y++ )
  252.          ret += _m[y] + "\n";
  253.       return ret;
  254.    }
  255.    int SizeX() const { return _m.size() ? _m[0].length() : 0; }
  256.    int SizeY() const { return _m.size(); }
  257.    const string& operator[]( int row ) const { return _m[row]; }
  258.    string& operator[]( int row ) { return _m[row]; }
  259.  
  260.    int Max1x3Tiles() const;
  261.    Board GenerateLayout() const;
  262.    int NumVariables() const { return (int)_TileVariables.size(); }
  263.    void SetVariables( int b ) // bitflags
  264.    {
  265.       int idx = NumVariables() - 1;
  266.       for ( map<char,pair<int,int> >::iterator it = _TileVariables.begin(); it != _TileVariables.end(); it++, idx-- )
  267.       {
  268.          int x = (*it).second.first;
  269.          int y = (*it).second.second;
  270.          _m[y][x] = b & (1<<idx) ? ' ' : '*';
  271.       }
  272.    }
  273.    string Num( int x ) const { stringstream ss; ss << x; return ss.str(); }
  274.    string TruthTable() const
  275.    {
  276.       if ( NumVariables() < 1 )
  277.          return "No truth table (no variables found!)";
  278.       if ( NumVariables() > 6 )
  279.          return "Too many variables for truth table";
  280.  
  281.       int maxTiles = Max1x3Tiles();
  282.       Board board = *this;
  283.  
  284.       string ret;
  285.       ret += "Truth table with " + Num( NumVariables() ) + " variables:\n";
  286.       for ( map<char,pair<int,int> >::const_iterator it = _TileVariables.begin(); it != _TileVariables.end(); it++ )
  287.       {
  288.          char c = (*it).first;
  289.          ret += c;
  290.       }
  291.       ret += " [is max possible, with given squares removed]\n";
  292.  
  293.       // for each row of the table...
  294.       for ( int b = 0; b < (1<<NumVariables()); b++ )
  295.       {
  296.          board.SetVariables( b );
  297.          for ( int i = board.NumVariables()-1; i >= 0; i-- )
  298.             ret += b & (1<<i) ? "1" : "0";
  299.          int maxTilesForTheseVariables = board.Max1x3Tiles();
  300.          bool maxStillPossible = maxTilesForTheseVariables == maxTiles;
  301.          ret += string(" ") + ( maxStillPossible? "1" : "0" );
  302.          if ( b == 0 )
  303.             ret += " //no squares removed (max always possible)";
  304.          ret += "\n";
  305.       }
  306.       return ret;
  307.    }
  308.  
  309. private:
  310.    void findTileVariables()
  311.    {
  312.       _TileVariables.clear();
  313.       map<char, int> letterCount;
  314.  
  315.       for ( int y = 0; y < SizeY(); y++ )
  316.       for ( int x = 0; x < SizeX(); x++ )
  317.       {
  318.          char c = _m[y][x];
  319.          letterCount[c]++;
  320.          _TileVariables[c] = pair<int,int>( x, y );
  321.          if ( letterCount[c] > 1 )
  322.             _TileVariables.erase( c );
  323.       }
  324.    }
  325.  
  326. private:
  327.    vector<string> _m;
  328.    map<char,pair<int,int> > _TileVariables; // advanced feature
  329. };
  330.  
  331. class BitBoard
  332. {
  333. public:
  334.    typedef long long RowType;
  335.    struct ThreeRows
  336.    {
  337.       ThreeRows( RowType r0, RowType r1, RowType r2 ) : row0(r0), row1(r1), row2(r2) {}
  338.       bool operator<( const ThreeRows& rhs ) const { return row0 != rhs.row0 ? row0 < rhs.row0
  339.                                                           : row1 != rhs.row1 ? row1 < rhs.row1
  340.                                                           :                    row2 < rhs.row2; }
  341.       RowType row0, row1, row2;
  342.    };
  343.  
  344.    BitBoard( const Board& b )
  345.    {
  346.       Init( b );
  347.    }
  348.    RowType toRowType( const string& row )
  349.    {
  350.       RowType r = 0;
  351.       for ( int x = 0; x < (int) row.length(); x++ )
  352.          r += RowType( row[x] != ' ' ) << x;
  353.       return r;
  354.    }
  355.    void Init( const Board& board )
  356.    {
  357.       _SizeX = board.SizeX();
  358.       if ( board.SizeX() > 64-3 )
  359.          return;
  360.       if ( board.SizeY() > 64-3 )
  361.          return;
  362.  
  363.       for ( int y = 0; y < board.SizeY(); y++ )
  364.          _m.push_back( toRowType( board[y] ) );
  365.    }
  366.  
  367.    int max1x3Tiles()
  368.    {
  369.       for ( int y = 0; y < ARR_SIZE( _Cache ); y++ )
  370.       for ( int x = 0; x < ARR_SIZE( _Cache[y] ); x++ )
  371.          _Cache[y][x].clear();
  372.       return max1x3Tiles( 0, 0, row(0), row(1), row(2) );
  373.    }
  374.    Board generateLayout()
  375.    {
  376.       Board outputBoard( _SizeX, _m.size() );
  377.       max1x3TilesPrint( 0, 0, row(0), row(1), row(2), outputBoard, 'A' );
  378.       return outputBoard;
  379.    }
  380.  
  381. private:
  382.    // recursive memoized function to find maximum layout starting at (x,y) (and going left-to-right, top-to-bottom)
  383.    // with the current and next two rows overridden to be (row0,row1,row2)
  384.    int max1x3Tiles( int x, int y, RowType row0, RowType row1, RowType row2 )
  385.    {
  386.       row0 &= ~((1LL<<x)-1); // clear out the part of the row we passed by already
  387.  
  388.       // return cached result if found
  389.       ThreeRows tr(row0,row1,row2);
  390.       if ( _Cache[y][x].count(tr) )
  391.          return _Cache[y][x][tr];
  392.  
  393.       if ( x >= _SizeX )
  394.          return max1x3Tiles( 0, y+1, row1, row2, row(y+3) ); // next row
  395.       if ( y >= (int)_m.size() )
  396.          return 0; // done
  397.  
  398.       // option 1. don't cover (x,y)
  399.       int bestScore = max1x3Tiles( x+1, y, row0, row1, row2 );
  400.  
  401.       // option 2. cover (x,y) horizontally
  402.       RowType horz = 7LL << x; // e.g. 000011100 in binary
  403.       bool canPlaceHorz = !( horz & ~row0 );
  404.       if ( canPlaceHorz )
  405.          bestScore = max( bestScore, 1+max1x3Tiles( x+3, y, row0 & ~horz, row1, row2 ) );
  406.  
  407.       // option 3. cover (x,y) vertically
  408.       RowType vert = 1LL << x;
  409.       bool canPlaceVert = !( vert & ~row0 ) && !( vert & ~row1 ) && !( vert & ~row2 );
  410.       if ( canPlaceVert )
  411.          bestScore = max( bestScore, 1+max1x3Tiles( x+1, y, row0 & ~vert, row1 & ~vert, row2 & ~vert ) );
  412.  
  413.       return _Cache[y][x][tr] = bestScore;
  414.    }
  415.  
  416.    // code to generate an actual maximum tile layout (uses a lot of duplicated code:()
  417.    int max1x3TilesPrint( int x, int y, RowType row0, RowType row1, RowType row2, Board& outputBoard, char curLetter )
  418.    {
  419.       row0 &= ~((1LL<<x)-1); // clear out the part of the row we passed by already
  420.  
  421.       if ( x >= _SizeX )
  422.          return max1x3TilesPrint( 0, y+1, row1, row2, row(y+3), outputBoard, curLetter ); // next row
  423.       if ( y >= (int)_m.size() )
  424.          return 0; // done
  425.       bool currentTileIsEmpty = !((1LL<<x)&row0);
  426.       if ( currentTileIsEmpty )
  427.          return max1x3TilesPrint( x+1, y, row0, row1, row2, outputBoard, curLetter );
  428.  
  429.       // option 1. don't cover (x,y)
  430.       int option1Score = max1x3Tiles( x+1, y, row0, row1, row2 );
  431.       int option2Score = -1;
  432.       int option3Score = -1;
  433.  
  434.       // option 2. cover (x,y) horizontally
  435.       RowType horz = 7LL << x; // e.g. 000011100 in binary
  436.       bool canPlaceHorz = !( horz & ~row0 );
  437.       if ( canPlaceHorz )
  438.          option2Score = 1+max1x3Tiles( x+3, y, row0 & ~horz, row1, row2 );
  439.  
  440.       // option 3. cover (x,y) vertically
  441.       RowType vert = 1LL << x;
  442.       bool canPlaceVert = !( vert & ~row0 ) && !( vert & ~row1 ) && !( vert & ~row2 );
  443.       if ( canPlaceVert )
  444.          option3Score = 1+max1x3Tiles( x+1, y, row0 & ~vert, row1 & ~vert, row2 & ~vert );
  445.  
  446.       int bestOption = option1Score > option2Score && option1Score > option3Score ? 1
  447.                      : option2Score >= option3Score ? 2 : 3;
  448.  
  449.       if ( bestOption == 1 )
  450.       {
  451.          outputBoard[y][x] = '*';
  452.          max1x3TilesPrint( x+1, y, row0, row1, row2, outputBoard, curLetter );
  453.       }
  454.       if ( bestOption == 2 )
  455.       {
  456.          outputBoard[y][x+0] = curLetter;
  457.          outputBoard[y][x+1] = curLetter;
  458.          outputBoard[y][x+2] = curLetter;
  459.          max1x3TilesPrint( x+3, y, row0 & ~horz, row1, row2, outputBoard, curLetter+1 );
  460.       }
  461.       if ( bestOption == 3 )
  462.       {
  463.          outputBoard[y+0][x] = curLetter;
  464.          outputBoard[y+1][x] = curLetter;
  465.          outputBoard[y+2][x] = curLetter;
  466.          max1x3TilesPrint( x+1, y, row0 & ~vert, row1 & ~vert, row2 & ~vert, outputBoard, curLetter+1 );
  467.       }
  468.       return max(option1Score,max(option2Score,option3Score));
  469.    }
  470.  
  471. private:
  472.    RowType row( int y ) const { return y < (int)_m.size() ? _m[y] : 0; }
  473. private:
  474.    vector<RowType> _m;
  475.    int _SizeX;
  476.    map<ThreeRows, int> _Cache[64][64];
  477. };
  478.  
  479.  
  480. int Board::Max1x3Tiles() const
  481. {
  482.    return BitBoard( *this ).max1x3Tiles();
  483. }
  484.  
  485. Board Board::GenerateLayout() const
  486. {
  487.    return BitBoard( *this ).generateLayout();
  488. }
  489.  
  490. int main(int argc, char *argv[])
  491. {
  492.    string mapFile = "../map.txt";
  493.    if ( argc == 2 )
  494.       mapFile = argv[1];
  495.    Board board( mapFile );
  496.    cout << "Input map: " << endl;
  497.    cout << board.Str() << endl;
  498.    cout << "maximum tiles = " << board.Max1x3Tiles() << endl;
  499.    cout << "One possible layout: " << endl;
  500.    cout << board.GenerateLayout().Str() << endl;
  501.    cout << board.TruthTable() << endl;
  502.  
  503.    return 0;
  504. }
clone this paste RAW Paste Data