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

namespace(function() {

// @Volatile -- must match order of MOVE_* in trace2
// Move these, dummy.
var PATH_NONE   = 0
var PATH_LEFT   = 1
var PATH_RIGHT  = 2
var PATH_TOP    = 3
var PATH_BOTTOM = 4

window.MAX_SOLUTIONS = 0
var solutionPaths = []
var asyncTimer = 0
var task = null
var puzzle = null
var path = []
var SOLVE_SYNC = false
var SYNC_THRESHOLD = 9 // Depth at which we switch to a synchronous solver (for perf)
var doPruning = false

var percentages = []
var NODE_DEPTH = 9
var nodes = 0
function countNodes(x, y, depth) {
  // Check for collisions (outside, gap, self, other)
  var cell = puzzle.getCell(x, y)
  if (cell == null) return
  if (cell.gap > window.GAP_NONE) return
  if (cell.line !== window.LINE_NONE) return

  if (puzzle.symType == SYM_TYPE_NONE) {
    puzzle.updateCell2(x, y, 'line', window.LINE_BLACK)
  } else {
    var sym = puzzle.getSymmetricalPos(x, y)
    if (puzzle.matchesSymmetricalPos(x, y, sym.x, sym.y)) return // Would collide with our reflection

    var symCell = puzzle.getCell(sym.x, sym.y)
    if (symCell.gap > window.GAP_NONE) return

    puzzle.updateCell2(x, y, 'line', window.LINE_BLUE)
    puzzle.updateCell2(sym.x, sym.y, 'line', window.LINE_YELLOW)
  }

  if (depth < NODE_DEPTH) {
    nodes++

    if (y%2 === 0) {
      countNodes(x - 1, y, depth + 1)
      countNodes(x + 1, y, depth + 1)
    }

    if (x%2 === 0) {
      countNodes(x, y - 1, depth + 1)
      countNodes(x, y + 1, depth + 1)
    }
  }

  tailRecurse(x, y)
}

// Generates a solution via DFS recursive backtracking
window.solve = function(p, partialCallback, finalCallback) {
  if (task != null) throw Error('Cannot start another solve() while one is already in progress')
  var start = (new Date()).getTime()

  puzzle = p
  var startPoints = []
  var numEndpoints = 0
  puzzle.hasNegations = false
  puzzle.hasPolyominos = false
  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 (cell.start === true) {
        startPoints.push({'x': x, 'y': y})
      }
      if (cell.end != null) numEndpoints++
      if (cell.type == 'nega') puzzle.hasNegations = true
      if (cell.type == 'poly' || cell.type == 'ylop') puzzle.hasPolyominos = true
    }
  }

  // Puzzles which are small enough should be solved synchronously, since the cost of asynchronizing
  // is greater than the cost of the puzzle.
  SOLVE_SYNC = false
  if (puzzle.symType != SYM_TYPE_NONE) { // 5x5 is the max for symmetry puzzles
    if (puzzle.width * puzzle.height <= 121) SOLVE_SYNC = true
  } else if (puzzle.pillar === true) { // 4x5 is the max for non-symmetry, pillar puzzles
    if (puzzle.width * puzzle.height <= 108) SOLVE_SYNC = true
  } else { // 5x5 is the max for non-symmetry, non-pillar puzzles
    if (puzzle.width * puzzle.height <= 121) SOLVE_SYNC = true
  }
  console.log('Puzzle is a', puzzle.width, 'by', puzzle.height, 'solving ' + (SOLVE_SYNC ? 'sync' : 'async'))

  // We pre-traverse the grid (only considering obvious failure states like going out of bounds),
  // and compute a total number of nodes that are reachable within some NODE_DEPTH steps.
  // Then, during actual traversal, we can compare the number of nodes reached to the precomputed count
  // to get a (fairly accurate) progress bar.
  for (var pos of startPoints) {
    countNodes(pos.x, pos.y, 0)
  }
  console.log('Pretraversal found', nodes, 'nodes')
  percentages = []
  for (var i=0; i<100; i++) {
    percentages.push(Math.floor(i * nodes / 100))
  }
  nodes = 0

  solutionPaths = []
  // Some reasonable default data, which will avoid crashes during the solveLoop.
  var earlyExitData = [false, {'isEdge': false}, {'isEdge': false}]
  if (window.MAX_SOLUTIONS === 0) window.MAX_SOLUTIONS = 10000

  // Large pruning optimization -- Attempt to early exit once we cut out a region.
  // Inspired by https://github.com/Overv/TheWitnessSolver
  // For non-pillar puzzles, every time we draw a line from one edge to another, we cut out two regions.
  // We can detect this by asking if we've ever left an edge, and determining if we've just touched an edge.
  // However, just touching the edge isn't sufficient, since we could still enter either region.
  // As such, we wait one additional step, to see which half we have moved in to, then we evaluate
  // whichever half you moved away from (since you can no longer re-enter it).
  //
  // Consider this pathway (tracing X-X-X-A-B-C).
  // ....X....
  // . . X . .
  // ....X....
  // . . A . .
  // ...CB....
  //
  // Note that, once we have reached B, the puzzle is divided in half. However, we could go either
  // left or right -- so we don't know which region is safe to validate.
  // Once we reach C, however, the region to the right is closed off.
  // As such, we can start a flood fill from the cell to the right of A, computed by A+(C-B).
  //
  // Unfortunately, this optimization doesn't work for pillars, since the two regions are still connected.
  // Additionally, this optimization doesn't work when custom mechanics are active, as many custom mechanics
  // depend on the path through the entire puzzle
  doPruning = (puzzle.pillar === false && !puzzle.settings.CUSTOM_MECHANICS)

  task = {
    'code': function() {
      var newTasks = []

      for (var pos of startPoints) {
        // ;(function(a){}(a))
        // This syntax is used to forcibly copy arguments which are otherwise part of the loop.
        // Note that we don't need to copy objects, just value types.
        ;(function(pos) {
          newTasks.push(function() {
            path = [pos]
            puzzle.startPoint = pos
            return solveLoop(pos.x, pos.y, numEndpoints, earlyExitData)
          })
        }(pos))
      }
      return newTasks
    }
  }

  taskLoop(partialCallback, function() {
    var end = (new Date()).getTime()
    console.log('Solved', puzzle, 'in', (end-start)/1000, 'seconds')
    if (finalCallback) finalCallback(solutionPaths)
  })
  return solutionPaths
}

