Friday, February 29, 2008

Depth-first search with append-map.

As Haskell demonstrating depth-first search in the List monad(concatMap), we can easily do it in javascript with append-map.

Search the pair (a,b) such that a + b % 2 == 0.
(prototype.js is required.)


Array.prototype.append = function() {
return [].concat.apply([],this);
}

function solve() {
var a = [0,1,2];
var b = [1,2,4];
return a.map(function(x) {
return b.map(function(y) {
if ((x + y) % 2)
return [[x,y]];
else
return [];
}).append()}).append();
}


And now, let's solve the problem "SEND+MORE=MONEY" in javascript. I used "flatten" in this case.


function solve() {
// var digs = [0,1,2,3,4,5,6,7,8,9];
var digs = $A($R(0,9));
var m = 1;
var o = 0;
var s = 9;
return digs.without(m,o,s).map(function(e) {
return digs.without(m,o,s,e).map(function(n) {
return digs.without(m,o,s,e,n).map(function(d) {
return digs.without(m,o,s,e,n,d).map(function(r) {
return digs.without(m,o,s,e,n,d,r).map(function(y) {
if (1000 * s + 100 * e + 10 * n + d +
1000 * m + 100 * o + 10 * r + e ==
10000 * m + 1000 * o + 100 * n + 10 * e + y)
return ''+s+e+n+d+'+'+m+o+r+e+'='+m+o+n+e+y;
else
return [];
})})})})}).flatten();
}

No comments: