public Solution12() { super(12); }

public static void main(String[] args) {

Solution12 solution = new Solution12();

solution.testPartOne();

}

@Override

String solvePartOne(String inputData) {

Map<Integer, List<boolean[][]>> shapes = parseShapes(inputData);

List<Region> regions = parseRegions(inputData);

int count = 0;

for (Region region : regions) {

if (canPlaceAll(region, shapes)) count++;

}

return String.valueOf(count);

}

@Override

String solvePartTwo(String inputData) {

return null;

}

private int area(boolean[][] s) {

int a = 0;

for (boolean[] r : s)

for (boolean c : r)

if (c) a++;

return a;

}

private boolean canPlaceAll(Region region, Map<Integer, List<boolean[][]>> shapes) {

List<Integer> presentIndices = new ArrayList<>();

int totalArea = 0;

for (int i = 0; i < region.counts.length; i++) {

if (!shapes.containsKey(i)) continue;

int a = area(shapes.get(i).get(0));

totalArea += region.counts[i] * a;

for (int c = 0; c < region.counts[i]; c++)

presentIndices.add(i);

}

// AREA PRUNE

if (totalArea > region.width * region.height) return false;

// BIGGEST FIRST

presentIndices.sort((a, b) ->

area(shapes.get(b).get(0)) - area(shapes.get(a).get(0)));

boolean[][] grid = new boolean[region.height][region.width];

return dfsPlace(grid, presentIndices, 0, shapes);

}

private int[] firstEmpty(boolean[][] grid) {

for (int i = 0; i < grid.length; i++)

for (int j = 0; j < grid[0].length; j++)

if (!grid[i][j]) return new int[]{i, j};

return null;

}

private boolean dfsPlace(boolean[][] grid, List<Integer> presents, int idx,

Map<Integer, List<boolean[][]>> shapes) {

if (idx == presents.size()) return true;

int[] cell = firstEmpty(grid);

if (cell == null) return false;

int cx = cell[0], cy = cell[1];

grid[cx][cy] = true; // temporarily block it

if (dfsPlace(grid, presents, idx, shapes)) return true;

grid[cx][cy] = false;

int presentIdx = presents.get(idx);

for (boolean[][] shape : shapes.get(presentIdx)) {

int h = shape.length, w = shape[0].length;

for (int si = 0; si < h; si++) {

for (int sj = 0; sj < w; sj++) {

if (!shape[si][sj]) continue;

int x = cx - si;

int y = cy - sj;

if (x < 0 || y < 0 ||

x + h > grid.length ||

y + w > grid[0].length)

continue;

if (canFit(grid, shape, x, y)) {

place(grid, shape, x, y, true);

if (dfsPlace(grid, presents, idx + 1, shapes)) return true;

place(grid, shape, x, y, false);

}

}

}

}

return false;

}

private boolean canFit(boolean[][] grid, boolean[][] shape, int x, int y) {

for (int i = 0; i < shape.length; i++)

for (int j = 0; j < shape[0].length; j++)

if (shape[i][j] && grid[x + i][y + j]) return false;

return true;

}

private void place(boolean[][] grid, boolean[][] shape, int x, int y, boolean val) {

for (int i = 0; i < shape.length; i++)

for (int j = 0; j < shape[0].length; j++)

if (shape[i][j]) grid[x + i][y + j] = val;

}

private Map<Integer, List<boolean[][]>> parseShapes(String inputData) {

Map<Integer, List<boolean[][]>> shapes = new HashMap<>();

String[] lines = inputData.split("\n");

int idx = 0;

while (idx < lines.length) {

String line = lines[idx].trim();

if (line.matches("\\d+:")) {

int shapeIdx = Integer.parseInt(line.replace(":", ""));

List<String> shapeLines = new ArrayList<>();

idx++;

while (idx < lines.length) {

String l = lines[idx].trim();

if (l.isEmpty() || l.matches("\\d+:") || l.matches("\\d+x\\d+:.*")) break;

shapeLines.add(l);

idx++;

}

if (!shapeLines.isEmpty()) {

int h = shapeLines.size(), w = shapeLines.get(0).length();

boolean[][] shape = new boolean[h][w];

for (int i = 0; i < h; i++)

for (int j = 0; j < w; j++)

shape[i][j] = shapeLines.get(i).charAt(j) == '#';

shapes.put(shapeIdx, generateAllOrientations(shape));

}

} else idx++;

}

return shapes;

}

private List<boolean[][]> generateAllOrientations(boolean[][] shape) {

List<boolean[][]> all = new ArrayList<>();

Set<String> seen = new HashSet<>();

boolean[][] cur = shape;

for (int flip = 0; flip < 2; flip++) {

boolean[][] tmp = (flip == 1) ? flipHorizontal(cur) : cur;

for (int r = 0; r < 4; r++) {

tmp = rotate90(tmp);

String key = canonical(tmp);

if (seen.add(key)) all.add(tmp);

}

}

return all;

}

private String canonical(boolean[][] s) {

StringBuilder sb = new StringBuilder();

for (boolean[] r : s)

for (boolean c : r)

sb.append(c ? '1' : '0');

return sb.toString();

}

private boolean[][] rotate90(boolean[][] mat) {

int h = mat.length, w = mat[0].length;

boolean[][] res = new boolean[w][h];

for (int i = 0; i < h; i++)

for (int j = 0; j < w; j++)

res[j][h - 1 - i] = mat[i][j];

return res;

}

private boolean[][] flipHorizontal(boolean[][] mat) {

int h = mat.length, w = mat[0].length;

boolean[][] res = new boolean[h][w];

for (int i = 0; i < h; i++)

for (int j = 0; j < w; j++)

res[i][w - 1 - j] = mat[i][j];

return res;

}

private List<Region> parseRegions(String inputData) {

List<Region> regions = new ArrayList<>();

for (String line : inputData.split("\n")) {

if (line.matches("\\d+x\\d+:.*")) {

String[] parts = line.split(":");

String[] dim = parts[0].split("x");

int w = Integer.parseInt(dim[0]);

int h = Integer.parseInt(dim[1]);

int[] counts = Arrays.stream(parts[1].trim().split("\\s+"))

.mapToInt(Integer::parseInt).toArray();

regions.add(new Region(w, h, counts));

}

}

return regions;

}

private static class Region {

int width, height;

int[] counts;

Region(int w, int h, int[] counts) {

this.width = w;

this.height = h;

this.counts = counts;

}

}