about summary refs log tree commit diff stats
path: root/app/assets/javascripts/puzzle.js
diff options
context:
space:
mode:
Diffstat (limited to 'app/assets/javascripts/puzzle.js')
-rw-r--r--app/assets/javascripts/puzzle.js538
1 files changed, 538 insertions, 0 deletions
diff --git a/app/assets/javascripts/puzzle.js b/app/assets/javascripts/puzzle.js new file mode 100644 index 0000000..4889e96 --- /dev/null +++ b/app/assets/javascripts/puzzle.js
@@ -0,0 +1,538 @@
1namespace(function() {
2
3// A 2x2 grid is internally a 5x5:
4// corner, edge, corner, edge, corner
5// edge, cell, edge, cell, edge
6// corner, edge, corner, edge, corner
7// edge, cell, edge, cell, edge
8// corner, edge, corner, edge, corner
9//
10// Corners and edges will have a value of true if the line passes through them
11// Cells will contain an object if there is an element in them
12window.Puzzle = class {
13 constructor(width, height, pillar=false) {
14 if (pillar === true) {
15 this.newGrid(2 * width, 2 * height + 1)
16 } else {
17 this.newGrid(2 * width + 1, 2 * height + 1)
18 }
19 this.pillar = pillar
20 this.settings = {
21 // If true, negation symbols are allowed to cancel other negation symbols.
22 NEGATIONS_CANCEL_NEGATIONS: true,
23
24 // If true, and the count of polyominos and onimoylops is zero, they cancel regardless of shape.
25 SHAPELESS_ZERO_POLY: false,
26
27 // If true, the traced line cannot go through the placement of a polyomino.
28 PRECISE_POLYOMINOS: true,
29
30 // If false, incorrect elements will not flash when failing the puzzle.
31 FLASH_FOR_ERRORS: true,
32
33 // If true, mid-segment startpoints will constitute solid lines, and form boundaries for the region.
34 FAT_STARTPOINTS: false,
35
36 // If true, custom mechanics are displayed (and validated) in this puzzle.
37 CUSTOM_MECHANICS: false,
38
39 // If true, polyominos may be placed partially off of the grid as an intermediate solution step.
40 // OUT_OF_BOUNDS_POLY: false,
41
42 // If true, the symmetry line will be invisible.
43 INVISIBLE_SYMMETRY: false,
44 }
45 }
46
47 static deserialize(json) {
48 var parsed = JSON.parse(json)
49 // Claim that it's not a pillar (for consistent grid sizing), then double-check ourselves later.
50 var puzzle = new Puzzle((parsed.grid.length - 1)/2, (parsed.grid[0].length - 1)/2)
51 puzzle.name = parsed.name
52 puzzle.autoSolved = parsed.autoSolved
53 puzzle.grid = parsed.grid
54 // Legacy: Grid squares used to use 'false' to indicate emptiness.
55 // Legacy: Cells may use {} to represent emptiness
56 // Now, we use:
57 // Cells default to null
58 // During onTraceStart, empty cells that are still inbounds are changed to {'type': 'nonce'} for tracing purposes.
59 // Lines default to {'type':'line', 'line':0}
60 for (var x=0; x<puzzle.width; x++) {
61 for (var y=0; y<puzzle.height; y++) {
62 var cell = puzzle.grid[x][y]
63 if (cell === false || cell == null || cell.type == null) {
64 if (x%2 === 1 && y%2 === 1) puzzle.grid[x][y] = null
65 else puzzle.grid[x][y] = {'type':'line', 'line':window.LINE_NONE}
66 } else {
67 if (cell.type === 'poly' || cell.type === 'ylop') {
68 if (cell.rot === 'all') {
69 // Legacy: Polys and ylops used to have a rot value (before I started using polyshape).
70 // rot=all is a holdover that was used to represent rotation polyominos.
71 puzzle.grid[x][y].polyshape |= window.ROTATION_BIT
72 delete puzzle.grid[x][y].rot
73 }
74 // Fixup: Sometimes we have a polyshape which is empty. Just ignore these objects.
75 if (puzzle.grid[x][y].polyshape & ~window.ROTATION_BIT === 0) puzzle.grid[x][y] = null
76 } else if ((x%2 !== 1 || y%2 !== 1) && cell.color != null) {
77 // Legacy: Lines used to use 'color' instead of 'line', but that was redundant with actual colors
78 cell.line = cell.color
79 delete cell.color
80 } else if (cell.gap === true) {
81 // Legacy: Gaps used to be null/true, are now null/1/2
82 puzzle.grid[x][y].gap = window.GAP_BREAK
83 }
84 }
85 }
86 }
87 // Legacy: Startpoints used to be only parsed.start
88 if (parsed.start) {
89 parsed.startPoints = [parsed.start]
90 }
91 // Legacy: Startpoints used to be a separate array, now they are flags
92 if (parsed.startPoints) {
93 for (var startPoint of parsed.startPoints) {
94 puzzle.grid[startPoint.x][startPoint.y].start = true
95 }
96 }
97 // Legacy: Endpoints used to be only parsed.end
98 if (parsed.end) {
99 parsed.endPoints = [parsed.end]
100 }
101 // Legacy: Endpoints used to be a separate array, now they are flags
102 if (parsed.endPoints) {
103 for (var endPoint of parsed.endPoints) {
104 puzzle.grid[endPoint.x][endPoint.y].end = endPoint.dir
105 }
106 }
107 // Legacy: Dots and gaps used to be separate arrays
108 // Now, they are flags on the individual lines.
109 if (parsed.dots) {
110 for (var dot of parsed.dots) {
111 puzzle.grid[dot.x][dot.y].dot = window.DOT_BLACK
112 }
113 }
114 if (parsed.gaps) {
115 for (var gap of parsed.gaps) {
116 puzzle.grid[gap.x][gap.y].gap = window.GAP_BREAK
117 }
118 }
119 if (parsed.settings) {
120 for (var key of Object.keys(parsed.settings)) {
121 puzzle.settings[key] = parsed.settings[key]
122 }
123 }
124 puzzle.pillar = parsed.pillar
125 puzzle.symmetry = parsed.symmetry
126 puzzle.symType = parsed.symType
127 puzzle.largezero = puzzle.width * puzzle.height
128 return puzzle
129 }
130
131 serialize() {
132 return JSON.stringify(this)
133 }
134
135 clone() {
136 return Puzzle.deserialize(this.serialize())
137 }
138
139 // This is explicitly *not* just clearing the grid, so that external references
140 // to the grid are not also cleared.
141 newGrid(width, height) {
142 if (width == null) { // Called by someone who just wants to clear the grid.
143 width = this.width
144 height = this.height
145 }
146 this.grid = []
147 for (var x=0; x<width; x++) {
148 this.grid[x] = []
149 for (var y=0; y<height; y++) {
150 if (x%2 === 1 && y%2 === 1) this.grid[x][y] = null
151 else this.grid[x][y] = {'type':'line', 'line':window.LINE_NONE}
152 }
153 }
154 // Performance: A large value which is === 0 to be used for pillar wrapping.
155 // Performance: Getting the size of the grid has a nonzero cost.
156 // Definitely getting the length of the first element isn't optimized.
157 this.largezero = width * height * 2
158 this.width = this.grid.length
159 this.height = this.grid[0].length
160 }
161
162 // Wrap a value around at the width of the grid. No-op if not in pillar mode.
163 _mod(val) {
164 if (this.pillar === false) return val
165 return (val + this.largezero) % this.width
166 }
167
168 // Determine if an x, y pair is a safe reference inside the grid. This should be invoked at the start of every
169 // function, but then functions can access the grid directly.
170 _safeCell(x, y) {
171 if (x < 0 || x >= this.width) return false
172 if (y < 0 || y >= this.height) return false
173 return true
174 }
175
176 getCell(x, y) {
177 x = this._mod(x)
178 if (!this._safeCell(x, y)) return null
179 return this.grid[x][y]
180 }
181
182 setCell(x, y, value) {
183 x = this._mod(x)
184 if (!this._safeCell(x, y)) return
185 this.grid[x][y] = value
186 }
187
188 getSymmetricalDir(dir) {
189 if (this.symType == SYM_TYPE_VERTICAL || this.symType == SYM_TYPE_ROTATIONAL || this.symType == SYM_TYPE_PARALLEL_H_FLIP) {
190 if (dir === 'left') return 'right'
191 if (dir === 'right') return 'left'
192 }
193 if (this.symType == SYM_TYPE_HORIZONTAL || this.symType == SYM_TYPE_ROTATIONAL || this.symType == SYM_TYPE_PARALLEL_V_FLIP) {
194 if (dir === 'top') return 'bottom'
195 if (dir === 'bottom') return 'top'
196 }
197 if (this.symType == SYM_TYPE_ROTATE_LEFT || this.symType == SYM_TYPE_FLIP_NEG_XY) {
198 if (dir === 'left') return 'bottom'
199 if (dir === 'right') return 'top'
200 }
201 if (this.symType == SYM_TYPE_ROTATE_RIGHT || this.symType == SYM_TYPE_FLIP_NEG_XY) {
202 if (dir === 'top') return 'right'
203 if (dir === 'bottom') return 'left'
204 }
205 if (this.symType == SYM_TYPE_ROTATE_LEFT || this.symType == SYM_TYPE_FLIP_XY) {
206 if (dir === 'top') return 'left'
207 if (dir === 'bottom') return 'right'
208 }
209 if (this.symType == SYM_TYPE_ROTATE_RIGHT || this.symType == SYM_TYPE_FLIP_XY) {
210 if (dir === 'right') return 'bottom'
211 if (dir === 'left') return 'top'
212 }
213 return dir
214 }
215
216 // The resulting position is guaranteed to be gridsafe.
217 getSymmetricalPos(x, y) {
218 var origx = x
219 var origy = y
220
221 if (this.symType == SYM_TYPE_VERTICAL || this.symType == SYM_TYPE_ROTATIONAL || this.symType == SYM_TYPE_PARALLEL_H_FLIP) {
222 x = (this.width - 1) - origx
223 }
224 if (this.symType == SYM_TYPE_HORIZONTAL || this.symType == SYM_TYPE_ROTATIONAL || this.symType == SYM_TYPE_PARALLEL_V_FLIP) {
225 y = (this.height - 1) - origy
226 }
227 if (this.symType == SYM_TYPE_ROTATE_LEFT || this.symType == SYM_TYPE_FLIP_XY) {
228 x = origy
229 }
230 if (this.symType == SYM_TYPE_ROTATE_RIGHT || this.symType == SYM_TYPE_FLIP_XY) {
231 y = origx
232 }
233 if (this.symType == SYM_TYPE_ROTATE_LEFT || this.symType == SYM_TYPE_FLIP_NEG_XY) {
234 y = (this.width - 1) - origx
235 }
236 if (this.symType == SYM_TYPE_ROTATE_RIGHT || this.symType == SYM_TYPE_FLIP_NEG_XY) {
237 x = (this.height - 1) - origy
238 }
239 if (this.symType == SYM_TYPE_PARALLEL_H || this.symType == SYM_TYPE_PARALLEL_H_FLIP) {
240 y = (origy == this.height / 2) ? (this.height / 2) : ((origy + (this.height + 1) / 2) % (this.height + 1))
241 }
242 if (this.symType == SYM_TYPE_PARALLEL_V || this.symType == SYM_TYPE_PARALLEL_V_FLIP) {
243 x = (origx == this.width / 2) ? (this.width / 2) : ((origx + (this.width + 1) / 2) % (this.width + 1))
244 }
245
246 return {'x':this._mod(x), 'y':y}
247 }
248
249 getSymmetricalCell(x, y) {
250 var pos = this.getSymmetricalPos(x, y)
251 return this.getCell(pos.x, pos.y)
252 }
253
254 matchesSymmetricalPos(x1, y1, x2, y2) {
255 return (y1 === y2 && this._mod(x1) === x2)
256 }
257
258 // A variant of getCell which specifically returns line values,
259 // and treats objects as being out-of-bounds
260 getLine(x, y) {
261 var cell = this.getCell(x, y)
262 if (cell == null) return null
263 if (cell.type !== 'line') return null
264 return cell.line
265 }
266
267 updateCell2(x, y, key, value) {
268 x = this._mod(x)
269 if (!this._safeCell(x, y)) return
270 var cell = this.grid[x][y]
271 if (cell == null) return
272 cell[key] = value
273 }
274
275 getValidEndDirs(x, y) {
276 x = this._mod(x)
277 if (!this._safeCell(x, y)) return []
278
279 var dirs = []
280 var leftCell = this.getCell(x - 1, y)
281 if (leftCell == null || leftCell.gap === window.GAP_FULL) dirs.push('left')
282 var topCell = this.getCell(x, y - 1)
283 if (topCell == null || topCell.gap === window.GAP_FULL) dirs.push('top')
284 var rightCell = this.getCell(x + 1, y)
285 if (rightCell == null || rightCell.gap === window.GAP_FULL) dirs.push('right')
286 var bottomCell = this.getCell(x, y + 1)
287 if (bottomCell == null || bottomCell.gap === window.GAP_FULL) dirs.push('bottom')
288 return dirs
289 }
290
291 // Note: Does not use this.width/this.height, so that it may be used to ask about resizing.
292 getSizeError(width, height) {
293 if (this.pillar && width < 4) return 'Pillars may not have a width of 1'
294 if (width * height < 25) return 'Puzzles may not be smaller than 2x2 or 1x4'
295 if (width > 21 || height > 21) return 'Puzzles may not be larger than 10 in either dimension'
296 if (this.symmetry != null) {
297 if (this.symmetry.x && width <= 2) return 'Symmetrical puzzles must be sufficiently wide for both lines'
298 if (this.symmetry.y && height <= 2) return 'Symmetrical puzzles must be sufficiently wide for both lines'
299 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'
300 }
301
302 return null
303 }
304
305
306 // Called on a solution. Computes a list of gaps to show as hints which *do not*
307 // break the path.
308 loadHints() {
309 this.hints = []
310 for (var x=0; x<this.width; x++) {
311 for (var y=0; y<this.height; y++) {
312 if (x%2 + y%2 === 1 && this.getLine(x, y) > window.LINE_NONE) {
313 this.hints.push({'x':x, 'y':y})
314 }
315 }
316 }
317 }
318
319 // Show a hint on the grid.
320 // If no hint is provided, will select the best one it can find,
321 // prioritizing breaking current lines on the grid.
322 // Returns the shown hint.
323 showHint(hint) {
324 if (hint != null) {
325 this.grid[hint.x][hint.y].gap = window.GAP_BREAK
326 return
327 }
328
329 var goodHints = []
330 var badHints = []
331
332 for (var hint of this.hints) {
333 if (this.getLine(hint.x, hint.y) > window.LINE_NONE) {
334 // Solution will be broken by this hint
335 goodHints.push(hint)
336 } else {
337 badHints.push(hint)
338 }
339 }
340 if (goodHints.length > 0) {
341 var hint = goodHints.splice(window.randInt(goodHints.length), 1)[0]
342 } else if (badHints.length > 0) {
343 var hint = badHints.splice(window.randInt(badHints.length), 1)[0]
344 } else {
345 return
346 }
347 this.grid[hint.x][hint.y].gap = window.GAP_BREAK
348 this.hints = badHints.concat(goodHints)
349 return hint
350 }
351
352 clearLines() {
353 for (var x=0; x<this.width; x++) {
354 for (var y=0; y<this.height; y++) {
355 this.updateCell2(x, y, 'line', 0)
356 this.updateCell2(x, y, 'dir', null)
357 }
358 }
359 }
360
361 _floodFill(x, y, region, col) {
362 var cell = col[y]
363 if (cell === MASKED_PROCESSED) return
364 if (cell !== MASKED_INB_NONCOUNT) {
365 region.push({'x':x, 'y':y})
366 }
367 col[y] = MASKED_PROCESSED
368
369 if (y < this.height - 1) this._floodFill(x, y + 1, region, col)
370 if (y > 0) this._floodFill(x, y - 1, region, col)
371 if (x < this.width - 1) this._floodFill(x + 1, y, region, this.grid[x+1])
372 else if (this.pillar !== false) this._floodFill(0, y, region, this.grid[0])
373 if (x > 0) this._floodFill(x - 1, y, region, this.grid[x-1])
374 else if (this.pillar !== false) this._floodFill(this.width-1, y, region, this.grid[this.width-1])
375 }
376
377 // Re-uses the same grid, but only called on edges which border the outside
378 // Called first to mark cells that are connected to the outside, i.e. should not be part of any region.
379 _floodFillOutside(x, y, col) {
380 var cell = col[y]
381 if (cell === MASKED_PROCESSED) return
382 if (x%2 !== y%2 && cell !== MASKED_GAP2) return // Only flood-fill through gap-2
383 if (x%2 === 0 && y%2 === 0 && cell === MASKED_DOT) return // Don't flood-fill through dots
384 col[y] = MASKED_PROCESSED
385
386 if (x%2 === 0 && y%2 === 0) return // Don't flood fill through corners (what? Clarify.)
387
388 if (y < this.height - 1) this._floodFillOutside(x, y + 1, col)
389 if (y > 0) this._floodFillOutside(x, y - 1, col)
390 if (x < this.width - 1) this._floodFillOutside(x + 1, y, this.grid[x+1])
391 else if (this.pillar !== false) this._floodFillOutside(0, y, this.grid[0])
392 if (x > 0) this._floodFillOutside(x - 1, y, this.grid[x-1])
393 else if (this.pillar !== false) this._floodFillOutside(this.width-1, y, this.grid[this.width-1])
394 }
395
396 // Returns the original grid (pre-masking). You will need to switch back once you are done flood filling.
397 switchToMaskedGrid() {
398 // Make a copy of the grid -- we will be overwriting it
399 var savedGrid = this.grid
400 this.grid = new Array(this.width)
401 // Override all elements with empty lines -- this means that flood fill is just
402 // looking for lines with line=0.
403 for (var x=0; x<this.width; x++) {
404 var savedRow = savedGrid[x]
405 var row = new Array(this.height)
406 var skip = 1
407 if (x%2 === 1) { // Cells are always part of the region
408 for (var y=1; y<this.height; y+=2) row[y] = MASKED_INB_COUNT
409 skip = 2 // Skip these cells during iteration
410 }
411 for (var y=0; y<this.height; y+=skip) {
412 var cell = savedRow[y]
413 if (cell.line > window.LINE_NONE) {
414 row[y] = MASKED_PROCESSED // Traced lines should not be a part of the region
415 } else if (cell.gap === window.GAP_FULL) {
416 row[y] = MASKED_GAP2
417 } else if (cell.dot > window.DOT_NONE) {
418 row[y] = MASKED_DOT
419 } else {
420 row[y] = MASKED_INB_COUNT
421 }
422 }
423 this.grid[x] = row
424 }
425
426 // Starting at a mid-segment startpoint
427 if (this.startPoint != null && this.startPoint.x%2 !== this.startPoint.y%2) {
428 if (this.settings.FAT_STARTPOINTS) {
429 // This segment is not in any region (acts as a barrier)
430 this.grid[this.startPoint.x][this.startPoint.y] = MASKED_OOB
431 } else {
432 // This segment is part of this region (acts as an empty cell)
433 this.grid[this.startPoint.x][this.startPoint.y] = MASKED_INB_NONCOUNT
434 }
435 }
436
437 // Ending at a mid-segment endpoint
438 if (this.endPoint != null && this.endPoint.x%2 !== this.endPoint.y%2) {
439 // This segment is part of this region (acts as an empty cell)
440 this.grid[this.endPoint.x][this.endPoint.y] = MASKED_INB_NONCOUNT
441 }
442
443 // Mark all outside cells as 'not in any region' (aka null)
444
445 // Top and bottom edges
446 for (var x=1; x<this.width; x+=2) {
447 this._floodFillOutside(x, 0, this.grid[x])
448 this._floodFillOutside(x, this.height - 1, this.grid[x])
449 }
450
451 // Left and right edges (only applies to non-pillars)
452 if (this.pillar === false) {
453 for (var y=1; y<this.height; y+=2) {
454 this._floodFillOutside(0, y, this.grid[0])
455 this._floodFillOutside(this.width - 1, y, this.grid[this.width-1])
456 }
457 }
458
459 return savedGrid
460 }
461
462 getRegions() {
463 var regions = []
464 var savedGrid = this.switchToMaskedGrid()
465
466 for (var x=0; x<this.width; x++) {
467 for (var y=0; y<this.height; y++) {
468 if (this.grid[x][y] == MASKED_PROCESSED) continue
469
470 // If this cell is empty (aka hasn't already been used by a region), then create a new one
471 // This will also mark all lines inside the new region as used.
472 var region = []
473 this._floodFill(x, y, region, this.grid[x])
474 regions.push(region)
475 }
476 }
477 this.grid = savedGrid
478 return regions
479 }
480
481 getRegion(x, y) {
482 x = this._mod(x)
483 if (!this._safeCell(x, y)) return
484
485 var savedGrid = this.switchToMaskedGrid()
486 if (this.grid[x][y] == MASKED_PROCESSED) {
487 this.grid = savedGrid
488 return null
489 }
490
491 // If the masked grid hasn't been used at this point, then create a new region.
492 // This will also mark all lines inside the new region as used.
493 var region = []
494 this._floodFill(x, y, region, this.grid[x])
495
496 this.grid = savedGrid
497 return region
498 }
499
500 logGrid() {
501 var output = ''
502 for (var y=0; y<this.height; y++) {
503 var row = []
504 for (var x=0; x<this.width; x++) {
505 var cell = this.getCell(x, y)
506 if (cell == null) row[x] = ' '
507 else if (cell.type === 'nonce') row[x] = ' '
508 else if (cell.start === true) row[x] = 'S'
509 else if (cell.end != null) row[x] = 'E'
510 else if (cell.type === 'line') {
511 if (cell.gap > 0) row[x] = ' '
512 if (cell.dot > 0) row[x] = 'X'
513 if (cell.line === 0) row[x] = '.'
514 if (cell.line === 1) row[x] = '#'
515 if (cell.line === 2) row[x] = '#'
516 if (cell.line === 3) row[x] = 'o'
517 } else row[x] = '?'
518 }
519 output += row.join('') + '\n'
520 }
521 console.info(output)
522 }
523}
524
525// The grid contains 5 colors:
526// null: Out of bounds or already processed
527var MASKED_OOB = null
528var MASKED_PROCESSED = null
529// 0: In bounds, awaiting processing, but should not be part of the final region.
530var MASKED_INB_NONCOUNT = 0
531// 1: In bounds, awaiting processing
532var MASKED_INB_COUNT = 1
533// 2: Gap-2. After _floodFillOutside, this means "treat normally" (it will be null if oob)
534var MASKED_GAP2 = 2
535// 3: Dot (of any kind), otherwise identical to 1. Should not be flood-filled through (why the f do we need this)
536var MASKED_DOT = 3
537
538})