Want more features on Pastebin? Sign Up, it's FREE!
Guest

Untitled

By: a guest on Sep 11th, 2011  |  syntax: None  |  size: 12.11 KB  |  views: 29  |  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. Here's a somewhat hacky, tricky-to-use modification to my dominoes program.  
  2.  
  3. It allows you to search for gadgets with certain truth tables.
  4.  
  5.  
  6. Say you want the following truth table:
  7.  
  8. Truth table with 3 variables:
  9. xyz [is max possible, with given squares removed]
  10. 000 1 //no squares removed (max always possible)
  11. 001 1
  12. 010 1
  13. 011 1
  14. 100 1
  15. 101 0
  16. 110 0
  17. 111 0
  18.  
  19. The value of the truth table is 00011111 in binary, 15 in decimal.
  20.  
  21. So, we'll design a board template and call Board::FindTruthTable( 15 ).
  22.  
  23. Let's say we want to search a symmetrical design.  Our board template may look like this:
  24.  
  25.  
  26. y****A****z
  27.    IEBEI
  28.    JFCFJ
  29.    KGDGK
  30.    LHxHL
  31.  
  32.  
  33. Now, Board::FindTruthTable() will replace all capital letters ('A' to 'Z') with either ' ' or '*'.  All settings will be tried.  For the example above, 2^12 settings will be tried.  All the gadgets generated with the requested truth table will be printed out.
  34.  
  35.  
  36.  
  37.  
  38.  
  39.  
  40. // Dominoes helper -- by Tom Sirgedas
  41. // Freeware
  42. #include <iostream>
  43. #include <string>
  44. #include <vector>
  45. #include <fstream>
  46. #include <algorithm>
  47. #include <map>
  48. #include <sstream>
  49.  
  50. #define ARR_SIZE(x) int(sizeof(x)/sizeof((x)[0]))
  51.  
  52. using namespace std;
  53.  
  54. class Board
  55. {
  56. public:
  57.    Board() {}
  58.    Board( int sizeX, int sizeY ) { _m = vector<string>( sizeY, string( sizeX, ' ' ) ); }
  59.    Board( const string& filename ) { Load( filename ); }
  60.    void Clear() { _m.clear(); }
  61.    void Load( const string& filename )
  62.    {
  63.       Clear();
  64.  
  65.       ifstream f( filename.c_str() );
  66.       if ( f.fail() )
  67.       {
  68.          cerr << "Error loading '" << filename << "'." << endl;
  69.          cerr << endl;
  70.          cerr << "Syntax Example:  dominoes.exe mymap.txt" << endl;
  71.          exit( 1 );
  72.       }
  73.       char buf[1024];
  74.       int maxWidth = 0;
  75.       while ( f.getline( buf, sizeof(buf) ) )
  76.       {
  77.          _m.push_back( buf );
  78.          maxWidth = max( maxWidth, (int)_m.back().length() );
  79.       }
  80.       for ( int y = 0; y < SizeY(); y++ )
  81.          _m[y] = _m[y] + string( maxWidth - _m[y].length(), ' ' );
  82.  
  83.       findTileVariables();
  84.    }
  85.    string Str() const
  86.    {
  87.       string ret;
  88.       for ( int y = 0; y < SizeY(); y++ )
  89.          ret += _m[y] + "\n";
  90.       return ret;
  91.    }
  92.    int SizeX() const { return _m.size() ? _m[0].length() : 0; }
  93.    int SizeY() const { return _m.size(); }
  94.    const string& operator[]( int row ) const { return _m[row]; }
  95.    string& operator[]( int row ) { return _m[row]; }
  96.  
  97.    int Max1x3Tiles() const;
  98.    Board GenerateLayout() const;
  99.    int NumVariables() const { return (int)_TileVariables.size(); }
  100.    void SetVariables( int b ) // bitflags
  101.    {
  102.       int idx = NumVariables() - 1;
  103.       for ( map<char,pair<int,int> >::iterator it = _TileVariables.begin(); it != _TileVariables.end(); it++, idx-- )
  104.       {
  105.          int x = (*it).second.first;
  106.          int y = (*it).second.second;
  107.          _m[y][x] = b & (1<<idx) ? ' ' : '*';
  108.       }
  109.    }
  110.    string Num( int x ) const { stringstream ss; ss << x; return ss.str(); }
  111.    int TruthTableInt() const
  112.    {
  113.       int ret = 0;
  114.       Board board = *this;
  115.       // for each row of the table...
  116.       int maxTiles = Max1x3Tiles();
  117.       for ( int b = 0; b < (1<<NumVariables()); b++ )
  118.       {
  119.          board.SetVariables( b );
  120.          int maxTilesForTheseVariables = board.Max1x3Tiles();
  121.          bool maxStillPossible = maxTilesForTheseVariables == maxTiles;
  122.          ret += maxStillPossible << b;
  123.       }
  124.       return ret;
  125.    }
  126.    string TruthTable() const
  127.    {
  128.       if ( NumVariables() < 1 )
  129.          return "No truth table (no variables found!)";
  130.       if ( NumVariables() > 6 )
  131.          return "Too many variables for truth table";
  132.  
  133.       int maxTiles = Max1x3Tiles();
  134.       Board board = *this;
  135.  
  136.       string ret;
  137.       ret += "Truth table with " + Num( NumVariables() ) + " variables:\n";
  138.       for ( map<char,pair<int,int> >::const_iterator it = _TileVariables.begin(); it != _TileVariables.end(); it++ )
  139.       {
  140.          char c = (*it).first;
  141.          ret += c;
  142.       }
  143.       ret += " [is max possible, with given squares removed]\n";
  144.  
  145.       // for each row of the table...
  146.       for ( int b = 0; b < (1<<NumVariables()); b++ )
  147.       {
  148.          board.SetVariables( b );
  149.          for ( int i = board.NumVariables()-1; i >= 0; i-- )
  150.             ret += b & (1<<i) ? "1" : "0";
  151.          int maxTilesForTheseVariables = board.Max1x3Tiles();
  152.          bool maxStillPossible = maxTilesForTheseVariables == maxTiles;
  153.          ret += string(" ") + ( maxStillPossible? "1" : "0" );
  154.          if ( b == 0 )
  155.             ret += " //no squares removed (max always possible)";
  156.          ret += "\n";
  157.       }
  158.       return ret;
  159.    }
  160.    void FindTruthTable( int targetTruthTableInt ) const
  161.    {
  162.       int numDigits = 0;
  163.       for ( int y = 0; y < SizeY(); y++ )
  164.       for ( int x = 0; x < SizeX(); x++ )
  165.          if ( isupper( _m[y][x] ) )
  166.             numDigits = max(numDigits,_m[y][x] - 'A' + 1);
  167.  
  168.       for ( int b = 0; b < (1<<numDigits); b++ )
  169.       {
  170.          if ( b && (b%1000) == 0 )
  171.             cout << b << "/" << (1<<numDigits) << endl;
  172.          Board board = *this;        
  173.          for ( int y = 0; y < SizeY(); y++ )
  174.          for ( int x = 0; x < SizeX(); x++ )
  175.             if ( isupper( _m[y][x] ) )
  176.                board._m[y][x] = b & (1<<(_m[y][x]-'A')) ? '*' : ' ';
  177.          board.findTileVariables();
  178.  
  179.          //cout << board.TruthTableInt() << endl;
  180.          //cout << board.Str() << board.TruthTableInt() << endl;
  181.          if ( board.TruthTableInt() == targetTruthTableInt )
  182.          {
  183.             cout << board.Str() << endl;
  184.             cout << board.TruthTable() << endl;
  185.             cout << endl;
  186.             cout << endl;
  187.          }
  188.       }
  189.    }
  190.  
  191. private:
  192.    void findTileVariables()
  193.    {
  194.       _TileVariables.clear();
  195.       map<char, int> letterCount;
  196.  
  197.       for ( int y = 0; y < SizeY(); y++ )
  198.       for ( int x = 0; x < SizeX(); x++ )
  199.       {
  200.          char c = _m[y][x];
  201.          letterCount[c]++;
  202.          _TileVariables[c] = pair<int,int>( x, y );
  203.          if ( letterCount[c] > 1 )
  204.             _TileVariables.erase( c );
  205.       }
  206.    }
  207.  
  208. private:
  209.    vector<string> _m;
  210.    map<char,pair<int,int> > _TileVariables; // advanced feature
  211. };
  212.  
  213. class BitBoard
  214. {
  215. public:
  216.    typedef long long RowType;
  217.    struct ThreeRows
  218.    {
  219.       ThreeRows( RowType r0, RowType r1, RowType r2 ) : row0(r0), row1(r1), row2(r2) {}
  220.       bool operator<( const ThreeRows& rhs ) const { return row0 != rhs.row0 ? row0 < rhs.row0
  221.                                                           : row1 != rhs.row1 ? row1 < rhs.row1
  222.                                                           :                    row2 < rhs.row2; }
  223.       RowType row0, row1, row2;
  224.    };
  225.  
  226.    BitBoard( const Board& b )
  227.    {
  228.       Init( b );
  229.    }
  230.    RowType toRowType( const string& row )
  231.    {
  232.       RowType r = 0;
  233.       for ( int x = 0; x < (int) row.length(); x++ )
  234.          r += RowType( row[x] != ' ' ) << x;
  235.       return r;
  236.    }
  237.    void Init( const Board& board )
  238.    {
  239.       _SizeX = board.SizeX();
  240.       if ( board.SizeX() > 64-3 )
  241.          return;
  242.       if ( board.SizeY() > 64-3 )
  243.          return;
  244.  
  245.       for ( int y = 0; y < board.SizeY(); y++ )
  246.          _m.push_back( toRowType( board[y] ) );
  247.    }
  248.  
  249.    int max1x3Tiles()
  250.    {
  251.       for ( int y = 0; y < ARR_SIZE( _Cache ); y++ )
  252.       for ( int x = 0; x < ARR_SIZE( _Cache[y] ); x++ )
  253.          _Cache[y][x].clear();
  254.       return max1x3Tiles( 0, 0, row(0), row(1), row(2) );
  255.    }
  256.    Board generateLayout()
  257.    {
  258.       Board outputBoard( _SizeX, _m.size() );
  259.       max1x3TilesPrint( 0, 0, row(0), row(1), row(2), outputBoard, 'A' );
  260.       return outputBoard;
  261.    }
  262.  
  263. private:
  264.    // recursive memoized function to find maximum layout starting at (x,y) (and going left-to-right, top-to-bottom)
  265.    // with the current and next two rows overridden to be (row0,row1,row2)
  266.    int max1x3Tiles( int x, int y, RowType row0, RowType row1, RowType row2 )
  267.    {
  268.       row0 &= ~((1LL<<x)-1); // clear out the part of the row we passed by already
  269.  
  270.       // return cached result if found
  271.       ThreeRows tr(row0,row1,row2);
  272.       if ( _Cache[y][x].count(tr) )
  273.          return _Cache[y][x][tr];
  274.  
  275.       if ( x >= _SizeX )
  276.          return max1x3Tiles( 0, y+1, row1, row2, row(y+3) ); // next row
  277.       if ( y >= (int)_m.size() )
  278.          return 0; // done
  279.  
  280.       // option 1. don't cover (x,y)
  281.       int bestScore = max1x3Tiles( x+1, y, row0, row1, row2 );
  282.  
  283.       // option 2. cover (x,y) horizontally
  284.       RowType horz = 7LL << x; // e.g. 000011100 in binary
  285.       bool canPlaceHorz = !( horz & ~row0 );
  286.       if ( canPlaceHorz )
  287.          bestScore = max( bestScore, 1+max1x3Tiles( x+3, y, row0 & ~horz, row1, row2 ) );
  288.  
  289.       // option 3. cover (x,y) vertically
  290.       RowType vert = 1LL << x;
  291.       bool canPlaceVert = !( vert & ~row0 ) && !( vert & ~row1 ) && !( vert & ~row2 );
  292.       if ( canPlaceVert )
  293.          bestScore = max( bestScore, 1+max1x3Tiles( x+1, y, row0 & ~vert, row1 & ~vert, row2 & ~vert ) );
  294.  
  295.       return _Cache[y][x][tr] = bestScore;
  296.    }
  297.  
  298.    // code to generate an actual maximum tile layout (uses a lot of duplicated code:()
  299.    int max1x3TilesPrint( int x, int y, RowType row0, RowType row1, RowType row2, Board& outputBoard, char curLetter )
  300.    {
  301.       row0 &= ~((1LL<<x)-1); // clear out the part of the row we passed by already
  302.  
  303.       if ( x >= _SizeX )
  304.          return max1x3TilesPrint( 0, y+1, row1, row2, row(y+3), outputBoard, curLetter ); // next row
  305.       if ( y >= (int)_m.size() )
  306.          return 0; // done
  307.       bool currentTileIsEmpty = !((1LL<<x)&row0);
  308.       if ( currentTileIsEmpty )
  309.          return max1x3TilesPrint( x+1, y, row0, row1, row2, outputBoard, curLetter );
  310.  
  311.       // option 1. don't cover (x,y)
  312.       int option1Score = max1x3Tiles( x+1, y, row0, row1, row2 );
  313.       int option2Score = -1;
  314.       int option3Score = -1;
  315.  
  316.       // option 2. cover (x,y) horizontally
  317.       RowType horz = 7LL << x; // e.g. 000011100 in binary
  318.       bool canPlaceHorz = !( horz & ~row0 );
  319.       if ( canPlaceHorz )
  320.          option2Score = 1+max1x3Tiles( x+3, y, row0 & ~horz, row1, row2 );
  321.  
  322.       // option 3. cover (x,y) vertically
  323.       RowType vert = 1LL << x;
  324.       bool canPlaceVert = !( vert & ~row0 ) && !( vert & ~row1 ) && !( vert & ~row2 );
  325.       if ( canPlaceVert )
  326.          option3Score = 1+max1x3Tiles( x+1, y, row0 & ~vert, row1 & ~vert, row2 & ~vert );
  327.  
  328.       int bestOption = option1Score > option2Score && option1Score > option3Score ? 1
  329.                      : option2Score >= option3Score ? 2 : 3;
  330.  
  331.       if ( bestOption == 1 )
  332.       {
  333.          outputBoard[y][x] = '*';
  334.          max1x3TilesPrint( x+1, y, row0, row1, row2, outputBoard, curLetter );
  335.       }
  336.       if ( bestOption == 2 )
  337.       {
  338.          outputBoard[y][x+0] = curLetter;
  339.          outputBoard[y][x+1] = curLetter;
  340.          outputBoard[y][x+2] = curLetter;
  341.          max1x3TilesPrint( x+3, y, row0 & ~horz, row1, row2, outputBoard, curLetter+1 );
  342.       }
  343.       if ( bestOption == 3 )
  344.       {
  345.          outputBoard[y+0][x] = curLetter;
  346.          outputBoard[y+1][x] = curLetter;
  347.          outputBoard[y+2][x] = curLetter;
  348.          max1x3TilesPrint( x+1, y, row0 & ~vert, row1 & ~vert, row2 & ~vert, outputBoard, curLetter+1 );
  349.       }
  350.       return max(option1Score,max(option2Score,option3Score));
  351.    }
  352.  
  353. private:
  354.    RowType row( int y ) const { return y < (int)_m.size() ? _m[y] : 0; }
  355. private:
  356.    vector<RowType> _m;
  357.    int _SizeX;
  358.    map<ThreeRows, int> _Cache[64][64];
  359. };
  360.  
  361.  
  362. int Board::Max1x3Tiles() const
  363. {
  364.    return BitBoard( *this ).max1x3Tiles();
  365. }
  366.  
  367. Board Board::GenerateLayout() const
  368. {
  369.    return BitBoard( *this ).generateLayout();
  370. }
  371.  
  372. int main(int argc, char *argv[])
  373. {
  374.    string mapFile = "map.txt";
  375.    if ( argc == 2 )
  376.       mapFile = argv[1];
  377.    Board board( mapFile );
  378.    //cout << "Input map: " << endl;
  379.    //cout << board.Str() << endl;
  380.    //cout << "maximum tiles = " << board.Max1x3Tiles() << endl;
  381.    //cout << "One possible layout: " << endl;
  382.    //cout << board.GenerateLayout().Str() << endl;
  383.    //cout << board.TruthTable() << endl;
  384.    //cout << board.TruthTableInt() << endl;
  385.    board.FindTruthTable( 15 );
  386.    return 0;
  387. }
clone this paste RAW Paste Data