Robust/src/Benchmarks/TileSearch/Tag/TileSearch.java

   1 //////////////////////////////////////////////
   2 //
   3 //  tileSearch is a program to solve the
   4 //  following problem:
   5 //
   6 //  Find all arrangements of N square tiles
   7 //  that evaluate to the highest possible score.
   8 //
   9 //  Each tile has an integer on its north, south
  10 //  east and west faces.  Tiles faces may only
  11 //  be adjacent to other tile faces with the
  12 //  same number.
  13 //
  14 //  Tiles may not be rotated.
  15 //
  16 //  All tiles in the final arrangement must
  17 //  be adjacent to at least one other tile.
  18 //
  19 //  The score of an arrangement is the sum of
  20 //  all tile face values that are not adjacent
  21 //  to another face.
  22 //
  23 //  Example input:
  24 //
  25 //  +-----+  +-----+  +-----+  +-----+
  26 //  |  3  |  |  4  |  |  9  |  |  3  |
  27 //  |2   1|  |5   5|  |1   1|  |5   2|
  28 //  |  4  |  |  3  |  |  4  |  |  9  |
  29 //  +-----+, +-----+, +-----+, +-----+
  30 //
  31 //  A valid arrangement could be:
  32 //
  33 //  +-----++-----+
  34 //  |  3  ||  9  |
  35 //  |2   1||1   1|
  36 //  |  4  ||  4  |
  37 //  +-----++-----+
  38 //         +-----++-----+
  39 //         |  4  ||  3  |
  40 //         |5   5||5   2|
  41 //         |  3  ||  9  |
  42 //         +-----++-----+
  43 //
  44 //  Which scores:
  45 //
  46 //  3 + 9 + 1 + 3 + 2 + 9 + 3 + 5 + 4 + 2 = 41
  47 //
  48 //
  49 //  What is the highest possible score for a
  50 //  given tile input?
  51 //
  52 //////////////////////////////////////////////
  53
  54 task Startup( StartupObject s{ initialstate } )
  55 {
  56         //System.printString("Top of task Startup\n");
  57     SubProblem top = new SubProblem(){ findingNewFits, main };
  58
  59     /*
  60     top.tilesToFit     = new Tile[2];
  61     top.tilesToFit[0]  = new Tile(  3,  2,  3,  1 );
  62     top.tilesToFit[1]  = new Tile(  2, -4, -4, -4 );
  63
  64     top.tilesFitted    = new Tile[1];
  65     top.tilesFitted[0] = new Tile( -1, -1,  1, -1 );
  66      */
  67
  68
  69     top.tilesToFit     = new Tile[3];
  70     top.tilesToFit[0]  = new Tile(  2,  1, -1,  0 );
  71     top.tilesToFit[1]  = new Tile(  1,  3,  0, -1 );
  72     top.tilesToFit[2]  = new Tile( -1,  1, -1,  0 );
  73     //top.tilesToFit[3]  = new Tile(  1,  2,  2, -1 );
  74     //top.tilesToFit[4]  = new Tile(  2,  2,  1,  2 );
  75     //top.tilesToFit[5]  = new Tile( -1,  1,  0,  1 );
  76
  77     top.tilesFitted    = new Tile[1];
  78     top.tilesFitted[0] = new Tile(  1, -1,  0,  2 );
  79
  80
  81     top.indexToFit  = 0;
  82     top.indexFitted = 0;
  83     top.workingGrid =
  84 //      new TileGrid( (top.tilesToFit.length+1)*2 + 1 );
  85         new TileGrid( (top.tilesToFit.length+5)*2 + 4 );
  86
  87     // put first fitted tile in the middle of the grid
  88     top.tilesFitted[0].x = top.workingGrid.gridSize/2;
  89     top.tilesFitted[0].y = top.workingGrid.gridSize/2;
  90     top.workingGrid.grid[top.tilesFitted[0].x]
  91                          [top.tilesFitted[0].y] = 0;
  92
  93     top.highScore      = 0;
  94     GlobalCounter counter = new GlobalCounter() {Init};
  95     taskexit( s{ !initialstate } );
  96 }
  97
  98 task findNewFits(optional SubProblem sp{ findingNewFits }, GlobalCounter counter{ Init })
  99 {
 100         if(!isavailable(sp)) {
 101                 counter.partial = true;
 102                 taskexit( sp{ !findingNewFits } );
 103         }
 104         //System.printString("Top of task findNewFits\n");
 105     // if we have run out of iterations of the
 106     // findNewFits task, mark waitingForSubProblems
 107     if( sp.indexToFit == sp.tilesToFit.length )
 108     {
 109         //System.printString( "****************************************\nFinish iterating intermediate subproblem\n*********************************\n");
 110         taskexit( sp{ !findingNewFits } );
 111     }
 112
 113     //System.printString( "###################################\n" );
 114     //sp.workingGrid.printGrid( sp.tilesFitted );
 115     //System.printString( "Want to add this tile:\n" );
 116     //sp.tilesToFit[sp.indexToFit].printTile();
 117     //System.printString( "to this tile:\n" );
 118     //sp.tilesFitted[sp.indexFitted].printTile();
 119
 120     //System.printString( "+++++++++++++++++++++++++++++++++++\nchecking if there is a fit:\n" );
 121
 122     if( sp.workingGrid.validFitNorth(
 123             sp.tilesToFit [sp.indexToFit],
 124             sp.tilesFitted[sp.indexFitted],
 125             sp.tilesFitted ) )
 126     {
 127         //System.printString( "North: \n" );
 128         SubProblem newSP = null;
 129         if(sp.tilesToFit.length == 1 ) {
 130             newSP = new SubProblem() { !scored, leaf };
 131             ++counter.counter;
 132         } else {
 133             newSP = new SubProblem() { findingNewFits };
 134         }
 135         sp.initializeSubProblem( newSP, 1 );
 136         //System.printString( "match! new a SubProblem\n" );
 137     }
 138
 139     if( sp.workingGrid.validFitSouth(
 140             sp.tilesToFit [sp.indexToFit],
 141             sp.tilesFitted[sp.indexFitted],
 142             sp.tilesFitted ) )
 143     {
 144         //System.printString( "South: \n" );
 145         SubProblem newSP = null;
 146         if(sp.tilesToFit.length == 1) {
 147             newSP = new SubProblem() { !scored, leaf };
 148             ++counter.counter;
 149         } else {
 150             newSP = new SubProblem() { findingNewFits };
 151         }
 152         sp.initializeSubProblem( newSP, 2 );
 153         //System.printString( "match! new a SubProblem\n" );
 154     }
 155
 156     if( sp.workingGrid.validFitEast(
 157             sp.tilesToFit [sp.indexToFit],
 158             sp.tilesFitted[sp.indexFitted],
 159             sp.tilesFitted ) )
 160     {
 161         //System.printString( "East: \n" );
 162         SubProblem newSP = null;
 163         if(sp.tilesToFit.length == 1) {
 164             newSP = new SubProblem() { !scored, leaf };
 165             ++counter.counter;
 166         } else {
 167             newSP = new SubProblem() { findingNewFits };
 168         }
 169         sp.initializeSubProblem( newSP, 3 );
 170         //System.printString( "match! new a SubProblem\n" );
 171     }
 172
 173     if( sp.workingGrid.validFitWest(
 174             sp.tilesToFit [sp.indexToFit],
 175             sp.tilesFitted[sp.indexFitted],
 176             sp.tilesFitted ) )
 177     {
 178         //System.printString( "West:\n" );
 179         SubProblem newSP = null;
 180         if(sp.tilesToFit.length == 1) {
 181             newSP = new SubProblem() { !scored, leaf };
 182             ++counter.counter;
 183         } else {
 184             newSP = new SubProblem() { findingNewFits };
 185         }
 186         sp.initializeSubProblem( newSP, 4 );
 187         //System.printString( "match! new a SubProblem\nSpawn finished! Go on find new fits.\n" );
 188     }
 189
 190     //System.printString( "Spawn finished! Go on find new fits.\n++++++++++++++++++++++++++++++++++++++\n" );
 191
 192     // otherwise perform another iteration of
 193     // the findNewFits task
 194     sp.incrementIndices();
 195     taskexit( sp{ findingNewFits } );
 196 }
 197
 198 task scoreSubProbleam(SubProblem sp{ !scored && leaf }) {
 199         //System.printString("Top of task scoreSubProblem\n");
 200     sp.scoreWorkingGrid();
 201     taskexit(sp { scored });
 202 }
 203
 204 //check the highest score
 205 task findHighestScore(SubProblem pSp{ !scored && main }, optional SubProblem cSp{ scored && leaf }, GlobalCounter counter{ Init } ) {
 206         //System.printString("Top of task findHighestScore\n");
 207     --counter.counter;
 208     //System.printString( "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n" );
 209     //System.printString( "find highest score:\n" + counter.counter + "\n" );
 210     //System.printString( "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n" );
 211     if(isavailable(cSp)) {
 212         if(pSp.highScore < cSp.highScore) {
 213             pSp.highScore = cSp.highScore;
 214         }
 215         if((counter.partial == true) || (cSp.partial == true)) {
 216             pSp.partial = true;
 217         }
 218     } else {
 219         pSp.partial = true;
 220     }
 221     if(counter.counter == 0) {
 222         taskexit(pSp{ scored }, cSp{ !leaf });
 223     } else {
 224         taskexit(cSp{ !leaf });
 225     }
 226 }
 227
 228 task printHighestScore(SubProblem sp{ scored && main }) {
 229         //System.printString("Top of task printHighestScore\n");
 230  // if(isavailable(sp)) {
 231     if(sp.partial == true) {
 232         System.printString ( "Result may not be the best one due to some failure during execution!\n" );
 233     }
 234     System.printString( "Found highest score: " + sp.highScore + "\n" );
 235     /*  } else {
 236                 System.printString( "Fail to process\n" );
 237         }*/
 238     taskexit(sp{ !scored });
 239 }