about summary refs log tree commit diff stats
path: root/app/assets/javascripts/solve.js
diff options
context:
space:
mode:
Diffstat (limited to 'app/assets/javascripts/solve.js')
-rw-r--r--app/assets/javascripts/solve.js531
1 files changed, 531 insertions, 0 deletions
diff --git a/app/assets/javascripts/solve.js b/app/assets/javascripts/solve.js new file mode 100644 index 0000000..8695291 --- /dev/null +++ b/app/assets/javascripts/solve.js
@@ -0,0 +1,531 @@
1namespace(function() {
2
3// @Volatile -- must match order of MOVE_* in trace2
4// Move these, dummy.
5var PATH_NONE = 0
6var PATH_LEFT = 1
7var PATH_RIGHT = 2
8var PATH_TOP = 3
9var PATH_BOTTOM = 4
10
11window.MAX_SOLUTIONS = 0
12var solutionPaths = []
13var asyncTimer = 0
14var task = null
15var puzzle = null
16var path = []
17var SOLVE_SYNC = false
18var SYNC_THRESHOLD = 9 // Depth at which we switch to a synchronous solver (for perf)
19var doPruning = false
20
21var percentages = []
22var NODE_DEPTH = 9
23var nodes = 0
24function countNodes(x, y, depth) {
25 // Check for collisions (outside, gap, self, other)
26 var cell = puzzle.getCell(x, y)
27 if (cell == null) return
28 if (cell.gap > window.GAP_NONE) return
29 if (cell.line !== window.LINE_NONE) return
30
31 if (puzzle.symType == SYM_TYPE_NONE) {
32 puzzle.updateCell2(x, y, 'line', window.LINE_BLACK)
33 } else {
34 var sym = puzzle.getSymmetricalPos(x, y)
35 if (puzzle.matchesSymmetricalPos(x, y, sym.x, sym.y)) return // Would collide with our reflection
36
37 var symCell = puzzle.getCell(sym.x, sym.y)
38 if (symCell.gap > window.GAP_NONE) return
39
40 puzzle.updateCell2(x, y, 'line', window.LINE_BLUE)
41 puzzle.updateCell2(sym.x, sym.y, 'line', window.LINE_YELLOW)
42 }
43
44 if (depth < NODE_DEPTH) {
45 nodes++
46
47 if (y%2 === 0) {
48 countNodes(x - 1, y, depth + 1)
49 countNodes(x + 1, y, depth + 1)
50 }
51
52 if (x%2 === 0) {
53 countNodes(x, y - 1, depth + 1)
54 countNodes(x, y + 1, depth + 1)
55 }
56 }
57
58 tailRecurse(x, y)
59}
60
61// Generates a solution via DFS recursive backtracking
62window.solve = function(p, partialCallback, finalCallback) {
63 if (task != null) throw Error('Cannot start another solve() while one is already in progress')
64 var start = (new Date()).getTime()
65
66 puzzle = p
67 var startPoints = []
68 var numEndpoints = 0
69 puzzle.hasNegations = false
70 puzzle.hasPolyominos = false
71 for (var x=0; x<puzzle.width; x++) {
72 for (var y=0; y<puzzle.height; y++) {
73 var cell = puzzle.grid[x][y]
74 if (cell == null) continue
75 if (cell.start === true) {
76 startPoints.push({'x': x, 'y': y})
77 }
78 if (cell.end != null) numEndpoints++
79 if (cell.type == 'nega') puzzle.hasNegations = true
80 if (cell.type == 'poly' || cell.type == 'ylop') puzzle.hasPolyominos = true
81 }
82 }
83
84 // Puzzles which are small enough should be solved synchronously, since the cost of asynchronizing
85 // is greater than the cost of the puzzle.
86 SOLVE_SYNC = false
87 if (puzzle.symType != SYM_TYPE_NONE) { // 5x5 is the max for symmetry puzzles
88 if (puzzle.width * puzzle.height <= 121) SOLVE_SYNC = true
89 } else if (puzzle.pillar === true) { // 4x5 is the max for non-symmetry, pillar puzzles
90 if (puzzle.width * puzzle.height <= 108) SOLVE_SYNC = true
91 } else { // 5x5 is the max for non-symmetry, non-pillar puzzles
92 if (puzzle.width * puzzle.height <= 121) SOLVE_SYNC = true
93 }
94 console.log('Puzzle is a', puzzle.width, 'by', puzzle.height, 'solving ' + (SOLVE_SYNC ? 'sync' : 'async'))
95
96 // We pre-traverse the grid (only considering obvious failure states like going out of bounds),
97 // and compute a total number of nodes that are reachable within some NODE_DEPTH steps.
98 // Then, during actual traversal, we can compare the number of nodes reached to the precomputed count
99 // to get a (fairly accurate) progress bar.
100 for (var pos of startPoints) {
101 countNodes(pos.x, pos.y, 0)
102 }
103 console.log('Pretraversal found', nodes, 'nodes')
104 percentages = []
105 for (var i=0; i<100; i++) {
106 percentages.push(Math.floor(i * nodes / 100))
107 }
108 nodes = 0
109
110 solutionPaths = []
111 // Some reasonable default data, which will avoid crashes during the solveLoop.
112 var earlyExitData = [false, {'isEdge': false}, {'isEdge': false}]
113 if (window.MAX_SOLUTIONS === 0) window.MAX_SOLUTIONS = 10000
114
115 // Large pruning optimization -- Attempt to early exit once we cut out a region.
116 // Inspired by https://github.com/Overv/TheWitnessSolver
117 // For non-pillar puzzles, every time we draw a line from one edge to another, we cut out two regions.
118 // We can detect this by asking if we've ever left an edge, and determining if we've just touched an edge.
119 // However, just touching the edge isn't sufficient, since we could still enter either region.
120 // As such, we wait one additional step, to see which half we have moved in to, then we evaluate
121 // whichever half you moved away from (since you can no longer re-enter it).
122 //
123 // Consider this pathway (tracing X-X-X-A-B-C).
124 // ....X....
125 // . . X . .
126 // ....X....
127 // . . A . .
128 // ...CB....
129 //
130 // Note that, once we have reached B, the puzzle is divided in half. However, we could go either
131 // left or right -- so we don't know which region is safe to validate.
132 // Once we reach C, however, the region to the right is closed off.
133 // As such, we can start a flood fill from the cell to the right of A, computed by A+(C-B).
134 //
135 // Unfortunately, this optimization doesn't work for pillars, since the two regions are still connected.
136 // Additionally, this optimization doesn't work when custom mechanics are active, as many custom mechanics
137 // depend on the path through the entire puzzle
138 doPruning = (puzzle.pillar === false && !puzzle.settings.CUSTOM_MECHANICS)
139
140 task = {
141 'code': function() {
142 var newTasks = []
143
144 for (var pos of startPoints) {
145 // ;(function(a){}(a))
146 // This syntax is used to forcibly copy arguments which are otherwise part of the loop.
147 // Note that we don't need to copy objects, just value types.
148 ;(function(pos) {
149 newTasks.push(function() {
150 path = [pos]
151 puzzle.startPoint = pos
152 return solveLoop(pos.x, pos.y, numEndpoints, earlyExitData)
153 })
154 }(pos))
155 }
156 return newTasks
157 }
158 }
159
160 taskLoop(partialCallback, function() {
161 var end = (new Date()).getTime()
162 console.log('Solved', puzzle, 'in', (end-start)/1000, 'seconds')
163 if (finalCallback) finalCallback(solutionPaths)
164 })
165 return solutionPaths
166}
167
168function taskLoop(partialCallback, finalCallback) {
169 if (task == null) {
170 finalCallback()
171 return
172 }
173
174 var newTasks = task.code()
175 task = task.nextTask
176 if (newTasks != null && newTasks.length > 0) {
177 // Tasks are pushed in order. To do DFS, we need to enqueue them in reverse order.
178 for (var i=newTasks.length - 1; i >= 0; i--) {
179 task = {
180 'code': newTasks[i],
181 'nextTask': task,
182 }
183 }
184 }
185
186 // Asynchronizing is expensive. As such, we don't want to do it too often.
187 // However, we would like 'cancel solving' to be responsive. So, we call setTimeout every so often.
188 var doAsync = false
189 if (!SOLVE_SYNC) {
190 doAsync = (asyncTimer++ % 100 === 0)
191 while (nodes >= percentages[0]) {
192 if (partialCallback) partialCallback(100 - percentages.length)
193 percentages.shift()
194 doAsync = true
195 }
196 }
197
198 if (doAsync) {
199 setTimeout(function() {
200 taskLoop(partialCallback, finalCallback)
201 }, 0)
202 } else {
203 taskLoop(partialCallback, finalCallback)
204 }
205}
206
207function tailRecurse(x, y) {
208 // Tail recursion: Back out of this cell
209 puzzle.updateCell2(x, y, 'line', window.LINE_NONE)
210 if (puzzle.symType != SYM_TYPE_NONE) {
211 var sym = puzzle.getSymmetricalPos(x, y)
212 puzzle.updateCell2(sym.x, sym.y, 'line', window.LINE_NONE)
213 }
214}
215
216// @Performance: This is the most central loop in this code.
217// Any performance efforts should be focused here.
218// Note: Most mechanics are NP (or harder), so don't feel bad about solving them by brute force.
219// https://arxiv.org/pdf/1804.10193.pdf
220function solveLoop(x, y, numEndpoints, earlyExitData) {
221 // Stop trying to solve once we reach our goal
222 if (solutionPaths.length >= window.MAX_SOLUTIONS) return
223
224 // Check for collisions (outside, gap, self, other)
225 var cell = puzzle.getCell(x, y)
226 if (cell == null) return
227 if (cell.gap > window.GAP_NONE) return
228 if (cell.line !== window.LINE_NONE) return
229
230 if (puzzle.symType == SYM_TYPE_NONE) {
231 puzzle.updateCell2(x, y, 'line', window.LINE_BLACK)
232 } else {
233 var sym = puzzle.getSymmetricalPos(x, y)
234 if (puzzle.matchesSymmetricalPos(x, y, sym.x, sym.y)) return // Would collide with our reflection
235
236 var symCell = puzzle.getCell(sym.x, sym.y)
237 if (symCell.gap > window.GAP_NONE) return
238
239 puzzle.updateCell2(x, y, 'line', window.LINE_BLUE)
240 puzzle.updateCell2(sym.x, sym.y, 'line', window.LINE_YELLOW)
241 }
242
243 if (path.length < NODE_DEPTH) nodes++
244
245 if (cell.end != null) {
246 path.push(PATH_NONE)
247 puzzle.endPoint = {'x': x, 'y': y}
248 var puzzleData = window.validate(puzzle, true)
249 if (puzzleData.valid()) solutionPaths.push(path.slice())
250 path.pop()
251
252 // If there are no further endpoints, tail recurse.
253 // Otherwise, keep going -- we might be able to reach another endpoint.
254 numEndpoints--
255 if (numEndpoints === 0) return tailRecurse(x, y)
256 }
257
258 var newEarlyExitData = null
259 if (doPruning) {
260 var isEdge = x <= 0 || y <= 0 || x >= puzzle.width - 1 || y >= puzzle.height - 1
261 newEarlyExitData = [
262 earlyExitData[0] || (!isEdge && earlyExitData[2].isEdge), // Have we ever left an edge?
263 earlyExitData[2], // The position before our current one
264 {'x':x, 'y':y, 'isEdge':isEdge} // Our current position.
265 ]
266 if (earlyExitData[0] && !earlyExitData[1].isEdge && earlyExitData[2].isEdge && isEdge) {
267 // See the above comment for an explanation of this math.
268 var floodX = earlyExitData[2].x + (earlyExitData[1].x - x)
269 var floodY = earlyExitData[2].y + (earlyExitData[1].y - y)
270 var region = puzzle.getRegion(floodX, floodY)
271 if (region != null) {
272 var regionData = window.validateRegion(puzzle, region, true)
273 if (!regionData.valid()) return tailRecurse(x, y)
274
275 // Additionally, we might have left an endpoint in the enclosed region.
276 // If so, we should decrement the number of remaining endpoints (and possibly tail recurse).
277 for (var pos of region) {
278 var endCell = puzzle.grid[pos.x][pos.y]
279 if (endCell != null && endCell.end != null) numEndpoints--
280 }
281
282 if (numEndpoints === 0) return tailRecurse(x, y)
283 }
284 }
285 }
286
287 if (SOLVE_SYNC || path.length > SYNC_THRESHOLD) {
288 path.push(PATH_NONE)
289
290 // Recursion order (LRUD) is optimized for BL->TR and mid-start puzzles
291 if (y%2 === 0) {
292 path[path.length-1] = PATH_LEFT
293 solveLoop(x - 1, y, numEndpoints, newEarlyExitData)
294
295 path[path.length-1] = PATH_RIGHT
296 solveLoop(x + 1, y, numEndpoints, newEarlyExitData)
297 }
298
299 if (x%2 === 0) {
300 path[path.length-1] = PATH_TOP
301 solveLoop(x, y - 1, numEndpoints, newEarlyExitData)
302
303 path[path.length-1] = PATH_BOTTOM
304 solveLoop(x, y + 1, numEndpoints, newEarlyExitData)
305 }
306
307 path.pop()
308 tailRecurse(x, y)
309
310 } else {
311 // Push a dummy element on the end of the path, so that we can fill it correctly as we DFS.
312 // This element is popped when we tail recurse (which always happens *after* all of our DFS!)
313 path.push(PATH_NONE)
314
315 // Recursion order (LRUD) is optimized for BL->TR and mid-start puzzles
316 var newTasks = []
317 if (y%2 === 0) {
318 newTasks.push(function() {
319 path[path.length-1] = PATH_LEFT
320 return solveLoop(x - 1, y, numEndpoints, newEarlyExitData)
321 })
322 newTasks.push(function() {
323 path[path.length-1] = PATH_RIGHT
324 return solveLoop(x + 1, y, numEndpoints, newEarlyExitData)
325 })
326 }
327
328 if (x%2 === 0) {
329 newTasks.push(function() {
330 path[path.length-1] = PATH_TOP
331 return solveLoop(x, y - 1, numEndpoints, newEarlyExitData)
332 })
333 newTasks.push(function() {
334 path[path.length-1] = PATH_BOTTOM
335 return solveLoop(x, y + 1, numEndpoints, newEarlyExitData)
336 })
337 }
338
339 newTasks.push(function() {
340 path.pop()
341 tailRecurse(x, y)
342 })
343
344 return newTasks
345 }
346}
347
348window.cancelSolving = function() {
349 console.info('Cancelled solving')
350 window.MAX_SOLUTIONS = 0 // Causes all new solveLoop calls to exit immediately.
351 tasks = []
352}
353
354// Only modifies the puzzle object (does not do any graphics updates). Used by metapuzzle.js to determine subpuzzle polyshapes.
355window.drawPathNoUI = function(puzzle, path) {
356 puzzle.clearLines()
357
358 // Extract the start data from the first path element
359 var x = path[0].x
360 var y = path[0].y
361 var cell = puzzle.getCell(x, y)
362 if (cell == null || cell.start !== true) throw Error('Path does not begin with a startpoint: ' + JSON.stringify(cell))
363
364 for (var i=1; i<path.length; i++) {
365 var cell = puzzle.getCell(x, y)
366
367 var dx = 0
368 var dy = 0
369 if (path[i] === PATH_NONE) { // Reached an endpoint, move into it
370 console.debug('Reached endpoint')
371 if (i != path.length-1) throw Error('Path contains ' + (path.length - 1 - i) + ' trailing directions')
372 break
373 } else if (path[i] === PATH_LEFT) dx = -1
374 else if (path[i] === PATH_RIGHT) dx = +1
375 else if (path[i] === PATH_TOP) dy = -1
376 else if (path[i] === PATH_BOTTOM) dy = +1
377 else throw Error('Path element ' + (i-1) + ' was not a valid path direction: ' + path[i])
378
379 x += dx
380 y += dy
381 // Set the cell color
382 if (puzzle.symType == SYM_TYPE_NONE) {
383 cell.line = window.LINE_BLACK
384 } else {
385 cell.line = window.LINE_BLUE
386 var sym = puzzle.getSymmetricalPos(x, y)
387 puzzle.updateCell2(sym.x, sym.y, 'line', window.LINE_YELLOW)
388 }
389 }
390
391 var cell = puzzle.getCell(x, y)
392 if (cell == null || cell.end == null) throw Error('Path does not end at an endpoint: ' + JSON.stringify(cell))
393}
394
395// Uses trace2 to draw the path on the grid, logs a graphical representation of the solution,
396// and also modifies the puzzle to contain the solution path.
397window.drawPath = function(puzzle, path, target='puzzle') {
398 // @Duplicated with trace2.clearGrid
399 var puzzleElem = document.getElementById(target)
400 window.deleteElementsByClassName(puzzleElem, 'cursor')
401 window.deleteElementsByClassName(puzzleElem, 'line-1')
402 window.deleteElementsByClassName(puzzleElem, 'line-2')
403 window.deleteElementsByClassName(puzzleElem, 'line-3')
404 puzzle.clearLines()
405
406 if (path == null || path.length === 0) return // "drawing" an empty path is a shorthand for clearing the grid.
407
408 // Extract the start data from the first path element
409 var x = path[0].x
410 var y = path[0].y
411 var cell = puzzle.getCell(x, y)
412 if (cell == null || cell.start !== true) throw Error('Path does not begin with a startpoint: ' + JSON.stringify(cell))
413
414 var start = document.getElementById('start_' + target + '_' + x + '_' + y)
415 var symStart = document.getElementById('symStart_' + target + '_' + x + '_' + y)
416 window.onTraceStart(puzzle, {'x':x, 'y':y}, document.getElementById(target), start, symStart)
417
418 console.info('Drawing solution of length', path.length)
419 for (var i=1; i<path.length; i++) {
420 var cell = puzzle.getCell(x, y)
421
422 var dx = 0
423 var dy = 0
424 if (path[i] === PATH_NONE) { // Reached an endpoint, move into it
425 console.debug('Reached endpoint')
426 if (cell.end === 'left') {
427 window.onMove(-24, 0)
428 } else if (cell.end === 'right') {
429 window.onMove(24, 0)
430 } else if (cell.end === 'top') {
431 window.onMove(0, -24)
432 } else if (cell.end === 'bottom') {
433 window.onMove(0, 24)
434 }
435 if (i != path.length-1) throw Error('Path contains ' + (path.length - 1 - i) + ' trailing directions')
436 break
437 } else if (path[i] === PATH_LEFT) {
438 dx = -1
439 cell.dir = 'left'
440 } else if (path[i] === PATH_RIGHT) {
441 dx = +1
442 cell.dir = 'right'
443 } else if (path[i] === PATH_TOP) {
444 dy = -1
445 cell.dir = 'top'
446 } else if (path[i] === PATH_BOTTOM) {
447 dy = +1
448 cell.dir = 'down'
449 } else {
450 throw Error('Path element ' + (i-1) + ' was not a valid path direction: ' + path[i])
451 }
452
453 console.debug('Currently at', x, y, cell, 'moving', dx, dy)
454
455 x += dx
456 y += dy
457 // Unflag the cell, move into it, and reflag it
458 cell.line = window.LINE_NONE
459 window.onMove(41 * dx, 41 * dy)
460 if (puzzle.symType == SYM_TYPE_NONE) {
461 cell.line = window.LINE_BLACK
462 } else {
463 cell.line = window.LINE_BLUE
464 var sym = puzzle.getSymmetricalPos(x, y)
465 puzzle.updateCell2(sym.x, sym.y, 'line', window.LINE_YELLOW)
466 }
467 }
468 var cell = puzzle.getCell(x, y)
469 if (cell == null || cell.end == null) throw Error('Path does not end at an endpoint: ' + JSON.stringify(cell))
470
471 var rows = ' |'
472 for (var x=0; x<puzzle.width; x++) {
473 rows += ('' + x).padEnd(5, ' ') + '|'
474 }
475 console.log(rows)
476 for (var y=0; y<puzzle.height; y++) {
477 var output = ('' + y).padEnd(3, ' ') + '|'
478 for (var x=0; x<puzzle.width; x++) {
479 var cell = puzzle.grid[x][y]
480 var dir = (cell != null && cell.dir != null ? cell.dir : '')
481 output += dir.padEnd(5, ' ') + '|'
482 }
483 console.log(output)
484 }
485}
486
487window.getSolutionIndex = function(pathList, solution) {
488 for (var i=0; i<pathList.length; i++) {
489 var path = pathList[i]
490 var x = path[0].x
491 var y = path[0].y
492 if (solution.grid[path[0].x][path[0].y].line === 0) continue
493
494 var match = true
495 for (var j=1; j<path.length; j++) {
496 var cell = solution.grid[x][y]
497 if (path[j] === PATH_NONE && cell.end != null) {
498 match = false
499 break
500 } else if (path[j] === PATH_LEFT) {
501 if (cell.dir != 'left') {
502 match = false
503 break
504 }
505 x--
506 } else if (path[j] === PATH_RIGHT) {
507 if (cell.dir != 'right') {
508 match = false
509 break
510 }
511 x++
512 } else if (path[j] === PATH_TOP) {
513 if (cell.dir != 'top') {
514 match = false
515 break
516 }
517 y--
518 } else if (path[j] === PATH_BOTTOM) {
519 if (cell.dir != 'bottom') {
520 match = false
521 break
522 }
523 y++
524 }
525 }
526 if (match) return i
527 }
528 return -1
529}
530
531})