function taskLoop(partialCallback, finalCallback) {
  if (task == null) {
    finalCallback()
    return
  }

  var newTasks = task.code()
  task = task.nextTask
  if (newTasks != null && newTasks.length > 0) {
    // Tasks are pushed in order. To do DFS, we need to enqueue them in reverse order.
    for (var i=newTasks.length - 1; i >= 0; i--) {
      task = {
        'code': newTasks[i],
        'nextTask': task,
      }
    }
  }

  // Asynchronizing is expensive. As such, we don't want to do it too often.
  // However, we would like 'cancel solving' to be responsive. So, we call setTimeout every so often.
  var doAsync = false
  if (!SOLVE_SYNC) {
    doAsync = (asyncTimer++ % 100 === 0)
    while (nodes >= percentages[0]) {
      if (partialCallback) partialCallback(100 - percentages.length)
      percentages.shift()
      doAsync = true
    }
  }

  if (doAsync) {
    setTimeout(function() {
      taskLoop(partialCallback, finalCallback)
    }, 0)
  } else {
    taskLoop(partialCallback, finalCallback)
  }
}

function tailRecurse(x, y) {
  // Tail recursion: Back out of this cell
  puzzle.updateCell2(x, y, 'line', window.LINE_NONE)
  if (puzzle.symType != SYM_TYPE_NONE) {
    var sym = puzzle.getSymmetricalPos(x, y)
    puzzle.updateCell2(sym.x, sym.y, 'line', window.LINE_NONE)
  }
}

// @Performance: This is the most central loop in this code.
// Any performance efforts should be focused here.
// Note: Most mechanics are NP (or harder), so don't feel bad about solving them by brute force.
// https://arxiv.org/pdf/1804.10193.pdf
function solveLoop(x, y, numEndpoints, earlyExitData) {
  // Stop trying to solve once we reach our goal
  if (solutionPaths.length >= window.MAX_SOLUTIONS) return

  // Check for collisions (outside, gap, self, other)
  var cell = puzzle.getCell(x, y)
  if (cell == null) return
  if (cell.gap > window.GAP_NONE) return
  if (cell.line !== window.LINE_NONE) return

  if (puzzle.symType == SYM_TYPE_NONE) {
    puzzle.updateCell2(x, y, 'line', window.LINE_BLACK)
  } else {
    var sym = puzzle.getSymmetricalPos(x, y)
    if (puzzle.matchesSymmetricalPos(x, y, sym.x, sym.y)) return // Would collide with our reflection

    var symCell = puzzle.getCell(sym.x, sym.y)
    if (symCell.gap > window.GAP_NONE) return

    puzzle.updateCell2(x, y, 'line', window.LINE_BLUE)
    puzzle.updateCell2(sym.x, sym.y, 'line', window.LINE_YELLOW)
  }

  if (path.length < NODE_DEPTH) nodes++

  if (cell.end != null) {
    path.push(PATH_NONE)
    puzzle.endPoint = {'x': x, 'y': y}
    var puzzleData = window.validate(puzzle, true)
    if (puzzleData.valid()) solutionPaths.push(path.slice())
    path.pop()

    // If there are no further endpoints, tail recurse.
    // Otherwise, keep going -- we might be able to reach another endpoint.
    numEndpoints--
    if (numEndpoints === 0) return tailRecurse(x, y)
  }

  var newEarlyExitData = null
  if (doPruning) {
    var isEdge = x <= 0 || y <= 0 || x >= puzzle.width - 1 || y >= puzzle.height - 1
    newEarlyExitData = [
      earlyExitData[0] || (!isEdge && earlyExitData[2].isEdge), // Have we ever left an edge?
      earlyExitData[2],                                         // The position before our current one
      {'x':x, 'y':y, 'isEdge':isEdge}                           // Our current position.
    ]
    if (earlyExitData[0] && !earlyExitData[1].isEdge && earlyExitData[2].isEdge && isEdge) {
      // See the above comment for an explanation of this math.
      var floodX = earlyExitData[2].x + (earlyExitData[1].x - x)
      var floodY = earlyExitData[2].y + (earlyExitData[1].y - y)
      var region = puzzle.getRegion(floodX, floodY)
      if (region != null) {
        var regionData = window.validateRegion(puzzle, region, true)
        if (!regionData.valid()) return tailRecurse(x, y)

        // Additionally, we might have left an endpoint in the enclosed region.
        // If so, we should decrement the number of remaining endpoints (and possibly tail recurse).
        for (var pos of region) {
          var endCell = puzzle.grid[pos.x][pos.y]
          if (endCell != null && endCell.end != null) numEndpoints--
        }

        if (numEndpoints === 0) return tailRecurse(x, y)
      }
    }
  }

  if (SOLVE_SYNC || path.length > SYNC_THRESHOLD) {
    path.push(PATH_NONE)

    // Recursion order (LRUD) is optimized for BL->TR and mid-start puzzles
    if (y%2 === 0) {
      path[path.length-1] = PATH_LEFT
      solveLoop(x - 1, y, numEndpoints, newEarlyExitData)

      path[path.length-1] = PATH_RIGHT
      solveLoop(x + 1, y, numEndpoints, newEarlyExitData)
    }

    if (x%2 === 0) {
      path[path.length-1] = PATH_TOP
      solveLoop(x, y - 1, numEndpoints, newEarlyExitData)

      path[path.length-1] = PATH_BOTTOM
      solveLoop(x, y + 1, numEndpoints, newEarlyExitData)
    }

    path.pop()
    tailRecurse(x, y)

  } else {
    // Push a dummy element on the end of the path, so that we can fill it correctly as we DFS.
    // This element is popped when we tail recurse (which always happens *after* all of our DFS!)
    path.push(PATH_NONE)

    // Recursion order (LRUD) is optimized for BL->TR and mid-start puzzles
    var newTasks = []
    if (y%2 === 0) {
      newTasks.push(function() {
        path[path.length-1] = PATH_LEFT
        return solveLoop(x - 1, y, numEndpoints, newEarlyExitData)
      })
      newTasks.push(function() {
        path[path.length-1] = PATH_RIGHT
        return solveLoop(x + 1, y, numEndpoints, newEarlyExitData)
      })
    }

    if (x%2 === 0) {
      newTasks.push(function() {
        path[path.length-1] = PATH_TOP
        return solveLoop(x, y - 1, numEndpoints, newEarlyExitData)
      })
      newTasks.push(function() {
        path[path.length-1] = PATH_BOTTOM
        return solveLoop(x, y + 1, numEndpoints, newEarlyExitData)
      })
    }

    newTasks.push(function() {
      path.pop()
      tailRecurse(x, y)
    })

    return newTasks
  }
}

