js/src/tests/js1_8/genexps/regress-380237-01.js

   1 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* ***** BEGIN LICENSE BLOCK *****
   3  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   4  *
   5  * The contents of this file are subject to the Mozilla Public License Version
   6  * 1.1 (the "License"); you may not use this file except in compliance with
   7  * the License. You may obtain a copy of the License at
   8  * http://www.mozilla.org/MPL/
   9  *
  10  * Software distributed under the License is distributed on an "AS IS" basis,
  11  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  12  * for the specific language governing rights and limitations under the
  13  * License.
  14  *
  15  * The Original Code is JavaScript Engine testing utilities.
  16  *
  17  * The Initial Developer of the Original Code is
  18  * Mozilla Foundation.
  19  * Portions created by the Initial Developer are Copyright (C) 2007
  20  * the Initial Developer. All Rights Reserved.
  21  *
  22  * Contributor(s): Brendan
  23  *
  24  * Alternatively, the contents of this file may be used under the terms of
  25  * either the GNU General Public License Version 2 or later (the "GPL"), or
  26  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  27  * in which case the provisions of the GPL or the LGPL are applicable instead
  28  * of those above. If you wish to allow use of your version of this file only
  29  * under the terms of either the GPL or the LGPL, and not to allow others to
  30  * use your version of this file under the terms of the MPL, indicate your
  31  * decision by deleting the provisions above and replace them with the notice
  32  * and other provisions required by the GPL or the LGPL. If you do not delete
  33  * the provisions above, a recipient may use your version of this file under
  34  * the terms of any one of the MPL, the GPL or the LGPL.
  35  *
  36  * ***** END LICENSE BLOCK ***** */
  37
  38
  39 //-----------------------------------------------------------------------------
  40 var BUGNUMBER = 380237;
  41 var summary = 'Generator expressions - sudoku';
  42 var actual = '';
  43 var expect = '';
  44
  45
  46 //-----------------------------------------------------------------------------
  47 test();
  48 //-----------------------------------------------------------------------------
  49
  50 function test()
  51 {
  52   enterFunc ('test');
  53   printBugNumber(BUGNUMBER);
  54   printStatus (summary);
  55
  56 if (this.version) version(180);
  57
  58 // XXX should be standard (and named clone, after Java?)
  59 Object.prototype.copy = function () {
  60     let o = {}
  61     for (let i in this)
  62         o[i] = this[i]
  63     return o
  64 }
  65
  66 // Make arrays and strings act more like Python lists by iterating their values, not their keys.
  67 Array.prototype.__iterator__ = String.prototype.__iterator__ = function () {
  68     for (let i = 0; i < this.length; i++)
  69         yield this[i]
  70 }
  71
  72 // Containment testing for arrays and strings that should be coherent with their __iterator__.
  73 Array.prototype.contains = String.prototype.contains = function (e) {
  74     return this.indexOf(e) != -1
  75 }
  76
  77 Array.prototype.repeat = String.prototype.repeat = function (n) {
  78     let s = this.constructor()
  79     for (let i = 0; i < n; i++)
  80         s = s.concat(this)
  81     return s
  82 }
  83
  84 String.prototype.center = function (w) {
  85     let n = this.length
  86     if (w <= n)
  87         return this
  88     let m = Math.floor((w - n) / 2)
  89     return ' '.repeat(m) + this + ' '.repeat(w - n - m)
  90 }
  91
  92 Array.prototype.toString = Array.prototype.toSource
  93 Object.prototype.toString = Object.prototype.toSource
  94
  95 // XXX thought spurred by the next two functions: array extras should default to identity function
  96
  97 function all(seq) {
  98     for (let e in seq)
  99         if (!e)
 100             return false
 101     return true
 102 }
 103
 104 function some(seq) {
 105     for (let e in seq)
 106         if (e)
 107             return e
 108     return false
 109 }
 110
 111 function cross(A, B) {
 112     return [a+b for (a in A) for (b in B)]
 113 }
 114
 115 function dict(A) {
 116     let d = {}
 117     for (let e in A)
 118         d[e[0]] = e[1]
 119     return d
 120 }
 121
 122 function set(A) {
 123     let s = []
 124     for (let e in A)
 125         if (!s.contains(e))
 126             s.push(e)
 127     return s
 128 }
 129
 130 function zip(A, B) {
 131     let z = []
 132     let n = Math.min(A.length, B.length)
 133     for (let i = 0; i < n; i++)
 134         z.push([A[i], B[i]])
 135     return z
 136 }
 137
 138 rows = 'ABCDEFGHI'
 139 cols = '123456789'
 140 digits   = '123456789'
 141 squares  = cross(rows, cols)
 142 unitlist = [cross(rows, c) for (c in cols)]
 143            .concat([cross(r, cols) for (r in rows)])
 144            .concat([cross(rs, cs) for (rs in ['ABC','DEF','GHI']) for (cs in ['123','456','789'])])
 145 units = dict([s, [u for (u in unitlist) if (u.contains(s))]]
 146              for (s in squares))
 147 peers = dict([s, set([s2 for (u in units[s]) for (s2 in u) if (s2 != s)])]
 148              for (s in squares))
 149
 150 // Given a string of 81 digits (or . or 0 or -), return a dict of {cell:values}.
 151 function parse_grid(grid) {
 152     grid = [c for (c in grid) if ('0.-123456789'.contains(c))]
 153     let values = dict([s, digits] for (s in squares))
 154
 155     for (let [s, d] in zip(squares, grid))
 156         if (digits.contains(d) && !assign(values, s, d))
 157             return false
 158     return values
 159 }
 160
 161 // Eliminate all the other values (except d) from values[s] and propagate.
 162 function assign(values, s, d) {
 163     if (all(eliminate(values, s, d2) for (d2 in values[s]) if (d2 != d)))
 164         return values
 165     return false
 166 }
 167
 168 // Eliminate d from values[s]; propagate when values or places <= 2.
 169 function eliminate(values, s, d) {
 170     if (!values[s].contains(d))
 171         return values // Already eliminated
 172     values[s] = values[s].replace(d, '')
 173     if (values[s].length == 0)
 174         return false  // Contradiction: removed last value
 175     if (values[s].length == 1) {
 176         // If there is only one value (d2) left in square, remove it from peers
 177         let d2 = values[s][0]
 178         if (!all(eliminate(values, s2, d2) for (s2 in peers[s])))
 179             return false
 180     }
 181     // Now check the places where d appears in the units of s
 182     for (let u in units[s]) {
 183         let dplaces = [s for (s in u) if (values[s].contains(d))]
 184         if (dplaces.length == 0)
 185             return false
 186         if (dplaces.length == 1)
 187             // d can only be in one place in unit; assign it there
 188             if (!assign(values, dplaces[0], d))
 189                 return false
 190     }
 191     return values
 192 }
 193
 194 // Used for debugging.
 195 function print_board(values) {
 196     let width = 1 + Math.max.apply(Math, [values[s].length for (s in squares)])
 197     let line = '\n' + ['-'.repeat(width*3)].repeat(3).join('+')
 198     for (let r in rows)
 199         print([values[r+c].center(width) + ('36'.contains(c) && '|' || '')
 200                for (c in cols)].join('') + ('CF'.contains(r) && line || ''))
 201     print('\n')
 202 }
 203
 204 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.."
 205
 206 print_board(parse_grid(easy))
 207
 208 // Using depth-first search and constraint propagation, try all possible values.
 209 function search(values) {
 210     if (!values)
 211         return false    // Failed earlier
 212     if (all(values[s].length == 1 for (s in squares)))
 213         return values   // Solved!
 214
 215     // Choose the unfilled square s with the fewest possibilities
 216     // XXX Math.min etc. should work with generator expressions and other iterators
 217     // XXX Math.min etc. should work on arrays (lists or tuples in Python) as well as numbers
 218     let a = [values[s].length + s for (s in squares) if (values[s].length > 1)].sort()
 219     let s = a[0].slice(-2)
 220
 221     return some(search(assign(values.copy(), s, d)) for (d in values[s]))
 222 }
 223
 224 hard = '4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......'
 225
 226 print_board(search(parse_grid(hard)))
 227
 228   delete Object.prototype.copy;
 229
 230   reportCompare(expect, actual, summary);
 231
 232   exitFunc ('test');
 233 }