Rep-tile problem solver

input01.txt

16
1 0
2 0
3 0
4 0
1 1
2 1
3 1
4 1
0 2
1 2
2 2
3 2
4 2
0 3
1 3
2 3

ReptileSolver.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Objects;
import java.util.Scanner;

public class ReptileSolver {
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int minX = 1_000_000_000, minY = 1_000_000_000;
    int maxX = -1_000_000_000, maxY = -1_000_000_000;
    int n = scanner.nextInt();
    int[][] coordinates = new int[n][2];
    for (int i = 0; i < n; i++) {
      int x = scanner.nextInt();
      int y = scanner.nextInt();
      coordinates[i][0] = x;
      coordinates[i][1] = y;
      minX = Math.min(x, minX);
      minY = Math.min(y, minY);
      maxX = Math.max(x, maxX);
      maxY = Math.max(y, maxY);
    }

    Reptile reptile = new Reptile(n, coordinates);
    ShapePair solution = findSolution(reptile);
    if (solution != null) {
      printSolution(minX, minY, maxX, maxY, solution.white.originalCoordinates,
          solution.black.originalCoordinates);
    } else {
      System.out.println("No solution");
    }
  }

  private static void printSolution(int minX, int minY, int maxX, int maxY, int[][] whiteCells,
      int[][] blackCells) {
    Arrays.sort(whiteCells, ReptileSolver::compareCoordinates);
    Arrays.sort(blackCells, ReptileSolver::compareCoordinates);
    int iw = 0;
    int ib = 0;
    for (int y = maxY; y >= minY; y--) {
      for (int x = minX; x <= maxX; x++) {
        if (iw < whiteCells.length && whiteCells[iw][0] == x && whiteCells[iw][1] == y) {
          System.out.print(".");
          iw++;
        } else if (ib < blackCells.length && blackCells[ib][0] == x && blackCells[ib][1] == y) {
          System.out.print("#");
          ib++;
        } else {
          System.out.print(" ");
        }
      }
      System.out.println();
    }
  }

  private static ShapePair findSolution(Reptile reptile) {
    for (ShapePair pair : reptile.split()) {
      Shape white = pair.white;
      Shape black = pair.black;
      if (testIdentical(white, black)) {
        return pair;
      }
      for (int j = 0; j < 3; j++) {
        white.rotate();
        if (testIdentical(white, black)) {
          return pair;
        }
      }
      white.flip();
      if (testIdentical(white, black)) {
        return pair;
      }
      for (int j = 0; j < 3; j++) {
        white.rotate();
        if (testIdentical(white, black)) {
          return pair;
        }
      }
    }
    return null;
  }

  private static boolean testIdentical(Shape white, Shape black) {
    for (int i = 0; i < white.cells.size(); i++) {
      Cell origin = white.cells.get(i);
      white.setOrigin(origin);
      if (white.equals(black)) return true;
    }
    white.setOrigin(white.cells.get(0));
    return false;
  }

  private static int compareCoordinates(int[] o1, int[] o2) {
    if (o1[1] != o2[1]) return o2[1] - o1[1];
    return o1[0] - o2[0];
  }

  private static class Reptile {
    public final int n;
    public final int[][] coordinates;

    public Reptile(int n, int[][] coordinates) {
      this.n = n;
      this.coordinates = coordinates;
    }

    public List<ShapePair> split() {
      List<ShapePair> ret = new ArrayList<>();
      for (int i = 0; i < 1 << n; i++) {
        if (Integer.bitCount(i) != n / 2) continue;
        List<int[]> whiteCoordinates = new ArrayList<>();
        List<int[]> blackCoordinates = new ArrayList<>();
        for (int j = 0; j < n; j++) {
          if ((i >> j & 1) == 1) {
            whiteCoordinates.add(coordinates[j]);
          } else {
            blackCoordinates.add(coordinates[j]);
          }
        }
        ret.add(new ShapePair(new Shape(n / 2, whiteCoordinates.toArray(new int[n / 2][])),
            new Shape(n / 2, blackCoordinates.toArray(new int[n / 2][]))));
      }
      return ret;
    }
  }

  private static class ShapePair {
    public final Shape white;
    public final Shape black;

    private ShapePair(Shape white, Shape black) {
      this.white = white;
      this.black = black;
    }

    @Override public String toString() {
      return "white:" + white + ", black:" + black;
    }
  }

  private static class Shape {
    public final List<Cell> cells = new ArrayList<>();
    private Cell origin;
    private int[][] originalCoordinates;

    public Shape(int n, int[][] coordinates) {
      originalCoordinates = new int[n][2];
      for (int i = 0; i < n; i++) {
        System.arraycopy(coordinates[i], 0, originalCoordinates[i], 0, 2);
      }
      for (int i = 0; i < n; i++) {
        int x = coordinates[i][0];
        int y = coordinates[i][1];
        Cell c = new Cell(x, y);
        cells.add(c);
        if (origin == null) {
          origin = c;
        }
      }

      setOrigin(origin);
    }

    public void setOrigin(Cell origin) {
      if (!cells.contains(origin)) {
        throw new IllegalArgumentException(
            "The specified origin cell is not contained in the shape: " + origin);
      }

      int originX = origin.x;
      int originY = origin.y;
      for (Cell c : cells) {
        c.x -= originX;
        c.y -= originY;
      }
    }

    public void rotate() {
      for (Cell c : cells) {
        int temp = c.x;
        c.x = c.y;
        c.y = -temp;
      }
    }

    public void flip() {
      for (Cell c : cells) {
        c.x *= -1;
      }
    }

    @Override public boolean equals(Object o) {
      if (this == o) return true;
      if (!(o instanceof Shape)) return false;
      Shape shape = (Shape) o;
      return Objects.equals(new HashSet<>(cells), new HashSet<>(shape.cells));
    }

    @Override public int hashCode() {
      return Objects.hash(cells);
    }

    @Override public String toString() {
      StringBuilder sb = new StringBuilder();
      sb.append("[");
      for (int[] originalCoordinate : originalCoordinates) {
        sb.append("(")
            .append(originalCoordinate[0])
            .append(", ")
            .append(originalCoordinate[1])
            .append(") ");
      }
      sb.setLength(sb.length() - 1);
      sb.append("]");
      return sb.toString();
    }
  }

  private static class Cell {
    public int x;
    public int y;

    public Cell(int x, int y) {
      this.x = x;
      this.y = y;
    }

    @Override public boolean equals(Object o) {
      if (this == o) return true;
      if (!(o instanceof Cell)) return false;
      Cell cell = (Cell) o;
      return x == cell.x && y == cell.y;
    }

    @Override public int hashCode() {
      return Objects.hash(x, y);
    }

    @Override public String toString() {
      return "(" + x + ", " + y + ")";
    }
  }
}