Skip to content

Instantly share code, notes, and snippets.

@jhusain
Forked from BrendanEich/gist:5753666
Last active May 6, 2024 03:30
Show Gist options
  • Save jhusain/8aa35cf8a53c41940b8c to your computer and use it in GitHub Desktop.
Save jhusain/8aa35cf8a53c41940b8c to your computer and use it in GitHub Desktop.
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)))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment