Guest User

Untitled

a guest
Mar 18th, 2011
307
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. string g_pic[] = {
  3.    "..........",
  4.    "...#####..",
  5.    "..#....#..",
  6.    "..####.#..",
  7.    "..#....#..",
  8.    "..........",
  9.    "..##..#...",
  10.    "..#.#.#...",
  11.    "..#..##...",
  12.    "..........",
  13.    "......#..#",
  14.    "...####.#.",
  15.    "...#..##..",
  16.    "...####..." };
  17.  
  18. struct Plate { int sx, sy, cost; };
  19. Plate plates[] = { { 1, 1, 1000 }, { 1, 2, 150 }, { 2, 1, 150 }, { 1, 3, 250 }, { 3, 1, 250 }, { 3, 3, 1 } };
  20.  
  21. int SY = sizeof(g_pic)/sizeof(g_pic[0]);
  22. int SX = g_pic[0].length();
  23. const int MAXSIZE = 64;
  24. const int NUMPLATES = sizeof(plates)/sizeof(plates[0]);
  25. __int64 zobristHash[MAXSIZE][MAXSIZE] = { 0 };
  26. __int64 zobristPlateHash[NUMPLATES][MAXSIZE][MAXSIZE] = { 0 };
  27.  
  28. __int64 rand64() { return ((__int64)rand()<<0)^((__int64)rand()<<15)^((__int64)rand()<<30)^((__int64)rand()<<45)^((__int64)rand()<<60); }
  29.  
  30. bool findNextEmpty( int& x, int& y )
  31. {
  32.    while ( 1 )
  33.    {
  34.       if ( g_pic[y][x] == '.' ) return true;
  35.       x++;
  36.       if ( x >= SX ) { x = 0; y++; }
  37.       if ( y >= SY ) return false;
  38.    }
  39. }
  40.  
  41. map<__int64, int> bestCost;
  42. int findCost( int posx, int posy, __int64 hash )
  43. {  
  44.    if ( bestCost.count( hash ) )
  45.       return bestCost[hash];
  46.  
  47.    if ( !findNextEmpty( posx, posy ) ) return bestCost[hash] = 0; // done -- no empty spots left
  48.  
  49.    int ret = INT_MAX;
  50.  
  51.    // try to place each kind of plate with upper-left corner at posx, posy
  52.    for ( int plateIdx = 0; plateIdx < NUMPLATES; plateIdx++ ) if ( zobristPlateHash[plateIdx][posy][posx] != 0 )
  53.    {
  54.       bool isLegalToPlace = true;
  55.       for ( int y = 0; y < plates[plateIdx].sy; y++ )
  56.       for ( int x = 0; x < plates[plateIdx].sx; x++ )
  57.          if ( g_pic[posy+y][posx+x] != '.' ) { isLegalToPlace = false; y=999; break; }
  58.       if ( !isLegalToPlace ) continue;
  59.  
  60.       // if we already know the cost to fill the remainder of the picture:
  61.       if ( bestCost.count( hash ^ zobristPlateHash[plateIdx][posy][posx] ) )
  62.       {
  63.          int cost = plates[plateIdx].cost + bestCost[hash ^ zobristPlateHash[plateIdx][posy][posx]];
  64.          ret = min( ret, cost );
  65.          continue;
  66.       }
  67.      
  68.       // place the piece
  69.       for ( int y = 0; y < plates[plateIdx].sy; y++ )
  70.       for ( int x = 0; x < plates[plateIdx].sx; x++ )
  71.          g_pic[posy+y][posx+x] = '#';
  72.      
  73.       // cost = cost of this piece + optimal cost of filling the rest
  74.       int cost = plates[plateIdx].cost + findCost( posx, posy, hash ^ zobristPlateHash[plateIdx][posy][posx] );
  75.       ret = min( ret, cost );
  76.      
  77.       // un-place the piece
  78.       for ( int y = 0; y < plates[plateIdx].sy; y++ )
  79.       for ( int x = 0; x < plates[plateIdx].sx; x++ )
  80.          g_pic[posy+y][posx+x] = '.';
  81.    }
  82.    
  83.    // memoize
  84.    return bestCost[hash] = ret;
  85. }
  86.  
  87. void reconstructSolution( int posx, int posy, __int64 hash, int expectedCost )
  88. {  
  89.    if ( !findNextEmpty( posx, posy ) ) return; // done
  90.    
  91.    for ( int plateIdx = 0; plateIdx < NUMPLATES; plateIdx++ ) if ( zobristPlateHash[plateIdx][posy][posx] != 0 )
  92.    {
  93.       bool ok = true;
  94.       for ( int y = 0; y < plates[plateIdx].sy; y++ )
  95.       for ( int x = 0; x < plates[plateIdx].sx; x++ )
  96.          if ( g_pic[posy+y][posx+x] != '.' )
  97.             ok = false;
  98.       if ( !ok ) continue;
  99.            
  100.       int cost = plates[plateIdx].cost + findCost( posx, posy, hash ^ zobristPlateHash[plateIdx][posy][posx] );
  101.       if ( cost != expectedCost ) continue;
  102.  
  103.       for ( int y = 0; y < plates[plateIdx].sy; y++ )
  104.       for ( int x = 0; x < plates[plateIdx].sx; x++ )
  105.          g_pic[posy+y][posx+x] = '0' + plateIdx;
  106.       reconstructSolution( posx, posy, hash ^ zobristPlateHash[plateIdx][posy][posx], expectedCost - plates[plateIdx].cost );
  107.       break;
  108.    }
  109. }
  110.  
  111. void main()
  112. {
  113.    // assign random zobrist hash value to each single square
  114.    for ( int posy = 0; posy < SY; posy++ )
  115.    for ( int posx = 0; posx < SX; posx++ )
  116.       zobristHash[posy][posx] = rand64();
  117.    
  118.    // the hash values of multiple squares is just each single square XOR'ed together
  119.    // pre-calculate the hash value for each piece at each position
  120.    for ( int plateIdx = 0; plateIdx < NUMPLATES; plateIdx++ )
  121.    for ( int posy = 0; posy <= SY - plates[plateIdx].sy; posy++ )
  122.    for ( int posx = 0; posx <= SX - plates[plateIdx].sx; posx++ )
  123.    {
  124.       for ( int y = 0; y < plates[plateIdx].sy; y++ )
  125.       for ( int x = 0; x < plates[plateIdx].sx; x++ )
  126.          zobristPlateHash[plateIdx][posy][posx] ^= zobristHash[posy+y][posx+x];
  127.    }
  128.    
  129.    int cost = findCost( 0, 0, 0 );  
  130.    echoprintf( "lowest cost = %d\n", cost );  
  131.    echoprintf( "(hashmap size = %d)\n", bestCost.size() );
  132.  
  133.    reconstructSolution( 0, 0, 0, cost );
  134.    echoprintf( "\n" );
  135.    for ( int y = 0; y < SY; y++ )
  136.       echoprintf( "%s\n", g_pic[y].c_str() );
  137.    echoprintf( "\n" );
  138. }
  139.  
  140. // output:
  141. //
  142. //lowest cost = 7352
  143. //(hashmap size = 41936)
  144. //
  145. //1112222221
  146. //111#####11
  147. //11#2222#13
  148. //11####1#13
  149. //22#1221#13
  150. //1221122555
  151. //11##11#555
  152. //11#1#1#555
  153. //11#11##221
  154. //1122112211
  155. //122221#11#
  156. //555####1#0
  157. //555#22##22
  158. //555####444
RAW Paste Data