Board.java

/**
The top-left corner is (0,0) = 0.
An empty cell is represented by the number 0.
The board is stored column-wise up-down in a single array of size width*height,
where index 0 through height-1 represent the first left-most column.
If i is the index in the array, then the corresponding grid-coordinate is (x,y) = (i/height, i%height).
*/
import java.util.*;
import static java.util.Arrays.*;

public class Board
{
	//Width and height of the board. Number of colors.
	public static final int width = 15, height = 15, colors = 5;

	//Short for width and height.
	private static final int xs = width, ys = height;

	//A zero-filled array of the size of a column.
	private static final int[] zero = new int[ys];

	/*** <Update: When blocks should fall> ***/
	// Takes a board where blocks have been removed,
	// and applies the blocks-fall-columns-shift-left logic.
	public static void redBoard(final int[] board)
	{
		for(int i = 0; i<xs*ys; i+=ys) redCol(board,i);
		redRow(board);
	}
	// Makes the blocks in the column with its top-square at index off fall.
	private static void redCol(final int[] board, final int off)
	{
		for(int i = off+ys-1, cnt = 0; i>=off; i--)
			if(board[i]==0) ++cnt;
			else if(cnt>0){ board[i+cnt] = board[i]; board[i] = 0; }
	}
	// Makes the columns of the board shift left.
	private static void redRow(final int[] board)
	{
		for(int i = 0, cnt = 0; i<xs; i++)
			if(board[i*ys+ys-1]==0) ++cnt;
			else if(cnt>0){ System.arraycopy(board,i*ys,board,ys*(i-cnt),ys); System.arraycopy(zero,0,board,i*ys,ys); }
	}
	/*** </Update> ***/

	/*** <Move: To perform a move> ***/
	// Takes the board and applies the move of removing the group containing index 'i' of size 'area'.
	// If the original score is given as input, then the new score is returned.
	// If input score=0 then the score of the move is returned.
	public static int doMove(final int[] board, final int i, final int area, int score)
	{
		dfsKill(board,i/ys,i%ys,board[i]);
		score += (area-2)*(area-2);
		redBoard(board);
		return score;
	}
	// Eliminates the group of color prv conatining the grid position (x,y).
	// (No other game logic is applied, i.e. no blocks or columns will move.)
	private static void dfsKill(final int[] board, final int x, final int y, final int prv)
	{
		if(x<0 || x>=xs || y<0 || y>=ys || prv!=board[x*ys+y]) return;
		board[x*ys+y] = 0;
		dfsKill(board,x-1,y,prv);
		dfsKill(board,x+1,y,prv);
		dfsKill(board,x,y-1,prv);
		dfsKill(board,x,y+1,prv);
	}
	// Same as dfsKill(), but returns the number of blocks eliminated.
	private static int dfsKill2(final int[] board, final int x, final int y, final int prv)
	{
		if(x<0 || x>=xs || y<0 || y>=ys || prv!=board[x*ys+y]) return 0;
		int sum = 1;
		board[x*ys+y] = 0;
		sum += dfsKill2(board,x-1,y,prv);
		sum += dfsKill2(board,x+1,y,prv);
		sum += dfsKill2(board,x,y-1,prv);
		sum += dfsKill2(board,x,y+1,prv);
		return sum;
	}
	/*** </Move> ***/

	/*** <Move findig> ***/
	// Returns an array of available moves (using VS-pruning) on the board.
	// The move are stored as tuples in the array, i.e. the j:th move occupies position 2*j and 2*j+1.
	// Position 2*j contains the index of a block of a removable group, 2*j+1 contains the number of blocks in this group.
	public static int[] getMoves(final int[] board)
	{
		return copyOf(mvs, moves(board));
	}
	// Same as getMoves() but applies no VS-pruning.
	public static int[] getRawMoves(final int[] board)
	{
		return copyOf(mvs, rawMoves(board));
	}

	//An array where moves generated by moves() are temporarily stored.
	public static final int[] mvs = new int[xs*ys];

