+/EE360P

distributed systems

git clone https://git.julia.blue/+/EE360P

vijaygarg1init07ca65d

master
14.0 KiB454 linesraw
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 {
24  public static final String DEPTH = "mapreduce.pentomino.depth";
25  public static final String WIDTH = "mapreduce.pentomino.width";
26  public static final String HEIGHT = "mapreduce.pentomino.height";
27  public 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   */
33  protected static interface ColumnName {
34    // NOTHING
35  }
36
37  /**
38   * Maintain information about a puzzle piece.
39   */
40  protected static class Piece implements ColumnName {
41    private String name;
42    private boolean [][] shape;
43    private int[] rotations;
44    private boolean flippable;
45    
46    public Piece(String name, String shape, 
47                 boolean flippable, int[] rotations) {
48      this.name = name;
49      this.rotations = rotations;
50      this.flippable = flippable;
51      StringTokenizer parser = new StringTokenizer(shape, "/");
52      List<boolean[]> lines = new ArrayList<boolean[]>();
53      while (parser.hasMoreTokens()) {
54        String token = parser.nextToken();
55        boolean[] line = new boolean[token.length()];
56        for(int i=0; i < line.length; ++i) {
57          line[i] = token.charAt(i) == 'x';
58        }
59        lines.add(line);
60      }
61      this.shape = new boolean[lines.size()][];
62      for(int i=0 ; i < lines.size(); i++) {
63        this.shape[i] = lines.get(i);
64      }
65    }
66    
67    public String getName() {
68      return name;
69    }
70    
71    public int[] getRotations() {
72      return rotations.clone();
73    }
74    
75    public boolean getFlippable() {
76      return flippable;
77    }
78    
79    private int doFlip(boolean flip, int x, int max) {
80      if (flip) {
81        return max - x - 1;
82      } else {
83        return x;
84      }
85    }
86    
87    public boolean[][] getShape(boolean flip, int rotate) {
88      boolean [][] result;
89      if (rotate % 2 == 0) {
90        int height = shape.length;
91        int width = shape[0].length;
92        result = new boolean[height][];
93        boolean flipX = rotate == 2;
94        boolean flipY = flip ^ (rotate == 2);
95        for (int y = 0; y < height; ++y) {
96          result[y] = new boolean[width];
97          for (int x=0; x < width; ++x) {
98            result[y][x] = shape[doFlip(flipY, y, height)]
99                                 [doFlip(flipX, x, width)];
100          }
101        }
102      } else {
103        int height = shape[0].length;
104        int width = shape.length;
105        result = new boolean[height][];
106        boolean flipX = rotate == 3;
107        boolean flipY = flip ^ (rotate == 1);
108        for (int y = 0; y < height; ++y) {
109          result[y] = new boolean[width];
110          for (int x=0; x < width; ++x) {
111            result[y][x] = shape[doFlip(flipX, x, width)]
112                                 [doFlip(flipY, y, height)];
113          }
114        }        
115      }
116      return 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   */
124  static class Point implements ColumnName {
125    int x;
126    int y;
127    Point(int x, int y) {
128      this.x = x;
129      this.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   */
142  public static String stringifySolution(int width, int height, 
143                                         List<List<ColumnName>> solution) {
144    String[][] picture = new String[height][width];
145    StringBuffer result = new StringBuffer();
146    // for each piece placement...
147    for(List<ColumnName> row: solution) {
148      // go through to find which piece was placed
149      Piece piece = null;
150      for(ColumnName item: row) {
151        if (item instanceof Piece) {
152          piece = (Piece) item;
153          break;
154        }
155      }
156      // for each point where the piece was placed, mark it with the piece name
157      for(ColumnName item: row) {
158        if (item instanceof Point) {
159          Point p = (Point) item;
160          picture[p.y][p.x] = piece.getName();
161        }
162      }
163    }
164    // put the string together
165    for(int y=0; y < picture.length; ++y) {
166      for (int x=0; x < picture[y].length; ++x) {
167        result.append(picture[y][x]);
168      }
169      result.append("\n");
170    }
171    return result.toString();
172  }
173  
174  public 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   */
182  public SolutionCategory getCategory(List<List<ColumnName>> names) {
183    Piece xPiece = null;
184    // find the "x" piece
185    for(Piece p: pieces) {
186      if ("x".equals(p.name)) {
187        xPiece = p;
188        break;
189      }
190    }
191    // find the row containing the "x"
192    for(List<ColumnName> row: names) {
193      if (row.contains(xPiece)) {
194        // figure out where the "x" is located
195        int low_x = width;
196        int high_x = 0;
197        int low_y = height;
198        int high_y = 0;
199        for(ColumnName col: row) {
200          if (col instanceof Point) {
201            int x = ((Point) col).x;
202            int y = ((Point) col).y;
203            if (x < low_x) {
204              low_x = x;
205            }
206            if (x > high_x) {
207              high_x = x;
208            }
209            if (y < low_y) {
210              low_y = y;
211            }
212            if (y > high_y) {
213              high_y = y;
214            }
215          }
216        }
217        boolean mid_x = (low_x + high_x == width - 1);
218        boolean mid_y = (low_y + high_y == height - 1);
219        if (mid_x && mid_y) {
220          return SolutionCategory.CENTER;
221        } else if (mid_x) {
222          return SolutionCategory.MID_X;
223        } else if (mid_y) {
224          return SolutionCategory.MID_Y;
225        }
226        break;
227      }
228    }
229    return SolutionCategory.UPPER_LEFT;
230  }
231  
232  /**
233   * A solution printer that just writes the solution to stdout.
234   */
235  private static class SolutionPrinter 
236                       implements DancingLinks.SolutionAcceptor<ColumnName> {
237    int width;
238    int height;
239    
240    public SolutionPrinter(int width, int height) {
241      this.width = width;
242      this.height = height;
243    }
244    
245    public void solution(List<List<ColumnName>> names) {
246      System.out.println(stringifySolution(width, height, names));
247    }
248  }
249  
250  protected int width;
251  protected int height;
252
253  protected List<Piece> pieces = new ArrayList<Piece>();
254  
255  /**
256   * Is the piece fixed under rotation?
257   */
258  protected static final int [] oneRotation = new int[]{0};
259  
260  /**
261   * Is the piece identical if rotated 180 degrees?
262   */
263  protected static final int [] twoRotations = new int[]{0,1};
264  
265  /**
266   * Are all 4 rotations unique?
267   */
268  protected static final int [] fourRotations = new int[]{0,1,2,3};
269  
270  /**
271   * Fill in the pieces list.
272   */
273  protected void initializePieces() {
274    pieces.add(new Piece("x", " x /xxx/ x ", false, oneRotation));
275    pieces.add(new Piece("v", "x  /x  /xxx", false, fourRotations));
276    pieces.add(new Piece("t", "xxx/ x / x ", false, fourRotations));
277    pieces.add(new Piece("w", "  x/ xx/xx ", false, fourRotations));
278    pieces.add(new Piece("u", "x x/xxx", false, fourRotations));
279    pieces.add(new Piece("i", "xxxxx", false, twoRotations));
280    pieces.add(new Piece("f", " xx/xx / x ", true, fourRotations));
281    pieces.add(new Piece("p", "xx/xx/x ", true, fourRotations));
282    pieces.add(new Piece("z", "xx / x / xx", true, twoRotations));
283    pieces.add(new Piece("n", "xx  / xxx", true, fourRotations));
284    pieces.add(new Piece("y", "  x /xxxx", true, fourRotations));
285    pieces.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   */
297  private static boolean isSide(int offset, int shapeSize, int board) {
298    return 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   */
314  private static void generateRows(DancingLinks dancer,
315                                   Piece piece,
316                                   int width,
317                                   int height,
318                                   boolean flip,
319                                   boolean[] row,
320                                   boolean upperLeft) {
321    // for each rotation
322    int[] rotations = piece.getRotations();
323    for(int rotIndex = 0; rotIndex < rotations.length; ++rotIndex) {
324      // get the shape
325      boolean[][] shape = piece.getShape(flip, rotations[rotIndex]);
326      // find all of the valid offsets
327      for(int x=0; x < width; ++x) {
328        for(int y=0; y < height; ++y) {
329          if (y + shape.length <= height && x + shape[0].length <= width &&
330              (!upperLeft || 
331                  (isSide(x, shape[0].length, width) && 
332                   isSide(y, shape.length, height)))) {
333            // clear the columns related to the points on the board
334            for(int idx=0; idx < width * height; ++idx) {
335              row[idx] = false;
336            }
337            // mark the shape
338            for(int subY=0; subY < shape.length; ++subY) {
339              for(int subX=0; subX < shape[0].length; ++subX) {
340                row[(y + subY) * width + x + subX] = shape[subY][subX];
341              }
342            }
343            dancer.addRow(row);
344          }         
345        }
346      }
347    }
348  }
349  
350  private DancingLinks<ColumnName> dancer = new DancingLinks<ColumnName>();
351  private DancingLinks.SolutionAcceptor<ColumnName> printer;
352  
353  {
354    initializePieces();
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   */
362  public Pentomino(int width, int height) {
363    initialize(width, height);
364  }
365
366  /**
367   * Create the object without initialization.
368   */
369  public Pentomino() {
370  }
371
372  void initialize(int width, int height) {
373    this.width = width;
374    this.height = height;
375    for(int y=0; y < height; ++y) {
376      for(int x=0; x < width; ++x) {
377        dancer.addColumn(new Point(x,y));
378      }
379    }
380    int pieceBase = dancer.getNumberColumns();
381    for(Piece p: pieces) {
382      dancer.addColumn(p);
383    }
384    boolean[] row = new boolean[dancer.getNumberColumns()];
385    for(int idx = 0; idx < pieces.size(); ++idx) {
386      Piece piece = pieces.get(idx);
387      row[idx + pieceBase] = true;
388      generateRows(dancer, piece, width, height, false, row, idx == 0);
389      if (piece.getFlippable()) {
390        generateRows(dancer, piece, width, height, true, row, idx == 0);
391      }
392      row[idx + pieceBase] = false;
393    }
394    printer = 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   */
402  public List<int[]> getSplits(int depth) {
403    return 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   */
413  public int solve(int[] split) {
414    return dancer.solve(split, printer);
415  }
416  
417  /**
418   * Find all of the solutions to the puzzle.
419   * @return the number of solutions found
420   */
421  public int solve() {
422    return 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   */
430  public void setPrinter(DancingLinks.SolutionAcceptor<ColumnName> printer) {
431    this.printer = printer;
432  }
433  
434  /**
435   * Solve the 6x10 pentomino puzzle.
436   */
437  public static void main(String[] args) {
438    int width = 6;
439    int height = 10;
440    Pentomino model = new Pentomino(width, height);
441    List splits = model.getSplits(2);
442    for(Iterator splitItr=splits.iterator(); splitItr.hasNext(); ) {
443      int[] choices = (int[]) splitItr.next();
444      System.out.print("split:");
445      for(int i=0; i < choices.length; ++i) {
446        System.out.print(" " + choices[i]);
447      }
448      System.out.println();
449      
450      System.out.println(model.solve(choices) + " solutions found.");
451    }
452  }
453
454}