window.cancelSolving = function() {
  console.info('Cancelled solving')
  window.MAX_SOLUTIONS = 0 // Causes all new solveLoop calls to exit immediately.
  tasks = []
}

// Only modifies the puzzle object (does not do any graphics updates). Used by metapuzzle.js to determine subpuzzle polyshapes.
window.drawPathNoUI = function(puzzle, path) {
  puzzle.clearLines()

  // Extract the start data from the first path element
  var x = path[0].x
  var y = path[0].y
  var cell = puzzle.getCell(x, y)
  if (cell == null || cell.start !== true) throw Error('Path does not begin with a startpoint: ' + JSON.stringify(cell))

  for (var i=1; i<path.length; i++) {
    var cell = puzzle.getCell(x, y)

    var dx = 0
    var dy = 0
    if (path[i] === PATH_NONE) { // Reached an endpoint, move into it
      console.debug('Reached endpoint')
      if (i != path.length-1) throw Error('Path contains ' + (path.length - 1 - i) + ' trailing directions')
      break
    } else if (path[i] === PATH_LEFT) dx = -1
    else if (path[i] === PATH_RIGHT)  dx = +1
    else if (path[i] === PATH_TOP)    dy = -1
    else if (path[i] === PATH_BOTTOM) dy = +1
    else throw Error('Path element ' + (i-1) + ' was not a valid path direction: ' + path[i])

    x += dx
    y += dy
    // Set the cell color
    if (puzzle.symType == SYM_TYPE_NONE) {
      cell.line = window.LINE_BLACK
    } else {
      cell.line = window.LINE_BLUE
      var sym = puzzle.getSymmetricalPos(x, y)
      puzzle.updateCell2(sym.x, sym.y, 'line', window.LINE_YELLOW)
    }
  }

  var cell = puzzle.getCell(x, y)
  if (cell == null || cell.end == null) throw Error('Path does not end at an endpoint: ' + JSON.stringify(cell))
}

