Robust/src/Benchmarks/TileSearch/Java/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 public class TileSearch {
  55
  56     public static void main(String args[]) {
  57         SubProblem top = new SubProblem();
  58         /*
  59         top.tilesToFit     = new Tile[2];
  60         top.tilesToFit[0]  = new Tile(  3,  2,  3,  1 );
  61         top.tilesToFit[1]  = new Tile(  2, -4, -4, -4 );
  62
  63         top.tilesFitted    = new Tile[1];
  64         top.tilesFitted[0] = new Tile( -1, -1,  1, -1 );
  65          */
  66
  67
  68         top.tilesToFit     = new Tile[3];
  69         top.tilesToFit[0]  = new Tile(  2,  1, -1,  0 );
  70         top.tilesToFit[1]  = new Tile(  1,  3,  0, -1 );
  71         top.tilesToFit[2]  = new Tile( -1,  1, -1,  0 );
  72         //top.tilesToFit[3]  = new Tile(  1,  2,  2, -1 );
  73         //top.tilesToFit[4]  = new Tile(  2,  2,  1,  2 );
  74         //top.tilesToFit[5]  = new Tile( -1,  1,  0,  1 );
  75
  76         top.tilesFitted    = new Tile[1];
  77         top.tilesFitted[0] = new Tile(  1, -1,  0,  2 );
  78
  79         top.indexToFit  = 0;
  80         top.indexFitted = 0;
  81         top.workingGrid = new TileGrid( (top.tilesToFit.length+5)*2 + 4 ); //new TileGrid( (top.tilesToFit.length+1)*2 + 1 );
  82
  83         // put first fitted tile in the middle of the grid
  84         top.tilesFitted[0].x = top.workingGrid.gridSize/2;
  85         top.tilesFitted[0].y = top.workingGrid.gridSize/2;
  86         top.workingGrid.grid[top.tilesFitted[0].x]
  87                              [top.tilesFitted[0].y] = 0;
  88
  89         top.highScore = 0;
  90
  91         int score = top.highestScore();
  92         System.printString("Highest score: " + score + "\n");
  93     }
  94
  95 }