import java.util.*;
public class Solution12 extends Solution {
public Solution12() { super(12); }
public static void main(String[] args) {
Solution12 solution = new Solution12();
solution.testPartOne();
}
@Override
String solvePartOne(String inputData) {
Map> shapes = parseShapes(inputData);
List 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> shapes) {
List 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 presents, int idx,
Map> 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> parseShapes(String inputData) {
Map> 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 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 generateAllOrientations(boolean[][] shape) {
List all = new ArrayList<>();
Set 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 parseRegions(String inputData) {
List 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;
}
}
}