git.zerfleddert.de Git - FreeShisen/blob - src/org/proofofconcept/shisensho/Board.java

   1 package org.proofofconcept.shisensho;
   2
   3 import java.util.ArrayList;
   4 import java.util.LinkedList;
   5 import java.util.List;
   6
   7 public class Board {
   8         private static String charpieces = " abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
   9
  10         public int difficulty=1; // 1=Hard ... N=Easy
  11         public boolean gravity=true;
  12         public int [] boardSize;
  13         public char[][] board;
  14         public LinkedList<Move> history;
  15
  16         // ----------------------
  17         // Public methods
  18         // ----------------------
  19
  20         public Board() {
  21         }
  22
  23         // The board always has a 1-square width free rectangle that has
  24         // to be taken into account when specifying the size
  25         public void initialize(int sizeI, int sizeJ) {
  26                 boardSize = new int[2];
  27                 boardSize[0]=sizeI;
  28                 boardSize[1]=sizeJ;
  29                 board = new char[boardSize[0]][boardSize[1]];
  30                 for (int i=0;i<boardSize[0];i++)
  31                         for (int j=0;j<boardSize[1];j++)
  32                                 board[i][j]=0;
  33                 history=new LinkedList<Move>();
  34         }
  35
  36         public static String pieceToString(char piece) {
  37                 return charpieces.substring(piece,1);
  38         }
  39
  40         public static char StringToPiece(String piece) {
  41                 char upiece;
  42                 long charpiecesLen=charpieces.length();
  43                 for(upiece=0;(upiece<charpiecesLen && charpieces.substring(upiece,1)!=piece);upiece++);
  44                 if (upiece<charpiecesLen) return upiece;
  45                 else return 0;
  46         }
  47
  48         public String toString() {
  49                 String result="  ";
  50                 for (int j=0;j<boardSize[1];j++) {
  51                         if (j>0) result+=" ";
  52                         result+=""+(j%10);
  53                 }
  54                 result+="\n  "+StringRepeat("--",boardSize[1]);
  55                 for (int i=0;i<boardSize[0];i++) {
  56                         result+="\n"+(i%10)+"|";
  57                         for (int j=0;j<boardSize[1];j++) {
  58                                 if (j>0) result+=" ";
  59                                 result+=charpieces.substring(board[i][j],board[i][j]+1);
  60                         }
  61                         result+=" |\n";
  62                         if (i<boardSize[0]-1)
  63                                 result+=" |"+StringRepeat("  ",boardSize[1])+"|";
  64                 }
  65                 result+="  "+StringRepeat("--",boardSize[1])+"\n";
  66                 return result;
  67         }
  68
  69         public void buildRandomBoard(int sizeI, int sizeJ, int difficulty, boolean gravity) {
  70                 initialize(sizeI,sizeJ);
  71                 this.difficulty=difficulty;
  72                 this.gravity=gravity;
  73
  74                 int numDifferentPieces=((boardSize[0]-2)*(boardSize[1]-2)/((difficulty+1)*2))+1;
  75                 for (int n=0;n<((difficulty+1)*2);n++) {
  76                         for (int k=0;k<numDifferentPieces;k++) {
  77                                 int i,j;
  78                                 do {
  79                                         j=(myrand() % (boardSize[1]-2))+1;
  80                                         i=findFreeRow(j);
  81                                 } while (i<1);
  82                                 // ShisenSho.log("numDifferentPieces="+numDifferentPieces+", n="+n+", k="+(int)k+", i="+i+", j="+j);
  83                                 // ShisenSho.log(toString());
  84                                 board[i][j]=(char)k;
  85                         }
  86                 }
  87         }
  88
  89         /*
  90           ALGORITHM TO COMPUTE CONNECTION PATH BETWEEN PIECES A (IA,JA) AND B (IB,JB)
  91
  92           - Delete A and B from the board (consider them as blank spaces)
  93           - Calculate the set H of possible horizontal lines in the board (lines through blank spaces)
  94           - Calculate the set V of possible vertical lines in the board
  95           - Find HA, VA, HB, VB in the sets
  96           - If HA=HB, result is a straight horizontal line A-B
  97           - If VA=VB, result is a straight vertical line A-B
  98           - If HA cuts VB, the result is an L line A-(IA,JB)-B
  99           - If VA cuts HB, the result is an L line A-(IB,JA)-B
 100           - If exists an V line that cuts HA and HB, the result is a Z line A-(IA,JV)-(IB-JV)-B
 101           - If exists an H line that cuts VA and VB, the result is a Z line A-(IV,JA)-(IV,JB)-B
 102
 103           The following data types are defined:
 104
 105           - Board
 106           - Point(int i, int j)
 107           - Line(Point a, Point b)
 108           - LineSet(Line l1, ..., Line lN)
 109
 110           The following operations are defined
 111
 112           - LineSet getHorizontalLines(Board board, Point a, Point b) // a and b needed to consider them as blank
 113           - LineSet getVerticalLines(Board board, Point a, Point b)
 114           - boolean lineIsHorizontal(Line l)
 115           - boolean lineIsVertical(Line l)
 116           - boolean lineContainsPoint(Line l, Point p)
 117           - boolean lineEqualsLine(Line l1, Line l2)
 118           - boolean lineCutsLine(Line l1, Line l2)
 119          */
 120         public List<Point> getPath(Point a, Point b) {
 121                 List<Point> result=new ArrayList<Point>();
 122
 123                 if (getPiece(a)!=getPiece(b)) return result;
 124
 125                 List<Line> h=getHorizontalLines(a,b);
 126                 List<Line> v=getVerticalLines(a,b);
 127                 Line ha=null, va=null, hb=null, vb=null;
 128
 129                 for (Line l : h) {
 130                         if (l.contains(a)) ha=l;
 131                         if (l.contains(b)) hb=l;
 132                         if (ha!=null && hb!=null) break;
 133                 }
 134
 135                 for (Line l : v) {
 136                         if (l.contains(a)) va=l;
 137                         if (l.contains(b)) vb=l;
 138                         if (va!=null && vb!=null) break;
 139                 }
 140
 141                 // stdout.printf("va=%s, ha=%s, vb=%s, hb=%s\n",va.toString(),ha.toString(),vb.toString(),hb.toString());
 142
 143                 if ((ha==null && va==null) || (hb==null && vb==null))
 144                         return result;
 145
 146                 if (ha.equals(hb) || va.equals(vb)) {
 147                         result.add(a);
 148                         result.add(b);
 149                         return result;
 150                 }
 151
 152                 Point ab;
 153
 154                 ab=ha.cuts(vb);
 155                 // stdout.printf("(ha cuts vb) ab=%s\n",ab.toString());
 156
 157                 if (ab!=null) {
 158                         result.add(a);
 159                         result.add(ab);
 160                         result.add(b);
 161                         return result;
 162                 }
 163
 164                 ab=va.cuts(hb);
 165                 // stdout.printf("(va cuts hb) ab=%s\n",ab.toString());
 166
 167                 if (ab!=null) {
 168                         result.add(a);
 169                         result.add(ab);
 170                         result.add(b);
 171                         return result;
 172                 }
 173
 174                 for (Line l : v) {
 175                         Point al=l.cuts(ha);
 176                         Point bl=l.cuts(hb);
 177
 178                         // stdout.printf("(%s cuts ha) al=%s\n",l.toString(),al.toString());
 179                         // stdout.printf("(%s cuts hb) bl=%s\n",l.toString(),bl.toString());
 180
 181                         if (al!=null && bl!=null) {
 182                                 result.add(a);
 183                                 result.add(al);
 184                                 result.add(bl);
 185                                 result.add(b);
 186                                 return result;
 187                         }
 188                 }
 189
 190                 for (Line l : h) {
 191                         Point al=l.cuts(va);
 192                         Point bl=l.cuts(vb);
 193
 194                         // stdout.printf("(%s cuts va) al=%s\n",l.toString(),al.toString());
 195                         // stdout.printf("(%s cuts vb) bl=%s\n",l.toString(),bl.toString());
 196
 197                         if (al!=null && bl!=null) {
 198                                 result.add(a);
 199                                 result.add(al);
 200                                 result.add(bl);
 201                                 result.add(b);
 202                                 return result;
 203                         }
 204                 }
 205
 206                 return result;
 207         }
 208
 209         public char getPiece(Point p) {
 210                 return board[p.i][p.j];
 211         }
 212
 213         public void setPiece(Point p, char piece) {
 214                 board[p.i][p.j]=piece;
 215         }
 216
 217         public String getStrPiece(Point p) {
 218                 char piece=board[p.i][p.j];
 219                 return charpieces.substring(piece,1);
 220         }
 221
 222         public void setStrPiece(Point p, String piece) {
 223                 char upiece;
 224                 long charpiecesLen=charpieces.length();
 225                 for(upiece=0;(upiece<charpiecesLen && charpieces.substring(upiece,1)!=piece);upiece++);
 226                 if (upiece<charpiecesLen) board[p.i][p.j]=upiece;
 227         }
 228
 229         public void play(Point a0, Point b0) {
 230                 // It's important to sink the upper piece first
 231                 Point a=(a0.i<b0.i)?a0:b0;
 232                 Point b=(a0.i<b0.i)?b0:a0;
 233                 Move m=new Move(a,b,getPiece(a));
 234                 history.add(0,m);
 235                 setPiece(a,(char)0);
 236                 processGravity(a);
 237                 setPiece(b,(char)0);
 238                 processGravity(b);
 239         }
 240
 241         public boolean getCanUndo() {
 242                 return !history.isEmpty();
 243         }
 244
 245         public void undo() {
 246                 if (!getCanUndo()) return;
 247                 Move m=history.remove(0);
 248                 undoGravity(m.b);
 249                 setPiece(m.b,m.piece);
 250                 undoGravity(m.a);
 251                 setPiece(m.a,m.piece);
 252         }
 253
 254         public List<Line> getPairs(int maxResults) {
 255                 List<Line> result=new ArrayList<Line>();
 256                 List<Integer> pieces=new ArrayList<Integer>();
 257                 List<List<Point>> piecePoints=new ArrayList<List<Point>>();
 258                 for (int i=0;i<boardSize[0];i++)
 259                         for (int j=0;j<boardSize[1];j++) {
 260                                 int piece=(int)board[i][j];
 261                                 if (piece==0) continue;
 262                                 int key=pieces.indexOf(piece);
 263                                 Point p=new Point(i,j);
 264                                 if (key==-1) {
 265                                         List<Point> points0=new ArrayList<Point>();
 266                                         points0.add(p);
 267                                         pieces.add(piece);
 268                                         piecePoints.add(points0);
 269
 270                                         key=pieces.indexOf(piece);
 271                                         piecePoints.get(key);
 272                                 } else {
 273                                         List<Point> points1=piecePoints.get(key);
 274                                         points1.add(p);
 275                                 }
 276                         }
 277
 278                 int nresults=0;
 279                 int k=0;
 280                 for (List<Point> points : piecePoints) {
 281                         int n=(int)points.size();
 282                         for (int i=0;i<n;i++) {
 283                                 Point a=points.get(i);
 284                                 for (int j=i+1;j<n;j++) {
 285                                         Point b=points.get(j);
 286                                         List<Point> path=getPath(a.copy(),b.copy());
 287                                         if (path!=null && path.size()>0) {
 288                                                 result.add(new Line(a,b));
 289                                                 if (nresults++==maxResults) break;
 290                                         }
 291                                 }
 292                                 if (nresults==maxResults) break;
 293                         }
 294                         k++;
 295                         if (nresults==maxResults) break;
 296                 }
 297                 return result;
 298         }
 299
 300         public int getNumPieces() {
 301                 int result=0;
 302                 for (int j=0;j<boardSize[1];j++) {
 303                         for (int i=0;i<boardSize[0];i++) {
 304                                 if (board[i][j]!=0) result++;
 305                         }
 306                 }
 307                 return result;
 308         }
 309
 310         // ----------------------
 311         // Private methods
 312         // ----------------------
 313
 314         /* RAND_MAX assumed to be 32767 */
 315         private int myrand() {
 316                 return (int)Math.floor(Math.random()*32768);
 317         }
 318
 319         private String StringRepeat(String s, int n) {
 320                 String result="";
 321                 for (int i=0;i<n;i++)
 322                         result+=s;
 323                 return result;
 324         }
 325
 326         private int findFreeRow(int j) {
 327                 for (int i=1;i<boardSize[0]-1;i++) {
 328                         if (board[i][j]!=0) return (i-1);
 329                 }
 330                 return (boardSize[0]-1-1);
 331         }
 332
 333         private List<Line> getHorizontalLines(Point excludeA, Point excludeB) {
 334                 List<Line> result=new ArrayList<Line>();
 335                 for (int i=0;i<boardSize[0];i++) {
 336                         int j0=-1;
 337                         boolean empty;
 338                         for (int j=0;j<boardSize[1];j++) {
 339                                 empty=(board[i][j]==0 || (i==excludeA.i && j==excludeA.j)
 340                                                 || (i==excludeB.i && j==excludeB.j));
 341                                 if (j0==-1 && empty) {
 342                                         j0=j;
 343                                 } else if (j0!=-1 && !empty) {
 344                                         result.add(new Line(new Point(i,j0), new Point(i,j-1)));
 345                                         j0=-1;
 346                                 }
 347                         }
 348                         if (j0!=-1) result.add(new Line(new Point(i,j0), new Point(i,boardSize[1]-1)));
 349                 }
 350
 351                 // stdout.printf("\ngetHorizontalLines( %s, %s ): ",excludeA.toString(),excludeB.toString());
 352                 // for (Line line : result) stdout.printf("%s ",line.toString());
 353                 // stdout.printf("\n");
 354
 355                 return result;
 356         }
 357
 358         private List<Line> getVerticalLines(Point excludeA, Point excludeB) {
 359                 List<Line> result=new ArrayList<Line>();
 360                 for (int j=0;j<boardSize[1];j++) {
 361                         int i0=-1;
 362                         boolean empty;
 363                         for (int i=0;i<boardSize[0];i++) {
 364                                 empty=(board[i][j]==0 || (i==excludeA.i && j==excludeA.j)
 365                                                 || (i==excludeB.i && j==excludeB.j));
 366                                 if (i0==-1 && empty) {
 367                                         i0=i;
 368                                 } else if (i0!=-1 && !empty) {
 369                                         result.add(new Line(new Point(i0,j), new Point(i-1,j)));
 370                                         i0=-1;
 371                                 }
 372                         }
 373                         if (i0!=-1) result.add(new Line(new Point(i0,j), new Point(boardSize[0]-1,j)));
 374                 }
 375
 376                 // stdout.printf("\ngetVerticalLines( %s, %s ): ",excludeA.toString(),excludeB.toString());
 377                 // for (Line line : result) stdout.printf("%s ",line.toString());
 378                 // stdout.printf("\n");
 379
 380                 return result;
 381         }
 382
 383         private void processGravity(Point p) {
 384                 if (gravity) for (int i=p.i;i>0;i--) board[i][p.j]=board[i-1][p.j];
 385         }
 386
 387         private void undoGravity(Point p) {
 388                 if (gravity) for (int i=0;i<p.i;i++) board[i][p.j]=board[i+1][p.j];
 389         }
 390
 391 }