+/EE360P
distributed systems
git clone https://git.julia.blue/+/EE360P
07ca65d
master
1/** 2* Licensed to the Apache Software Foundation (ASF) under one 3* or more contributor license agreements. See the NOTICE file 4* distributed with this work for additional information 5* regarding copyright ownership. The ASF licenses this file 6* to you under the Apache License, Version 2.0 (the 7* "License"); you may not use this file except in compliance 8* with the License. You may obtain a copy of the License at 9* 10* http://www.apache.org/licenses/LICENSE-2.0 11* 12* Unless required by applicable law or agreed to in writing, software 13* distributed under the License is distributed on an "AS IS" BASIS, 14* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 15* See the License for the specific language governing permissions and 16* limitations under the License. 17*/ 18 19package org .apache .hadoop .examples .dancing ; 20 21import java .util .*; 22 23public class Pentomino { 24public static final String DEPTH ="mapreduce.pentomino.depth" ; 25public static final String WIDTH ="mapreduce.pentomino.width" ; 26public static final String HEIGHT ="mapreduce.pentomino.height" ; 27public static final String CLASS ="mapreduce.pentomino.class" ; 28 29/** 30* This interface just is a marker for what types I expect to get back 31* as column names. 32*/ 33protected static interface ColumnName { 34// NOTHING 35 } 36 37/** 38* Maintain information about a puzzle piece. 39*/ 40protected static class Piece implements ColumnName { 41private String name ; 42private boolean [][]shape ; 43private int []rotations ; 44private boolean flippable ; 45 46public Piece (String name ,String shape , 47boolean flippable ,int []rotations ) { 48this .name =name ; 49this .rotations =rotations ; 50this .flippable =flippable ; 51StringTokenizer parser =new StringTokenizer (shape ,"/" ); 52List <boolean []>lines =new ArrayList <boolean []>(); 53while (parser .hasMoreTokens ()) { 54String token =parser .nextToken (); 55boolean []line =new boolean [token .length ()]; 56for (int i =0 ;i <line .length ; ++i ) { 57line [i ] =token .charAt (i ) =='x' ; 58 } 59lines .add (line ); 60 } 61this .shape =new boolean [lines .size ()][]; 62for (int i =0 ;i <lines .size ();i ++) { 63this .shape [i ] =lines .get (i ); 64 } 65 } 66 67public String getName () { 68return name ; 69 } 70 71public int []getRotations () { 72return rotations .clone (); 73 } 74 75public boolean getFlippable () { 76return flippable ; 77 } 78 79private int doFlip (boolean flip ,int x ,int max ) { 80if (flip ) { 81return max -x -1 ; 82 }else { 83return x ; 84 } 85 } 86 87public boolean [][]getShape (boolean flip ,int rotate ) { 88boolean [][]result ; 89if (rotate %2 ==0 ) { 90int height =shape .length ; 91int width =shape [0 ].length ; 92result =new boolean [height ][]; 93boolean flipX =rotate ==2 ; 94boolean flipY =flip ^ (rotate ==2 ); 95for (int y =0 ;y <height ; ++y ) { 96result [y ] =new boolean [width ]; 97for (int x =0 ;x <width ; ++x ) { 98result [y ][x ] =shape [doFlip (flipY ,y ,height )] 99 [doFlip (flipX ,x ,width )]; 100 } 101 } 102 }else { 103int height =shape [0 ].length ; 104int width =shape .length ; 105result =new boolean [height ][]; 106boolean flipX =rotate ==3 ; 107boolean flipY =flip ^ (rotate ==1 ); 108for (int y =0 ;y <height ; ++y ) { 109result [y ] =new boolean [width ]; 110for (int x =0 ;x <width ; ++x ) { 111result [y ][x ] =shape [doFlip (flipX ,x ,width )] 112 [doFlip (flipY ,y ,height )]; 113 } 114 } 115 } 116return result ; 117 } 118 } 119 120/** 121* A point in the puzzle board. This represents a placement of a piece into 122* a given point on the board. 123*/ 124static class Point implements ColumnName { 125int x ; 126int y ; 127Point (int x ,int y ) { 128this .x =x ; 129this .y =y ; 130 } 131 } 132 133 134/** 135* Convert a solution to the puzzle returned by the model into a string 136* that represents the placement of the pieces onto the board. 137* @param width the width of the puzzle board 138* @param height the height of the puzzle board 139* @param solution the list of column names that were selected in the model 140* @return a string representation of completed puzzle board 141*/ 142public static String stringifySolution (int width ,int height , 143List <List <ColumnName >>solution ) { 144String [][]picture =new String [height ][width ]; 145StringBuffer result =new StringBuffer (); 146// for each piece placement... 147for (List <ColumnName >row :solution ) { 148// go through to find which piece was placed 149Piece piece =null ; 150for (ColumnName item :row ) { 151if (item instanceof Piece ) { 152piece = (Piece )item ; 153break ; 154 } 155 } 156// for each point where the piece was placed, mark it with the piece name 157for (ColumnName item :row ) { 158if (item instanceof Point ) { 159Point p = (Point )item ; 160picture [p .y ][p .x ] =piece .getName (); 161 } 162 } 163 } 164// put the string together 165for (int y =0 ;y <picture .length ; ++y ) { 166for (int x =0 ;x <picture [y ].length ; ++x ) { 167result .append (picture [y ][x ]); 168 } 169result .append ("\n" ); 170 } 171return result .toString (); 172 } 173 174public enum SolutionCategory {UPPER_LEFT ,MID_X ,MID_Y ,CENTER } 175 176/** 177* Find whether the solution has the x in the upper left quadrant, the 178* x-midline, the y-midline or in the center. 179* @param names the solution to check 180* @return the catagory of the solution 181*/ 182public SolutionCategory getCategory (List <List <ColumnName >>names ) { 183Piece xPiece =null ; 184// find the "x" piece 185for (Piece p :pieces ) { 186if ("x" .equals (p .name )) { 187xPiece =p ; 188break ; 189 } 190 } 191// find the row containing the "x" 192for (List <ColumnName >row :names ) { 193if (row .contains (xPiece )) { 194// figure out where the "x" is located 195int low_x =width ; 196int high_x =0 ; 197int low_y =height ; 198int high_y =0 ; 199for (ColumnName col :row ) { 200if (col instanceof Point ) { 201int x = ((Point )col ).x ; 202int y = ((Point )col ).y ; 203if (x <low_x ) { 204low_x =x ; 205 } 206if (x >high_x ) { 207high_x =x ; 208 } 209if (y <low_y ) { 210low_y =y ; 211 } 212if (y >high_y ) { 213high_y =y ; 214 } 215 } 216 } 217boolean mid_x = (low_x +high_x ==width -1 ); 218boolean mid_y = (low_y +high_y ==height -1 ); 219if (mid_x &&mid_y ) { 220return SolutionCategory .CENTER ; 221 }else if (mid_x ) { 222return SolutionCategory .MID_X ; 223 }else if (mid_y ) { 224return SolutionCategory .MID_Y ; 225 } 226break ; 227 } 228 } 229return SolutionCategory .UPPER_LEFT ; 230 } 231 232/** 233* A solution printer that just writes the solution to stdout. 234*/ 235private static class SolutionPrinter 236implements DancingLinks .SolutionAcceptor <ColumnName > { 237int width ; 238int height ; 239 240public SolutionPrinter (int width ,int height ) { 241this .width =width ; 242this .height =height ; 243 } 244 245public void solution (List <List <ColumnName >>names ) { 246System .out .println (stringifySolution (width ,height ,names )); 247 } 248 } 249 250protected int width ; 251protected int height ; 252 253protected List <Piece >pieces =new ArrayList <Piece >(); 254 255/** 256* Is the piece fixed under rotation? 257*/ 258protected static final int []oneRotation =new int []{0 }; 259 260/** 261* Is the piece identical if rotated 180 degrees? 262*/ 263protected static final int []twoRotations =new int []{0 ,1 }; 264 265/** 266* Are all 4 rotations unique? 267*/ 268protected static final int []fourRotations =new int []{0 ,1 ,2 ,3 }; 269 270/** 271* Fill in the pieces list. 272*/ 273protected void initializePieces () { 274pieces .add (new Piece ("x" ," x /xxx/ x " ,false ,oneRotation )); 275pieces .add (new Piece ("v" ,"x /x /xxx" ,false ,fourRotations )); 276pieces .add (new Piece ("t" ,"xxx/ x / x " ,false ,fourRotations )); 277pieces .add (new Piece ("w" ," x/ xx/xx " ,false ,fourRotations )); 278pieces .add (new Piece ("u" ,"x x/xxx" ,false ,fourRotations )); 279pieces .add (new Piece ("i" ,"xxxxx" ,false ,twoRotations )); 280pieces .add (new Piece ("f" ," xx/xx / x " ,true ,fourRotations )); 281pieces .add (new Piece ("p" ,"xx/xx/x " ,true ,fourRotations )); 282pieces .add (new Piece ("z" ,"xx / x / xx" ,true ,twoRotations )); 283pieces .add (new Piece ("n" ,"xx / xxx" ,true ,fourRotations )); 284pieces .add (new Piece ("y" ," x /xxxx" ,true ,fourRotations )); 285pieces .add (new Piece ("l" ," x/xxxx" ,true ,fourRotations )); 286 } 287 288/** 289* Is the middle of piece on the upper/left side of the board with 290* a given offset and size of the piece? This only checks in one 291* dimension. 292* @param offset the offset of the piece 293* @param shapeSize the size of the piece 294* @param board the size of the board 295* @return is it in the upper/left? 296*/ 297private static boolean isSide (int offset ,int shapeSize ,int board ) { 298return 2 *offset +shapeSize <=board ; 299 } 300 301/** 302* For a given piece, generate all of the potential placements and add them 303* as rows to the model. 304* @param dancer the problem model 305* @param piece the piece we are trying to place 306* @param width the width of the board 307* @param height the height of the board 308* @param flip is the piece flipped over? 309* @param row a workspace the length of the each row in the table 310* @param upperLeft is the piece constrained to the upper left of the board? 311* this is used on a single piece to eliminate most of the trivial 312* roations of the solution. 313*/ 314private static void generateRows (DancingLinks dancer , 315Piece piece , 316int width , 317int height , 318boolean flip , 319boolean []row , 320boolean upperLeft ) { 321// for each rotation 322int []rotations =piece .getRotations (); 323for (int rotIndex =0 ;rotIndex <rotations .length ; ++rotIndex ) { 324// get the shape 325boolean [][]shape =piece .getShape (flip ,rotations [rotIndex ]); 326// find all of the valid offsets 327for (int x =0 ;x <width ; ++x ) { 328for (int y =0 ;y <height ; ++y ) { 329if (y +shape .length <=height &&x +shape [0 ].length <=width && 330 (!upperLeft || 331 (isSide (x ,shape [0 ].length ,width ) && 332isSide (y ,shape .length ,height )))) { 333// clear the columns related to the points on the board 334for (int idx =0 ;idx <width *height ; ++idx ) { 335row [idx ] =false ; 336 } 337// mark the shape 338for (int subY =0 ;subY <shape .length ; ++subY ) { 339for (int subX =0 ;subX <shape [0 ].length ; ++subX ) { 340row [(y +subY ) *width +x +subX ] =shape [subY ][subX ]; 341 } 342 } 343dancer .addRow (row ); 344 } 345 } 346 } 347 } 348 } 349 350private DancingLinks <ColumnName >dancer =new DancingLinks <ColumnName >(); 351private DancingLinks .SolutionAcceptor <ColumnName >printer ; 352 353 { 354initializePieces (); 355 } 356 357/** 358* Create the model for a given pentomino set of pieces and board size. 359* @param width the width of the board in squares 360* @param height the height of the board in squares 361*/ 362public Pentomino (int width ,int height ) { 363initialize (width ,height ); 364 } 365 366/** 367* Create the object without initialization. 368*/ 369public Pentomino () { 370 } 371 372void initialize (int width ,int height ) { 373this .width =width ; 374this .height =height ; 375for (int y =0 ;y <height ; ++y ) { 376for (int x =0 ;x <width ; ++x ) { 377dancer .addColumn (new Point (x ,y )); 378 } 379 } 380int pieceBase =dancer .getNumberColumns (); 381for (Piece p :pieces ) { 382dancer .addColumn (p ); 383 } 384boolean []row =new boolean [dancer .getNumberColumns ()]; 385for (int idx =0 ;idx <pieces .size (); ++idx ) { 386Piece piece =pieces .get (idx ); 387row [idx +pieceBase ] =true ; 388generateRows (dancer ,piece ,width ,height ,false ,row ,idx ==0 ); 389if (piece .getFlippable ()) { 390generateRows (dancer ,piece ,width ,height ,true ,row ,idx ==0 ); 391 } 392row [idx +pieceBase ] =false ; 393 } 394printer =new SolutionPrinter (width ,height ); 395 } 396 397/** 398* Generate a list of prefixes to a given depth 399* @param depth the length of each prefix 400* @return a list of arrays of ints, which are potential prefixes 401*/ 402public List <int []>getSplits (int depth ) { 403return dancer .split (depth ); 404 } 405 406/** 407* Find all of the solutions that start with the given prefix. The printer 408* is given each solution as it is found. 409* @param split a list of row indexes that should be choosen for each row 410* in order 411* @return the number of solutions found 412*/ 413public int solve (int []split ) { 414return dancer .solve (split ,printer ); 415 } 416 417/** 418* Find all of the solutions to the puzzle. 419* @return the number of solutions found 420*/ 421public int solve () { 422return dancer .solve (printer ); 423 } 424 425/** 426* Set the printer for the puzzle. 427* @param printer A call-back object that is given each solution as it is 428* found. 429*/ 430public void setPrinter (DancingLinks .SolutionAcceptor <ColumnName >printer ) { 431this .printer =printer ; 432 } 433 434/** 435* Solve the 6x10 pentomino puzzle. 436*/ 437public static void main (String []args ) { 438int width =6 ; 439int height =10 ; 440Pentomino model =new Pentomino (width ,height ); 441List splits =model .getSplits (2 ); 442for (Iterator splitItr =splits .iterator ();splitItr .hasNext (); ) { 443int []choices = (int [])splitItr .next (); 444System .out ."split:" ); 445for (int i =0 ;i <choices .length ; ++i ) { 446System .out ." " +choices [i ]); 447 } 448System .out .println (); 449 450System .out .println (model .solve (choices ) +" solutions found." ); 451 } 452 } 453 454}