js/src/tests/ecma_6/Comprehensions/sudoku.js@129ffea94266
js/src/tests/ecma_6/Comprehensions/sudoku.js
Sat, 03 Jan 2015 20:18:00 +0100
- author
- Michael Schloh von Bennewitz <michael@schloh.com>
- date
- Sat, 03 Jan 2015 20:18:00 +0100
- branch
- TOR_BUG_3246
- changeset 7
- 129ffea94266
- permissions
- -rw-r--r--
Conditionally enable double key logic according to:
private browsing mode or privacy.thirdparty.isolate preference and
implement in GetCookieStringCommon and FindCookie where it counts...
With some reservations of how to convince FindCookie users to test
condition and pass a nullptr when disabling double key logic.
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/. */
7 function copy(obj) {
8 var o = {};
9 for (var i in obj)
10 o[i] = obj[i];
11 return o;
12 }
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 }
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 }
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 }
36 Array.prototype.toString = Array.prototype.toSource
37 Object.prototype.toString = Object.prototype.toSource
39 function all(seq) {
40 for (var e of seq)
41 if (!e)
42 return false;
43 return true;
44 }
46 function some(seq) {
47 for (var e of seq)
48 if (e)
49 return e;
50 return false;
51 }
53 function cross(A, B) {
54 return [for (a of A) for (b of B) a+b];
55 }
57 function dict(A) {
58 var d = {};
59 for (var e of A)
60 d[e[0]] = e[1];
61 return d;
62 }
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 }
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 }
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]]));
90 peers = dict((for (s of squares)
91 [s, set([for (u of units[s]) for (s2 of u) if (s2 != s) s2])]));
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]));
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 }
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 }
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 }
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 }
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..";
152 print_board(parse_grid(easy));
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!
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);
167 return some((for (d of values[s]) search(assign(copy(values), s, d))));
168 }
170 hard = '4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......';
172 print_board(search(parse_grid(hard)))
174 if (typeof reportCompare === "function")
175 reportCompare(true, true);
