1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/js/src/tests/ecma_6/Comprehensions/sudoku.js Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,175 @@
1.4 +/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
1.5 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.6 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.7 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.8 +
1.9 +
1.10 +function copy(obj) {
1.11 + var o = {};
1.12 + for (var i in obj)
1.13 + o[i] = obj[i];
1.14 + return o;
1.15 +}
1.16 +
1.17 +Array.prototype.contains = String.prototype.contains = function (e) {
1.18 + for (var elt of this)
1.19 + if (elt == e)
1.20 + return true;
1.21 + return false;
1.22 +}
1.23 +
1.24 +Array.prototype.repeat = String.prototype.repeat = function (n) {
1.25 + var s = this.constructor();
1.26 + for (var i = 0; i < n; i++)
1.27 + s = s.concat(this);
1.28 + return s;
1.29 +}
1.30 +
1.31 +String.prototype.center = function (w) {
1.32 + var n = this.length;
1.33 + if (w <= n)
1.34 + return this;
1.35 + var m = Math.floor((w - n) / 2);
1.36 + return ' '.repeat(m) + this + ' '.repeat(w - n - m);
1.37 +}
1.38 +
1.39 +Array.prototype.toString = Array.prototype.toSource
1.40 +Object.prototype.toString = Object.prototype.toSource
1.41 +
1.42 +function all(seq) {
1.43 + for (var e of seq)
1.44 + if (!e)
1.45 + return false;
1.46 + return true;
1.47 +}
1.48 +
1.49 +function some(seq) {
1.50 + for (var e of seq)
1.51 + if (e)
1.52 + return e;
1.53 + return false;
1.54 +}
1.55 +
1.56 +function cross(A, B) {
1.57 + return [for (a of A) for (b of B) a+b];
1.58 +}
1.59 +
1.60 +function dict(A) {
1.61 + var d = {};
1.62 + for (var e of A)
1.63 + d[e[0]] = e[1];
1.64 + return d;
1.65 +}
1.66 +
1.67 +function set(A) {
1.68 + var s = [];
1.69 + for (var e of A)
1.70 + if (!s.contains(e))
1.71 + s.push(e);
1.72 + return s;
1.73 +}
1.74 +
1.75 +function zip(A, B) {
1.76 + var z = [];
1.77 + var n = Math.min(A.length, B.length);
1.78 + for (var i = 0; i < n; i++)
1.79 + z.push([A[i], B[i]]);
1.80 + return z;
1.81 +}
1.82 +
1.83 +rows = 'ABCDEFGHI';
1.84 +cols = '123456789';
1.85 +digits = '123456789';
1.86 +squares = cross(rows, cols);
1.87 +unitlist = [for (c of cols) cross(rows, c)]
1.88 + .concat([for (r of rows) cross(r, cols)])
1.89 + .concat([for (rs of ['ABC','DEF','GHI']) for (cs of ['123','456','789']) cross(rs, cs)]);
1.90 +units = dict((for (s of squares)
1.91 + [s, [for (u of unitlist) if (u.contains(s)) u]]));
1.92 +
1.93 +peers = dict((for (s of squares)
1.94 + [s, set([for (u of units[s]) for (s2 of u) if (s2 != s) s2])]));
1.95 +
1.96 +// Given a string of 81 digits (or . or 0 or -), return a dict of {cell:values}.
1.97 +function parse_grid(grid) {
1.98 + grid = [for (c of grid) if ('0.-123456789'.contains(c)) c];
1.99 + var values = dict((for (s of squares) [s, digits]));
1.100 +
1.101 + for (var pair of zip(squares, grid)) {
1.102 + var s = pair[0], d = pair[1];
1.103 + if (digits.contains(d) && !assign(values, s, d))
1.104 + return false;
1.105 + }
1.106 + return values;
1.107 +}
1.108 +
1.109 +// Eliminate all the other values (except d) from values[s] and propagate.
1.110 +function assign(values, s, d) {
1.111 + if (all((for (d2 of values[s]) if (d2 != d) eliminate(values, s, d2))))
1.112 + return values;
1.113 + return false;
1.114 +}
1.115 +
1.116 +// Eliminate d from values[s]; propagate when values or places <= 2.
1.117 +function eliminate(values, s, d) {
1.118 + if (!values[s].contains(d))
1.119 + return values; // Already eliminated
1.120 + values[s] = values[s].replace(d, '');
1.121 + if (values[s].length == 0)
1.122 + return false; // Contradiction: removed last value
1.123 + if (values[s].length == 1) {
1.124 + // If there is only one value (d2) left in square, remove it from peers
1.125 + var d2 = values[s][0];
1.126 + if (!all((for (s2 of peers[s]) eliminate(values, s2, d2))))
1.127 + return false;
1.128 + }
1.129 + // Now check the places where d appears in the units of s
1.130 + for (var u of units[s]) {
1.131 + var dplaces = [for (s of u) if (values[s].contains(d)) s];
1.132 + if (dplaces.length == 0)
1.133 + return false;
1.134 + if (dplaces.length == 1)
1.135 + // d can only be in one place in unit; assign it there
1.136 + if (!assign(values, dplaces[0], d))
1.137 + return false;
1.138 + }
1.139 + return values;
1.140 +}
1.141 +
1.142 +// Used for debugging.
1.143 +function print_board(values) {
1.144 + var width = 1 + Math.max.apply(Math, [for (s of squares) values[s].length]);
1.145 + var line = '\n' + ['-'.repeat(width*3)].repeat(3).join('+');
1.146 + for (var r of rows)
1.147 + print([for (c of cols)
1.148 + values[r+c].center(width) + ('36'.contains(c) && '|' || '')]
1.149 + .join('') + ('CF'.contains(r) && line || ''));
1.150 + print('\n');
1.151 +}
1.152 +
1.153 +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..";
1.154 +
1.155 +print_board(parse_grid(easy));
1.156 +
1.157 +// Using depth-first search and constraint propagation, try all possible values.
1.158 +function search(values) {
1.159 + if (!values)
1.160 + return false; // Failed earlier
1.161 + if (all((for (s of squares) values[s].length == 1)))
1.162 + return values; // Solved!
1.163 +
1.164 + // Choose the unfilled square s with the fewest possibilities
1.165 + // XXX Math.min etc. should work with generator expressions and other iterators
1.166 + // XXX Math.min etc. should work on arrays (lists or tuples in Python) as well as numbers
1.167 + var a = [for (s of squares) if (values[s].length > 1) values[s].length + s].sort();
1.168 + var s = a[0].slice(-2);
1.169 +
1.170 + return some((for (d of values[s]) search(assign(copy(values), s, d))));
1.171 +}
1.172 +
1.173 +hard = '4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......';
1.174 +
1.175 +print_board(search(parse_grid(hard)))
1.176 +
1.177 +if (typeof reportCompare === "function")
1.178 + reportCompare(true, true);
