Robust/src/Benchmarks/TileSearch/Java/SubProblem.java

   1 public class SubProblem {
   2
   3         public SubProblem(){
   4         partial = false;
   5     }
   6
   7     public Tile[]   tilesToFit;
   8     public Tile[]   tilesFitted;
   9     public TileGrid workingGrid;
  10
  11     // these indices are into the respective
  12     // tile arrays
  13     public int indexToFit;
  14     public int indexFitted;
  15
  16     // this score represents the evaluation
  17     // of every arrangement of this sub-problem's
  18     // bestArrangements list
  19     public int highScore;
  20
  21     public boolean partial;
  22
  23     public void incrementIndices() {
  24         ++indexFitted;
  25         if( indexFitted == tilesFitted.length ) {
  26             indexFitted = 0;
  27             ++indexToFit;
  28         }
  29     }
  30
  31     public void initializeSubProblem( SubProblem nsp, int checkingFits ) {
  32         nsp.tilesToFit = new Tile[tilesToFit.length - 1];
  33         nsp.indexToFit = 0;
  34
  35         int j = 0;
  36         for( int i = 0; i < tilesToFit.length; ++i ) {
  37             // copy everything but the tile that
  38             // is being moved to the fitted list
  39             if( i != indexToFit ) {
  40                 nsp.tilesToFit[j] = tilesToFit[i].copy();
  41                 ++j;
  42             }
  43         }
  44
  45         nsp.tilesFitted = new Tile[tilesFitted.length + 1];
  46         nsp.tilesFitted[nsp.tilesFitted.length - 1] = tilesToFit[indexToFit].copy();
  47         nsp.indexFitted = 0;
  48         for( int i = 0; i < tilesFitted.length; ++i ) {
  49             nsp.tilesFitted[i] = tilesFitted[i].copy();
  50             //  if((checkingFits == 1) ||
  51             //                  (checkingFits == 3)) {
  52             nsp.tilesFitted[i].x = tilesFitted[i].x;
  53             nsp.tilesFitted[i].y = tilesFitted[i].y;
  54             //  }
  55         }
  56
  57         // set fitted tiles position according to fit type
  58         if( checkingFits == 1 ) {
  59             nsp.tilesFitted[nsp.tilesFitted.length - 1].x =
  60                 tilesFitted[indexFitted].x;
  61             nsp.tilesFitted[nsp.tilesFitted.length - 1].y =
  62                 tilesFitted[indexFitted].y - 1;
  63         } else if( checkingFits == 2 ) {
  64             nsp.tilesFitted[nsp.tilesFitted.length - 1].x =
  65                 tilesFitted[indexFitted].x;
  66             nsp.tilesFitted[nsp.tilesFitted.length - 1].y =
  67                 tilesFitted[indexFitted].y + 1;
  68         } else if( checkingFits == 3 ) {
  69             nsp.tilesFitted[nsp.tilesFitted.length - 1].x =
  70                 tilesFitted[indexFitted].x + 1;
  71             nsp.tilesFitted[nsp.tilesFitted.length - 1].y =
  72                 tilesFitted[indexFitted].y;
  73         } else { // ( checkingFits == 4 )
  74             nsp.tilesFitted[nsp.tilesFitted.length - 1].x =
  75                 tilesFitted[indexFitted].x - 1;
  76             nsp.tilesFitted[nsp.tilesFitted.length - 1].y =
  77                 tilesFitted[indexFitted].y;
  78         }
  79
  80         // copy grid and place newly fitted tile in sub-problem's
  81         // version of the grid
  82         nsp.workingGrid = workingGrid.copy();
  83         nsp.workingGrid.grid[nsp.tilesFitted[nsp.tilesFitted.length - 1].x]
  84                              [nsp.tilesFitted[nsp.tilesFitted.length - 1].y] =
  85                                  nsp.tilesFitted.length - 1;
  86
  87         nsp.highScore      = highScore;
  88
  89         /*
  90         System.printString( "-----------new sub-problem------------\n" );
  91         //System.printString( "raw grid\n" );
  92         //nsp.workingGrid.printGridRaw();
  93         System.printString( "tiles fitted:\n" );
  94         nsp.printTileArray( nsp.tilesFitted );
  95         System.printString( "tiles to fit:\n" );
  96         nsp.printTileArray( nsp.tilesToFit );
  97         //System.printString( "the nice grid:\n" );
  98         //nsp.workingGrid.printGrid( nsp.tilesFitted );
  99         System.printString( "nsp.indexToFit: " );
 100         System.printInt( nsp.indexToFit );
 101         System.printString( "\n" );
 102         System.printString( "nsp.indexFitted: " );
 103         System.printInt( nsp.indexFitted );
 104         System.printString( "\n" );
 105         System.printString( "-----------end sub-problem------------\n" );
 106          */
 107     }
 108
 109     public void scoreWorkingGrid() {
 110         highScore = 0;
 111         for( int i = 0; i < tilesFitted.length; ++i ) {
 112             Tile tileToScore = tilesFitted[i];
 113             // add those face values that are not adjacent to other face
 114             // N
 115             if(this.workingGrid.grid[tileToScore.x][tileToScore.y-1] == -1) {
 116                 highScore += tileToScore.n;
 117             }
 118             // S
 119             if(this.workingGrid.grid[tileToScore.x][tileToScore.y+1] == -1) {
 120                 highScore += tileToScore.s;
 121             }
 122             // E
 123             if(this.workingGrid.grid[tileToScore.x+1][tileToScore.y] == -1) {
 124                 highScore += tileToScore.e;
 125             }
 126             // W
 127             if(this.workingGrid.grid[tileToScore.x-1][tileToScore.y] == -1) {
 128                 highScore += tileToScore.w;
 129             }
 130         }
 131     }
 132
 133     public int highestScore() {
 134         int score = 0;
 135
 136         if( this.tilesToFit.length == 0 ){
 137             scoreWorkingGrid();
 138             score = this.highScore;
 139         } else {
 140             while(indexToFit != tilesToFit.length) {
 141                 if( workingGrid.validFitNorth(tilesToFit [indexToFit], tilesFitted[indexFitted], tilesFitted ) ) {
 142                     //System.printString( "North: \n" );
 143                     SubProblem newSP = new SubProblem();
 144                     initializeSubProblem( newSP, 1 );
 145                     int temp = newSP.highestScore();
 146                     if(score < temp) {
 147                         score = temp;
 148                     }
 149                     //System.printString( "match! new a SubProblem\n" );
 150                 }
 151
 152                 if( workingGrid.validFitSouth(tilesToFit [indexToFit], tilesFitted[indexFitted], tilesFitted ) ) {
 153                     //System.printString( "South: \n" );
 154                     SubProblem newSP = new SubProblem();
 155                     initializeSubProblem( newSP, 2 );
 156                     int temp = newSP.highestScore();
 157                     if(score < temp) {
 158                         score = temp;
 159                     }
 160                     //System.printString( "match! new a SubProblem\n" );
 161                 }
 162
 163                 if( workingGrid.validFitEast(tilesToFit [indexToFit], tilesFitted[indexFitted], tilesFitted ) ) {
 164                     //System.printString( "East: \n" );
 165                     SubProblem newSP = new SubProblem();
 166                     initializeSubProblem( newSP, 3 );
 167                     int temp = newSP.highestScore();
 168                     if(score < temp) {
 169                         score = temp;
 170                     }
 171                     //System.printString( "match! new a SubProblem\n" );
 172                 }
 173
 174                 if( workingGrid.validFitWest(tilesToFit [indexToFit], tilesFitted[indexFitted], tilesFitted ) ) {
 175                     //System.printString( "West: \n" );
 176                     SubProblem newSP = new SubProblem();
 177                     initializeSubProblem( newSP, 4 );
 178                     int temp = newSP.highestScore();
 179                     if(score < temp) {
 180                         score = temp;
 181                     }
 182                     //System.printString( "match! new a SubProblem\nSpawn finished! Go on find new fits.\n" );
 183                 }
 184
 185                 incrementIndices();
 186             }
 187         }
 188
 189         return score;
 190     }
 191
 192     public void printTileArray( Tile tiles[] ) {
 193         for( int i = 0; i < tiles.length; ++i ) {
 194             tiles[i].printRow0();
 195             System.printString( "  " );
 196         }
 197         System.printString("\n");
 198
 199         for( int i = 0; i < tiles.length; ++i ) {
 200             tiles[i].printRow1();
 201             System.printString( "  " );
 202         }
 203         System.printString("\n");
 204
 205         for( int i = 0; i < tiles.length; ++i ) {
 206             tiles[i].printRow2();
 207             System.printString( "  " );
 208         }
 209         System.printString("\n");
 210
 211         for( int i = 0; i < tiles.length; ++i ) {
 212             tiles[i].printRow3();
 213             System.printString( "  " );
 214         }
 215         System.printString("\n");
 216
 217         for( int i = 0; i < tiles.length; ++i ) {
 218             tiles[i].printRow4();
 219             System.printString( ", " );
 220         }
 221         System.printString("\n");
 222     }
 223 }