1 files changed, 331 insertions, 0 deletions

@@ -0,0 +1,331 @@
+namespace(function() {
+
+function getPolySize(polyshape) {
+  var size = 0
+  for (var x=0; x<4; x++) {
+    for (var y=0; y<4; y++) {
+      if (isSet(polyshape, x, y)) size++
+    }
+  }
+  return size
+}
+
+function mask(x, y) {
+  return 1 << ((3-y)*4 + x)
+}
+
+function isSet(polyshape, x, y) {
+  if (x < 0 || y < 0) return false
+  if (x >= 4 || y >= 4) return false
+  return (polyshape & mask(x, y)) !== 0
+}
+
+// This is 2^20, whereas all the other bits fall into 2^(0-15)
+window.ROTATION_BIT = (1 << 20)
+
+window.isRotated = function(polyshape) {
+  return (polyshape & ROTATION_BIT) !== 0
+}
+
+function getRotations(polyshape) {
+  if (!isRotated(polyshape)) return [polyshape]
+
+  var rotations = [0, 0, 0, 0]
+  for (var x=0; x<4; x++) {
+    for (var y=0; y<4; y++) {
+      if (isSet(polyshape, x, y)) {
+        rotations[0] ^= mask(x, y)
+        rotations[1] ^= mask(y, 3-x)
+        rotations[2] ^= mask(3-x, 3-y)
+        rotations[3] ^= mask(3-y, x)
+      }
+    }
+  }
+
+  return rotations
+}
+
+// 90 degree rotations of the polyomino
+window.rotatePolyshape = function(polyshape, count=1) {
+  var rotations = getRotations(polyshape | window.ROTATION_BIT)
+  return rotations[count % 4]
+}
+
+// IMPORTANT NOTE: When formulating these, the top row must contain (0, 0)
+// That means there will never be any negative y values.
+// (0, 0) must also be a cell in the shape, so that
+// placing the shape at (x, y) will fill (x, y)
+// Ylops will have -1s on all adjacent cells, to break "overlaps" for polyominos.
+window.polyominoFromPolyshape = function(polyshape, ylop=false, precise=true) {
+  var topLeft = null
+  for (var y=0; y<4; y++) {
+    for (var x=0; x<4; x++) {
+      if (isSet(polyshape, x, y)) {
+        topLeft = {'x':x, 'y':y}
+        break
+      }
+    }
+    if (topLeft != null) break
+  }
+  if (topLeft == null) return [] // Empty polyomino
+
+  var polyomino = []
+  for (var x=0; x<4; x++) {
+    for (var y=0; y<4; y++) {
+      if (!isSet(polyshape, x, y)) continue
+      polyomino.push({'x':2*(x - topLeft.x), 'y':2*(y - topLeft.y)})
+
+      // "Precise" polyominos adds cells in between the apparent squares in the polyomino.
+      // This prevents the solution line from going through polyominos in the solution.
+      if (precise) {
+        if (ylop) {
+          // Ylops fill up/left if no adjacent cell, and always fill bottom/right
+          if (!isSet(polyshape, x - 1, y)) {
+            polyomino.push({'x':2*(x - topLeft.x) - 1, 'y':2*(y - topLeft.y)})
+          }
+          if (!isSet(polyshape, x, y - 1)) {
+            polyomino.push({'x':2*(x - topLeft.x), 'y':2*(y - topLeft.y) - 1})
+          }
+          polyomino.push({'x':2*(x - topLeft.x) + 1, 'y':2*(y - topLeft.y)})
+          polyomino.push({'x':2*(x - topLeft.x), 'y':2*(y - topLeft.y) + 1})
+        } else {
+          // Normal polys only fill bottom/right if there is an adjacent cell.
+          if (isSet(polyshape, x + 1, y)) {
+            polyomino.push({'x':2*(x - topLeft.x) + 1, 'y':2*(y - topLeft.y)})
+          }
+          if (isSet(polyshape, x, y + 1)) {
+            polyomino.push({'x':2*(x - topLeft.x), 'y':2*(y - topLeft.y) + 1})
+          }
+        }
+      }
+    }
+  }
+  return polyomino
+}
+
+window.polyshapeFromPolyomino = function(polyomino) {
+  var topLeft = {'x': 9999, 'y': 9999}
+  for (var pos of polyomino) {
+    if (pos.x%2 != 1 || pos.y%2 != 1) continue // We only care about cells, not edges or intersections
+    
+    // Unlike when we're making a polyomino, we just want to top and left flush the shape,
+    // we don't actually need (0, 0) to be filled.
+    if (pos.x < topLeft.x) topLeft.x = pos.x
+    if (pos.y < topLeft.y) topLeft.y = pos.y
+  }
+  if (topLeft == null) return 0 // Empty polyomino
+
+  var polyshape = 0
+  for (var pos of polyomino) {
+    if (pos.x%2 != 1 || pos.y%2 != 1) continue // We only care about cells, not edges or intersections
+    var x = (pos.x - topLeft.x) / 2 // 0.5x to convert from puzzle coordinates to polyshape coordinates
+    var y = (pos.y - topLeft.y) / 2 // 0.5x to convert from puzzle coordinates to polyshape coordinates
+    polyshape |= mask(x, y)
+  }
+  
+  return polyshape
+}
+
+// In some cases, polyominos and onimoylops will fully cancel each other out.
+// However, even if they are the same size, that doesn't guarantee that they fit together.
+// As an optimization, we save the results for known combinations of shapes, since there are likely many
+// fewer pairings of shapes than paths through the grid.
+var knownCancellations = {}
+
+// Attempt to fit polyominos in a region into the puzzle.
+// This function checks for early exits, then simplifies the grid to a numerical representation:
+// * 1 represents a square that has been double-covered (by two polyominos)
+//   * Or, in the cancellation case, it represents a square that was covered by a polyomino and not by an onimoylop
+// * 0 represents a square that is satisfied, either because:
+//   * it is outside the region
+//   * (In the normal case) it was inside the region, and has been covered by a polyomino
+//   * (In the cancellation case) it was covered by an equal number of polyominos and onimoylops
+// * -1 represents a square that needs to be covered once (inside the region, or outside but covered by an onimoylop)
+// * -2 represents a square that needs to be covered twice (inside the region & covered by an onimoylop)
+// * And etc, for additional layers of polyominos/onimoylops.
+window.polyFit = function(region, puzzle) {
+  var polys = []
+  var ylops = []
+  var polyCount = 0
+  var regionSize = 0
+  for (var pos of region) {
+    if (pos.x%2 === 1 && pos.y%2 === 1) regionSize++
+    var cell = puzzle.grid[pos.x][pos.y]
+    if (cell == null) continue
+    if (cell.polyshape === 0) continue
+    if (cell.type === 'poly') {
+      polys.push(cell)
+      polyCount += getPolySize(cell.polyshape)
+    } else if (cell.type === 'ylop') {
+      ylops.push(cell)
+      polyCount -= getPolySize(cell.polyshape)
+    }
+  }
+  if (polys.length + ylops.length === 0) {
+    console.log('No polyominos or onimoylops inside the region, vacuously true')
+    return true
+  }
+  if (polyCount > 0 && polyCount !== regionSize) {
+    console.log('Combined size of polyominos and onimoylops', polyCount, 'does not match region size', regionSize)
+    return false
+  }
+  if (polyCount < 0) {
+    console.log('Combined size of onimoylops is greater than polyominos by', -polyCount)
+    return false
+  }
+  var key = null
+  if (polyCount === 0) {
+    if (puzzle.settings.SHAPELESS_ZERO_POLY) {
+      console.log('Combined size of polyominos and onimoylops is zero')
+      return true
+    }
+    // These will be ordered by the order of cells in the region, which isn't exactly consistent.
+    // In practice, it seems to be good enough.
+    key = ''
+    for (var ylop of ylops) key += ' ' + ylop.polyshape
+    key += '|'
+    for (var poly of polys) key += ' ' + poly.polyshape
+    var ret = knownCancellations[key]
+    if (ret != null) return ret
+  }
+
+  // For polyominos, we clear the grid to mark it up again:
+  var savedGrid = puzzle.grid
+  puzzle.newGrid()
+  // First, we mark all cells as 0: Cells outside the target region should be unaffected.
+  for (var x=0; x<puzzle.width; x++) {
+    for (var y=0; y<puzzle.height; y++) {
+      puzzle.setCell(x, y, 0)
+    }
+  }
+  // In the normal case, we mark every cell as -1: It needs to be covered by one poly
+  if (polyCount > 0) {
+    for (var pos of region) puzzle.grid[pos.x][pos.y] = -1
+  }
+  // In the exact match case, we leave every cell marked 0: Polys and ylops need to cancel.
+
+  var ret = placeYlops(ylops, 0, polys, puzzle)
+  if (polyCount === 0) knownCancellations[key] = ret
+  puzzle.grid = savedGrid
+  return ret
+}
+
+// If false, poly doesn't fit and grid is unmodified
+// If true, poly fits and grid is modified (with the placement)
+function tryPlacePolyshape(cells, x, y, puzzle, sign) {
+  console.spam('Placing at', x, y, 'with sign', sign)
+  var numCells = cells.length
+  for (var i=0; i<numCells; i++) {
+    var cell = cells[i]
+    var puzzleCell = puzzle.getCell(cell.x + x, cell.y + y)
+    if (puzzleCell == null) return false
+    cell.value = puzzleCell
+  }
+  for (var i=0; i<numCells; i++) {
+    var cell = cells[i]
+    puzzle.setCell(cell.x + x, cell.y + y, cell.value + sign)
+  }
+  return true
+}
+
+// Places the ylops such that they are inside of the grid, then checks if the polys
+// zero the region.
+function placeYlops(ylops, i, polys, puzzle) {
+  // Base case: No more ylops to place, start placing polys
+  if (i === ylops.length) return placePolys(polys, puzzle)
+
+  var ylop = ylops[i]
+  var ylopRotations = getRotations(ylop.polyshape)
+  for (var x=1; x<puzzle.width; x+=2) {
+    for (var y=1; y<puzzle.height; y+=2) {
+      console.log('Placing ylop', ylop, 'at', x, y)
+      for (var polyshape of ylopRotations) {
+        var cells = polyominoFromPolyshape(polyshape, true, puzzle.settings.PRECISE_POLYOMINOS)
+        if (!tryPlacePolyshape(cells, x, y, puzzle, -1)) continue
+        console.group('')
+        if (placeYlops(ylops, i+1, polys, puzzle)) return true
+        console.groupEnd('')
+        if (!tryPlacePolyshape(cells, x, y, puzzle, +1)) continue
+      }
+    }
+  }
+  console.log('Tried all ylop placements with no success.')
+  return false
+}
+
+// Returns whether or not a set of polyominos fit into a region.
+// Solves via recursive backtracking: Some piece must fill the top left square,
+// so try every piece to fill it, then recurse.
+function placePolys(polys, puzzle) {
+  // Check for overlapping polyominos, and handle exit cases for all polyominos placed.
+  var allPolysPlaced = (polys.length === 0)
+  for (var x=0; x<puzzle.width; x++) {
+    var row = puzzle.grid[x]
+    for (var y=0; y<puzzle.height; y++) {
+      var cell = row[y]
+      if (cell > 0) {
+        console.log('Cell', x, y, 'has been overfilled and no ylops left to place')
+        return false
+      }
+      if (allPolysPlaced && cell < 0 && x%2 === 1 && y%2 === 1) {
+        // Normal, center cell with a negative value & no polys remaining.
+        console.log('All polys placed, but grid not full')
+        return false
+      }
+    }
+  }
+  if (allPolysPlaced) {
+    console.log('All polys placed, and grid full')
+    return true
+  }
+
+  // The top-left (first open cell) must be filled by a polyomino.
+  // However in the case of pillars, there is no top-left, so we try all open cells in the
+  // top-most open row
+  var openCells = []
+  for (var y=1; y<puzzle.height; y+=2) {
+    for (var x=1; x<puzzle.width; x+=2) {
+      if (puzzle.grid[x][y] >= 0) continue
+      openCells.push({'x':x, 'y':y})
+      if (puzzle.pillar === false) break
+    }
+    if (openCells.length > 0) break
+  }
+
+  if (openCells.length === 0) {
+    console.log('Polys remaining but grid full')
+    return false
+  }
+
+  for (var openCell of openCells) {
+    var attemptedPolyshapes = []
+    for (var i=0; i<polys.length; i++) {
+      var poly = polys[i]
+      console.spam('Selected poly', poly)
+      if (attemptedPolyshapes.includes(poly.polyshape)) {
+        console.spam('Polyshape', poly.polyshape, 'has already been attempted')
+        continue
+      }
+      attemptedPolyshapes.push(poly.polyshape)
+      polys.splice(i, 1)
+      for (var polyshape of getRotations(poly.polyshape)) {
+        console.spam('Selected polyshape', polyshape)
+        var cells = polyominoFromPolyshape(polyshape, false, puzzle.settings.PRECISE_POLYOMINOS)
+        if (!tryPlacePolyshape(cells, openCell.x, openCell.y, puzzle, +1)) {
+          console.spam('Polyshape', polyshape, 'does not fit into', openCell.x, openCell.y)
+          continue
+        }
+        console.group('')
+        if (placePolys(polys, puzzle)) return true
+        console.groupEnd('')
+        // Should not fail, as it's an inversion of the above tryPlacePolyshape
+        tryPlacePolyshape(cells, openCell.x, openCell.y, puzzle, -1)
+      }
+      polys.splice(i, 0, poly)
+    }
+  }
+  console.log('Grid non-empty with >0 polys, but no valid recursion.')
+  return false
+}
+
+})