From 7cb79294b0246308e5e5421b53b447867316d537 Mon Sep 17 00:00:00 2001 From: jjenista Date: Wed, 2 Dec 2009 23:17:01 +0000 Subject: [PATCH] not put together yet, but nice to have a task benchmark that avoids any special features, such as optional keyword --- .../TileSearch/NoOptional/GlobalCounter.java | 10 + .../TileSearch/NoOptional/SubProblem.java | 168 ++++++ .../TileSearch/NoOptional/Tile.java | 481 ++++++++++++++++++ .../TileSearch/NoOptional/TileSearch.java | 266 ++++++++++ 4 files changed, 925 insertions(+) create mode 100644 Robust/src/Benchmarks/TileSearch/NoOptional/GlobalCounter.java create mode 100644 Robust/src/Benchmarks/TileSearch/NoOptional/SubProblem.java create mode 100644 Robust/src/Benchmarks/TileSearch/NoOptional/Tile.java create mode 100644 Robust/src/Benchmarks/TileSearch/NoOptional/TileSearch.java diff --git a/Robust/src/Benchmarks/TileSearch/NoOptional/GlobalCounter.java b/Robust/src/Benchmarks/TileSearch/NoOptional/GlobalCounter.java new file mode 100644 index 00000000..68f853e6 --- /dev/null +++ b/Robust/src/Benchmarks/TileSearch/NoOptional/GlobalCounter.java @@ -0,0 +1,10 @@ +public class GlobalCounter { + flag Init; + public int counter; + public boolean partial; + + public GlobalCounter() { + counter = 0; + partial = false; + } +} diff --git a/Robust/src/Benchmarks/TileSearch/NoOptional/SubProblem.java b/Robust/src/Benchmarks/TileSearch/NoOptional/SubProblem.java new file mode 100644 index 00000000..25795677 --- /dev/null +++ b/Robust/src/Benchmarks/TileSearch/NoOptional/SubProblem.java @@ -0,0 +1,168 @@ +public class SubProblem { + flag findingNewFits; + flag scored; + flag main; + flag leaf; + + public SubProblem(){ + partial = false; + } + + public Tile[] tilesToFit; + public Tile[] tilesFitted; + public TileGrid workingGrid; + + // these indices are into the respective + // tile arrays + public int indexToFit; + public int indexFitted; + + // this score represents the evaluation + // of every arrangement of this sub-problem's + // bestArrangements list + public int highScore; + + public boolean partial; + + public void incrementIndices() { + ++indexFitted; + if( indexFitted == tilesFitted.length ) { + indexFitted = 0; + ++indexToFit; + } + } + + public void initializeSubProblem( SubProblem nsp, int checkingFits ) { + nsp.tilesToFit = new Tile[tilesToFit.length - 1]; + nsp.indexToFit = 0; + + int j = 0; + for( int i = 0; i < tilesToFit.length; ++i ) { + // copy everything but the tile that + // is being moved to the fitted list + if( i != indexToFit ) { + nsp.tilesToFit[j] = tilesToFit[i].copy(); + ++j; + } + } + + nsp.tilesFitted = new Tile[tilesFitted.length + 1]; + nsp.tilesFitted[nsp.tilesFitted.length - 1] = tilesToFit[indexToFit].copy(); + nsp.indexFitted = 0; + for( int i = 0; i < tilesFitted.length; ++i ) { + nsp.tilesFitted[i] = tilesFitted[i].copy(); + // if((checkingFits == 1) || + // (checkingFits == 3)) { + nsp.tilesFitted[i].x = tilesFitted[i].x; + nsp.tilesFitted[i].y = tilesFitted[i].y; + // } + } + + // set fitted tiles position according to fit type + if( checkingFits == 1 ) { + nsp.tilesFitted[nsp.tilesFitted.length - 1].x = + tilesFitted[indexFitted].x; + nsp.tilesFitted[nsp.tilesFitted.length - 1].y = + tilesFitted[indexFitted].y - 1; + } else if( checkingFits == 2 ) { + nsp.tilesFitted[nsp.tilesFitted.length - 1].x = + tilesFitted[indexFitted].x; + nsp.tilesFitted[nsp.tilesFitted.length - 1].y = + tilesFitted[indexFitted].y + 1; + } else if( checkingFits == 3 ) { + nsp.tilesFitted[nsp.tilesFitted.length - 1].x = + tilesFitted[indexFitted].x + 1; + nsp.tilesFitted[nsp.tilesFitted.length - 1].y = + tilesFitted[indexFitted].y; + } else { // ( checkingFits == 4 ) + nsp.tilesFitted[nsp.tilesFitted.length - 1].x = + tilesFitted[indexFitted].x - 1; + nsp.tilesFitted[nsp.tilesFitted.length - 1].y = + tilesFitted[indexFitted].y; + } + + // copy grid and place newly fitted tile in sub-problem's + // version of the grid + nsp.workingGrid = workingGrid.copy(); + nsp.workingGrid.grid[nsp.tilesFitted[nsp.tilesFitted.length - 1].x] + [nsp.tilesFitted[nsp.tilesFitted.length - 1].y] = + nsp.tilesFitted.length - 1; + + nsp.highScore = highScore; + + /* + System.printString( "-----------new sub-problem------------\n" ); + //System.printString( "raw grid\n" ); + //nsp.workingGrid.printGridRaw(); + System.printString( "tiles fitted:\n" ); + nsp.printTileArray( nsp.tilesFitted ); + System.printString( "tiles to fit:\n" ); + nsp.printTileArray( nsp.tilesToFit ); + //System.printString( "the nice grid:\n" ); + //nsp.workingGrid.printGrid( nsp.tilesFitted ); + System.printString( "nsp.indexToFit: " ); + System.printInt( nsp.indexToFit ); + System.printString( "\n" ); + System.printString( "nsp.indexFitted: " ); + System.printInt( nsp.indexFitted ); + System.printString( "\n" ); + System.printString( "-----------end sub-problem------------\n" ); + */ + } + + public void scoreWorkingGrid() { + highScore = 0; + for( int i = 0; i < tilesFitted.length; ++i ) { + Tile tileToScore = tilesFitted[i]; + // add those face values that are not adjacent to other face + // N + if(this.workingGrid.grid[tileToScore.x][tileToScore.y-1] == -1) { + highScore += tileToScore.n; + } + // S + if(this.workingGrid.grid[tileToScore.x][tileToScore.y+1] == -1) { + highScore += tileToScore.s; + } + // E + if(this.workingGrid.grid[tileToScore.x+1][tileToScore.y] == -1) { + highScore += tileToScore.e; + } + // W + if(this.workingGrid.grid[tileToScore.x-1][tileToScore.y] == -1) { + highScore += tileToScore.w; + } + } + } + + public printTileArray( Tile tiles[] ) { + for( int i = 0; i < tiles.length; ++i ) { + tiles[i].printRow0(); + System.printString( " " ); + } + System.printString( "\n" ); + + for( int i = 0; i < tiles.length; ++i ) { + tiles[i].printRow1(); + System.printString( " " ); + } + System.printString( "\n" ); + + for( int i = 0; i < tiles.length; ++i ) { + tiles[i].printRow2(); + System.printString( " " ); + } + System.printString( "\n" ); + + for( int i = 0; i < tiles.length; ++i ) { + tiles[i].printRow3(); + System.printString( " " ); + } + System.printString( "\n" ); + + for( int i = 0; i < tiles.length; ++i ) { + tiles[i].printRow4(); + System.printString( ", " ); + } + System.printString( "\n" ); + } +} diff --git a/Robust/src/Benchmarks/TileSearch/NoOptional/Tile.java b/Robust/src/Benchmarks/TileSearch/NoOptional/Tile.java new file mode 100644 index 00000000..211c229d --- /dev/null +++ b/Robust/src/Benchmarks/TileSearch/NoOptional/Tile.java @@ -0,0 +1,481 @@ +public class Tile { + public Tile( int n, int s, int e, int w ) { + this.n = n; + this.s = s; + this.e = e; + this.w = w; + } + + // value of tile faces + int n, s, e, w; + + public Tile copy() { + Tile t = new Tile( n, s, e, w ); + return t; + } + + public void printTile() { + printRow0(); System.printString( "\n" ); + printRow1(); System.printString( "\n" ); + printRow2(); System.printString( "\n" ); + printRow3(); System.printString( "\n" ); + printRow4(); System.printString( "\n" ); + } + + public void printRow0() { + System.printString ( "+-------+" ); + } + + public printRow1() { + if( n < 0 ) { + System.printString( "| " ); + } else { + System.printString( "| " ); + } + System.printInt( n ); + System.printString( " |" ); + } + + public void printRow2() { + if( w < 0 ) { + System.printString( "|" ); + } else { + System.printString( "| " ); + } + System.printInt ( w ); + if( e < 0 ) { + System.printString( " " ); + } else { + System.printString( " " ); + } + System.printInt ( e ); + System.printString ( " |" ); + } + + public void printRow3() { + if( s < 0 ) { + System.printString( "| " ); + } else { + System.printString( "| " ); + } + System.printInt ( s ); + System.printString ( " |" ); + } + + public void printRow4() { + System.printString ( "+-------+" ); + } + + // position in the grid + // this information is also represented by + // the indices into a TileGrid, but it is + // convenient to duplicate it + int x, y; +} + +public class TileGrid { + public TileGrid( int gridSize ) { + // make the grid size big enough + // such that starting with a tile + // in the middle and placing tiles + // in one direction, that the grid + // is big enough without requiring + // bound-checking + this.gridSize = gridSize; + + grid = new int[gridSize][]; + for( int i = 0; i < gridSize; ++i ) { + grid[i] = new int[gridSize]; + for( int j = 0; j < gridSize; ++j ) { + // use -1 to indicate no tile + grid[i][j] = -1; + } + } + } + + public int gridSize; + + // each element of this grid is an integer + // index into a tilesFitted array -- not + // very good object-oriented style! + public int grid[][]; + + public TileGrid copy() { + TileGrid tg = new TileGrid( gridSize ); + + for( int i = 0; i < gridSize; ++i ) { + for( int j = 0; j < gridSize; ++j ) { + tg.grid[i][j] = grid[i][j]; + } + } + + return tg; + } + + public boolean anyValidFit( Tile tileToFit, + Tile tileFitted, + Tile[] tilesFitted ) { + //System.printString( "top fo anyValidFit\n" ); + return validFitNorth( tileToFit, tileFitted, tilesFitted ) || + validFitSouth( tileToFit, tileFitted, tilesFitted ) || + validFitEast ( tileToFit, tileFitted, tilesFitted ) || + validFitWest ( tileToFit, tileFitted, tilesFitted ); + } + + public boolean validFitNorth( Tile tileToFit, + Tile tileFitted, + Tile[] tilesFitted ) { + //System.printString( "top of validFitNorth\n" ); + //System.printString( "tileToFit.s:" + tileToFit.s + "\n" ); + //System.printString( "tileFitted.n:" + tileFitted.n + "\n" ); + + // when the tileToFit's S matches fitted N... + if( tileToFit.s == tileFitted.n ) { + tileToFit.x = tileFitted.x; + tileToFit.y = tileFitted.y - 1; + + /* + System.printString( "Check if can put it here\n" ); + System.printString( "x: " + tileToFit.x + "; y: " + tileToFit.y + "\n" ); + System.printInt( grid[tileToFit.x][tileToFit.y] ); + System.printString( "\n" ); + System.printInt( grid[tileToFit.x][tileToFit.y-1] ); + if(grid[tileToFit.x][tileToFit.y-1] != -1) { + System.printString( " s:" + tilesFitted[grid[tileToFit.x][tileToFit.y-1]].s ); + } + System.printString( "\n" ); + System.printInt( grid[tileToFit.x+1][tileToFit.y] ); + if(grid[tileToFit.x+1][tileToFit.y] != -1) { + System.printString( " w:" + tilesFitted[grid[tileToFit.x+1][tileToFit.y]].w ); + } + System.printString( "\n" ); + System.printInt( grid[tileToFit.x-1][tileToFit.y] ); + if(grid[tileToFit.x-1][tileToFit.y] != -1) { + System.printString( " e:" + tilesFitted[grid[tileToFit.x-1][tileToFit.y]].e ); + } + System.printString( "\n" ); + */ + // check that the place to fit is empty AND + // (place to fit + N is empty or matches) AND + // (place to fit + E is empty or matches) AND + // (place to fit + W is empty or matches) + if( grid[tileToFit.x][tileToFit.y] == -1 && + + (grid[tileToFit.x][tileToFit.y-1] == -1 || + tilesFitted[grid[tileToFit.x][tileToFit.y-1]].s == tileToFit.n) && + + (grid[tileToFit.x+1][tileToFit.y] == -1 || + tilesFitted[grid[tileToFit.x+1][tileToFit.y]].w == tileToFit.e) && + + (grid[tileToFit.x-1][tileToFit.y] == -1 || + tilesFitted[grid[tileToFit.x-1][tileToFit.y]].e == tileToFit.w) ) { + return true; + } + } + + return false; + } + + public boolean validFitSouth( Tile tileToFit, + Tile tileFitted, + Tile[] tilesFitted ) { + //System.printString( "top of validFitSouth\n" ); + + // when the tileToFit's N matches fitted S... + if( tileToFit.n == tileFitted.s ) { + tileToFit.x = tileFitted.x; + tileToFit.y = tileFitted.y + 1; + + // check that the place to fit is empty AND + // (place to fit + S is empty or matches) AND + // (place to fit + E is empty or matches) AND + // (place to fit + W is empty or matches) + if( grid[tileToFit.x][tileToFit.y] == -1 && + + (grid[tileToFit.x][tileToFit.y+1] == -1 || + tilesFitted[grid[tileToFit.x][tileToFit.y+1]].n == tileToFit.s) && + + (grid[tileToFit.x+1][tileToFit.y] == -1 || + tilesFitted[grid[tileToFit.x+1][tileToFit.y]].w == tileToFit.e) && + + (grid[tileToFit.x-1][tileToFit.y] == -1 || + tilesFitted[grid[tileToFit.x-1][tileToFit.y]].e == tileToFit.w) ) { + return true; + } + } + + return false; + } + + public boolean validFitEast( Tile tileToFit, + Tile tileFitted, + Tile[] tilesFitted ) { + //System.printString( "top of validFitEast\n" ); + + // when the tileToFit's W matches fitted E... + if( tileToFit.w == tileFitted.e ) { + tileToFit.x = tileFitted.x + 1; + tileToFit.y = tileFitted.y; + + /* + System.printString( "raw grid:\n" ); + printGridRaw(); + + System.printString( "x: " ); + System.printInt( tileToFit.x ); + System.printString( "\n" ); + + System.printString( "y: " ); + System.printInt( tileToFit.y ); + System.printString( "\n" ); + + System.printString( "tile index 1: " ); + System.printInt( grid[tileToFit.x][tileToFit.y-1] ); + System.printString( "\n" ); + + System.printString( "tile index 2: " ); + System.printInt( grid[tileToFit.x][tileToFit.y+1] ); + System.printString( "\n" ); + + System.printString( "tile index 3: " ); + System.printInt( grid[tileToFit.x+1][tileToFit.y] ); + System.printString( "\n" ); + */ + + // check that the place to fit is empty AND + // (place to fit + N is empty or matches) AND + // (place to fit + S is empty or matches) AND + // (place to fit + E is empty or matches) + if( grid[tileToFit.x][tileToFit.y] == -1 && + + ( grid[tileToFit.x][tileToFit.y-1] == -1 || + tilesFitted[grid[tileToFit.x][tileToFit.y-1]].s == tileToFit.n) && + + ( grid[tileToFit.x][tileToFit.y+1] == -1 || + tilesFitted[grid[tileToFit.x][tileToFit.y+1]].n == tileToFit.s) && + + ( grid[tileToFit.x+1][tileToFit.y] == -1 || + tilesFitted[grid[tileToFit.x+1][tileToFit.y]].w == tileToFit.e) ) { + return true; + } + } + + return false; + } + + public boolean validFitWest( Tile tileToFit, + Tile tileFitted, + Tile[] tilesFitted ) { + //System.printString( "top of validFitWest\n" ); + + // when the tileToFit's E matches fitted W... + if( tileToFit.e == tileFitted.w ) { + tileToFit.x = tileFitted.x - 1; + tileToFit.y = tileFitted.y; + + // check that the place to fit is empty AND + // (place to fit + N is empty or matches) AND + // (place to fit + S is empty or matches) AND + // (place to fit + W is empty or matches) + if( grid[tileToFit.x][tileToFit.y] == -1 && + + (grid[tileToFit.x][tileToFit.y-1] == -1 || + tilesFitted[grid[tileToFit.x][tileToFit.y-1]].s == tileToFit.n) && + + (grid[tileToFit.x][tileToFit.y+1] == -1 || + tilesFitted[grid[tileToFit.x][tileToFit.y+1]].n == tileToFit.s) && + + (grid[tileToFit.x-1][tileToFit.y] == -1 || + tilesFitted[grid[tileToFit.x-1][tileToFit.y]].e == tileToFit.w) ) { + return true; + } + } + + return false; + } + + + // indices to represent the bounding + // box of tiles placed in the grid + public int x0, y0, x1, y1; + + public void printGridRaw() { + for( int j = 0; j < gridSize; ++j ) { + for( int i = 0; i < gridSize; ++i ) { + System.printInt( grid[i][j] ); + + if( grid[i][j] < 0 ) { + System.printString( " " ); + } + else { + System.printString( " " ); + } + } + System.printString( "\n" ); + } + } + + public void printGrid( Tile[] tilesFitted ) { + /* + System.printString( "Printing a grid...\n" ); + printGridRaw(); + + computeBoundingBox(); + + for( int j = y0; j <= y1; ++j ) + { + for( int i = x0; i <= x1; ++i ) + { + System.printString( "i=" ); + System.printInt( i ); + System.printString( ", j=" ); + System.printInt( j ); + //System.printString( "\n" ); + + if( grid[i][j] == -1 ) { + printEmptyTileRow(); + } else { + tilesFitted[grid[i][j]].printRow0(); + } + } + System.printString( "\n" ); + + for( int i = x0; i <= x1; ++i ) + { + System.printString( "i=" ); + System.printInt( i ); + System.printString( ", j=" ); + System.printInt( j ); + //System.printString( "\n" ); + + if( grid[i][j] == -1 ) { + printEmptyTileRow(); + } else { + tilesFitted[grid[i][j]].printRow1(); + } + } + System.printString( "\n" ); + + for( int i = x0; i <= x1; ++i ) + { + System.printString( "i=" ); + System.printInt( i ); + System.printString( ", j=" ); + System.printInt( j ); + //System.printString( "\n" ); + + if( grid[i][j] == -1 ) { + printEmptyTileRow(); + } else { + tilesFitted[grid[i][j]].printRow2(); + } + } + System.printString( "\n" ); + + for( int i = x0; i <= x1; ++i ) + { + System.printString( "i=" ); + System.printInt( i ); + System.printString( ", j=" ); + System.printInt( j ); + //System.printString( "\n" ); + + if( grid[i][j] == -1 ) { + printEmptyTileRow(); + } else { + tilesFitted[grid[i][j]].printRow3(); + } + } + System.printString( "\n" ); + + for( int i = x0; i <= x1; ++i ) + { + System.printString( "i=" ); + System.printInt( i ); + System.printString( ", j=" ); + System.printInt( j ); + //System.printString( "\n" ); + + if( grid[i][j] == -1 ) { + printEmptyTileRow(); + } else { + tilesFitted[grid[i][j]].printRow4(); + } + } + System.printString( "\n" ); + } + */ + } + + public void printEmptyTileRow() { + System.printString( " " ); + } + + public void computeBoundingBox() { + System.printString( "Starting computeBoundingBox\n" ); + + int i = 0; + while( i < gridSize*gridSize ) { + int a = i % gridSize; + int b = i / gridSize; + + if( grid[b][a] != -1 ) { + x0 = b; + + // this statement is like "break" + i = gridSize*gridSize; + } + + ++i; + } + + i = 0; + while( i < gridSize*gridSize ) { + int a = i % gridSize; + int b = i / gridSize; + + if( grid[a][b] != -1 ) { + y0 = b; + + // this statement is like "break" + i = gridSize*gridSize; + } + + ++i; + } + + i = 0; + while( i < gridSize*gridSize ) { + int a = i % gridSize; + int b = i / gridSize; + int c = gridSize - 1 - b; + + if( grid[c][a] != -1 ) { + x1 = c; + + // this statement is like "break" + i = gridSize*gridSize; + } + + ++i; + } + + i = 0; + while( i < gridSize*gridSize ) { + int a = i % gridSize; + int b = i / gridSize; + int c = gridSize - 1 - b; + + if( grid[a][c] != -1 ) { + y1 = c; + + // this statement is like "break" + i = gridSize*gridSize; + } + + ++i; + } + + System.printString( "Ending computeBoundingBox\n" ); + } +} diff --git a/Robust/src/Benchmarks/TileSearch/NoOptional/TileSearch.java b/Robust/src/Benchmarks/TileSearch/NoOptional/TileSearch.java new file mode 100644 index 00000000..1bb3d41f --- /dev/null +++ b/Robust/src/Benchmarks/TileSearch/NoOptional/TileSearch.java @@ -0,0 +1,266 @@ +////////////////////////////////////////////// +// +// tileSearch is a program to solve the +// following problem: +// +// Find all arrangements of N square tiles +// that evaluate to the highest possible score. +// +// Each tile has an integer on its north, south +// east and west faces. Tiles faces may only +// be adjacent to other tile faces with the +// same number. +// +// Tiles may not be rotated. +// +// All tiles in the final arrangement must +// be adjacent to at least one other tile. +// +// The score of an arrangement is the sum of +// all tile face values that are not adjacent +// to another face. +// +// Example input: +// +// +-----+ +-----+ +-----+ +-----+ +// | 3 | | 4 | | 9 | | 3 | +// |2 1| |5 5| |1 1| |5 2| +// | 4 | | 3 | | 4 | | 9 | +// +-----+, +-----+, +-----+, +-----+ +// +// A valid arrangement could be: +// +// +-----++-----+ +// | 3 || 9 | +// |2 1||1 1| +// | 4 || 4 | +// +-----++-----+ +// +-----++-----+ +// | 4 || 3 | +// |5 5||5 2| +// | 3 || 9 | +// +-----++-----+ +// +// Which scores: +// +// 3 + 9 + 1 + 3 + 2 + 9 + 3 + 5 + 4 + 2 = 41 +// +// +// What is the highest possible score for a +// given tile input? +// +////////////////////////////////////////////// + +task Startup( StartupObject s{ initialstate } ) +{ + //System.printString("Top of task Startup\n"); + SubProblem top = new SubProblem(){ findingNewFits, main }; + + + // use this initialization to solve the above example + // +-----+ +-----+ +-----+ +-----+ + // | 3 | | 4 | | 9 | | 3 | + // |2 1| |5 5| |1 1| |5 2| + // | 4 | | 3 | | 4 | | 9 | + // +-----+, +-----+, +-----+, +-----+ + top.tilesToFit = new Tile[3]; + top.tilesToFit[0] = new Tile( 3, 4, 1, 2 ); + top.tilesToFit[1] = new Tile( 4, 3, 5, 5 ); + top.tilesToFit[2] = new Tile( 9, 4, 1, 1 ); + + top.tilesFitted = new Tile[1]; + top.tilesFitted[0] = new Tile( 3, 9, 2, 5 ); + + + + /* + top.tilesToFit = new Tile[2]; + top.tilesToFit[0] = new Tile( 3, 2, 3, 1 ); + top.tilesToFit[1] = new Tile( 2, -4, -4, -4 ); + + top.tilesFitted = new Tile[1]; + top.tilesFitted[0] = new Tile( -1, -1, 1, -1 ); + */ + + /* + top.tilesToFit = new Tile[3]; + top.tilesToFit[0] = new Tile( 2, 1, -1, 0 ); + top.tilesToFit[1] = new Tile( 1, 3, 0, -1 ); + top.tilesToFit[2] = new Tile( -1, 1, -1, 0 ); + */ + + //top.tilesToFit[3] = new Tile( 1, 2, 2, -1 ); + //top.tilesToFit[4] = new Tile( 2, 2, 1, 2 ); + //top.tilesToFit[5] = new Tile( -1, 1, 0, 1 ); + + /* + top.tilesFitted = new Tile[1]; + top.tilesFitted[0] = new Tile( 1, -1, 0, 2 ); + */ + + top.indexToFit = 0; + top.indexFitted = 0; + top.workingGrid = +// new TileGrid( (top.tilesToFit.length+1)*2 + 1 ); + new TileGrid( (top.tilesToFit.length+5)*2 + 4 ); + + // put first fitted tile in the middle of the grid + top.tilesFitted[0].x = top.workingGrid.gridSize/2; + top.tilesFitted[0].y = top.workingGrid.gridSize/2; + top.workingGrid.grid[top.tilesFitted[0].x] + [top.tilesFitted[0].y] = 0; + + top.highScore = 0; + GlobalCounter counter = new GlobalCounter() {Init}; + taskexit( s{ !initialstate } ); +} + +task findNewFits(/*optional*/ SubProblem sp{ findingNewFits }, GlobalCounter counter{ Init }) +{ + /* + if(!isavailable(sp)) { + counter.partial = true; + taskexit( sp{ !findingNewFits } ); + } + */ + + //System.printString("Top of task findNewFits\n"); + // if we have run out of iterations of the + // findNewFits task, mark waitingForSubProblems + if( sp.indexToFit == sp.tilesToFit.length ) + { + //System.printString( "****************************************\nFinish iterating intermediate subproblem\n*********************************\n"); + taskexit( sp{ !findingNewFits } ); + } + + //System.printString( "###################################\n" ); + //sp.workingGrid.printGrid( sp.tilesFitted ); + //System.printString( "Want to add this tile:\n" ); + //sp.tilesToFit[sp.indexToFit].printTile(); + //System.printString( "to this tile:\n" ); + //sp.tilesFitted[sp.indexFitted].printTile(); + + //System.printString( "+++++++++++++++++++++++++++++++++++\nchecking if there is a fit:\n" ); + + if( sp.workingGrid.validFitNorth( + sp.tilesToFit [sp.indexToFit], + sp.tilesFitted[sp.indexFitted], + sp.tilesFitted ) ) + { + //System.printString( "North: \n" ); + SubProblem newSP = null; + if(sp.tilesToFit.length == 1 ) { + newSP = new SubProblem() { !scored, leaf }; + ++counter.counter; + } else { + newSP = new SubProblem() { findingNewFits }; + } + sp.initializeSubProblem( newSP, 1 ); + //System.printString( "match! new a SubProblem\n" ); + } + + if( sp.workingGrid.validFitSouth( + sp.tilesToFit [sp.indexToFit], + sp.tilesFitted[sp.indexFitted], + sp.tilesFitted ) ) + { + //System.printString( "South: \n" ); + SubProblem newSP = null; + if(sp.tilesToFit.length == 1) { + newSP = new SubProblem() { !scored, leaf }; + ++counter.counter; + } else { + newSP = new SubProblem() { findingNewFits }; + } + sp.initializeSubProblem( newSP, 2 ); + //System.printString( "match! new a SubProblem\n" ); + } + + if( sp.workingGrid.validFitEast( + sp.tilesToFit [sp.indexToFit], + sp.tilesFitted[sp.indexFitted], + sp.tilesFitted ) ) + { + //System.printString( "East: \n" ); + SubProblem newSP = null; + if(sp.tilesToFit.length == 1) { + newSP = new SubProblem() { !scored, leaf }; + ++counter.counter; + } else { + newSP = new SubProblem() { findingNewFits }; + } + sp.initializeSubProblem( newSP, 3 ); + //System.printString( "match! new a SubProblem\n" ); + } + + if( sp.workingGrid.validFitWest( + sp.tilesToFit [sp.indexToFit], + sp.tilesFitted[sp.indexFitted], + sp.tilesFitted ) ) + { + //System.printString( "West:\n" ); + SubProblem newSP = null; + if(sp.tilesToFit.length == 1) { + newSP = new SubProblem() { !scored, leaf }; + ++counter.counter; + } else { + newSP = new SubProblem() { findingNewFits }; + } + sp.initializeSubProblem( newSP, 4 ); + //System.printString( "match! new a SubProblem\nSpawn finished! Go on find new fits.\n" ); + } + + //System.printString( "Spawn finished! Go on find new fits.\n++++++++++++++++++++++++++++++++++++++\n" ); + + // otherwise perform another iteration of + // the findNewFits task + sp.incrementIndices(); + taskexit( sp{ findingNewFits } ); +} + +task scoreSubProbleam(SubProblem sp{ !scored && leaf }) { + //System.printString("Top of task scoreSubProblem\n"); + sp.scoreWorkingGrid(); + taskexit(sp { scored }); +} + +//check the highest score +task findHighestScore(SubProblem pSp{ !scored && main }, /*optional*/ SubProblem cSp{ scored && leaf }, GlobalCounter counter{ Init } ) { + //System.printString("Top of task findHighestScore\n"); + --counter.counter; + //System.printString( "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n" ); + //System.printString( "find highest score:\n" + counter.counter + "\n" ); + //System.printString( "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n" ); + + /* + if(isavailable(cSp)) { + if(pSp.highScore < cSp.highScore) { + pSp.highScore = cSp.highScore; + } + if((counter.partial == true) || (cSp.partial == true)) { + pSp.partial = true; + } + } else { + pSp.partial = true; + } + */ + + if(counter.counter == 0) { + taskexit(pSp{ scored }, cSp{ !leaf }); + } else { + taskexit(cSp{ !leaf }); + } +} + +task printHighestScore(SubProblem sp{ scored && main }) { + //System.printString("Top of task printHighestScore\n"); + // if(isavailable(sp)) { + if(sp.partial == true) { + System.printString ( "Result may not be the best one due to some failure during execution!\n" ); + } + System.printString( "Found highest score: " + sp.highScore + "\n" ); + /* } else { + System.printString( "Fail to process\n" ); + }*/ + taskexit(sp{ !scored }); +} -- 2.34.1