einstein-solver/ein.js

// var mo = require("./solver");
 /*
     .addVariabelSet("Nationality", ["Norwegian", "German", "Dane", "Swede", "Englishman"])
     .addVariabelSet("Color", ["Yellow", "Red", "White", "Blue", "Green"])
     .addVariabelSet("Smokes", ["Prince", "Blend", "Dunhill", "BlueMasters", "PallMall"])
     .addVariabelSet("Drinks", ["Bier", "Water", "Coffee", "Milk", "Tea"])
     .addVariabelSet("Animals", ["Birds", "Dogs", "Cats", "Horses", "Fish","Snake"])
     */

function EV() {
    this.__e = {};
}
EV.prototype.__e = {};
EV.prototype.emit = function(n) {
    var that = this;
    var args = [].slice.apply(arguments, [1]);
    (this.__e[n] || []).map(function(lis) {
        lis.map(function(fn) {
            fn.apply(that, args)
        })
    })
    return this;
}
EV.prototype.on = function(n) {
    var args = [].slice.apply(arguments, [1]);
    this.__e[n] = this.__e[n] || [];
    this.__e[n].push(args);
    return this;
}

function inherits(ctor, superCtor) {
    var Obj = function() {};
    Obj.prototype = superCtor.prototype;
    ctor.prototype = new Obj
}


function permutates(xs) {
    var ret = [];

    for (var i = 0; i < xs.length; i = i + 1) {
        var rest = permutates(xs.slice(0, i).concat(xs.slice(i + 1)));

        if (!rest.length) {
            ret.push([xs[i]])
        } else {
            for (var j = 0; j < rest.length; j = j + 1) {
                ret.push([xs[i]].concat(rest[j]))
            }
        }
    }
    return ret;
}

function mo() {
    this.variabler = {};
    this.funcs = {};
    this.rulas = [];
}
inherits(mo, EV)

mo.prototype.addVariabelSet = function(navn, arr) {
    this.variabler[navn] = arr
    return this;
}
mo.prototype.addVariableTable = function(navn, arr) {
    return this;
}
mo.prototype.addFunction = function(name, func) {
    this.funcs[name] = func;
    return this;
}
mo.prototype.addClause = function() {
    var args = Array.prototype.slice.apply(arguments, []);
    while (args.length) {
        var arg = args.shift();

        var props = Object.keys(arg);
        var propid1, propid2;

        if (this.variabler[props[0]]) {
            propid1 = Object.keys(this.variabler).indexOf(props[0]);
        }
        if (this.variabler[props[1]]) {
            propid2 = Object.keys(this.variabler).indexOf(props[1]);
        } else {}
        var arr = []
        if (propid1 > -1 && propid2 > -1) {
            val1 = this.variabler[props[0]].indexOf(arg[props[0]])
            val2 = this.variabler[props[1]].indexOf(arg[props[1]])
            arr = ["check", propid1, propid2, val1, val2, [props[0], arg[props[0]], props[1], arg[props[1]]].join(" ")];
        } else {
            var lookfor = props[props.length - 1];
            if (this.funcs[lookfor]) {
                arr = this.funcs[lookfor].apply(this, [arg])
            }
        }
    }
    this.rulas.push(arr);
    return this;
}

mo.prototype.build = function(tabl) {
    var r = [];
    var arr = [];
    var pertable = []

    for (var navn in this.variabler) {
        pertable.push(permutates((this.variabler[navn]).map(function(a, i) {
            return i
        })));
    }
    pertable = pertable.sort(function(a,b){ return a.length > b.length ? 1 : a.length < b.length ? -1 : 0 });

    pertable.map(function(a){

        console.log("A",a.length)

    })


    return pertable.pop()
}

mo.prototype.checkPos = function(prop1, prop2, val1, val2) {

    return this.current[this.sos[prop1]][val2] == val1

}

mo.prototype.check = function(prop1, prop2, val1, val2) {
    var i;
    //   console.log(prop1,this.sos[prop1], prop2, this.current[this.sos[prop1]],this.current[this.sos[prop2]],val1,val2)
    for (i = 0; i < 5; i++) {
        if (this.current[this.sos[prop1]][i] == val1) {
            //         console.log("II,",i,this.current[this.sos[prop1]][i],"=",val1,"&", this.current[this.sos[prop2]][i],"=",val2 );
            var p;
            p = (this.current[this.sos[prop2]][i] == val2)
            return p;
        }
    }
    return false;
}
mo.prototype.checkLeft = function(prop1, prop2, val1, val2) {
    var i;
    for (i = 0; i < 4; i++) {
        if (this.current[this.sos[prop1]][i] == val1) {
            var p;
            p = (this.current[this.sos[prop2]][i + 1] == val2)
            return p;
        }
    }
    return false;
}
mo.prototype.checkRight = function(prop1, prop2, val1, val2) {
    var i;
    for (i = 1; i < 5; i++) {
        if (this.current[this.sos[prop1]][i] == val1) {
            var p;
            p = (this.current[this.sos[prop2]][i - 1] == val2)
            return p;
        }
    }
    return false;
}

