# 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