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

namespace(function() {

class RegionData {
  constructor() {
    this.invalidElements = []
    this.veryInvalidElements = []
    this.negations = []
  }

  addInvalid(elem) {
    this.invalidElements.push(elem)
  }

  addVeryInvalid(elem) {
    this.veryInvalidElements.push(elem)
  }

  valid() {
    return (this.invalidElements.length === 0 && this.veryInvalidElements.length === 0)
  }
}

// Sanity checks for data which comes from the user. Now that people have learned that /publish is an open endpoint,
// we have to make sure they don't submit data which passes validation but is untrustworthy.
// These checks should always pass for puzzles created by the built-in editor.
window.validateUserData = function(puzzle, path) {
  if (path == null) throw Error('Path cannot be null')

  var sizeError = puzzle.getSizeError(puzzle.width, puzzle.height)
  if (sizeError != null) throw Error(sizeError)

  var puzzleHasStart = false
  var puzzleHasEnd = false

  if (puzzle.grid.length !== puzzle.width) throw Error('Puzzle width does not match grid size')
  for (var x=0; x<puzzle.width; x++) {
    if (puzzle.grid[x].length !== puzzle.height) throw Error('Puzzle height does not match grid size')
    for (var y=0; y<puzzle.height; y++) {
      var cell = puzzle.grid[x][y]
      if (cell == null) continue

      if (cell.start === true) {
        puzzleHasStart = true
        if (puzzle.symType != SYM_TYPE_NONE) {
          var symCell = puzzle.getSymmetricalCell(x, y)
          if (symCell == null || symCell.start !== true) {
            throw Error('Startpoint at ' + x + ' ' + y + ' does not have a symmetrical startpoint')
          }
        }
      }
      if (cell.end != null) {
        puzzleHasEnd = true
        if (puzzle.symType != SYM_TYPE_NONE) {
          var symCell = puzzle.getSymmetricalCell(x, y)
          if (symCell == null || symCell.end == null || symCell.end != puzzle.getSymmetricalDir(cell.end)) {
            throw Error('Endpoint at ' + x + ' ' + y + ' does not have a symmetrical endpoint')
          }
        }
      }
    }
  }
  if (!puzzleHasStart) throw Error('Puzzle does not have a startpoint')
  if (!puzzleHasEnd) throw Error('Puzzle does not have an endpoint')
}
// Determines if the current grid state is solvable. Modifies the puzzle element with:
// valid: Whether or not the puzzle is valid
// invalidElements: Symbols which are invalid (for the purpose of negating / flashing)
// negations: Negation pairs (for the purpose of darkening)
window.validate = function(puzzle, quick) {
  console.log('Validating', puzzle)
  var puzzleData = new RegionData() // Assumed valid until we find an invalid element

  var needsRegions = false
  // These two are both used by validateRegion, so they are saved on the puzzle itself.
  puzzle.hasNegations = false
  puzzle.hasPolyominos = false

  // Validate gap failures as an early exit.
  for (var x=0; x<puzzle.width; x++) {
    for (var y=0; y<puzzle.height; y++) {
      var cell = puzzle.grid[x][y]
      if (cell == null) continue
      if (!needsRegions && cell.type != 'line' && cell.type != 'triangle') needsRegions = true
      if (cell.type == 'nega') puzzle.hasNegations = true
      if (cell.type == 'poly' || cell.type == 'ylop') puzzle.hasPolyominos = true
      if (cell.line > window.LINE_NONE) {
        if (cell.gap > window.GAP_NONE) {
          console.log('Solution line goes over a gap at', x, y)
          puzzleData.invalidElements.push({'x': x, 'y': y})
          if (quick) return puzzleData
        }
        if ((cell.dot === window.DOT_BLUE && cell.line === window.LINE_YELLOW) ||
            (cell.dot === window.DOT_YELLOW && cell.line === window.LINE_BLUE)) {
          console.log('Incorrectly covered dot: Dot is', cell.dot, 'but line is', cell.line)
          puzzleData.invalidElements.push({'x': x, 'y': y})
          if (quick) return puzzleData
        }
      }
    }
  }

  if (needsRegions) {
    var regions = puzzle.getRegions()
  } else {
    var monoRegion = []
    for (var x=0; x<puzzle.width; x++) {
      for (var y=0; y<puzzle.height; y++) {
        if (x%2 === 1 && y%2 === 1) {
          monoRegion.push({'x': x, 'y': y})
        } else if (puzzle.grid[x][y].line === window.LINE_NONE) {
          monoRegion.push({'x': x, 'y': y})
        }
      }
    }
    var regions = [monoRegion]
  }
  console.log('Found', regions.length, 'region(s)')
  console.debug(regions)

  if (puzzle.settings.CUSTOM_MECHANICS) {
    for (var region of regions) {
      regionData = validateRegion(puzzle, region, quick)
      puzzleData.negations = puzzleData.negations.concat(regionData.negations)
      puzzleData.invalidElements = puzzleData.invalidElements.concat(regionData.invalidElements)
      puzzleData.invalidElements = puzzleData.invalidElements.concat(regionData.veryInvalidElements)
    }
    // When using custom mechanics, we have to handle negations slightly differently.
    // Negations need to be applied after all regions are validated, so that we can evaluate negations for
    // all regions simultaneously. This is because certain custom mechanics are cross-region.

    // ...

  } else {
    for (var region of regions) {
      regionData = validateRegion(puzzle, region, quick)
      console.log('Region valid:', regionData.valid())
      puzzleData.negations = puzzleData.negations.concat(regionData.negations)
      puzzleData.invalidElements = puzzleData.invalidElements.concat(regionData.invalidElements)
      // Note: Not using veryInvalid because I don't need to do logic on these elements, just flash them.
      puzzleData.invalidElements = puzzleData.invalidElements.concat(regionData.veryInvalidElements)
      if (quick && !puzzleData.valid()) break
    }
  }
  console.log('Puzzle has', puzzleData.invalidElements.length, 'invalid elements')
  return puzzleData
}

// Determines whether or not a particular region is valid or not, including negation symbols.
// If quick is true, exits after the first invalid element is found (small performance gain)
// This function applies negations to all "very invalid elements", i.e. elements which cannot become
// valid by another element being negated. Then, it passes off to regionCheckNegations2,
// which attempts to apply any remaining negations to any other invalid elements.
window.validateRegion = function(puzzle, region, quick) {
  if (!puzzle.hasNegations) return regionCheck(puzzle, region, quick)

  // Get a list of negation symbols in the grid, and set them to 'nonce'
  var negationSymbols = []
  for (var pos of region) {
    var cell = puzzle.grid[pos.x][pos.y]
    if (cell != null && cell.type === 'nega') {
      pos.cell = cell
      negationSymbols.push(pos)
      puzzle.updateCell2(pos.x, pos.y, 'type', 'nonce')
    }
  }
  console.debug('Found', negationSymbols.length, 'negation symbols')
  if (negationSymbols.length === 0) {
    // No negation symbols in this region. Note that there must be negation symbols elsewhere
    // in the puzzle, since puzzle.hasNegations was true.
    return regionCheck(puzzle, region, quick)
  }

  // Get a list of elements that are currently invalid (before any negations are applied)
  // This cannot be quick, as we need a full list (for the purposes of negation).
  var regionData = regionCheck(puzzle, region, false)
  console.debug('Negation-less regioncheck valid:', regionData.valid())

  // Set 'nonce' back to 'nega' for the negation symbols
  for (var pos of negationSymbols) {
    puzzle.updateCell2(pos.x, pos.y, 'type', 'nega')
  }

  var invalidElements = regionData.invalidElements
  var veryInvalidElements = regionData.veryInvalidElements

  for (var i=0; i<invalidElements.length; i++) {
    invalidElements[i].cell = puzzle.getCell(invalidElements[i].x, invalidElements[i].y)
  }
  for (var i=0; i<veryInvalidElements.length; i++) {
    veryInvalidElements[i].cell = puzzle.getCell(veryInvalidElements[i].x, veryInvalidElements[i].y)
  }

  console.debug('Forcibly negating', veryInvalidElements.length, 'symbols')
  var baseCombination = []
  while (negationSymbols.length > 0 && veryInvalidElements.length > 0) {
    var source = negationSymbols.pop()
    var target = veryInvalidElements.pop()
    puzzle.setCell(source.x, source.y, null)
    puzzle.setCell(target.x, target.y, null)
    baseCombination.push({'source':source, 'target':target})
  }

  var regionData = regionCheckNegations2(puzzle, region, negationSymbols, invalidElements)

  // Restore required negations
  for (var combination of baseCombination) {
    puzzle.setCell(combination.source.x, combination.source.y, combination.source.cell)
    puzzle.setCell(combination.target.x, combination.target.y, combination.target.cell)
    regionData.negations.push(combination)
  }
  return regionData
}

// Recursively matches negations and invalid elements from the grid. Note that this function
// doesn't actually modify the two lists, it just iterates through them with index/index2.
function regionCheckNegations2(puzzle, region, negationSymbols, invalidElements, index=0, index2=0) {
  if (index2 >= negationSymbols.length) {
    console.debug('0 negation symbols left, returning negation-less regionCheck')
    return regionCheck(puzzle, region, false) // @Performance: We could pass quick here.
  }

  if (index >= invalidElements.length) {
    var i = index2
    // pair off all negation symbols, 2 at a time
    if (puzzle.settings.NEGATIONS_CANCEL_NEGATIONS) {
      for (; i<negationSymbols.length-1; i+=2) {
        var source = negationSymbols[i]
        var target = negationSymbols[i+1]
        puzzle.setCell(source.x, source.y, null)
        puzzle.setCell(target.x, target.y, null)
      }
    }

    console.debug(negationSymbols.length - i, 'negation symbol(s) left over with nothing to negate')
    for (; i<negationSymbols.length; i++) {
      puzzle.updateCell2(negationSymbols[i].x, negationSymbols[i].y, 'type', 'nonce')
    }
    // Cannot be quick, as we need the full list of invalid symbols.
    var regionData = regionCheck(puzzle, region, false)

    i = index2
    if (puzzle.settings.NEGATIONS_CANCEL_NEGATIONS) {
      for (; i<negationSymbols.length-1; i+=2) {
        var source = negationSymbols[i]
        var target = negationSymbols[i+1]
        puzzle.setCell(source.x, source.y, source.cell)
        puzzle.setCell(target.x, target.y, target.cell)
        regionData.negations.push({'source':source, 'target':target})
      }
    }
    for (; i<negationSymbols.length; i++) {
      puzzle.updateCell2(negationSymbols[i].x, negationSymbols[i].y, 'type', 'nega')
      regionData.addInvalid(negationSymbols[i])
    }
    return regionData
  }

  var source = negationSymbols[index2++]
  puzzle.setCell(source.x, source.y, null)

  var firstRegionData = null
  for (var i=index; i<invalidElements.length; i++) {
    var target = invalidElements[i]
    console.spam('Attempting negation pair', source, target)

    console.group()
    puzzle.setCell(target.x, target.y, null)
    var regionData = regionCheckNegations2(puzzle, region, negationSymbols, invalidElements, i + 1, index2)
    puzzle.setCell(target.x, target.y, target.cell)
    console.groupEnd()

    if (!firstRegionData) {
      firstRegionData = regionData
      firstRegionData.negations.push({'source':source, 'target':target})
    }
    if (regionData.valid()) {
      regionData.negations.push({'source':source, 'target':target})
      break
    }
  }

  puzzle.setCell(source.x, source.y, source.cell)
  // For display purposes only. The first attempt will always pair off the most negation symbols,
  // so it's the best choice to display (if we're going to fail).
  return (regionData.valid() ? regionData : firstRegionData)
}

// Checks if a region is valid. This does not handle negations -- we assume that there are none.
// Note that this function needs to always ask the puzzle for the current contents of the cell,
// since the region is only coordinate locations, and might be modified by regionCheckNegations2
// @Performance: This is a pretty core function to the solve loop.
function regionCheck(puzzle, region, quick) {
  console.log('Validating region of size', region.length, region)
  var regionData = new RegionData()

  var squares = []
  var stars = []
  var coloredObjects = {}
  var squareColor = null

  for (var pos of region) {
    var cell = puzzle.grid[pos.x][pos.y]
    if (cell == null) continue

    // Check for uncovered dots
    if (cell.dot > window.DOT_NONE) {
      console.log('Dot at', pos.x, pos.y, 'is not covered')
      regionData.addVeryInvalid(pos)
      if (quick) return regionData
    }

    // Check for triangles
    if (cell.type === 'triangle') {
      var count = 0
      if (puzzle.getLine(pos.x - 1, pos.y) > window.LINE_NONE) count++
      if (puzzle.getLine(pos.x + 1, pos.y) > window.LINE_NONE) count++
      if (puzzle.getLine(pos.x, pos.y - 1) > window.LINE_NONE) count++
      if (puzzle.getLine(pos.x, pos.y + 1) > window.LINE_NONE) count++
      if (cell.count !== count) {
        console.log('Triangle at grid['+pos.x+']['+pos.y+'] has', count, 'borders')
        regionData.addVeryInvalid(pos)
        if (quick) return regionData
      }
    }

    // Count color-based elements
    if (cell.color != null) {
      var count = coloredObjects[cell.color]
      if (count == null) {
        count = 0
      }
      coloredObjects[cell.color] = count + 1

      if (cell.type === 'square') {
        squares.push(pos)
        if (squareColor == null) {
          squareColor = cell.color
        } else if (squareColor != cell.color) {
          squareColor = -1 // Signal value which indicates square color collision
        }
      }

      if (cell.type === 'star') {
        pos.color = cell.color
        stars.push(pos)
      }
    }
  }

  if (squareColor === -1) {
    regionData.invalidElements = regionData.invalidElements.concat(squares)
    if (quick) return regionData
  }

  for (var star of stars) {
    var count = coloredObjects[star.color]
    if (count === 1) {
      console.log('Found a', star.color, 'star in a region with 1', star.color, 'object')
      regionData.addVeryInvalid(star)
      if (quick) return regionData
    } else if (count > 2) {
      console.log('Found a', star.color, 'star in a region with', count, star.color, 'objects')
      regionData.addInvalid(star)
      if (quick) return regionData
    }
  }

  if (puzzle.hasPolyominos) {
    if (!window.polyFit(region, puzzle)) {
      for (var pos of region) {
        var cell = puzzle.grid[pos.x][pos.y]
        if (cell == null) continue
        if (cell.type === 'poly' || cell.type === 'ylop') {
          regionData.addInvalid(pos)
          if (quick) return regionData
        }
      }
    }
  }

  if (puzzle.settings.CUSTOM_MECHANICS) {
    window.validateBridges(puzzle, region, regionData)
    window.validateArrows(puzzle, region, regionData)
    window.validateSizers(puzzle, region, regionData)
  }

  console.debug('Region has', regionData.veryInvalidElements.length, 'very invalid elements')
  console.debug('Region has', regionData.invalidElements.length, 'invalid elements')
  return regionData
}
})