mo.prototype.checkBoth = function(prop1, prop2, val1, val2) {

    return this.checkLeft(prop1, prop2, val1, val2) || this.checkRight(prop1, prop2, val1, val2)
}

/*
mo.prototype.inner_solve_l_1 = function(cands) {

}
mo.prototype.inner_solve_l_2 = function(cands) {

}
mo.prototype.inner_solve_l_3 = function(cands) {

}
mo.prototype.inner_solve_l_4 = function(cands) {

}
mo.prototype.inner_solve_l_5 = function(cands) {

}
*/



mo.prototype.inner_solve = function(cands) {
    /*todo tada - slip fri for for for for for */
    var self = this;

    var cc = cands.length;
    var ticks = [0, 0, 0, 0, 0];
    var ic = 0;
    var iomax = self.rulas.length;
    var ioa = 0;
    var suma = cands.reduce(function(a, b) {
        return b[1].length * a
    }, 1)

    console.log(cands);

    console.log(this.rulas);
    

    return;


    for (var i0 = 0; i0 < cands[0][1].length; i0++) {
        if (cands[1]) {

            for (var i1 = 0; i1 < cands[1][1].length; i1++) {
                if (cands[2]) {

                    for (var i2 = 0; i2 < cands[2][1].length; i2++) {
                        if (cands[3]) {

                        } else {
                            total = suma * self.subspace * self.subspace
                            var st = [0, 1, 2, 3, 4]
                            self.sos[cands[0][0]] = cands[0][1][i0]
                            self.sos[cands[1][0]] = cands[1][1][i1]
                            self.sos[cands[2][0]] = cands[2][1][i2]

                            st.splice(st.indexOf(cands[0][0]), 1);
                            st.splice(st.indexOf(cands[1][0]), 1);
                            st.splice(st.indexOf(cands[2][0]), 1);
                            for (var i3 = 0; i3 < self.subspace; i3++) {
                                for (var i4 = 0; i4 < self.subspace; i4++) {
                                    ic++
                                    self.sos[st[0]] = i3
                                    self.sos[st[1]] = i4
                                    var io = 0;
                                    var ff = true;
                                    while (io < iomax && ff) {
                                        ff = false;
                                        var t = self.rulas[io];
                                        ff = self[t.slice(0, 1)[0]].apply(self, t.slice(1))
                                        if (ff) {
                                            io++;
                                        }
                                    }
                                    if (io > ioa) {
                                        ioa = io;
                                        var tt = self.rulas.map(function(t) {
                                            return [self[t.slice(0, 1)[0]].apply(self, t.slice(1))].concat(t);
                                        })
                                        self.emit("part", ic, io, ioa, iomax, self.sos, tt.map(function(a) {
                                            return a.join(" ")
                                        }))
                                    }
                                    if (ioa >= iomax) {
                                        return self.sos;
                                    }
                                    if (ic % 1000000 === 0) {
                                        self.emit("status", (ic / (total / 100)).toFixed(2) + "%", total, ic, ioa, iomax)
                                        // console.log("X2", ic, io, ioa, iomax,":>", self.sos[cands[0][0]], self.sos[cands[1][0]], self.sos[cands[2][0]], i3, i4);
                                    }
                                }
                            }
                        }
                    }
                } else {


                    var st = [0, 1, 2, 3, 4]
                    self.sos[cands[0][0]] = cands[0][1][i0]
                    self.sos[cands[1][0]] = cands[1][1][i1]
                    //                           self.sos[cands[2][0]] = cands[2][1][i2]

                    st.splice(st.indexOf(cands[0][0]), 1);
                    st.splice(st.indexOf(cands[1][0]), 1);
                    //                             st.splice(st.indexOf(cands[2][0]), 1);
                    total = suma * self.subspace * self.subspace * self.subspace;

                    for (var i2 = 0; i2 < self.subspace; i2++) {
                        for (var i3 = 0; i3 < self.subspace; i3++) {
                            for (var i4 = 0; i4 < self.subspace; i4++) {
                                ic++
                                self.sos[st[0]] = i2
                                self.sos[st[1]] = i3
                                self.sos[st[2]] = i4
                                var io = 0;
                                var ff = true;
                                while (io < iomax && ff) {
                                    ff = false;
                                    var t = self.rulas[io];
                                    ff = self[t.slice(0, 1)[0]].apply(self, t.slice(1))
                                    if (ff) {
                                        io++;
                                    }
                                }
                                if (io > ioa) {
                                    ioa = io;
                                    var tt = self.rulas.map(function(t) {
                                        return [self[t.slice(0, 1)[0]].apply(self, t.slice(1))].concat(t);
                                    })
                                    self.emit("part", ic, io, ioa, iomax, self.sos, tt.map(function(a) {
                                        return a.join(" ")
                                    }))
                                }
                                if (ioa >= iomax) {
                                    return self.sos;
                                }
                                if (ic % 1000000 === 0) {
                                    console.log("X3", ic, io, ioa, iomax, ":>", self.sos[cands[0][0]], self.sos[cands[1][0]], i2, i3, i4);
                                }
                            }
                        }

                    }







                }

            }


        }

    }


    return false;



}


