import { readFileSync } from 'node:fs';

let sampleMode = false;
let usedArray = [];

const sampleArray = readFileSync('sample.txt').toString().split("\n");
const inputArray = readFileSync('input.txt').toString().split("\n");

if (sampleMode) {
  usedArray = sampleArray;
} else {
  usedArray = inputArray;
}

// Part One

console.time("part1");

// Parse input
const shapes = [];
const regions = [];

let idx = 0;
// Parse shapes - continue until we hit a region line (NxN: ...)
while (idx < usedArray.length) {
  const regionMatch = usedArray[idx].match(/^(\d+)x(\d+): (.+)$/);
  if (regionMatch) break; // Start of regions section

  const shapeMatch = usedArray[idx].match(/^(\d+):$/);
  if (shapeMatch) {
    const shapeLines = [];
    idx++;
    while (idx < usedArray.length && usedArray[idx] !== '' && !usedArray[idx].match(/^\d+:/) && !usedArray[idx].match(/^\d+x\d+:/)) {
      shapeLines.push(usedArray[idx]);
      idx++;
    }
    // Convert shape to list of coordinates
    const coords = [];
    for (let y = 0; y < shapeLines.length; y++) {
      for (let x = 0; x < shapeLines[y].length; x++) {
        if (shapeLines[y][x] === '#') {
          coords.push([x, y]);
        }
      }
    }
    shapes.push(coords);
  } else {
    idx++;
  }
}

// Parse regions
while (idx < usedArray.length) {
  if (usedArray[idx] === '') { idx++; continue; }
  const match = usedArray[idx].match(/^(\d+)x(\d+): (.+)$/);
  if (match) {
    const width = Number(match[1]);
    const height = Number(match[2]);
    const counts = match[3].split(' ').map(Number);
    regions.push({ width, height, counts });
  }
  idx++;
}

// Generate all rotations and flips of a shape
function getAllOrientations(coords) {
  const orientations = new Set();
  let current = coords;

  for (let flip = 0; flip < 2; flip++) {
    for (let rot = 0; rot < 4; rot++) {
      // Normalize: translate to origin (min x = 0, min y = 0)
      const minX = Math.min(...current.map(c => c[0]));
      const minY = Math.min(...current.map(c => c[1]));
      const normalized = current.map(c => [c[0] - minX, c[1] - minY]);
      normalized.sort((a, b) => a[1] - b[1] || a[0] - b[0]);
      orientations.add(JSON.stringify(normalized));

      // Rotate 90 degrees: (x, y) -> (-y, x)
      current = current.map(c => [-c[1], c[0]]);
    }
    // Flip horizontally: (x, y) -> (-x, y)
    current = coords.map(c => [-c[0], c[1]]);
  }

  return [...orientations].map(s => JSON.parse(s));
}

// Precompute all orientations for all shapes
const shapeOrientations = shapes.map(getAllOrientations);

// Check if a region can fit all required presents
function canFit(width, height, counts) {
  const grid = Array(height).fill(null).map(() => Array(width).fill(false));

  // Build list of pieces to place
  const pieces = [];
  for (let shapeIdx = 0; shapeIdx < counts.length; shapeIdx++) {
    for (let j = 0; j < counts[shapeIdx]; j++) {
      pieces.push(shapeIdx);
    }
  }

  // Calculate total cells needed - must not exceed region size
  const totalCells = pieces.reduce((sum, shapeIdx) => sum + shapes[shapeIdx].length, 0);
  if (totalCells > width * height) return false; // Can't exceed region size

  if (pieces.length === 0) return true;

  function canPlace(orientedShape, startX, startY) {
    for (const [dx, dy] of orientedShape) {
      const x = startX + dx;
      const y = startY + dy;
      if (x < 0 || x >= width || y < 0 || y >= height || grid[y][x]) {
        return false;
      }
    }
    return true;
  }

  function place(orientedShape, startX, startY) {
    for (const [dx, dy] of orientedShape) {
      grid[startY + dy][startX + dx] = true;
    }
  }

  function unplace(orientedShape, startX, startY) {
    for (const [dx, dy] of orientedShape) {
      grid[startY + dy][startX + dx] = false;
    }
  }

  // Track placement positions for each shape type to avoid duplicates
  const lastPlacement = new Map(); // shapeIdx -> [x, y] of last placement

  function solve(pieceIdx) {
    if (pieceIdx >= pieces.length) {
      return true; // All pieces placed successfully
    }

    const shapeIdx = pieces[pieceIdx];
    const orientations = shapeOrientations[shapeIdx];

    // Get minimum position for this shape type (to avoid duplicate placements of same shape)
    const minPos = lastPlacement.get(shapeIdx);

    for (const oriented of orientations) {
      // Try all valid placements in the grid
      for (let startY = 0; startY < height; startY++) {
        for (let startX = 0; startX < width; startX++) {
          // Skip if we've already placed this shape type at a later position
          // (enforces canonical ordering for identical pieces)
          if (minPos && (startY < minPos[1] || (startY === minPos[1] && startX <= minPos[0]))) {
            continue;
          }

          if (canPlace(oriented, startX, startY)) {
            place(oriented, startX, startY);
            const prevPos = lastPlacement.get(shapeIdx);
            lastPlacement.set(shapeIdx, [startX, startY]);
            if (solve(pieceIdx + 1)) return true;
            if (prevPos) {
              lastPlacement.set(shapeIdx, prevPos);
            } else {
              lastPlacement.delete(shapeIdx);
            }
            unplace(oriented, startX, startY);
          }
        }
      }
    }

    return false;
  }

  return solve(0);
}

let fitCount = 0;
for (const region of regions) {
  if (canFit(region.width, region.height, region.counts)) {
    fitCount++;
  }
}

console.timeEnd("part1");
console.log(fitCount);


// Part Two

console.time("part2");

console.timeEnd("part2");
console.log("Free star!");

// functions