path: root/app/assets/javascripts/puzzle.js

namespace(function() {

// A 2x2 grid is internally a 5x5:
// corner, edge, corner, edge, corner
// edge,   cell, edge,   cell, edge
// corner, edge, corner, edge, corner
// edge,   cell, edge,   cell, edge
// corner, edge, corner, edge, corner
//
// Corners and edges will have a value of true if the line passes through them
// Cells will contain an object if there is an element in them
window.Puzzle = class {
  constructor(width, height, pillar=false) {
    if (pillar === true) {
      this.newGrid(2 * width, 2 * height + 1)
    } else {
      this.newGrid(2 * width + 1, 2 * height + 1)
    }
    this.pillar = pillar
    this.settings = {
      // If true, negation symbols are allowed to cancel other negation symbols.
      NEGATIONS_CANCEL_NEGATIONS: true,

      // If true, and the count of polyominos and onimoylops is zero, they cancel regardless of shape.
      SHAPELESS_ZERO_POLY: false,

      // If true, the traced line cannot go through the placement of a polyomino.
      PRECISE_POLYOMINOS: true,

      // If false, incorrect elements will not flash when failing the puzzle.
      FLASH_FOR_ERRORS: true,

      // If true, mid-segment startpoints will constitute solid lines, and form boundaries for the region.
      FAT_STARTPOINTS: false,

      // If true, custom mechanics are displayed (and validated) in this puzzle.
      CUSTOM_MECHANICS: false,

      // If true, polyominos may be placed partially off of the grid as an intermediate solution step.
      // OUT_OF_BOUNDS_POLY: false,

      // If true, the symmetry line will be invisible.
      INVISIBLE_SYMMETRY: false,
    }
  }

  static deserialize(json) {
    var parsed = JSON.parse(json)
    // Claim that it's not a pillar (for consistent grid sizing), then double-check ourselves later.
    var puzzle = new Puzzle((parsed.grid.length - 1)/2, (parsed.grid[0].length - 1)/2)
    puzzle.name = parsed.name
    puzzle.autoSolved = parsed.autoSolved
    puzzle.grid = parsed.grid
    // Legacy: Grid squares used to use 'false' to indicate emptiness.
    // Legacy: Cells may use {} to represent emptiness
    // Now, we use:
    // Cells default to null
    // During onTraceStart, empty cells that are still inbounds are changed to {'type': 'nonce'} for tracing purposes.
    // Lines default to {'type':'line', 'line':0}
    for (var x=0; x<puzzle.width; x++) {
      for (var y=0; y<puzzle.height; y++) {
        var cell = puzzle.grid[x][y]
        if (cell === false || cell == null || cell.type == null) {
          if (x%2 === 1 && y%2 === 1) puzzle.grid[x][y] = null
          else puzzle.grid[x][y] = {'type':'line', 'line':window.LINE_NONE}
        } else {
          if (cell.type === 'poly' || cell.type === 'ylop') {
            if (cell.rot === 'all') {
              // Legacy: Polys and ylops used to have a rot value (before I started using polyshape).
              // rot=all is a holdover that was used to represent rotation polyominos.
              puzzle.grid[x][y].polyshape |= window.ROTATION_BIT
              delete puzzle.grid[x][y].rot
            }
            // Fixup: Sometimes we have a polyshape which is empty. Just ignore these objects.
            if (puzzle.grid[x][y].polyshape & ~window.ROTATION_BIT === 0) puzzle.grid[x][y] = null
          } else if ((x%2 !== 1 || y%2 !== 1) && cell.color != null) {
            // Legacy: Lines used to use 'color' instead of 'line', but that was redundant with actual colors
            cell.line = cell.color
            delete cell.color
          } else if (cell.gap === true) {
            // Legacy: Gaps used to be null/true, are now null/1/2
            puzzle.grid[x][y].gap = window.GAP_BREAK
          }
        }
      }
    }
    // Legacy: Startpoints used to be only parsed.start
    if (parsed.start) {
      parsed.startPoints = [parsed.start]
    }
    // Legacy: Startpoints used to be a separate array, now they are flags
    if (parsed.startPoints) {
      for (var startPoint of parsed.startPoints) {
        puzzle.grid[startPoint.x][startPoint.y].start = true
      }
    }
    // Legacy: Endpoints used to be only parsed.end
    if (parsed.end) {
      parsed.endPoints = [parsed.end]
    }
    // Legacy: Endpoints used to be a separate array, now they are flags
    if (parsed.endPoints) {
      for (var endPoint of parsed.endPoints) {
        puzzle.grid[endPoint.x][endPoint.y].end = endPoint.dir
      }
    }
    // Legacy: Dots and gaps used to be separate arrays
    // Now, they are flags on the individual lines.
    if (parsed.dots) {
      for (var dot of parsed.dots) {
        puzzle.grid[dot.x][dot.y].dot = window.DOT_BLACK
      }
    }
    if (parsed.gaps) {
      for (var gap of parsed.gaps) {
        puzzle.grid[gap.x][gap.y].gap = window.GAP_BREAK
      }
    }
    if (parsed.settings) {
      for (var key of Object.keys(parsed.settings)) {
        puzzle.settings[key] = parsed.settings[key]
      }
    }
    puzzle.pillar = parsed.pillar
    puzzle.symmetry = parsed.symmetry
    puzzle.symType = parsed.symType
    puzzle.largezero = puzzle.width * puzzle.height
    return puzzle
  }

  serialize() {
    return JSON.stringify(this)
  }

  clone() {
    return Puzzle.deserialize(this.serialize())
  }

  // This is explicitly *not* just clearing the grid, so that external references
  // to the grid are not also cleared.
  newGrid(width, height) {
    if (width == null) { // Called by someone who just wants to clear the grid.
      width = this.width
      height = this.height
    }
    this.grid = []
    for (var x=0; x<width; x++) {
      this.grid[x] = []
      for (var y=0; y<height; y++) {
        if (x%2 === 1 && y%2 === 1) this.grid[x][y] = null
        else this.grid[x][y] = {'type':'line', 'line':window.LINE_NONE}
      }
    }
    // Performance: A large value which is === 0 to be used for pillar wrapping.
    // Performance: Getting the size of the grid has a nonzero cost.
    // Definitely getting the length of the first element isn't optimized.
    this.largezero = width * height * 2
    this.width = this.grid.length
    this.height = this.grid[0].length
  }

  // Wrap a value around at the width of the grid. No-op if not in pillar mode.
  _mod(val) {
    if (this.pillar === false) return val
    return (val + this.largezero) % this.width
  }

  // Determine if an x, y pair is a safe reference inside the grid. This should be invoked at the start of every
  // function, but then functions can access the grid directly.
  _safeCell(x, y) {
    if (x < 0 || x >= this.width) return false
    if (y < 0 || y >= this.height) return false
    return true
  }

  getCell(x, y) {
    x = this._mod(x)
    if (!this._safeCell(x, y)) return null
    return this.grid[x][y]
  }

  setCell(x, y, value) {
    x = this._mod(x)
    if (!this._safeCell(x, y)) return
    this.grid[x][y] = value
  }

  getSymmetricalDir(dir) {
    if (this.symType == SYM_TYPE_VERTICAL || this.symType == SYM_TYPE_ROTATIONAL || this.symType == SYM_TYPE_PARALLEL_H_FLIP) {
      if (dir === 'left') return 'right'
      if (dir === 'right') return 'left'
    }
    if (this.symType == SYM_TYPE_HORIZONTAL || this.symType == SYM_TYPE_ROTATIONAL || this.symType == SYM_TYPE_PARALLEL_V_FLIP) {
      if (dir === 'top') return 'bottom'
      if (dir === 'bottom') return 'top'
    }
    if (this.symType == SYM_TYPE_ROTATE_LEFT || this.symType == SYM_TYPE_FLIP_NEG_XY) {
      if (dir === 'left') return 'bottom'
      if (dir === 'right') return 'top'
    }
    if (this.symType == SYM_TYPE_ROTATE_RIGHT || this.symType == SYM_TYPE_FLIP_NEG_XY) {
      if (dir === 'top') return 'right'
      if (dir === 'bottom') return 'left'
    }
    if (this.symType == SYM_TYPE_ROTATE_LEFT || this.symType == SYM_TYPE_FLIP_XY) {
      if (dir === 'top') return 'left'
      if (dir === 'bottom') return 'right'
    }
    if (this.symType == SYM_TYPE_ROTATE_RIGHT || this.symType == SYM_TYPE_FLIP_XY) {
      if (dir === 'right') return 'bottom'
      if (dir === 'left') return 'top'
    }
    return dir
  }

  // The resulting position is guaranteed to be gridsafe.
  getSymmetricalPos(x, y) {
    var origx = x
    var origy = y

    if (this.symType == SYM_TYPE_VERTICAL || this.symType == SYM_TYPE_ROTATIONAL || this.symType == SYM_TYPE_PARALLEL_H_FLIP) {
      x = (this.width - 1) - origx
    }
    if (this.symType == SYM_TYPE_HORIZONTAL || this.symType == SYM_TYPE_ROTATIONAL || this.symType == SYM_TYPE_PARALLEL_V_FLIP) {
      y = (this.height - 1) - origy
    }
    if (this.symType == SYM_TYPE_ROTATE_LEFT || this.symType == SYM_TYPE_FLIP_XY) {
      x = origy
    }
    if (this.symType == SYM_TYPE_ROTATE_RIGHT || this.symType == SYM_TYPE_FLIP_XY) {
      y = origx
    }
    if (this.symType == SYM_TYPE_ROTATE_LEFT || this.symType == SYM_TYPE_FLIP_NEG_XY) {
      y = (this.width - 1) - origx
    }
    if (this.symType == SYM_TYPE_ROTATE_RIGHT || this.symType == SYM_TYPE_FLIP_NEG_XY) {
      x = (this.height - 1) - origy
    }
    if (this.symType == SYM_TYPE_PARALLEL_H || this.symType == SYM_TYPE_PARALLEL_H_FLIP) {
      y = (origy == this.height / 2) ? (this.height / 2) : ((origy + (this.height + 1) / 2) % (this.height + 1))
    }
    if (this.symType == SYM_TYPE_PARALLEL_V || this.symType == SYM_TYPE_PARALLEL_V_FLIP) {
      x = (origx == this.width / 2) ? (this.width / 2) : ((origx + (this.width + 1) / 2) % (this.width + 1))
    }

    return {'x':this._mod(x), 'y':y}
  }

  getSymmetricalCell(x, y) {
    var pos = this.getSymmetricalPos(x, y)
    return this.getCell(pos.x, pos.y)
  }

  matchesSymmetricalPos(x1, y1, x2, y2) {
    return (y1 === y2 && this._mod(x1) === x2)
  }

  // A variant of getCell which specifically returns line values,
  // and treats objects as being out-of-bounds
  getLine(x, y) {
    var cell = this.getCell(x, y)
    if (cell == null) return null
    if (cell.type !== 'line') return null
    return cell.line
  }

  updateCell2(x, y, key, value) {
    x = this._mod(x)
    if (!this._safeCell(x, y)) return
    var cell = this.grid[x][y]
    if (cell == null) return
    cell[key] = value
  }

  getValidEndDirs(x, y) {
    x = this._mod(x)
    if (!this._safeCell(x, y)) return []

    var dirs = []
    var leftCell = this.getCell(x - 1, y)
    if (leftCell == null || leftCell.gap === window.GAP_FULL) dirs.push('left')
    var topCell = this.getCell(x, y - 1)
    if (topCell == null || topCell.gap === window.GAP_FULL) dirs.push('top')
    var rightCell = this.getCell(x + 1, y)
    if (rightCell == null || rightCell.gap === window.GAP_FULL) dirs.push('right')
    var bottomCell = this.getCell(x, y + 1)
    if (bottomCell == null || bottomCell.gap === window.GAP_FULL) dirs.push('bottom')
    return dirs
  }

  // Note: Does not use this.width/this.height, so that it may be used to ask about resizing.
  getSizeError(width, height) {
    if (this.pillar && width < 4) return 'Pillars may not have a width of 1'
    if (width * height < 25) return 'Puzzles may not be smaller than 2x2 or 1x4'
    if (width > 21 || height > 21) return 'Puzzles may not be larger than 10 in either dimension'
    if (this.symmetry != null) {
      if (this.symmetry.x && width <= 2) return 'Symmetrical puzzles must be sufficiently wide for both lines'
      if (this.symmetry.y && height <= 2) return 'Symmetrical puzzles must be sufficiently wide for both lines'
      if (this.pillar && this.symmetry.x && width % 4 !== 0) return 'X + Pillar symmetry must be an even number of rows, to keep both startpoints at the same parity'
    }

    return null
  }


  // Called on a solution. Computes a list of gaps to show as hints which *do not*
  // break the path.
  loadHints() {
    this.hints = []
    for (var x=0; x<this.width; x++) {
      for (var y=0; y<this.height; y++) {
        if (x%2 + y%2 === 1 && this.getLine(x, y) > window.LINE_NONE) {
          this.hints.push({'x':x, 'y':y})
        }
      }
    }
  }

  // Show a hint on the grid.
  // If no hint is provided, will select the best one it can find,
  // prioritizing breaking current lines on the grid.
  // Returns the shown hint.
  showHint(hint) {
    if (hint != null) {
      this.grid[hint.x][hint.y].gap = window.GAP_BREAK
      return
    }

    var goodHints = []
    var badHints = []

    for (var hint of this.hints) {
      if (this.getLine(hint.x, hint.y) > window.LINE_NONE) {
        // Solution will be broken by this hint
        goodHints.push(hint)
      } else {
        badHints.push(hint)
      }
    }
    if (goodHints.length > 0) {
      var hint = goodHints.splice(window.randInt(goodHints.length), 1)[0]
    } else if (badHints.length > 0) {
      var hint = badHints.splice(window.randInt(badHints.length), 1)[0]
    } else {
      return
    }
    this.grid[hint.x][hint.y].gap = window.GAP_BREAK
    this.hints = badHints.concat(goodHints)
    return hint
  }

  clearLines() {
    for (var x=0; x<this.width; x++) {
      for (var y=0; y<this.height; y++) {
        this.updateCell2(x, y, 'line', 0)
        this.updateCell2(x, y, 'dir', null)
      }
    }
  }

  _floodFill(x, y, region, col) {
    var cell = col[y]
    if (cell === MASKED_PROCESSED) return
    if (cell !== MASKED_INB_NONCOUNT) {
      region.push({'x':x, 'y':y})
    }
    col[y] = MASKED_PROCESSED

    if (y < this.height - 1)        this._floodFill(x,        y + 1, region, col)
    if (y > 0)                      this._floodFill(x,        y - 1, region, col)
    if (x < this.width - 1)         this._floodFill(x + 1,        y, region, this.grid[x+1])
    else if (this.pillar !== false) this._floodFill(0,            y, region, this.grid[0])
    if (x > 0)                      this._floodFill(x - 1,        y, region, this.grid[x-1])
    else if (this.pillar !== false) this._floodFill(this.width-1, y, region, this.grid[this.width-1])
  }

  // Re-uses the same grid, but only called on edges which border the outside
  // Called first to mark cells that are connected to the outside, i.e. should not be part of any region.
  _floodFillOutside(x, y, col) {
    var cell = col[y]
    if (cell === MASKED_PROCESSED) return
    if (x%2 !== y%2 && cell !== MASKED_GAP2) return // Only flood-fill through gap-2
    if (x%2 === 0 && y%2 === 0 && cell === MASKED_DOT) return // Don't flood-fill through dots
    col[y] = MASKED_PROCESSED

    if (x%2 === 0 && y%2 === 0) return // Don't flood fill through corners (what? Clarify.)

    if (y < this.height - 1)        this._floodFillOutside(x,        y + 1, col)
    if (y > 0)                      this._floodFillOutside(x,        y - 1, col)
    if (x < this.width - 1)         this._floodFillOutside(x + 1,        y, this.grid[x+1])
    else if (this.pillar !== false) this._floodFillOutside(0,            y, this.grid[0])
    if (x > 0)                      this._floodFillOutside(x - 1,        y, this.grid[x-1])
    else if (this.pillar !== false) this._floodFillOutside(this.width-1, y, this.grid[this.width-1])
  }

  // Returns the original grid (pre-masking). You will need to switch back once you are done flood filling.
  switchToMaskedGrid() {
    // Make a copy of the grid -- we will be overwriting it
    var savedGrid = this.grid
    this.grid = new Array(this.width)
    // Override all elements with empty lines -- this means that flood fill is just
    // looking for lines with line=0.
    for (var x=0; x<this.width; x++) {
      var savedRow = savedGrid[x]
      var row = new Array(this.height)
      var skip = 1
      if (x%2 === 1) { // Cells are always part of the region
        for (var y=1; y<this.height; y+=2) row[y] = MASKED_INB_COUNT
        skip = 2 // Skip these cells during iteration
      }
      for (var y=0; y<this.height; y+=skip) {
        var cell = savedRow[y]
        if (cell.line > window.LINE_NONE) {
          row[y] = MASKED_PROCESSED // Traced lines should not be a part of the region
        } else if (cell.gap === window.GAP_FULL) {
          row[y] = MASKED_GAP2
        } else if (cell.dot > window.DOT_NONE) {
          row[y] = MASKED_DOT
        } else {
          row[y] = MASKED_INB_COUNT
        }
      }
      this.grid[x] = row
    }

    // Starting at a mid-segment startpoint
    if (this.startPoint != null && this.startPoint.x%2 !== this.startPoint.y%2) {
      if (this.settings.FAT_STARTPOINTS) {
        // This segment is not in any region (acts as a barrier)
        this.grid[this.startPoint.x][this.startPoint.y] = MASKED_OOB
      } else {
        // This segment is part of this region (acts as an empty cell)
        this.grid[this.startPoint.x][this.startPoint.y] = MASKED_INB_NONCOUNT
      }
    }

    // Ending at a mid-segment endpoint
    if (this.endPoint != null && this.endPoint.x%2 !== this.endPoint.y%2) {
      // This segment is part of this region (acts as an empty cell)
      this.grid[this.endPoint.x][this.endPoint.y] = MASKED_INB_NONCOUNT
    }

    // Mark all outside cells as 'not in any region' (aka null)

    // Top and bottom edges
    for (var x=1; x<this.width; x+=2) {
      this._floodFillOutside(x, 0, this.grid[x])
      this._floodFillOutside(x, this.height - 1, this.grid[x])
    }

    // Left and right edges (only applies to non-pillars)
    if (this.pillar === false) {
      for (var y=1; y<this.height; y+=2) {
        this._floodFillOutside(0, y, this.grid[0])
        this._floodFillOutside(this.width - 1, y, this.grid[this.width-1])
      }
    }

    return savedGrid
  }

  getRegions() {
    var regions = []
    var savedGrid = this.switchToMaskedGrid()

    for (var x=0; x<this.width; x++) {
      for (var y=0; y<this.height; y++) {
        if (this.grid[x][y] == MASKED_PROCESSED) continue

        // If this cell is empty (aka hasn't already been used by a region), then create a new one
        // This will also mark all lines inside the new region as used.
        var region = []
        this._floodFill(x, y, region, this.grid[x])
        regions.push(region)
      }
    }
    this.grid = savedGrid
    return regions
  }

  getRegion(x, y) {
    x = this._mod(x)
    if (!this._safeCell(x, y)) return

    var savedGrid = this.switchToMaskedGrid()
    if (this.grid[x][y] == MASKED_PROCESSED) {
      this.grid = savedGrid
      return null
    }

    // If the masked grid hasn't been used at this point, then create a new region.
    // This will also mark all lines inside the new region as used.
    var region = []
    this._floodFill(x, y, region, this.grid[x])

    this.grid = savedGrid
    return region
  }

  logGrid() {
    var output = ''
    for (var y=0; y<this.height; y++) {
      var row = []
      for (var x=0; x<this.width; x++) {
        var cell = this.getCell(x, y)
        if (cell == null)                  row[x] = ' '
        else if (cell.type === 'nonce')    row[x] = ' '
        else if (cell.start === true)      row[x] = 'S'
        else if (cell.end != null)         row[x] = 'E'
        else if (cell.type === 'line') {
          if (cell.gap > 0)                row[x] = ' '
          if (cell.dot > 0)                row[x] = 'X'
          if (cell.line === 0)             row[x] = '.'
          if (cell.line === 1)             row[x] = '#'
          if (cell.line === 2)             row[x] = '#'
          if (cell.line === 3)             row[x] = 'o'
        } else                             row[x] = '?'
      }
      output += row.join('') + '\n'
    }
    console.info(output)
  }
}

// The grid contains 5 colors:
// null: Out of bounds or already processed
var MASKED_OOB = null
var MASKED_PROCESSED = null
// 0: In bounds, awaiting processing, but should not be part of the final region.
var MASKED_INB_NONCOUNT = 0
// 1: In bounds, awaiting processing
var MASKED_INB_COUNT = 1
// 2: Gap-2. After _floodFillOutside, this means "treat normally" (it will be null if oob)
var MASKED_GAP2 = 2
// 3: Dot (of any kind), otherwise identical to 1. Should not be flood-filled through (why the f do we need this)
var MASKED_DOT = 3

})