mo.prototype.solve = function() {
    var self = this;
    self.current = this.build("House");
    console.log(self.current);
    
    var sa = Object.keys(this.variabler);
    self.sos = sa.map(function(a) {
        return 0; //self.current.length - 1; //Math.floor(Math.random()*self.current.length-1);
    })
    self.subspace = self.current.length;
    self.varspace = sa.length;


    var iteration = 0;
    var maxi = 0;
    var ioa = -1;


    // først find variabler som bruges i samme opslag.
    var tas = {}
    var firsta = [];
    self.rulas.map(function(ru) {
        console.log(ru);
        if (ru[1] == ru[2]) {
            firsta.push(ru);
        }
    })

    self.sos = self.sos.map(function(a) {
        return 0
    })

    var osa = -1
    console.log(firsta);

    var cands = [];


    for (var x = 0; x < firsta.length; x++) {
        self.sos = self.sos.map(function(a) {
            return 0
        })

        var t = firsta[x];
        var ca = [];
        for (var i = 0; i < self.subspace; i++) {
            var ff = false;
            self.sos[t[1]] = i
            ff = self[t.slice(0, 1)[0]].apply(self, t.slice(1))
            if (ff) {
                ca.push(i);
            }
        }
        cands.push([t[1], ca]);
    }


    self.sos = self.sos.map(function(a) {
        return 0
    })
    var result = this.inner_solve(cands);
    this.emit("done", result);
}


mo.prototype.printit = function(vals) {
    var self = this;
    var vals = vals || self.sos;
    var lpad = function(s, l) {
        while (s.length < l) {
            s = " " + s
        };
        return s;
    }
    var rpad = function(s, l) {
        while (s.length < l) {
            s = s + " "
        };
        return s;
    }
    var s = [];
    s.push([" ", 1, 2, 3, 4, 5].map(function(a) {
        return lpad("" + a, 12)
    }).join(" "));
    Object.keys(self.variabler).map(function(k, ia) {
        s.push([k, 0, 1, 2, 3, 4].map(function(a, io) {
            return a == k ? rpad(k + ":" + vals[ia], 20) : lpad("" + self.variabler[k][self.current[vals[ia]][a]], 12)
        }).join(" "))
    })
    console.log(s.join("\n") + "\n")
}