	//The number of groups of size 1, as of the latest call to moves().
	public static int onecnt;

	// A method for generating moves on the format described by getMoves().
	// The moves are stored in the publicly available mvs-arrays.
	// The method returns the number of available moves times 2, i.e. the valid part of the mvs-array.
	public static int moves(final int[] board)
	{
		int nxt = onecnt = 0;
		for(int x = 0, pos = 0; x<xs; x++)
			for(int y = 0; y<ys; y++, pos++)
				if(board[pos]>0)
				{
					mvs[nxt++] = pos;
					if((mvs[nxt++] = area(board,x,y,board[pos]))==1){ nxt -= 2; ++onecnt; }
					else if(y+mvs[nxt-1]<ys)
					{
						final int area = mvs[nxt-1], color = board[pos];
						boolean prunable = (y==0 || board[pos-1]==0) && color==board[pos+area-1];
						for(int i = pos+1; prunable && i<pos+area-1; i++) prunable &= color==board[i];
						if(prunable) nxt -= 2; //Only if alternatives exists.
					}
				}
		for(int i = 0; i<xs*ys; i++) board[i] = -board[i];
		return nxt;
	}
	// Like moves() but omits moves which removes groups of color tabu,
	// unless no other moves exist, then this method is equivalent to moves().
	public static int tabuMoves(final int[] board, final int tabu)
	{
		int nxt = onecnt = 0;
		for(int x = 0, pos = 0; x<xs; x++)
			for(int y = 0; y<ys; y++, pos++)
				if(board[pos]>0 && board[pos]!=tabu)
				{
					mvs[nxt++] = pos;
					if((mvs[nxt++] = area(board,x,y,board[pos]))==1){ nxt -= 2; ++onecnt; }
					else if(y+mvs[nxt-1]<ys)
					{
						final int area = mvs[nxt-1], color = board[pos];
						boolean prunable = (y==0 || board[pos-1]==0) && color==board[pos+area-1];
						for(int i = pos+1; prunable && i<pos+area-1; i++) prunable &= color==board[i];
						if(prunable) nxt -= 2; //Only if alternatives exists.
					}
				}
		if(nxt==0)
			for(int x = 0, pos = 0; x<xs; x++)
				for(int y = 0; y<ys; y++, pos++)
					if(board[pos]>0)
					{
						mvs[nxt++] = pos;
						if((mvs[nxt++] = area(board,x,y,board[pos]))==1){ nxt -= 2; ++onecnt; }
						else if(y+mvs[nxt-1]<ys)
						{
							final int area = mvs[nxt-1], color = board[pos];
							boolean prunable = (y==0 || board[pos-1]==0) && color==board[pos+area-1];
							for(int i = pos+1; prunable && i<pos+area-1; i++) prunable &= color==board[i];
							if(prunable) nxt -= 2; //Only if alternatives exists.
						}
					}
		for(int i = 0; i<xs*ys; i++) board[i] = -board[i];
		return nxt;
	}
	// Like moves() but does not use VS-pruning.
	public static int rawMoves(final int[] board)
	{
		int nxt = onecnt = 0;
		for(int x = 0, pos = 0; x<xs; x++)
			for(int y = 0; y<ys; y++, pos++)
				if(board[pos]>0)
				{
					mvs[nxt++] = pos;
					if((mvs[nxt++] = area(board,x,y,board[pos]))==1){ nxt -= 2; ++onecnt; }
				}
		for(int i = 0; i<xs*ys; i++) board[i] = -board[i];
		return nxt;
	}
	// Calculates the area of the group containing position (x,y) with color prv.
	// Side-effect: All blocks in this group will have their color set to -prv.
	private static int area(final int[] board, final int x, final int y, final int prv)
	{
		if(x<0 || x>=xs || y<0 || y>=ys || prv!=board[x*ys+y]) return 0;
		board[x*ys+y] *= -1;
		int sum = 1;
		sum += area(board,x-1,y,prv);
		sum += area(board,x+1,y,prv);
		sum += area(board,x,y-1,prv);
		sum += area(board,x,y+1,prv);
		return sum;
	}
	/*** </Move finding> ***/

