gistfile1.txt

var print = console.log.bind(console);

// partial implementation of Array.from
Array.from = function(iterable) {
    var results = [];
    for(var x of iterable) {
        results.push(x);
    }
    return results;
};

Array.prototype.flatMap = function(projection) {
    var results = [];
    for(var x of this) {
        for(var y of projection(x)) {
            results.push(y);
        }
    }

    return results;
};

// This nominal type is used to facilitate the pipeline adapter pattern
// over the Iterable nominal type.
function Iterable(iterator){
    // firefox uses the "@@iterator" string because it does not have a symbol implementation yet
    this["@@iterator"] = iterator;
}

Iterable.prototype.map = function(projection) {
    var self = this;
    return new Iterable(function*(){
        for(var x of self) {
            yield projection(x);
        }
    });
};

Iterable.prototype.filter = function(predicate) {
    var self = this;
    return new Iterable(function*(){
        for(var x of self) {
            if (predicate(x))
                yield x;
        }
    });
};

Iterable.prototype.flatMap = function(projection) {
    var self = this;
    return new Iterable(function*(){
        for(var x of self) {
            for(var y of projection(x)) {
                yield y;
            }
        }
    });
};

Iterable.from = function(arr) {
    if (arr instanceof Iterable) {
        return arr;
    }

    return new Iterable(arr["@@iterator"].bind(arr));
};

Iterable.prototype.toArray = function() {
    var results = [];
    for(var x of this["@@iterator"]()) {
        results.push(x);
    }
    return results;
}

function copy(obj) {
  var o = {};
  for (var i in obj)
    o[i] = obj[i];
  return o;
}

Array.prototype.contains = String.prototype.contains = function (e) {
  for (var elt of this)
    if (elt == e)
      return true;
  return false;
}

Array.prototype.iterable = String.prototype.iterable = function (e) {
    return Iterable.from(this);
};

Array.prototype.repeat = String.prototype.repeat = function (n) {
  var s = this.constructor();
  for (var i = 0; i < n; i++)
    s = s.concat(this);
  return s;
}