module.exports = mo;


 var t = new mo()
     .addVariabelSet("Nationality", ["Norwegian", "Dane", "Englishman", "German", "Swede"])
     .addVariabelSet("Color", ["Yellow", "Blue", "Red", "Green", "White"])
     .addVariabelSet("Smokes", ["Dunhill", "Blend", "PallMall", "Prince", "BlueMasters"])
     .addVariabelSet("Drinks", ["Water", "Tea", "Milk", "Coffee", "Bier" ])
     .addVariabelSet("Animals", ["Cats", "Horses", "Birds", "Fish", "Dogs"])
     .addFunction("Neighbor", function(arg) {
         var prop1 = Object.keys(arg)[0];
         var prop2 = Object.keys(arg[Object.keys(arg)[1]])[0]
         var val1 = arg[prop1];
         var val2 = arg["Neighbor"][prop2];
         var propid1 = Object.keys(this.variabler).indexOf(prop1)
         var propid2 = Object.keys(this.variabler).indexOf(prop2)
         var valid1 = (this.variabler[prop1]).indexOf(val1)
         var valid2 = (this.variabler[prop2]).indexOf(val2)
         return ["checkBoth", propid1, propid2, valid1, valid2, [prop1, val1, "Besides", prop2, val2].join(" ")]
     })
     .addFunction("Neighbor_Before", function(arg) {
         var prop1 = Object.keys(arg)[0];
         var prop2 = Object.keys(arg[Object.keys(arg)[1]])[0]
         var val1 = arg[prop1];
         var val2 = arg["Neighbor_Before"][prop2];
         var propid1 = Object.keys(this.variabler).indexOf(prop1)
         var propid2 = Object.keys(this.variabler).indexOf(prop2)
         var valid1 = (this.variabler[prop1]).indexOf(val1)
         var valid2 = (this.variabler[prop2]).indexOf(val2)
         return ["checkLeft", propid1, propid2, valid1, valid2, [prop1, val1, "Before", prop2, val2].join(" ")]
     })
     .addFunction("Neighbor_After", function() {
         var prop1 = Object.keys(arg)[0];
         var prop2 = Object.keys(arg[Object.keys(arg)[1]])[0]
         var val1 = arg[prop1];
         var val2 = arg["Neighbor_After"][prop2];
         var propid1 = Object.keys(this.variabler).indexOf(prop1)
         var propid2 = Object.keys(this.variabler).indexOf(prop2)
         var valid1 = (this.variabler[prop1]).indexOf(val1)
         var valid2 = (this.variabler[prop2]).indexOf(val2)
         return ["checkRight", propid1, propid2, valid1, valid2, [prop1, val1, "After", prop2, val2].join(" ")]
     })
     .addFunction("House", function(arg) {
         var prop1 = Object.keys(arg)[0];
         var prop2 = prop1
         var propid1 = Object.keys(this.variabler).indexOf(prop1)
         var val1 = arg[prop1];
         var val2 = arg["House"];
         var valid1 = (this.variabler[prop1]).indexOf(val1)
         return ['checkPos', propid1, propid1, valid1, val2, [prop1, val1, "House", val2].join(" ")]
     })
     .addClause({
         "Nationality": "Norwegian",
         "House": 0
     })
     .addClause({
         "Drinks": "Milk",
         "House": 2
     })
     .addClause({
         "Nationality": "Norwegian",
         "Neighbor": {
             "Color": "Blue"
         }
     })
     .addClause({
         "Nationality": "Englishman",
         "Color": "Red"
     })
     .addClause({
         "Smokes": "Blend",
         "Neighbor": {
             "Drinks": "Water"
         }
     })
     .addClause({
         "Nationality": "Swede",
         "Animals": "Dogs"
     })
     .addClause({
         "Nationality": "Dane",
         "Drinks": "Tea"
     })
     .addClause({
         "Color": "Green",
         "Drinks": "Coffee"
     })
     .addClause({
         "Smokes": "PallMall",
         "Animals": "Birds"
     })
     .addClause({
         "Color": "Yellow",
         "Smokes": "Dunhill"
     })
     .addClause({
         "Nationality": "German",
         "Smokes": "Prince"
     })
     .addClause({
         "Smokes": "Blend",
         "Neighbor": {
             "Animals": "Cats"
         }
     })
     .addClause({
         "Animals": "Horses",
         "Neighbor": {
             "Smokes": "Dunhill"
         }
     })
     .addClause({
         "Smokes": "BlueMasters",
         "Drinks": "Bier"
     })
     .addClause({
         "Color": "Green",
         "Neighbor_Before": {
             "Color": "White"
         }
     })
     .on("status", function(per, total, ic, ioa, iomax) {
         console.log("Status", per, ic + " of " + total, "sat " + ioa + " of " + iomax);
     })
     .on("part", function(iterations, foundl, foundt, total, sos, rules) {
         this.parts = this.parts || [];
         this.parts.push([iterations, foundt, total, sos, rules]);
     })
     .on("done", function(result) {
         if (result) {
             console.log("FOUND SOLUTION:", result);
             this.printit(result);
             if (this.parts && this.parts.length) {
                 var rr = this.parts.pop();
                 console.log(rr[4]);
             }
         } else {
             console.log("NO SOLUTION");
             console.log("Closest:");
             if (this.parts && this.parts.length) {
                 var rr = this.parts.pop();
                 // console.log("RRRRR",rr);
                 this.printit(rr[3])
                 console.log(rr[4]);
             }
         }
     })
     .solve()