	/*** <End of Game> ***/
	// Takes a valid end-game board and returns the associated score.
	// If no blocks remain, the bonus is returned, otherwise the deduction is returned.
	public static int endscore(final int[] board)
	{
		if(board[ys-1]==0) return 1000;
		final int[] cnt = new int[colors];
		int score = 0;
		for(int x = 0, pos = 0; x<xs; x++)
			for(int y = 0; y<ys; y++, pos++)
				if(board[pos]>0)
				{
					final int s = area(board, x, y, board[pos]);
					if(s==1) ++cnt[~board[pos]]; //++cnt[-board[pos] - 1];
					else score += (s-2)*(s-2);
				}
		for(int i = 0; i<xs*ys; i++) board[i] = -board[i];
		for(int i = 0; i<colors; i++) score -= (cnt[i]-2)*(cnt[i]-2);
		return score;
	}
	// Returns whether the (valid) board is empty or not.
	public static boolean isEmpty(final int[] board)
	{
		return board[ys-1]==0;
	}

	// Returns an upper bound on the score achievable for this board.
	public static int upperscore(final int[] board)
	{
		final int[] cnt = new int[colors+1];
		for(int i = 0; i<xs*ys; i++) ++cnt[board[i]];
		int bound = 0; boolean bonus = true;
		for(int i = 1; i<=colors; bonus &= cnt[i++]!=1)
			if(cnt[i]>=2)
				bound += (cnt[i]-2)*(cnt[i]-2);
		return bonus ? 1000+bound : bound;
	}
	// Returns an lower bound on the score achievable for this board.
	public static int lowerscore(final int[] board)
	{
		final int len = rawMoves(board);
		int bound = onecnt==0 ? 1000 : 0;
		for(int i = 1; i<len; i+=2) bound += (mvs[i]-2)*(mvs[i]-2);
		return bound;
	}
	/*** </End of Game> ***/

	/*** <Hash> ***/
	private static final Random rnd = new Random();

	//Matrix used for zobrist hashing, each position gets an assigned random number
	// for each state it can be in (i.e. empty or a certain colored block).
	private static long[][] zob = new long[xs*ys][colors+1];
	static
	{
		for(int i = 0; i<xs*ys; i++)
			for(int c = 0; c<=colors; c++)
				zob[i][c] = rnd.nextLong();
	}

	// Returns the zobrist hash of the board.
	public static long hash(final int[] board)
	{
		long hash = 0;
		for(int i = 0; i<xs*ys; i++) hash ^= zob[i][board[i]];
		return hash;
	}
	// Returns a smarter zobrist hash that only takes the relative position
	// of colors into account (what the colors are does not matter).
	public static long smarthash(final int[] board)
	{
		final int[] idx = new int[colors+1];
		for(int i = 1; i<=colors; i++) idx[i] = -1;
		int nxt = 1;

		long hash = 0;
		for(int i = 0; i<xs*ys; i++)
		{
			int tmp = idx[board[i]];
			if(tmp<0) tmp = idx[board[i]] = nxt++;
			hash ^= zob[i][tmp];
		}
		return hash;
	}
	/*** </Hash> ***/

	/*** <Verifier> ***/
	// Takes a board and a solution for this board, and verifies if the solution is valid.
	// Index 0 of the solution-array gives the claimed score, position [1,solution.length)
	// gives moves i.e. some position of a block in the group that should be removed.
	public static boolean verify(final int[] board, final int[] solution)
	{
		int score = 0;
		for(int i = 1; i<solution.length; i++)
		{
			final int pos = solution[i];
			if(board[pos]==0) return false;
			final int sqr = dfsKill2(board, pos/ys, pos%ys, board[pos]) - 2;
			if(sqr<0) return false;
			score += sqr*sqr;
			redBoard(board);
		}
		score += endscore(board);

		return score==solution[0];
	}
	/*** </Verifier> ***/
}