1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/js/src/tests/js1_8/genexps/regress-380237-01.js Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,201 @@
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 +//-----------------------------------------------------------------------------
1.11 +var BUGNUMBER = 380237;
1.12 +var summary = 'Generator expressions - sudoku';
1.13 +var actual = '';
1.14 +var expect = '';
1.15 +
1.16 +
1.17 +//-----------------------------------------------------------------------------
1.18 +test();
1.19 +//-----------------------------------------------------------------------------
1.20 +
1.21 +function test()
1.22 +{
1.23 + enterFunc ('test');
1.24 + printBugNumber(BUGNUMBER);
1.25 + printStatus (summary);
1.26 +
1.27 +if (this.version) version(180);
1.28 +
1.29 +// XXX should be standard (and named clone, after Java?)
1.30 +Object.prototype.copy = function () {
1.31 + let o = {}
1.32 + for (let i in this)
1.33 + o[i] = this[i]
1.34 + return o
1.35 +}
1.36 +
1.37 +// Make arrays and strings act more like Python lists by iterating their values, not their keys.
1.38 +Array.prototype.__iterator__ = String.prototype.__iterator__ = function () {
1.39 + for (let i = 0; i < this.length; i++)
1.40 + yield this[i]
1.41 +}
1.42 +
1.43 +// Containment testing for arrays and strings that should be coherent with their __iterator__.
1.44 +Array.prototype.contains = String.prototype.contains = function (e) {
1.45 + return this.indexOf(e) != -1
1.46 +}
1.47 +
1.48 +Array.prototype.repeat = String.prototype.repeat = function (n) {
1.49 + let s = this.constructor()
1.50 + for (let i = 0; i < n; i++)
1.51 + s = s.concat(this)
1.52 + return s
1.53 +}
1.54 +
1.55 +String.prototype.center = function (w) {
1.56 + let n = this.length
1.57 + if (w <= n)
1.58 + return this
1.59 + let m = Math.floor((w - n) / 2)
1.60 + return ' '.repeat(m) + this + ' '.repeat(w - n - m)
1.61 +}
1.62 +
1.63 +Array.prototype.toString = Array.prototype.toSource
1.64 +Object.prototype.toString = Object.prototype.toSource
1.65 +
1.66 +// XXX thought spurred by the next two functions: array extras should default to identity function
1.67 +
1.68 +function all(seq) {
1.69 + for (let e in seq)
1.70 + if (!e)
1.71 + return false
1.72 + return true
1.73 +}
1.74 +
1.75 +function some(seq) {
1.76 + for (let e in seq)
1.77 + if (e)
1.78 + return e
1.79 + return false
1.80 +}
1.81 +
1.82 +function cross(A, B) {
1.83 + return [a+b for (a in A) for (b in B)]
1.84 +}
1.85 +
1.86 +function dict(A) {
1.87 + let d = {}
1.88 + for (let e in A)
1.89 + d[e[0]] = e[1]
1.90 + return d
1.91 +}
1.92 +
1.93 +function set(A) {
1.94 + let s = []
1.95 + for (let e in A)
1.96 + if (!s.contains(e))
1.97 + s.push(e)
1.98 + return s
1.99 +}
1.100 +
1.101 +function zip(A, B) {
1.102 + let z = []
1.103 + let n = Math.min(A.length, B.length)
1.104 + for (let i = 0; i < n; i++)
1.105 + z.push([A[i], B[i]])
1.106 + return z
1.107 +}
1.108 +
1.109 +rows = 'ABCDEFGHI'
1.110 +cols = '123456789'
1.111 +digits = '123456789'
1.112 +squares = cross(rows, cols)
1.113 +unitlist = [cross(rows, c) for (c in cols)]
1.114 + .concat([cross(r, cols) for (r in rows)])
1.115 + .concat([cross(rs, cs) for (rs in ['ABC','DEF','GHI']) for (cs in ['123','456','789'])])
1.116 +units = dict([s, [u for (u in unitlist) if (u.contains(s))]]
1.117 + for (s in squares))
1.118 +peers = dict([s, set([s2 for (u in units[s]) for (s2 in u) if (s2 != s)])]
1.119 + for (s in squares))
1.120 +
1.121 +// Given a string of 81 digits (or . or 0 or -), return a dict of {cell:values}.
1.122 +function parse_grid(grid) {
1.123 + grid = [c for (c in grid) if ('0.-123456789'.contains(c))]
1.124 + let values = dict([s, digits] for (s in squares))
1.125 +
1.126 + for (let [s, d] in zip(squares, grid))
1.127 + if (digits.contains(d) && !assign(values, s, d))
1.128 + return false
1.129 + return values
1.130 +}
1.131 +
1.132 +// Eliminate all the other values (except d) from values[s] and propagate.
1.133 +function assign(values, s, d) {
1.134 + if (all(eliminate(values, s, d2) for (d2 in values[s]) if (d2 != d)))
1.135 + return values
1.136 + return false
1.137 +}
1.138 +
1.139 +// Eliminate d from values[s]; propagate when values or places <= 2.
1.140 +function eliminate(values, s, d) {
1.141 + if (!values[s].contains(d))
1.142 + return values // Already eliminated
1.143 + values[s] = values[s].replace(d, '')
1.144 + if (values[s].length == 0)
1.145 + return false // Contradiction: removed last value
1.146 + if (values[s].length == 1) {
1.147 + // If there is only one value (d2) left in square, remove it from peers
1.148 + let d2 = values[s][0]
1.149 + if (!all(eliminate(values, s2, d2) for (s2 in peers[s])))
1.150 + return false
1.151 + }
1.152 + // Now check the places where d appears in the units of s
1.153 + for (let u in units[s]) {
1.154 + let dplaces = [s for (s in u) if (values[s].contains(d))]
1.155 + if (dplaces.length == 0)
1.156 + return false
1.157 + if (dplaces.length == 1)
1.158 + // d can only be in one place in unit; assign it there
1.159 + if (!assign(values, dplaces[0], d))
1.160 + return false
1.161 + }
1.162 + return values
1.163 +}
1.164 +
1.165 +// Used for debugging.
1.166 +function print_board(values) {
1.167 + let width = 1 + Math.max.apply(Math, [values[s].length for (s in squares)])
1.168 + let line = '\n' + ['-'.repeat(width*3)].repeat(3).join('+')
1.169 + for (let r in rows)
1.170 + print([values[r+c].center(width) + ('36'.contains(c) && '|' || '')
1.171 + for (c in cols)].join('') + ('CF'.contains(r) && line || ''))
1.172 + print('\n')
1.173 +}
1.174 +
1.175 +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.176 +
1.177 +print_board(parse_grid(easy))
1.178 +
1.179 +// Using depth-first search and constraint propagation, try all possible values.
1.180 +function search(values) {
1.181 + if (!values)
1.182 + return false // Failed earlier
1.183 + if (all(values[s].length == 1 for (s in squares)))
1.184 + return values // Solved!
1.185 +
1.186 + // Choose the unfilled square s with the fewest possibilities
1.187 + // XXX Math.min etc. should work with generator expressions and other iterators
1.188 + // XXX Math.min etc. should work on arrays (lists or tuples in Python) as well as numbers
1.189 + let a = [values[s].length + s for (s in squares) if (values[s].length > 1)].sort()
1.190 + let s = a[0].slice(-2)
1.191 +
1.192 + return some(search(assign(values.copy(), s, d)) for (d in values[s]))
1.193 +}
1.194 +
1.195 +hard = '4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......'
1.196 +
1.197 +print_board(search(parse_grid(hard)))
1.198 +
1.199 + delete Object.prototype.copy;
1.200 +
1.201 + reportCompare(expect, actual, summary);
1.202 +
1.203 + exitFunc ('test');
1.204 +}
