diff -r 000000000000 -r 6474c204b198 js/src/tests/js1_8/genexps/regress-380237-01.js --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/js/src/tests/js1_8/genexps/regress-380237-01.js Wed Dec 31 06:09:35 2014 +0100 @@ -0,0 +1,201 @@ +/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + + +//----------------------------------------------------------------------------- +var BUGNUMBER = 380237; +var summary = 'Generator expressions - sudoku'; +var actual = ''; +var expect = ''; + + +//----------------------------------------------------------------------------- +test(); +//----------------------------------------------------------------------------- + +function test() +{ + enterFunc ('test'); + printBugNumber(BUGNUMBER); + printStatus (summary); + +if (this.version) version(180); + +// XXX should be standard (and named clone, after Java?) +Object.prototype.copy = function () { + let o = {} + for (let i in this) + o[i] = this[i] + return o +} + +// Make arrays and strings act more like Python lists by iterating their values, not their keys. +Array.prototype.__iterator__ = String.prototype.__iterator__ = function () { + for (let i = 0; i < this.length; i++) + yield this[i] +} + +// Containment testing for arrays and strings that should be coherent with their __iterator__. +Array.prototype.contains = String.prototype.contains = function (e) { + return this.indexOf(e) != -1 +} + +Array.prototype.repeat = String.prototype.repeat = function (n) { + let s = this.constructor() + for (let i = 0; i < n; i++) + s = s.concat(this) + return s +} + +String.prototype.center = function (w) { + let n = this.length + if (w <= n) + return this + let m = Math.floor((w - n) / 2) + return ' '.repeat(m) + this + ' '.repeat(w - n - m) +} + +Array.prototype.toString = Array.prototype.toSource +Object.prototype.toString = Object.prototype.toSource + +// XXX thought spurred by the next two functions: array extras should default to identity function + +function all(seq) { + for (let e in seq) + if (!e) + return false + return true +} + +function some(seq) { + for (let e in seq) + if (e) + return e + return false +} + +function cross(A, B) { + return [a+b for (a in A) for (b in B)] +} + +function dict(A) { + let d = {} + for (let e in A) + d[e[0]] = e[1] + return d +} + +function set(A) { + let s = [] + for (let e in A) + if (!s.contains(e)) + s.push(e) + return s +} + +function zip(A, B) { + let z = [] + let n = Math.min(A.length, B.length) + for (let i = 0; i < n; i++) + z.push([A[i], B[i]]) + return z +} + +rows = 'ABCDEFGHI' +cols = '123456789' +digits = '123456789' +squares = cross(rows, cols) +unitlist = [cross(rows, c) for (c in cols)] + .concat([cross(r, cols) for (r in rows)]) + .concat([cross(rs, cs) for (rs in ['ABC','DEF','GHI']) for (cs in ['123','456','789'])]) +units = dict([s, [u for (u in unitlist) if (u.contains(s))]] + for (s in squares)) +peers = dict([s, set([s2 for (u in units[s]) for (s2 in u) if (s2 != s)])] + for (s in squares)) + +// Given a string of 81 digits (or . or 0 or -), return a dict of {cell:values}. +function parse_grid(grid) { + grid = [c for (c in grid) if ('0.-123456789'.contains(c))] + let values = dict([s, digits] for (s in squares)) + + for (let [s, d] in zip(squares, grid)) + if (digits.contains(d) && !assign(values, s, d)) + return false + return values +} + +// Eliminate all the other values (except d) from values[s] and propagate. +function assign(values, s, d) { + if (all(eliminate(values, s, d2) for (d2 in values[s]) if (d2 != d))) + return values + return false +} + +// Eliminate d from values[s]; propagate when values or places <= 2. +function eliminate(values, s, d) { + if (!values[s].contains(d)) + return values // Already eliminated + values[s] = values[s].replace(d, '') + if (values[s].length == 0) + return false // Contradiction: removed last value + if (values[s].length == 1) { + // If there is only one value (d2) left in square, remove it from peers + let d2 = values[s][0] + if (!all(eliminate(values, s2, d2) for (s2 in peers[s]))) + return false + } + // Now check the places where d appears in the units of s + for (let u in units[s]) { + let dplaces = [s for (s in u) if (values[s].contains(d))] + if (dplaces.length == 0) + return false + if (dplaces.length == 1) + // d can only be in one place in unit; assign it there + if (!assign(values, dplaces[0], d)) + return false + } + return values +} + +// Used for debugging. +function print_board(values) { + let width = 1 + Math.max.apply(Math, [values[s].length for (s in squares)]) + let line = '\n' + ['-'.repeat(width*3)].repeat(3).join('+') + for (let r in rows) + print([values[r+c].center(width) + ('36'.contains(c) && '|' || '') + for (c in cols)].join('') + ('CF'.contains(r) && line || '')) + print('\n') +} + +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.." + +print_board(parse_grid(easy)) + +// Using depth-first search and constraint propagation, try all possible values. +function search(values) { + if (!values) + return false // Failed earlier + if (all(values[s].length == 1 for (s in squares))) + return values // Solved! + + // Choose the unfilled square s with the fewest possibilities + // XXX Math.min etc. should work with generator expressions and other iterators + // XXX Math.min etc. should work on arrays (lists or tuples in Python) as well as numbers + let a = [values[s].length + s for (s in squares) if (values[s].length > 1)].sort() + let s = a[0].slice(-2) + + return some(search(assign(values.copy(), s, d)) for (d in values[s])) +} + +hard = '4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......' + +print_board(search(parse_grid(hard))) + + delete Object.prototype.copy; + + reportCompare(expect, actual, summary); + + exitFunc ('test'); +}