diff options
author | Star Rauchenberger <fefferburbia@gmail.com> | 2023-11-30 13:29:08 -0500 |
---|---|---|
committer | Star Rauchenberger <fefferburbia@gmail.com> | 2023-11-30 13:29:08 -0500 |
commit | 0929719a845897cc8567cf972e07a69a71f0fa6f (patch) | |
tree | 2b6f69c1d906abb6e0abf8a0f1d51725bc78087d /app/assets/javascripts/validate.js | |
parent | 01c1947537e4e23ded0c16812a7cd9d49ad88356 (diff) | |
download | wittle-0929719a845897cc8567cf972e07a69a71f0fa6f.tar.gz wittle-0929719a845897cc8567cf972e07a69a71f0fa6f.tar.bz2 wittle-0929719a845897cc8567cf972e07a69a71f0fa6f.zip |
Migrate to a full rails app
Diffstat (limited to 'app/assets/javascripts/validate.js')
-rw-r--r-- | app/assets/javascripts/validate.js | 391 |
1 files changed, 391 insertions, 0 deletions
diff --git a/app/assets/javascripts/validate.js b/app/assets/javascripts/validate.js new file mode 100644 index 0000000..d6e6484 --- /dev/null +++ b/app/assets/javascripts/validate.js | |||
@@ -0,0 +1,391 @@ | |||
1 | namespace(function() { | ||
2 | |||
3 | class RegionData { | ||
4 | constructor() { | ||
5 | this.invalidElements = [] | ||
6 | this.veryInvalidElements = [] | ||
7 | this.negations = [] | ||
8 | } | ||
9 | |||
10 | addInvalid(elem) { | ||
11 | this.invalidElements.push(elem) | ||
12 | } | ||
13 | |||
14 | addVeryInvalid(elem) { | ||
15 | this.veryInvalidElements.push(elem) | ||
16 | } | ||
17 | |||
18 | valid() { | ||
19 | return (this.invalidElements.length === 0 && this.veryInvalidElements.length === 0) | ||
20 | } | ||
21 | } | ||
22 | |||
23 | // Sanity checks for data which comes from the user. Now that people have learned that /publish is an open endpoint, | ||
24 | // we have to make sure they don't submit data which passes validation but is untrustworthy. | ||
25 | // These checks should always pass for puzzles created by the built-in editor. | ||
26 | window.validateUserData = function(puzzle, path) { | ||
27 | if (path == null) throw Error('Path cannot be null') | ||
28 | |||
29 | var sizeError = puzzle.getSizeError(puzzle.width, puzzle.height) | ||
30 | if (sizeError != null) throw Error(sizeError) | ||
31 | |||
32 | var puzzleHasStart = false | ||
33 | var puzzleHasEnd = false | ||
34 | |||
35 | if (puzzle.grid.length !== puzzle.width) throw Error('Puzzle width does not match grid size') | ||
36 | for (var x=0; x<puzzle.width; x++) { | ||
37 | if (puzzle.grid[x].length !== puzzle.height) throw Error('Puzzle height does not match grid size') | ||
38 | for (var y=0; y<puzzle.height; y++) { | ||
39 | var cell = puzzle.grid[x][y] | ||
40 | if (cell == null) continue | ||
41 | |||
42 | if (cell.start === true) { | ||
43 | puzzleHasStart = true | ||
44 | if (puzzle.symType != SYM_TYPE_NONE) { | ||
45 | var symCell = puzzle.getSymmetricalCell(x, y) | ||
46 | if (symCell == null || symCell.start !== true) { | ||
47 | throw Error('Startpoint at ' + x + ' ' + y + ' does not have a symmetrical startpoint') | ||
48 | } | ||
49 | } | ||
50 | } | ||
51 | if (cell.end != null) { | ||
52 | puzzleHasEnd = true | ||
53 | if (puzzle.symType != SYM_TYPE_NONE) { | ||
54 | var symCell = puzzle.getSymmetricalCell(x, y) | ||
55 | if (symCell == null || symCell.end == null || symCell.end != puzzle.getSymmetricalDir(cell.end)) { | ||
56 | throw Error('Endpoint at ' + x + ' ' + y + ' does not have a symmetrical endpoint') | ||
57 | } | ||
58 | } | ||
59 | } | ||
60 | } | ||
61 | } | ||
62 | if (!puzzleHasStart) throw Error('Puzzle does not have a startpoint') | ||
63 | if (!puzzleHasEnd) throw Error('Puzzle does not have an endpoint') | ||
64 | } | ||
65 | // Determines if the current grid state is solvable. Modifies the puzzle element with: | ||
66 | // valid: Whether or not the puzzle is valid | ||
67 | // invalidElements: Symbols which are invalid (for the purpose of negating / flashing) | ||
68 | // negations: Negation pairs (for the purpose of darkening) | ||
69 | window.validate = function(puzzle, quick) { | ||
70 | console.log('Validating', puzzle) | ||
71 | var puzzleData = new RegionData() // Assumed valid until we find an invalid element | ||
72 | |||
73 | var needsRegions = false | ||
74 | // These two are both used by validateRegion, so they are saved on the puzzle itself. | ||
75 | puzzle.hasNegations = false | ||
76 | puzzle.hasPolyominos = false | ||
77 | |||
78 | // Validate gap failures as an early exit. | ||
79 | for (var x=0; x<puzzle.width; x++) { | ||
80 | for (var y=0; y<puzzle.height; y++) { | ||
81 | var cell = puzzle.grid[x][y] | ||
82 | if (cell == null) continue | ||
83 | if (!needsRegions && cell.type != 'line' && cell.type != 'triangle') needsRegions = true | ||
84 | if (cell.type == 'nega') puzzle.hasNegations = true | ||
85 | if (cell.type == 'poly' || cell.type == 'ylop') puzzle.hasPolyominos = true | ||
86 | if (cell.line > window.LINE_NONE) { | ||
87 | if (cell.gap > window.GAP_NONE) { | ||
88 | console.log('Solution line goes over a gap at', x, y) | ||
89 | puzzleData.invalidElements.push({'x': x, 'y': y}) | ||
90 | if (quick) return puzzleData | ||
91 | } | ||
92 | if ((cell.dot === window.DOT_BLUE && cell.line === window.LINE_YELLOW) || | ||
93 | (cell.dot === window.DOT_YELLOW && cell.line === window.LINE_BLUE)) { | ||
94 | console.log('Incorrectly covered dot: Dot is', cell.dot, 'but line is', cell.line) | ||
95 | puzzleData.invalidElements.push({'x': x, 'y': y}) | ||
96 | if (quick) return puzzleData | ||
97 | } | ||
98 | } | ||
99 | } | ||
100 | } | ||
101 | |||
102 | if (needsRegions) { | ||
103 | var regions = puzzle.getRegions() | ||
104 | } else { | ||
105 | var monoRegion = [] | ||
106 | for (var x=0; x<puzzle.width; x++) { | ||
107 | for (var y=0; y<puzzle.height; y++) { | ||
108 | if (x%2 === 1 && y%2 === 1) { | ||
109 | monoRegion.push({'x': x, 'y': y}) | ||
110 | } else if (puzzle.grid[x][y].line === window.LINE_NONE) { | ||
111 | monoRegion.push({'x': x, 'y': y}) | ||
112 | } | ||
113 | } | ||
114 | } | ||
115 | var regions = [monoRegion] | ||
116 | } | ||
117 | console.log('Found', regions.length, 'region(s)') | ||
118 | console.debug(regions) | ||
119 | |||
120 | if (puzzle.settings.CUSTOM_MECHANICS) { | ||
121 | for (var region of regions) { | ||
122 | regionData = validateRegion(puzzle, region, quick) | ||
123 | puzzleData.negations = puzzleData.negations.concat(regionData.negations) | ||
124 | puzzleData.invalidElements = puzzleData.invalidElements.concat(regionData.invalidElements) | ||
125 | puzzleData.invalidElements = puzzleData.invalidElements.concat(regionData.veryInvalidElements) | ||
126 | } | ||
127 | // When using custom mechanics, we have to handle negations slightly differently. | ||
128 | // Negations need to be applied after all regions are validated, so that we can evaluate negations for | ||
129 | // all regions simultaneously. This is because certain custom mechanics are cross-region. | ||
130 | |||
131 | // ... | ||
132 | |||
133 | } else { | ||
134 | for (var region of regions) { | ||
135 | regionData = validateRegion(puzzle, region, quick) | ||
136 | console.log('Region valid:', regionData.valid()) | ||
137 | puzzleData.negations = puzzleData.negations.concat(regionData.negations) | ||
138 | puzzleData.invalidElements = puzzleData.invalidElements.concat(regionData.invalidElements) | ||
139 | // Note: Not using veryInvalid because I don't need to do logic on these elements, just flash them. | ||
140 | puzzleData.invalidElements = puzzleData.invalidElements.concat(regionData.veryInvalidElements) | ||
141 | if (quick && !puzzleData.valid()) break | ||
142 | } | ||
143 | } | ||
144 | console.log('Puzzle has', puzzleData.invalidElements.length, 'invalid elements') | ||
145 | return puzzleData | ||
146 | } | ||
147 | |||
148 | // Determines whether or not a particular region is valid or not, including negation symbols. | ||
149 | // If quick is true, exits after the first invalid element is found (small performance gain) | ||
150 | // This function applies negations to all "very invalid elements", i.e. elements which cannot become | ||
151 | // valid by another element being negated. Then, it passes off to regionCheckNegations2, | ||
152 | // which attempts to apply any remaining negations to any other invalid elements. | ||
153 | window.validateRegion = function(puzzle, region, quick) { | ||
154 | if (!puzzle.hasNegations) return regionCheck(puzzle, region, quick) | ||
155 | |||
156 | // Get a list of negation symbols in the grid, and set them to 'nonce' | ||
157 | var negationSymbols = [] | ||
158 | for (var pos of region) { | ||
159 | var cell = puzzle.grid[pos.x][pos.y] | ||
160 | if (cell != null && cell.type === 'nega') { | ||
161 | pos.cell = cell | ||
162 | negationSymbols.push(pos) | ||
163 | puzzle.updateCell2(pos.x, pos.y, 'type', 'nonce') | ||
164 | } | ||
165 | } | ||
166 | console.debug('Found', negationSymbols.length, 'negation symbols') | ||
167 | if (negationSymbols.length === 0) { | ||
168 | // No negation symbols in this region. Note that there must be negation symbols elsewhere | ||
169 | // in the puzzle, since puzzle.hasNegations was true. | ||
170 | return regionCheck(puzzle, region, quick) | ||
171 | } | ||
172 | |||
173 | // Get a list of elements that are currently invalid (before any negations are applied) | ||
174 | // This cannot be quick, as we need a full list (for the purposes of negation). | ||
175 | var regionData = regionCheck(puzzle, region, false) | ||
176 | console.debug('Negation-less regioncheck valid:', regionData.valid()) | ||
177 | |||
178 | // Set 'nonce' back to 'nega' for the negation symbols | ||
179 | for (var pos of negationSymbols) { | ||
180 | puzzle.updateCell2(pos.x, pos.y, 'type', 'nega') | ||
181 | } | ||
182 | |||
183 | var invalidElements = regionData.invalidElements | ||
184 | var veryInvalidElements = regionData.veryInvalidElements | ||
185 | |||
186 | for (var i=0; i<invalidElements.length; i++) { | ||
187 | invalidElements[i].cell = puzzle.getCell(invalidElements[i].x, invalidElements[i].y) | ||
188 | } | ||
189 | for (var i=0; i<veryInvalidElements.length; i++) { | ||
190 | veryInvalidElements[i].cell = puzzle.getCell(veryInvalidElements[i].x, veryInvalidElements[i].y) | ||
191 | } | ||
192 | |||
193 | console.debug('Forcibly negating', veryInvalidElements.length, 'symbols') | ||
194 | var baseCombination = [] | ||
195 | while (negationSymbols.length > 0 && veryInvalidElements.length > 0) { | ||
196 | var source = negationSymbols.pop() | ||
197 | var target = veryInvalidElements.pop() | ||
198 | puzzle.setCell(source.x, source.y, null) | ||
199 | puzzle.setCell(target.x, target.y, null) | ||
200 | baseCombination.push({'source':source, 'target':target}) | ||
201 | } | ||
202 | |||
203 | var regionData = regionCheckNegations2(puzzle, region, negationSymbols, invalidElements) | ||
204 | |||
205 | // Restore required negations | ||
206 | for (var combination of baseCombination) { | ||
207 | puzzle.setCell(combination.source.x, combination.source.y, combination.source.cell) | ||
208 | puzzle.setCell(combination.target.x, combination.target.y, combination.target.cell) | ||
209 | regionData.negations.push(combination) | ||
210 | } | ||
211 | return regionData | ||
212 | } | ||
213 | |||
214 | // Recursively matches negations and invalid elements from the grid. Note that this function | ||
215 | // doesn't actually modify the two lists, it just iterates through them with index/index2. | ||
216 | function regionCheckNegations2(puzzle, region, negationSymbols, invalidElements, index=0, index2=0) { | ||
217 | if (index2 >= negationSymbols.length) { | ||
218 | console.debug('0 negation symbols left, returning negation-less regionCheck') | ||
219 | return regionCheck(puzzle, region, false) // @Performance: We could pass quick here. | ||
220 | } | ||
221 | |||
222 | if (index >= invalidElements.length) { | ||
223 | var i = index2 | ||
224 | // pair off all negation symbols, 2 at a time | ||
225 | if (puzzle.settings.NEGATIONS_CANCEL_NEGATIONS) { | ||
226 | for (; i<negationSymbols.length-1; i+=2) { | ||
227 | var source = negationSymbols[i] | ||
228 | var target = negationSymbols[i+1] | ||
229 | puzzle.setCell(source.x, source.y, null) | ||
230 | puzzle.setCell(target.x, target.y, null) | ||
231 | } | ||
232 | } | ||
233 | |||
234 | console.debug(negationSymbols.length - i, 'negation symbol(s) left over with nothing to negate') | ||
235 | for (; i<negationSymbols.length; i++) { | ||
236 | puzzle.updateCell2(negationSymbols[i].x, negationSymbols[i].y, 'type', 'nonce') | ||
237 | } | ||
238 | // Cannot be quick, as we need the full list of invalid symbols. | ||
239 | var regionData = regionCheck(puzzle, region, false) | ||
240 | |||
241 | i = index2 | ||
242 | if (puzzle.settings.NEGATIONS_CANCEL_NEGATIONS) { | ||
243 | for (; i<negationSymbols.length-1; i+=2) { | ||
244 | var source = negationSymbols[i] | ||
245 | var target = negationSymbols[i+1] | ||
246 | puzzle.setCell(source.x, source.y, source.cell) | ||
247 | puzzle.setCell(target.x, target.y, target.cell) | ||
248 | regionData.negations.push({'source':source, 'target':target}) | ||
249 | } | ||
250 | } | ||
251 | for (; i<negationSymbols.length; i++) { | ||
252 | puzzle.updateCell2(negationSymbols[i].x, negationSymbols[i].y, 'type', 'nega') | ||
253 | regionData.addInvalid(negationSymbols[i]) | ||
254 | } | ||
255 | return regionData | ||
256 | } | ||
257 | |||
258 | var source = negationSymbols[index2++] | ||
259 | puzzle.setCell(source.x, source.y, null) | ||
260 | |||
261 | var firstRegionData = null | ||
262 | for (var i=index; i<invalidElements.length; i++) { | ||
263 | var target = invalidElements[i] | ||
264 | console.spam('Attempting negation pair', source, target) | ||
265 | |||
266 | console.group() | ||
267 | puzzle.setCell(target.x, target.y, null) | ||
268 | var regionData = regionCheckNegations2(puzzle, region, negationSymbols, invalidElements, i + 1, index2) | ||
269 | puzzle.setCell(target.x, target.y, target.cell) | ||
270 | console.groupEnd() | ||
271 | |||
272 | if (!firstRegionData) { | ||
273 | firstRegionData = regionData | ||
274 | firstRegionData.negations.push({'source':source, 'target':target}) | ||
275 | } | ||
276 | if (regionData.valid()) { | ||
277 | regionData.negations.push({'source':source, 'target':target}) | ||
278 | break | ||
279 | } | ||
280 | } | ||
281 | |||
282 | puzzle.setCell(source.x, source.y, source.cell) | ||
283 | // For display purposes only. The first attempt will always pair off the most negation symbols, | ||
284 | // so it's the best choice to display (if we're going to fail). | ||
285 | return (regionData.valid() ? regionData : firstRegionData) | ||
286 | } | ||
287 | |||
288 | // Checks if a region is valid. This does not handle negations -- we assume that there are none. | ||
289 | // Note that this function needs to always ask the puzzle for the current contents of the cell, | ||
290 | // since the region is only coordinate locations, and might be modified by regionCheckNegations2 | ||
291 | // @Performance: This is a pretty core function to the solve loop. | ||
292 | function regionCheck(puzzle, region, quick) { | ||
293 | console.log('Validating region of size', region.length, region) | ||
294 | var regionData = new RegionData() | ||
295 | |||
296 | var squares = [] | ||
297 | var stars = [] | ||
298 | var coloredObjects = {} | ||
299 | var squareColor = null | ||
300 | |||
301 | for (var pos of region) { | ||
302 | var cell = puzzle.grid[pos.x][pos.y] | ||
303 | if (cell == null) continue | ||
304 | |||
305 | // Check for uncovered dots | ||
306 | if (cell.dot > window.DOT_NONE) { | ||
307 | console.log('Dot at', pos.x, pos.y, 'is not covered') | ||
308 | regionData.addVeryInvalid(pos) | ||
309 | if (quick) return regionData | ||
310 | } | ||
311 | |||
312 | // Check for triangles | ||
313 | if (cell.type === 'triangle') { | ||
314 | var count = 0 | ||
315 | if (puzzle.getLine(pos.x - 1, pos.y) > window.LINE_NONE) count++ | ||
316 | if (puzzle.getLine(pos.x + 1, pos.y) > window.LINE_NONE) count++ | ||
317 | if (puzzle.getLine(pos.x, pos.y - 1) > window.LINE_NONE) count++ | ||
318 | if (puzzle.getLine(pos.x, pos.y + 1) > window.LINE_NONE) count++ | ||
319 | if (cell.count !== count) { | ||
320 | console.log('Triangle at grid['+pos.x+']['+pos.y+'] has', count, 'borders') | ||
321 | regionData.addVeryInvalid(pos) | ||
322 | if (quick) return regionData | ||
323 | } | ||
324 | } | ||
325 | |||
326 | // Count color-based elements | ||
327 | if (cell.color != null) { | ||
328 | var count = coloredObjects[cell.color] | ||
329 | if (count == null) { | ||
330 | count = 0 | ||
331 | } | ||
332 | coloredObjects[cell.color] = count + 1 | ||
333 | |||
334 | if (cell.type === 'square') { | ||
335 | squares.push(pos) | ||
336 | if (squareColor == null) { | ||
337 | squareColor = cell.color | ||
338 | } else if (squareColor != cell.color) { | ||
339 | squareColor = -1 // Signal value which indicates square color collision | ||
340 | } | ||
341 | } | ||
342 | |||
343 | if (cell.type === 'star') { | ||
344 | pos.color = cell.color | ||
345 | stars.push(pos) | ||
346 | } | ||
347 | } | ||
348 | } | ||
349 | |||
350 | if (squareColor === -1) { | ||
351 | regionData.invalidElements = regionData.invalidElements.concat(squares) | ||
352 | if (quick) return regionData | ||
353 | } | ||
354 | |||
355 | for (var star of stars) { | ||
356 | var count = coloredObjects[star.color] | ||
357 | if (count === 1) { | ||
358 | console.log('Found a', star.color, 'star in a region with 1', star.color, 'object') | ||
359 | regionData.addVeryInvalid(star) | ||
360 | if (quick) return regionData | ||
361 | } else if (count > 2) { | ||
362 | console.log('Found a', star.color, 'star in a region with', count, star.color, 'objects') | ||
363 | regionData.addInvalid(star) | ||
364 | if (quick) return regionData | ||
365 | } | ||
366 | } | ||
367 | |||
368 | if (puzzle.hasPolyominos) { | ||
369 | if (!window.polyFit(region, puzzle)) { | ||
370 | for (var pos of region) { | ||
371 | var cell = puzzle.grid[pos.x][pos.y] | ||
372 | if (cell == null) continue | ||
373 | if (cell.type === 'poly' || cell.type === 'ylop') { | ||
374 | regionData.addInvalid(pos) | ||
375 | if (quick) return regionData | ||
376 | } | ||
377 | } | ||
378 | } | ||
379 | } | ||
380 | |||
381 | if (puzzle.settings.CUSTOM_MECHANICS) { | ||
382 | window.validateBridges(puzzle, region, regionData) | ||
383 | window.validateArrows(puzzle, region, regionData) | ||
384 | window.validateSizers(puzzle, region, regionData) | ||
385 | } | ||
386 | |||
387 | console.debug('Region has', regionData.veryInvalidElements.length, 'very invalid elements') | ||
388 | console.debug('Region has', regionData.invalidElements.length, 'invalid elements') | ||
389 | return regionData | ||
390 | } | ||
391 | }) | ||