String.prototype.center = function (w) {
  var n = this.length;
  if (w <= n)
    return this;
  var 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

function all(seq) {
  for (var e of seq)
    if (!e)
      return false;
  return true;
}

function some(seq) {
  for (var e of seq)
    if (e)
      return e;
  return false;
}

function cross(A, B) {
  //original code:              [for (a of A) for (b of B) a+b];
  //with ES7 comprehensions:    (for (a from A.iterable()) for (b from B.iterable()) a + b).toArray();
  // desugars to...
  return A.iterable().flatMap(a => B.iterable().map(b => a + b)).toArray();
}

function dict(A) {
  var d = {};
  for (var e of A)
    d[e[0]] = e[1];
  return d;
}

function set(A) {
  var s = [];
  for (var e of A)
    if (!s.contains(e))
      s.push(e);
  return s;
}

function zip(A, B) {
  var z = [];
  var n = Math.min(A.length, B.length);
  for (var i = 0; i < n; i++)
    z.push([A[i], B[i]]);
  return z;
}

rows = 'ABCDEFGHI';
cols = '123456789';
digits   = '123456789';
squares  = cross(rows, cols);
// ORIGINAL CODE:
//unitlist = [for (c of cols) cross(rows, c)]
  //  .concat([for (r of rows) cross(r, cols)])
  //  .concat([for (rs of ['ABC','DEF','GHI']) for (cs of ['123','456','789']) cross(rs, cs)]);

// ES7 COMPREHENSIONS:
//unitlist = (for (c from Array.from(cols)) cross(rows, c))
  //  .concat((for (r from Array.from(rows)) cross(r, cols)))
  //  .concat((for (rs from ['ABC','DEF','GHI']) for (cs from ['123','456','789']) cross(rs, cs)));

// DESUGARS TO:
unitlist = 
  Array.
    from(cols).
    map(c => cross(rows, c)).
    concat(Array.from(rows).map(r => cross(r, cols))).
    concat(['ABC','DEF','GHI'].flatMap(rs => ['123','456','789'].map(cs => cross(rs, cs))));

//ORIGINAL CODE:
/*units = dict((for (s of squares)
                [s, [for (u of unitlist) if (u.contains(s)) u]])); */
//ES7 COMPREHENSIONS: 
/*units = dict((for (s from squares.iterable())
                [s, (for (u from unitlist) if (u.contains(s)) u)])); */
units = dict(
    squares.
        iterable().
        map(s => [s, unitlist.filter(u => u.contains(s))]));

// ORIGINAL CODE:
/*peers = dict((for (s of squares)
                [s, set([for (u of units[s]) for (s2 of u) if (s2 != s) s2])])); */
// ES7 COMPREHENSIONS:
/*peers = dict((for (s from squares.iterable())
                [s, set((for (u from units[s]) for (s2 from u) if (s2 != s) s2))])); */
// DESUGARS TO:
peers = dict(    
    squares.
        iterable().
        map(s => [
            s, 
            set(units[s].flatMap(u => u.filter(s2 => s2 != s)))
        ]));

// Given a string of 81 digits (or . or 0 or -), return a dict of {cell:values}.
function parse_grid(grid) {
  /*ORIGINAL CODE:      grid = [for (c of grid) if ('0.-123456789'.contains(c)) c]; */
  /*ES7 COMPREHENSIONS: grid = (for (c from grid.iterable()) if ('0.-123456789'.contains(c)) c); */
  // DESUGARS TO: 
  grid = 
    grid.
        iterable().
        filter(c => '0.-123456789'.contains(c)).
        toArray();

  //ORIGINAL CODE:      var values = dict((for (s of squares) [s, digits]));
  //ES7 COMPREHENSIONS: var values = dict((for (s from squares) [s, digits]));
  // DESUGARS TO: 
  var values = dict(squares.map(s => [s, digits]));

  for (var pair of zip(squares, grid)) {
    var s = pair[0], d = pair[1];
    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) {
  //ORIGINAL CODE:      if (all((for (d2 of values[s]) if (d2 != d) eliminate(values, s, d2))))
  //ES7 COMPREHENSIONS: if (all((for (d2 from values[s].iterable())) if (d2 != d) eliminate(values, s, d2))))
  if (all(values[s].iterable().filter(d2 => d2 != d).map(d2 => eliminate(values, s, d2))))
    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
    var d2 = values[s][0];
    //if (!all((for (s2 of peers[s]) eliminate(values, s2, d2))))
    if (!all(peers[s].map(s2 => eliminate(values, s2, d2))))
      return false;
  }
  // Now check the places where d appears in the units of s
  for (var u of units[s]) {
    //var dplaces = [for (s of u) if (values[s].contains(d)) s];
    var dplaces = u.filter(s => 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) {
  //var width = 1 + Math.max.apply(Math, [for (s of squares) values[s].length]);
  var width = 1 + Math.max.apply(Math, squares.map(s => values[s].length));
  var line = '\n' + ['-'.repeat(width*3)].repeat(3).join('+');
  for (var r of rows)
    /*
    print([for (c of cols)
              values[r+c].center(width) + ('36'.contains(c) && '|' || '')]
          .join('') + ('CF'.contains(r) && line || '')); */

    print(
        Array.
        from(cols).
        map(c => 
              values[r+c].center(width) 
                + ('36'.contains(c) && '|' || '')).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((for (s of squares) values[s].length == 1)))
  if (all(squares.map(s => values[s].length == 1)))
    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
  //var a = [for (s of squares) if (values[s].length > 1) values[s].length + s].sort();
  var a = 
    Iterable.
        from(squares).
        filter(s => values[s].length > 1).
        map(s => values[s].length + s).
        toArray().
        sort();

  var s = a[0].slice(-2);

  //return some((for (d of values[s]) search(assign(copy(values), s, d))));
  return some(
    Iterable.
        from(values[s]).
        map(d => search(assign(copy(values), s, d))));
}

hard = '4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......';

print_board(search(parse_grid(hard)))