// Uses trace2 to draw the path on the grid, logs a graphical representation of the solution,
// and also modifies the puzzle to contain the solution path.
window.drawPath = function(puzzle, path, target='puzzle') {
  // @Duplicated with trace2.clearGrid
  var puzzleElem = document.getElementById(target)
  window.deleteElementsByClassName(puzzleElem, 'cursor')
  window.deleteElementsByClassName(puzzleElem, 'line-1')
  window.deleteElementsByClassName(puzzleElem, 'line-2')
  window.deleteElementsByClassName(puzzleElem, 'line-3')
  puzzle.clearLines()
  
  if (path == null || path.length === 0) return // "drawing" an empty path is a shorthand for clearing the grid.

  // Extract the start data from the first path element
  var x = path[0].x
  var y = path[0].y
  var cell = puzzle.getCell(x, y)
  if (cell == null || cell.start !== true) throw Error('Path does not begin with a startpoint: ' + JSON.stringify(cell))

  var start = document.getElementById('start_' + target + '_' + x + '_' + y)
  var symStart = document.getElementById('symStart_' + target + '_' + x + '_' + y)
  window.onTraceStart(puzzle, {'x':x, 'y':y}, document.getElementById(target), start, symStart)

  console.info('Drawing solution of length', path.length)
  for (var i=1; i<path.length; i++) {
    var cell = puzzle.getCell(x, y)

    var dx = 0
    var dy = 0
    if (path[i] === PATH_NONE) { // Reached an endpoint, move into it
      console.debug('Reached endpoint')
      if (cell.end === 'left') {
        window.onMove(-24, 0)
      } else if (cell.end === 'right') {
        window.onMove(24, 0)
      } else if (cell.end === 'top') {
        window.onMove(0, -24)
      } else if (cell.end === 'bottom') {
        window.onMove(0, 24)
      }
      if (i != path.length-1) throw Error('Path contains ' + (path.length - 1 - i) + ' trailing directions')
      break
    } else if (path[i] === PATH_LEFT) {
      dx = -1
      cell.dir = 'left'
    } else if (path[i] === PATH_RIGHT) {
      dx = +1
      cell.dir = 'right'
    } else if (path[i] === PATH_TOP) {
      dy = -1
      cell.dir = 'top'
    } else if (path[i] === PATH_BOTTOM) {
      dy = +1
      cell.dir = 'down'
    } else {
      throw Error('Path element ' + (i-1) + ' was not a valid path direction: ' + path[i])
    }

    console.debug('Currently at', x, y, cell, 'moving', dx, dy)

    x += dx
    y += dy
    // Unflag the cell, move into it, and reflag it
    cell.line = window.LINE_NONE
    window.onMove(41 * dx, 41 * dy)
    if (puzzle.symType == SYM_TYPE_NONE) {
      cell.line = window.LINE_BLACK
    } else {
      cell.line = window.LINE_BLUE
      var sym = puzzle.getSymmetricalPos(x, y)
      puzzle.updateCell2(sym.x, sym.y, 'line', window.LINE_YELLOW)
    }
  }
  var cell = puzzle.getCell(x, y)
  if (cell == null || cell.end == null) throw Error('Path does not end at an endpoint: ' + JSON.stringify(cell))

  var rows = '   |'
  for (var x=0; x<puzzle.width; x++) {
    rows += ('' + x).padEnd(5, ' ') + '|'
  }
  console.log(rows)
  for (var y=0; y<puzzle.height; y++) {
    var output = ('' + y).padEnd(3, ' ') + '|'
    for (var x=0; x<puzzle.width; x++) {
      var cell = puzzle.grid[x][y]
      var dir = (cell != null && cell.dir != null ? cell.dir : '')
      output += dir.padEnd(5, ' ') + '|'
    }
    console.log(output)
  }
}

window.getSolutionIndex = function(pathList, solution) {
  for (var i=0; i<pathList.length; i++) {
    var path = pathList[i]
    var x = path[0].x
    var y = path[0].y
    if (solution.grid[path[0].x][path[0].y].line === 0) continue

    var match = true
    for (var j=1; j<path.length; j++) {
      var cell = solution.grid[x][y]
      if (path[j] === PATH_NONE && cell.end != null) {
        match = false
        break
      } else if (path[j] === PATH_LEFT) {
        if (cell.dir != 'left') {
          match = false
          break
        }
        x--
      } else if (path[j] === PATH_RIGHT) {
        if (cell.dir != 'right') {
          match = false
          break
        }
        x++
      } else if (path[j] === PATH_TOP) {
        if (cell.dir != 'top') {
          match = false
          break
        }
        y--
      } else if (path[j] === PATH_BOTTOM) {
        if (cell.dir != 'bottom') {
          match = false
          break
        }
        y++
      }
    }
    if (match) return i
  }
  return -1
}

})