+++ /dev/null
-package org.proofofconcept.shisensho;
-
-import java.util.ArrayList;
-import java.util.LinkedList;
-import java.util.List;
-
-public class Board {
- private static String charpieces = " abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
-
- public int difficulty=1; // 1=Hard ... N=Easy
- public boolean gravity=true;
- public int [] boardSize;
- public char[][] board;
- public LinkedList<Move> history;
-
- // ----------------------
- // Public methods
- // ----------------------
-
- public Board() {
- }
-
- // The board always has a 1-square width free rectangle that has
- // to be taken into account when specifying the size
- public void initialize(int sizeI, int sizeJ) {
- boardSize = new int[2];
- boardSize[0]=sizeI;
- boardSize[1]=sizeJ;
- board = new char[boardSize[0]][boardSize[1]];
- for (int i=0;i<boardSize[0];i++)
- for (int j=0;j<boardSize[1];j++)
- board[i][j]=0;
- history=new LinkedList<Move>();
- }
-
- public static String pieceToString(char piece) {
- return charpieces.substring(piece,1);
- }
-
- public static char StringToPiece(String piece) {
- char upiece;
- long charpiecesLen=charpieces.length();
- for(upiece=0;(upiece<charpiecesLen && charpieces.substring(upiece,1)!=piece);upiece++);
- if (upiece<charpiecesLen) return upiece;
- else return 0;
- }
-
- public String toString() {
- String result=" ";
- for (int j=0;j<boardSize[1];j++) {
- if (j>0) result+=" ";
- result+=""+(j%10);
- }
- result+="\n "+StringRepeat("--",boardSize[1]);
- for (int i=0;i<boardSize[0];i++) {
- result+="\n"+(i%10)+"|";
- for (int j=0;j<boardSize[1];j++) {
- if (j>0) result+=" ";
- result+=charpieces.substring(board[i][j],board[i][j]+1);
- }
- result+=" |\n";
- if (i<boardSize[0]-1)
- result+=" |"+StringRepeat(" ",boardSize[1])+"|";
- }
- result+=" "+StringRepeat("--",boardSize[1])+"\n";
- return result;
- }
-
- public void buildRandomBoard(int sizeI, int sizeJ, int difficulty, boolean gravity) {
- initialize(sizeI,sizeJ);
- this.difficulty=difficulty;
- this.gravity=gravity;
-
- int numDifferentPieces=((boardSize[0]-2)*(boardSize[1]-2)/((difficulty+1)*2))+1;
- for (int n=0;n<((difficulty+1)*2);n++) {
- for (int k=0;k<numDifferentPieces;k++) {
- int i,j;
- do {
- j=(myrand() % (boardSize[1]-2))+1;
- i=findFreeRow(j);
- } while (i<1);
- // ShisenSho.log("numDifferentPieces="+numDifferentPieces+", n="+n+", k="+(int)k+", i="+i+", j="+j);
- // ShisenSho.log(toString());
- board[i][j]=(char)k;
- }
- }
- }
-
- /*
- ALGORITHM TO COMPUTE CONNECTION PATH BETWEEN PIECES A (IA,JA) AND B (IB,JB)
-
- - Delete A and B from the board (consider them as blank spaces)
- - Calculate the set H of possible horizontal lines in the board (lines through blank spaces)
- - Calculate the set V of possible vertical lines in the board
- - Find HA, VA, HB, VB in the sets
- - If HA=HB, result is a straight horizontal line A-B
- - If VA=VB, result is a straight vertical line A-B
- - If HA cuts VB, the result is an L line A-(IA,JB)-B
- - If VA cuts HB, the result is an L line A-(IB,JA)-B
- - If exists an V line that cuts HA and HB, the result is a Z line A-(IA,JV)-(IB-JV)-B
- - If exists an H line that cuts VA and VB, the result is a Z line A-(IV,JA)-(IV,JB)-B
-
- The following data types are defined:
-
- - Board
- - Point(int i, int j)
- - Line(Point a, Point b)
- - LineSet(Line l1, ..., Line lN)
-
- The following operations are defined
-
- - LineSet getHorizontalLines(Board board, Point a, Point b) // a and b needed to consider them as blank
- - LineSet getVerticalLines(Board board, Point a, Point b)
- - boolean lineIsHorizontal(Line l)
- - boolean lineIsVertical(Line l)
- - boolean lineContainsPoint(Line l, Point p)
- - boolean lineEqualsLine(Line l1, Line l2)
- - boolean lineCutsLine(Line l1, Line l2)
- */
- public List<Point> getPath(Point a, Point b) {
- List<Point> result=new ArrayList<Point>();
-
- if (getPiece(a)!=getPiece(b)) return result;
-
- List<Line> h=getHorizontalLines(a,b);
- List<Line> v=getVerticalLines(a,b);
- Line ha=null, va=null, hb=null, vb=null;
-
- for (Line l : h) {
- if (l.contains(a)) ha=l;
- if (l.contains(b)) hb=l;
- if (ha!=null && hb!=null) break;
- }
-
- for (Line l : v) {
- if (l.contains(a)) va=l;
- if (l.contains(b)) vb=l;
- if (va!=null && vb!=null) break;
- }
-
- // stdout.printf("va=%s, ha=%s, vb=%s, hb=%s\n",va.toString(),ha.toString(),vb.toString(),hb.toString());
-
- if ((ha==null && va==null) || (hb==null && vb==null))
- return result;
-
- if (ha.equals(hb) || va.equals(vb)) {
- result.add(a);
- result.add(b);
- return result;
- }
-
- Point ab;
-
- ab=ha.cuts(vb);
- // stdout.printf("(ha cuts vb) ab=%s\n",ab.toString());
-
- if (ab!=null) {
- result.add(a);
- result.add(ab);
- result.add(b);
- return result;
- }
-
- ab=va.cuts(hb);
- // stdout.printf("(va cuts hb) ab=%s\n",ab.toString());
-
- if (ab!=null) {
- result.add(a);
- result.add(ab);
- result.add(b);
- return result;
- }
-
- for (Line l : v) {
- Point al=l.cuts(ha);
- Point bl=l.cuts(hb);
-
- // stdout.printf("(%s cuts ha) al=%s\n",l.toString(),al.toString());
- // stdout.printf("(%s cuts hb) bl=%s\n",l.toString(),bl.toString());
-
- if (al!=null && bl!=null) {
- result.add(a);
- result.add(al);
- result.add(bl);
- result.add(b);
- return result;
- }
- }
-
- for (Line l : h) {
- Point al=l.cuts(va);
- Point bl=l.cuts(vb);
-
- // stdout.printf("(%s cuts va) al=%s\n",l.toString(),al.toString());
- // stdout.printf("(%s cuts vb) bl=%s\n",l.toString(),bl.toString());
-
- if (al!=null && bl!=null) {
- result.add(a);
- result.add(al);
- result.add(bl);
- result.add(b);
- return result;
- }
- }
-
- return result;
- }
-
- public char getPiece(Point p) {
- return board[p.i][p.j];
- }
-
- public void setPiece(Point p, char piece) {
- board[p.i][p.j]=piece;
- }
-
- public String getStrPiece(Point p) {
- char piece=board[p.i][p.j];
- return charpieces.substring(piece,1);
- }
-
- public void setStrPiece(Point p, String piece) {
- char upiece;
- long charpiecesLen=charpieces.length();
- for(upiece=0;(upiece<charpiecesLen && charpieces.substring(upiece,1)!=piece);upiece++);
- if (upiece<charpiecesLen) board[p.i][p.j]=upiece;
- }
-
- public void play(Point a0, Point b0) {
- // It's important to sink the upper piece first
- Point a=(a0.i<b0.i)?a0:b0;
- Point b=(a0.i<b0.i)?b0:a0;
- Move m=new Move(a,b,getPiece(a));
- history.add(0,m);
- setPiece(a,(char)0);
- processGravity(a);
- setPiece(b,(char)0);
- processGravity(b);
- }
-
- public boolean getCanUndo() {
- return !history.isEmpty();
- }
-
- public void undo() {
- if (!getCanUndo()) return;
- Move m=history.remove(0);
- undoGravity(m.b);
- setPiece(m.b,m.piece);
- undoGravity(m.a);
- setPiece(m.a,m.piece);
- }
-
- public List<Line> getPairs(int maxResults) {
- List<Line> result=new ArrayList<Line>();
- List<Integer> pieces=new ArrayList<Integer>();
- List<List<Point>> piecePoints=new ArrayList<List<Point>>();
- for (int i=0;i<boardSize[0];i++)
- for (int j=0;j<boardSize[1];j++) {
- int piece=(int)board[i][j];
- if (piece==0) continue;
- int key=pieces.indexOf(piece);
- Point p=new Point(i,j);
- if (key==-1) {
- List<Point> points0=new ArrayList<Point>();
- points0.add(p);
- pieces.add(piece);
- piecePoints.add(points0);
-
- key=pieces.indexOf(piece);
- piecePoints.get(key);
- } else {
- List<Point> points1=piecePoints.get(key);
- points1.add(p);
- }
- }
-
- int nresults=0;
- int k=0;
- for (List<Point> points : piecePoints) {
- int n=(int)points.size();
- for (int i=0;i<n;i++) {
- Point a=points.get(i);
- for (int j=i+1;j<n;j++) {
- Point b=points.get(j);
- List<Point> path=getPath(a.copy(),b.copy());
- if (path!=null && path.size()>0) {
- result.add(new Line(a,b));
- if (nresults++==maxResults) break;
- }
- }
- if (nresults==maxResults) break;
- }
- k++;
- if (nresults==maxResults) break;
- }
- return result;
- }
-
- public int getNumPieces() {
- int result=0;
- for (int j=0;j<boardSize[1];j++) {
- for (int i=0;i<boardSize[0];i++) {
- if (board[i][j]!=0) result++;
- }
- }
- return result;
- }
-
- // ----------------------
- // Private methods
- // ----------------------
-
- /* RAND_MAX assumed to be 32767 */
- private int myrand() {
- return (int)Math.floor(Math.random()*32768);
- }
-
- private String StringRepeat(String s, int n) {
- String result="";
- for (int i=0;i<n;i++)
- result+=s;
- return result;
- }
-
- private int findFreeRow(int j) {
- for (int i=1;i<boardSize[0]-1;i++) {
- if (board[i][j]!=0) return (i-1);
- }
- return (boardSize[0]-1-1);
- }
-
- private List<Line> getHorizontalLines(Point excludeA, Point excludeB) {
- List<Line> result=new ArrayList<Line>();
- for (int i=0;i<boardSize[0];i++) {
- int j0=-1;
- boolean empty;
- for (int j=0;j<boardSize[1];j++) {
- empty=(board[i][j]==0 || (i==excludeA.i && j==excludeA.j)
- || (i==excludeB.i && j==excludeB.j));
- if (j0==-1 && empty) {
- j0=j;
- } else if (j0!=-1 && !empty) {
- result.add(new Line(new Point(i,j0), new Point(i,j-1)));
- j0=-1;
- }
- }
- if (j0!=-1) result.add(new Line(new Point(i,j0), new Point(i,boardSize[1]-1)));
- }
-
- // stdout.printf("\ngetHorizontalLines( %s, %s ): ",excludeA.toString(),excludeB.toString());
- // for (Line line : result) stdout.printf("%s ",line.toString());
- // stdout.printf("\n");
-
- return result;
- }
-
- private List<Line> getVerticalLines(Point excludeA, Point excludeB) {
- List<Line> result=new ArrayList<Line>();
- for (int j=0;j<boardSize[1];j++) {
- int i0=-1;
- boolean empty;
- for (int i=0;i<boardSize[0];i++) {
- empty=(board[i][j]==0 || (i==excludeA.i && j==excludeA.j)
- || (i==excludeB.i && j==excludeB.j));
- if (i0==-1 && empty) {
- i0=i;
- } else if (i0!=-1 && !empty) {
- result.add(new Line(new Point(i0,j), new Point(i-1,j)));
- i0=-1;
- }
- }
- if (i0!=-1) result.add(new Line(new Point(i0,j), new Point(boardSize[0]-1,j)));
- }
-
- // stdout.printf("\ngetVerticalLines( %s, %s ): ",excludeA.toString(),excludeB.toString());
- // for (Line line : result) stdout.printf("%s ",line.toString());
- // stdout.printf("\n");
-
- return result;
- }
-
- private void processGravity(Point p) {
- if (gravity) for (int i=p.i;i>0;i--) board[i][p.j]=board[i-1][p.j];
- }
-
- private void undoGravity(Point p) {
- if (gravity) for (int i=0;i<p.i;i++) board[i][p.j]=board[i+1][p.j];
- }
-
-}
projects / FreeShisen / blobdiff