The Tor Browser / file comparison
comparison: js/src/tests/ecma_6/Comprehensions/sudoku.js
js/src/tests/ecma_6/Comprehensions/sudoku.js
- branch
- TOR_BUG_3246
- changeset 7
- 129ffea94266
equal
deleted
inserted
replaced
| -1:000000000000 | 0:f4d4402f8718 |
|---|---|
| 1 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ | |
| 2 /* This Source Code Form is subject to the terms of the Mozilla Public | |
| 3 * License, v. 2.0. If a copy of the MPL was not distributed with this | |
| 4 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ | |
| 5 | |
| 6 | |
| 7 function copy(obj) { | |
| 8 var o = {}; | |
| 9 for (var i in obj) | |
| 10 o[i] = obj[i]; | |
| 11 return o; | |
| 12 } | |
| 13 | |
| 14 Array.prototype.contains = String.prototype.contains = function (e) { | |
| 15 for (var elt of this) | |
| 16 if (elt == e) | |
| 17 return true; | |
| 18 return false; | |
| 19 } | |
| 20 | |
| 21 Array.prototype.repeat = String.prototype.repeat = function (n) { | |
| 22 var s = this.constructor(); | |
| 23 for (var i = 0; i < n; i++) | |
| 24 s = s.concat(this); | |
| 25 return s; | |
| 26 } | |
| 27 | |
| 28 String.prototype.center = function (w) { | |
| 29 var n = this.length; | |
| 30 if (w <= n) | |
| 31 return this; | |
| 32 var m = Math.floor((w - n) / 2); | |
| 33 return ' '.repeat(m) + this + ' '.repeat(w - n - m); | |
| 34 } | |
| 35 | |
| 36 Array.prototype.toString = Array.prototype.toSource | |
| 37 Object.prototype.toString = Object.prototype.toSource | |
| 38 | |
| 39 function all(seq) { | |
| 40 for (var e of seq) | |
| 41 if (!e) | |
| 42 return false; | |
| 43 return true; | |
| 44 } | |
| 45 | |
| 46 function some(seq) { | |
| 47 for (var e of seq) | |
| 48 if (e) | |
| 49 return e; | |
| 50 return false; | |
| 51 } | |
| 52 | |
| 53 function cross(A, B) { | |
| 54 return [for (a of A) for (b of B) a+b]; | |
| 55 } | |
| 56 | |
| 57 function dict(A) { | |
| 58 var d = {}; | |
| 59 for (var e of A) | |
| 60 d[e[0]] = e[1]; | |
| 61 return d; | |
| 62 } | |
| 63 | |
| 64 function set(A) { | |
| 65 var s = []; | |
| 66 for (var e of A) | |
| 67 if (!s.contains(e)) | |
| 68 s.push(e); | |
| 69 return s; | |
| 70 } | |
| 71 | |
| 72 function zip(A, B) { | |
| 73 var z = []; | |
| 74 var n = Math.min(A.length, B.length); | |
| 75 for (var i = 0; i < n; i++) | |
| 76 z.push([A[i], B[i]]); | |
| 77 return z; | |
| 78 } | |
| 79 | |
| 80 rows = 'ABCDEFGHI'; | |
| 81 cols = '123456789'; | |
| 82 digits = '123456789'; | |
| 83 squares = cross(rows, cols); | |
| 84 unitlist = [for (c of cols) cross(rows, c)] | |
| 85 .concat([for (r of rows) cross(r, cols)]) | |
| 86 .concat([for (rs of ['ABC','DEF','GHI']) for (cs of ['123','456','789']) cross(rs, cs)]); | |
| 87 units = dict((for (s of squares) | |
| 88 [s, [for (u of unitlist) if (u.contains(s)) u]])); | |
| 89 | |
| 90 peers = dict((for (s of squares) | |
| 91 [s, set([for (u of units[s]) for (s2 of u) if (s2 != s) s2])])); | |
| 92 | |
| 93 // Given a string of 81 digits (or . or 0 or -), return a dict of {cell:values}. | |
| 94 function parse_grid(grid) { | |
| 95 grid = [for (c of grid) if ('0.-123456789'.contains(c)) c]; | |
| 96 var values = dict((for (s of squares) [s, digits])); | |
| 97 | |
| 98 for (var pair of zip(squares, grid)) { | |
| 99 var s = pair[0], d = pair[1]; | |
| 100 if (digits.contains(d) && !assign(values, s, d)) | |
| 101 return false; | |
| 102 } | |
| 103 return values; | |
| 104 } | |
| 105 | |
| 106 // Eliminate all the other values (except d) from values[s] and propagate. | |
| 107 function assign(values, s, d) { | |
| 108 if (all((for (d2 of values[s]) if (d2 != d) eliminate(values, s, d2)))) | |
| 109 return values; | |
| 110 return false; | |
| 111 } | |
| 112 | |
| 113 // Eliminate d from values[s]; propagate when values or places <= 2. | |
| 114 function eliminate(values, s, d) { | |
| 115 if (!values[s].contains(d)) | |
| 116 return values; // Already eliminated | |
| 117 values[s] = values[s].replace(d, ''); | |
| 118 if (values[s].length == 0) | |
| 119 return false; // Contradiction: removed last value | |
| 120 if (values[s].length == 1) { | |
| 121 // If there is only one value (d2) left in square, remove it from peers | |
| 122 var d2 = values[s][0]; | |
| 123 if (!all((for (s2 of peers[s]) eliminate(values, s2, d2)))) | |
| 124 return false; | |
| 125 } | |
| 126 // Now check the places where d appears in the units of s | |
| 127 for (var u of units[s]) { | |
| 128 var dplaces = [for (s of u) if (values[s].contains(d)) s]; | |
| 129 if (dplaces.length == 0) | |
| 130 return false; | |
| 131 if (dplaces.length == 1) | |
| 132 // d can only be in one place in unit; assign it there | |
| 133 if (!assign(values, dplaces[0], d)) | |
| 134 return false; | |
| 135 } | |
| 136 return values; | |
| 137 } | |
| 138 | |
| 139 // Used for debugging. | |
| 140 function print_board(values) { | |
| 141 var width = 1 + Math.max.apply(Math, [for (s of squares) values[s].length]); | |
| 142 var line = '\n' + ['-'.repeat(width*3)].repeat(3).join('+'); | |
| 143 for (var r of rows) | |
| 144 print([for (c of cols) | |
| 145 values[r+c].center(width) + ('36'.contains(c) && '|' || '')] | |
| 146 .join('') + ('CF'.contains(r) && line || '')); | |
| 147 print('\n'); | |
| 148 } | |
| 149 | |
| 150 easy = "..3.2.6..9..3.5..1..18.64....81.29..7.......8..67.82....26.95..8..2.3..9..5.1.3.."; | |
| 151 | |
| 152 print_board(parse_grid(easy)); | |
| 153 | |
| 154 // Using depth-first search and constraint propagation, try all possible values. | |
| 155 function search(values) { | |
| 156 if (!values) | |
| 157 return false; // Failed earlier | |
| 158 if (all((for (s of squares) values[s].length == 1))) | |
| 159 return values; // Solved! | |
| 160 | |
| 161 // Choose the unfilled square s with the fewest possibilities | |
| 162 // XXX Math.min etc. should work with generator expressions and other iterators | |
| 163 // XXX Math.min etc. should work on arrays (lists or tuples in Python) as well as numbers | |
| 164 var a = [for (s of squares) if (values[s].length > 1) values[s].length + s].sort(); | |
| 165 var s = a[0].slice(-2); | |
| 166 | |
| 167 return some((for (d of values[s]) search(assign(copy(values), s, d)))); | |
| 168 } | |
| 169 | |
| 170 hard = '4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......'; | |
| 171 | |
| 172 print_board(search(parse_grid(hard))) | |
| 173 | |
| 174 if (typeof reportCompare === "function") | |
| 175 reportCompare(true, true); |
