zebra.js: A variable constrain lib (javascript).

On my previews posts I talked about my tries on building a zebra puzzle generator, one of my goals was also to build constrain problem solver lib in Javascript with a prolog flavour.

I released the code on github zebrajs, and today I updated the code with a few improvements and some new features.

In this post I will talk about that changes.

zebrajs

The core of zebra lib are the variables, there is a few things that you can do with them:

Create a Variable

After importing variables lib, you can create a variable like this:

var a = v();

You can initialize a variable by passing a options object to the constructor, you can pass value and domain:

  • value (optional): the value of the variable,
  • domain (optional): an array of possible values that the variable can take.

Examples:

var a = v();
var b = v({value: "blue"});
var c = v({domain: ["red", "blue", "green"]});
var d = v({value: "blue", domain: ["red", "blue", "green"]});

Get value

The function getValue(), returns the variable value or undefined if variable as no value.
A variables with no initial value can return a value depending on variable manipulation and constrains.

var a = v();
var b = v({value: "blue"});
var c = v({domain: ["red", "blue", "green"]});
var d = v({value: "blue", domain: ["red", "blue", "green"]});
console.log(a.getValue()); // undefined
console.log(b.getValue()); // "blue"
console.log(c.getValue()); // undefined
console.log(d.getValue()); // "blue"

Unify

A variable can be unified with other var like this:

var a = v();
var b = v();
console.log(a.unify(b)); // true

Variable unification is like saying that variables are the same, meaning that if one of the unified vars get a value all other vars will have the same value.

Not all variables can be unified, a variable can only be successful unified if doesn’t break any constrains, for example:

var a = v({value: "blue"});
var b = v({value: "yellow"});
console.log(a.unify(b)); // false

a and b can’t be unified because they have different values.

Other example:

var a = v();
var b = v({value: "blue"});
a.unify (b);
console.log(a.getValue()); // "blue"

After unifying var a with b, a will get the b value.

A more interesting example:

var a = v([{domain: [1, 2, 3]});
var b = v([{domain: [3, 4, 5]});

console.log(a.getValue()); // undefined
console.log(b.getValue()); // undefined

a.unify(b);
console.log(a.getValue()); // 3
console.log(b.getValue()); // 3

Variable a and b, are initialized with possible values, but with no actual value.
After a is unified with b, the only possible value that a and b share is 3, since they must have the same value a and b can only be 3.

Set Value

A variable value can be set on initialization (always successful) or after initialization using setValue() function, like unify
a value can only be set if it doesn’t break any constrain.

Example:

var a = v();
var b = v();
a.unify(b);
console.log(a.setValue("blue")); // true
console.log(b.setValue("yellow")); // false

a and b start with no values and then a is unified with b, after a is set with value “blue” b will also have the same value “blue”, so setting b as “yellow” will
fail.

Not Unify

The function notUnify, sets a constrain on both variables than they can not have the same value.

Example:

var a = v();
var b = v();
a.notUnify(b);
console.log(a.setValue("blue")); // true
console.log(b.setValue("blue")); // false

a and b start with no values, and notUnify makes a and b distinct, meaning they cant have the same value, next variable a is set to value “blue” with success,
but setting b to same value (“blue”) will fail, since a and b cant have the same value.

* notUnify also affects unify behaviour, and unify affects notUnify behaviour.

Example:

var a = v();
var b = v();
var c = v();
console.log(a.notUnify(b)); // true
console.log(b.unify(c)); // true
console.log(a.unify(c)); // false

First a is set not to unify with b (a =/= b), next b is set to unify with c (b=c), so if a=/=b and b=c then a must be different from c, so unifying var a with c fails.

Set no value

The function setNoValue is used to discard possible values from the variable.

Example:

var a = v({domain: ["yellow", "blue", "red"]});
console.log(a.getValue()); // undefined
a.setNoValue("yellow");
a.setNoValue("red");
console.log(a.getValue()); // "blue"

The variable a is declared with possible values “yellow”, “blue” and “red”, after discarding possible values “yellow” and “red”, a can only be “blue”.

Get Values

The getValues functions will return all variable possible values (not the same as domain).

Example:

var a = v({domain: ["yellow", "blue", "red"]});
console.log(a.getValue()); // undefined
a.setNoValue("yellow");
console.log(a.getValues()); // ["blue", "red"]

While var a domain is “yellow”, “blue” and “red”, after discarding “yellow” as a possible value the only possible values remaining are “blue” and “red”.

Try Values

TryValues function is a brute force function that will try all possible variable values and check if other constrained variables hold (if they are guaranteed to have a value).

Example:

var a = v(domain: ["yellow", "blue", "red", "white", "green"]);
var b = v(domain: ["blue", "red", "white"]);
var c = v(domain: ["blue", "red", "white"]);
var d = v(domain: ["blue", "red", "white"]);
var e = v(domain: ["yellow", "blue", "red", "white", "green"]);

a.notUnify(b);
a.notUnify(c);
a.notUnify(d);
a.notUnify(e);

b.notUnify(c);
b.notUnify(d);
b.notUnify(e);

c.notUnify(d);
c.notUnify(e);

d.notUnify(e);

a.tryValues();
console.log(a.getValues()); // ["yellow", "green"]

The notUnify sets vars a, b, c, d and e as distinct, meaning they cant have the same value.

the a.tryValues will try to set all possible a values, and do the same to other vars, checking if all other vars still have at least on possible value.
For example, a=yellow, b=blue, c=red, d=white and e=”green” , is a possible outcome so yellow is a possible value.
But in case a=blue, b=red, c=white, but d cant be set to any value, even if we set b=white and c=red, d will still have no possible value so a cant be blue.

When tryValues end a can only have two possible values yellow and green.

Events: onchange

A function can be set to be triggered when a variable changes, a variable is considered to change if is value is change or possible values change.

Exemple:

var a = v({domain: ["blue", "red", "yellow"]});
a.onchange(function (v) {
  console.log(v.getValues());
});

a.setNoValue("yellow"); // it will trigger function that will print ["blue", "red"]

Thats almost it,

I also made a genetic search algorithm and a example on how to generate zebra puzzles, but since this is already a big post I will talk about that on
other post.

Happy coding ;)

Posted in Uncategorized | Leave a comment

The Poor Man JavaScript Prolog: Generate zebra puzzle! (Part 4)

I just released the zebra puzzle generator on github as variable constrain lib.

I said I would clean up a bit the code, but its still pretty messy…

To run the generator go to folder examples/zebra and type:

nodejs main.js

The generator is very slow so it may take several minutes to generate the puzzles.

The puzzles are saved on a file as json format like this:

[{"constrains":[{"type":"next to","x":"dunhill","y":"dane"},{"type":"middle","x":"pallmall","y":null},{"type":"next to","x":"white","y":"tea"},{"type":"next to","x":"milk","y":"water"},{"type":"immediately to the left of","x":"water","y":"dog"},{"type":"next to","x":"beer","y":"norwegian"},{"type":"immediately to the left of","x":"prince","y":"horse"},{"type":"immediately to the left of","x":"horse","y":"cats"},{"type":"same position as","x":"yellow","y":"birds"},{"type":"immediately to the left of","x":"swede","y":"zebra"},{"type":"same position as","x":"blue","y":"dog"},{"type":"middle","x":"green","y":null},{"type":"middle","x":"coffee","y":null},{"type":"immediately to the left of","x":"german","y":"bluemaster"},{"type":"middle","x":"english","y":null},{"type":"immediately to the left of","x":"bluemaster","y":"prince"}],"missing":["red","blend"],"solution":{"houses":["yellow","blue","green","white","red"],"drinks":["water","milk","coffee","beer","tea"],"people":["german","swede","english","dane","norwegian"],"smokes":["blend","bluemaster","prince","pallmall","dunhill"],"animal":["birds","dog","zebra","horse","cats"]}}]

Its a array of objects, every object is a generated puzzle and contains the following keys:

  • “constrains”: the clues of the puzzle, every clue contain the type of the clue and one (x) or two (y) values.
  • “missing”: the values that are missing from the constrains/clues, normally this would be two. For example: “missing”:["red","blend"].

    Missing values can be presented to user like this:

    • One of the houses is red,
    • Someone smokes blend.
    • or as a question: Who lives in red house and who smokes blend.
    • or in a graphical GUI like grids or something like that you can just present all values and no need to reference the missing values.
  • “solution”: the solution for this puzzle, the solution is on the format of type: [values], for example:

    {“houses”:["yellow","blue","green","white","red"], “drinks”:["water","milk","coffee","beer","tea"], …}

    In this example the people living in yellow house drink water.

Now that I have something working I will try to optimize the lib and generator, first I will try to optimize the algorithms but when that is done I would like to try to web-workers/threads to speed up things :) (that would be fun…)

Happy coding.

Posted in Uncategorized | Leave a comment