Category Archives: nodejs

zebrajs update, testing and testcase generation

What do you think of this post?
  • Awesome (0.0%)
  • Interesting (0.0%)
  • Useful (0.0%)
  • Boring (0.0%)
  • Sucks (0.0%)

ZebraJS Update

The last few days I have been rewriting the variables lib, this updates includes:

  • Added examples (exemples/logic/add.js), from my previews post,
  • Better memory management with version system (commit, revert, remove) instead the old dumb stack (save and load) system,
  • simplified the code to achieve better performance,
  • Testing and debugging libs:
    • lib/variables_test.js: Monitors all lib operations and throws a exception if it finds a inconsistency on the lib,
    • lib/variables_test_msg.js: Monitors all lib operations and stops the program with a error message,
    • lib/variables_testcase.js: Monitors all lib operations and stops the program with a error message and generates a testcase for mocha.

The sudoku puzzle takes now, almost 3 seconds to solve and check for all possibilities:
real 0m2.837s
user 0m2.496s
sys 0m0.038s

I think its good since we have to take into account the time nodejs takes to start up the program.

Testing and testcase generation

When we rewrite part of a program bugs will always appear especially on big rewrites, that’s why having a test framework is useful, we run all the test and fix everything that doesn’t pass the tests, then we run our examples and they all fail and burn lol…
So I think its good practice to find bugs and write some more test, this will prevent future fail, and will also confirm your bug suspicions…The problem is when you write a bunch of testcases but all of them passes, meaning that the bug is more tricky than you would expect.

So after I got tired to write tests, I tried to find a good tool to help me, but I found none, the problem was:

  • Debugger: Node-inspector doesn’t work very well for me and besides debugging requires a little work and inspection to find bugs,
  • Profiler: I cant understand the output of profilers and cant get the information that I need,
  • Symbolic Execution: I have been reading about this, seems great but didn’t find anything for nodejs,
  • Other options: There is probably other options, I just made a quick search didn’t bother to look how to personalize the tools to make what I expected…shame on me 😛 (any suggestion or comments are welcome)

So I decided to take on other approach, I made a proxy class, that has this features:

  • Monitor all calls of a object,
  • For every call made it constructs a call trace with the provided arguments,
  • Extensible with the functions:
    • before: execute before call,
    • after: execute after call,
    • error: execute if a exception occurs
  • Run the trace again and generate a minimal test case.
  • Setting up proxy trace should be only a matter of changing the require libs to proxy libs, no other changes in the code should be made.

And this is how its working for zebrajs lib:

  • I created a proxy to Variables and VariablesFactory,
  • On after and before calls I check my variables integrity with the should.js lib, if something wrong occurs I throw an exception,
  • On my error handling function I call proxy.sandbox to generate a small test case where the error occurs,
  • I go to one of examples, and change the ‘require(“lib/variables”)’ with my proxy ‘require(“lib/variables_testcase”)’, and then run the example like this
    ‘nodejs my_example.js > log.txt’. If a error occurs it will present me with a testcase on the bottom of the log.txt.
  • I copy the testcase to my mocha test/ folder, normally I change the testcase adding more tests, check the expected values and change them to what they should be, ect, etc…
  • I then correct the bugs, check if everything is right and keep the testcase for future development 😉

Until now I think this proxy object is pretty useful to test “real” programs/examples, of course not everything is great, proxy lib may have bugs (it probably has, since the code is a mess), the check functions may have bugs, the performance is decreased a lot and some testcases may take some time to generate.

Here is a testcase that was generated (This error occur as normal exception of js, the test case generated was really big, I then added some checks to catch the bug early…):

 it("should f_0 commit", function() {
                var f_0 = new VariableFactory();
                var v_71 = f_0.v({domain:[1,2,3,4,5,6,7,8,9], });
                var v_80 = f_0.v({domain:[1,2,3,4,5,6,7,8,9], });
                should(v_71.notUnify(v_80)).eql(true);
                should(v_71.notUnify(v_80)).eql(true);
                /*
                        invalid version number < 0
                        f_0 commit
                */
                should(f_0.commit()).eql(0); // I changed this from -1 to 0 since it was the correct expected value,
  });

This is a little trick bug, since it didn’t occur if I comment one of the lines with notUnify, It was cool to see that the test case generated was
exactly the smallest to the error occur, it made my day lol...
And that’s it 😉 ...

Testcase generator algorithm

The testcase generator is a pretty dumb piece of code, when a error occurs I do the following on proxy.sanbox:

  • It grabs only the calls on the root of the trace, its not interested on internal calls, and do a list,
  • After call list is created it will setup a "clean" and "controlled" environment to execute the calls,
  • Then it runs the call list, ignoring calls from the bottom of the list, if the error still occurs than it can remove the ignored call,
    it continues to do this until it reaches the beginning of the list,
  • It then creates a string, as a mocha testcase, with the remaining calls in the list, since it has all information like returned values it can
    create assertions of the expected values, of course some of them may be wrong but that’s must be checked by the programmer, and a wrong assertion is
    definitely a bug.

Well that’s it, Happy codding.

What do you think of this post?
  • Awesome (0.0%)
  • Interesting (0.0%)
  • Useful (0.0%)
  • Boring (0.0%)
  • Sucks (0.0%)

zebrajs facts: take that prolog :D

What do you think of this post?
  • Awesome (0.0%)
  • Interesting (0.0%)
  • Useful (0.0%)
  • Boring (0.0%)
  • Sucks (0.0%)

Today for fun I decided to implement some mathematical operators/logic operator on the zebrajs lib.

So I decided to make a post on the add operator.

The add implementation uses the idea of facts in prolog.
In prolog a fact is expressed like this:

father(rolando, filipe);
father(rolando, isabel);

Above I am simple saying that rolando is the father of filipe and isabel, and that is fact.
When I execute for example father(X, filipe), X will take the value rolando.

On the zebrajs there is no notion of facts, but a similar behaviour can be implemented, this is how I did it:

function Facts (values, factory, args, callback) {
	return function () {
		values.forEach(function (value) {
			if (value.length === args.length) {
				var ok = true;
				factory.save();
				for (var i=0; i!==args.length; i++) {
					ok = value[i].unify(args[i]);
					if (!ok) {break;}
				}
			
				if (ok) {
					callback(args);
				}
				
				factory.load();
			}
		});
	};
};

And the function can be used like this to define for example AND operator:

function AND (p, q, r, callback) {
	return Facts ([
		[v({domain: [0]}), v({domain: [0]}), v({domain: [0]})],
		[v({domain: [0]}), v({domain: [1]}), v({domain: [0]})],
		[v({domain: [1]}), v({domain: [0]}), v({domain: [0]})],
		[v({domain: [1]}), v({domain: [1]}), v({domain: [1]})]
	], factory, [p, q, r], callback);	
};

The fact functions takes a table of values, and return a function that will try to unify the input variables with the variables on the table if it succeeds to unify a full table line then a solution was found and a callback function is called.

For example:

var AND(v(), v(), v({domain: [1]}), function (vars) {
  console.log(vars[0].getValue() + " AND " + vars[1].getValue() + " = " + vars[2].getValue());
});

It will print: “1 AND 1 = 1″, because the only line that can be unified with the input values is the last one “[v({domain: [1]}), v({domain: [1]}), v({domain: [1]})]”

Now the same thing can be done to define a simple 1 bit ADD operator, I will define
the ADD with input: p + q = r, c (previews operation carry) and cc (carry).
The table will contain all possible values to compute 1-bit add operation, for example:
p + q + c = r, cc
0 + 0 + 0 = 0, 0
0 + 0 + 1 = 1, 0
0 + 1 + 0 = 1, 0

1 + 1 + 1 = 1, 1

function ADD (p, q, c, r, cc, callback) {
	return Facts ([
		[v({domain: [0]}), v({domain: [0]}), v({domain: [0]}), v({domain: [0]}), v({domain: [0]})],
		[v({domain: [0]}), v({domain: [0]}), v({domain: [1]}), v({domain: [1]}), v({domain: [0]})],
		[v({domain: [0]}), v({domain: [1]}), v({domain: [0]}), v({domain: [1]}), v({domain: [0]})],
		[v({domain: [0]}), v({domain: [1]}), v({domain: [1]}), v({domain: [0]}), v({domain: [1]})],
		[v({domain: [1]}), v({domain: [0]}), v({domain: [0]}), v({domain: [1]}), v({domain: [0]})],
		[v({domain: [1]}), v({domain: [0]}), v({domain: [1]}), v({domain: [0]}), v({domain: [1]})],
		[v({domain: [1]}), v({domain: [1]}), v({domain: [0]}), v({domain: [0]}), v({domain: [1]})],
		[v({domain: [1]}), v({domain: [1]}), v({domain: [1]}), v({domain: [1]}), v({domain: [1]})],
	], factory, [p, q, c, r, cc], callback);
};

This operator can now be used to construct a n-bit operator, the input now would
be an array of variables (on reverse order), for example, p=2=[v({domain: [0]}), v({domain: [1]})]=10 (binary).

function ADDn (p, q, r, callback) {
	var c = v({domain: [0]});
	
	var f = function () {
		callback(p, q, r);
	};
	
	p.forEach (function (_p, index) {
		var cc = v();
		f = ADD(_p, q[index], c, r[index], cc, f);
		c = cc;
	});
		
	return f;
};

This function will construct a sequence of ADDs passing carry flag from one operation to other, a 2 bits operation would look something like this:
– ADD(p1, q1, v({domain: [0]), r1, cc, ADD(p2, q2, cc, r2, cc2, callback));
Notice that cc is the carry of first operation that is passed to the second operation.

Now I can use add function like this:

var add = ADDn([v(), v()], [v(), v()], [v(), v()], callback);

To make things simpler I defined a function to generate variables from decimal number to zebrajs vars and wrap it up on a nice add function.

And now the fun part :), use add function to solve [simple] equations, like this a+b=9:

var a = add(undefined, undefined, 9, 5 /* number of bits */, add_print); a();

And the result would is:

decimal: 2 + 7 = 9
bits: 00010 + 00111 = 01001

decimal: 3 + 6 = 9
bits: 00011 + 00110 = 01001

decimal: 6 + 3 = 9
bits: 00110 + 00011 = 01001

decimal: 7 + 2 = 9
bits: 00111 + 00010 = 01001

decimal: 4 + 5 = 9
bits: 00100 + 00101 = 01001

decimal: 5 + 4 = 9
bits: 00101 + 00100 = 01001

decimal: 0 + 9 = 9
bits: 00000 + 01001 = 01001

decimal: 1 + 8 = 9
bits: 00001 + 01000 = 01001

decimal: 8 + 1 = 9
bits: 01000 + 00001 = 01001

decimal: 9 + 0 = 9
bits: 01001 + 00000 = 01001

decimal: 10 + -1 = 9
bits: 01010 + 11111 = 01001

decimal: 11 + -2 = 9
bits: 01011 + 11110 = 01001

decimal: 14 + -5 = 9
bits: 01110 + 11011 = 01001

decimal: 15 + -6 = 9
bits: 01111 + 11010 = 01001

decimal: 12 + -3 = 9
bits: 01100 + 11101 = 01001

decimal: 13 + -4 = 9
bits: 01101 + 11100 = 01001

decimal: -6 + 15 = 9
bits: 11010 + 01111 = 01001

decimal: -5 + 14 = 9
bits: 11011 + 01110 = 01001

decimal: -2 + 11 = 9
bits: 11110 + 01011 = 01001

decimal: -1 + 10 = 9
bits: 11111 + 01010 = 01001

decimal: -4 + 13 = 9
bits: 11100 + 01101 = 01001

decimal: -3 + 12 = 9
bits: 11101 + 01100 = 01001

decimal: -14 + -9 = 9
bits: 10010 + 10111 = 01001

decimal: -13 + -10 = 9
bits: 10011 + 10110 = 01001

decimal: -10 + -13 = 9
bits: 10110 + 10011 = 01001

decimal: -9 + -14 = 9
bits: 10111 + 10010 = 01001

decimal: -12 + -11 = 9
bits: 10100 + 10101 = 01001

decimal: -11 + -12 = 9
bits: 10101 + 10100 = 01001

decimal: -16 + -7 = 9
bits: 10000 + 11001 = 01001

decimal: -15 + -8 = 9
bits: 10001 + 11000 = 01001

decimal: -8 + -15 = 9
bits: 11000 + 10001 = 01001

decimal: -7 + -16 = 9
bits: 11001 + 10000 = 01001

Some results are not mathematical right, this is due to overflow, in this case the number of bits is limited to 5, the same problem would occur on a normal CPU.

The cool part of defining operator this way is that they work on any direction, so we can have any number of unknown variables. The operator can be chained to make a equation and they can be solved by just running it.

For example I had defined a multiply function, this function can easily be used to calculate
a square root, example: x*x=16, x would be solved to 4.

The multiply function is much more complicated and really slow:

function MULn (p, q, r, callback) {

	var grid = [];
	var l = p.length;
		
	var f = function () {
		callback(p, q, r);
	};
	
	for (var i=0; i<l ; i++) {
		var line = [];
		for (var j=0; j<i; j++) {
			line.push(v({domain: [0]}));
		}

		p.forEach(function (_p, index) {
			var a = v();
			var b = q[i];

			f = AND(_p, b, a, f);
			line.push(a);
		});
		
		for (var j=line.length; j<r.length; j++) {
			line.push(v({domain: [0]}));
		}
		
		grid.push(line);
		var gl = grid.length;
		if ((gl > 0) && !(grid.length&1)) {
			// 1, 2, [3], 4, [5]
			// save intermidiate add results.
			var line;
			if (i===l-1) {
				line = r;
			}
			else {
				line = [];
				for (var j=0; j<r .length; j++) {
					line.push(v());
				}
			}

			grid.push(line);
			// 0 1 [2], 2-2=0, 2-1=1, 2
			
			f = ADDn(grid[gl-2], grid[gl-1], grid[gl], f);
		}
	}
	
	return f;
};

It was fun to define this operators but there are still a lot of problems before any practical use for this.

Problems

  • Operations are too slow, not only operators should be optimized but also the zebrajs lib
  • Overflow results on wrong mathematical results, it should be a way to handle and avoid this.

The code is not yet on the repository, I will try to at least clean the code before a commit 😉

What do you think of this post?
  • Awesome (0.0%)
  • Interesting (0.0%)
  • Useful (0.0%)
  • Boring (0.0%)
  • Sucks (0.0%)

zebrajs improvements

What do you think of this post?
  • Awesome (0.0%)
  • Interesting (0.0%)
  • Useful (0.0%)
  • Boring (0.0%)
  • Sucks (0.0%)

Hi,

(** Zebrajs a constrain problem solving lib **)

Recently I discover that my zebrajs lib was broken, mostly because of type conversion, so I decided that was time to start adding automated testing to the lib.

I didn’t want anything to much complicated so I choose the mocha with should.js and I am very happy with it.

The test file is here they are pretty simple.

Now with tests I hope to avoid breaking the lib and that it became much more stable.

Try it out 😀 and give me some feedback.

What do you think of this post?
  • Awesome (0.0%)
  • Interesting (0.0%)
  • Useful (0.0%)
  • Boring (0.0%)
  • Sucks (0.0%)

zebra.js: Generating Zebra puzzles.

What do you think of this post?
  • Awesome (0.0%)
  • Interesting (0.0%)
  • Useful (0.0%)
  • Boring (0.0%)
  • Sucks (0.0%)

The zebrajs is a variable constrain library that I developed to solve constrain problems like zebra puzzles (aka Einstein puzzles), sudoku and other constrain puzzles.

In this post I will explain how I solve and generate zebra puzzles using zebrajs.

The Puzzle

First lets define our puzzles. The puzzles are nothing more than a grid size and a list of clues, for example:

{
"grid":{"w":2,"h":2}, 
"clues":[
  {"type":"immediately to the left of","a":{"v":"var1_0","y":1},"b":{"v":"var1_1","y":1}},
  {"type":"immediately to the left of","a":{"v":"var0_0","y":0},"b":{"v":"var0_1","y":0}}]
}

We only considered puzzles with unique solutions, a puzzle with more than one solution is considered to be invalid.

The puzzles clues are defined with a constrain type and the related variables, for example:

  {"type":"immediately to the left of","a":{"v":"var1_0","y":1},"b":{"v":"var1_1","y":1}},

On the above case we have a clue with two variables “a” and “b”, I call the “v” variable property an item, they are defined as a string like this: “var0_0″, “var0_1″, …
The names of items are not important, what matters is that the same name refers to the same item.

The goal of the puzzle is to deduce all items positions, in our puzzles the “y” coordinate is already known, stored as property “y”. You can think of y as a class or group, for example in original zebra puzzle items are organized in category’s like: houses, nationality, animals, smokes and drinks.

Solving

Like I said before the goal of the puzzle is to find all item positions, we already know item y position so we only need to find out the x coordinate value.

To solve the puzzle, for every clue, we are going to create a zebrajs variable (x), the variable will be initialized with the domain of all possible x coordinates and with appropriated change events for the item/var clue.

For example the “immediately to the left of” setup function is defined like this:

var constrains = {
...
"immediately to the left of": function (grid, a, b) {
		var domain = [];
		for (var i=0; i < grid .w-1; i++) {
			domain.push(i);
		}

		a.x = v({domain:domain});
		
		var domain = [];
		for (var i=1; i < grid.w; i++) {
			domain.push(i);
		}
		
		b.x = v({domain:domain});
		
		b.x.change (function (a) {
			return function (b) {
				var da = a.getValues();
				var db = b.getValues();

				da.forEach (function (x) {
					if (db.indexOf(x+1) === -1) {
						a.setNoValue(x);
					}
				});
			};
		}(a.x));
				
		a.x.change (function (b) {
			return function (a) {
				var da = a.getValues();
				var db = b.getValues();

				db.forEach (function (x) {
					if (da.indexOf(x-1) === -1) {
						b.setNoValue(x);
					}
				});
			};
		}(b.x));
	},
...
}

We can invoke the function like this: constrains[clue.type](grid, clue.a, clue.b) and it will create the new x variable with the correct domain for every variable.

For example, if a is immediately to the left of b it means that in a grid of 5x5 "a" must be at possible x coordinates [0, 1, 2, 3] and "b" must be at [1, 2, 3, 4].
After creating x variables with corresponding domains we can setup change event on both variables to update related variables, for example if "a" domain changes to [1, 2] than "b" domain must change to [2, 3] because we know that "b" must be immediately to the left of "a".

The last constrain that we need to setup on variables is that for every row "x" variable must have a distinct value, we can easily do it like this:

        function setVars (a, b) {
		if ((a && b) && (a.v!==b.v) && (a.y===b.y)){
			a.x.not_unify(b.x);
		}
	};

	for (var i=0; i < clues.length-1; i++) {
		var clue1 = clues[i];
		for (var j=i+1; j < clues .length; j++) {
			var clue2 = clues[j];
				
			setVars(clue1.a, clue2.a);
			setVars(clue1.a, clue2.b);
			setVars(clue1.b, clue2.a);
			setVars(clue1.b, clue2.b);
		}
	}

The code simple compares all clue variables and if they have the same y value and are not the same item ("v") then x variables are distinct and we say they don’t unify.

Now that all variables are created with the correct constrains we just need to unify all equal variables (variables with same item name), we do it like this:

        clues.forEach (function (clue, index) {
		items[clue.a.v] = items[clue.a.v] || clue.a.x;
		items[clue.a.v].unify(clue.a.x);
		if (clue.b) {
			items[clue.b.v] = items[clue.b.v] || clue.b.x;	
			items[clue.b.v].unify(clue.b.x);
		}
	});

What is happening? Why unifying would solve the puzzle?

Well we have created all variables with the according constrains and domains depending on the type of clues, clue variables are identified by their item name meaning same name refers to same variable so they must be unifiable.

A successful unified variable guaranties that no constrains on any unified variable are break and we can say that constrains are merged.

For example, lets say that we have a item “var0_0″ on a “middle” constrain with x domain [1, 2, 3] and a immediately left constrain with same item “var0_0″ and x domain [0, 1, 2, 3],
since the item is the same for both constrain variables we can unify the x variables and
since x must be in the middle the result of “var0_0″ x coordinates domain would be
[1, 2, 3], by continuing to unify equal variables we are limiting x coordinate values for that variable (item) and if we end up with only one possible value for x coordinate than
position is determined.

Other deductions

Sometimes not so obviously deduction can be made, for this kind of deductions we use a brute force function called try values.

The function is very expensive since it will try all possible x variable values and check if any tried value would result on a variable with no values, if this happens than the value is marked as a not unifiable value, restricting the range of x possible values.

Since the function is very expensive I run it after all constrains have been applied, this will limit the number of possible values remaining.

vars.forEach (function (v) {
   v.tryValues(sl);
});

Generating Zebra Puzzles

The process of finding puzzles can be defined as this:

  • Let C be the set of all possible constrains
  • and S = Powerset(C).
  • for all elements s in S, s is valid puzzle if solve function can find a unique solution using s.

Now as you can imagine the size of search space will increase tremendous when increasing grid size and the number of constrains making it impossible to test all combinations.

I tried different search methods to speed up the search of a solution, I even tried genetic search, but they were taking to long, maybe my heuristic wasn’t good enough.

Anyway I using a faster method, its a simple try and fail.

And it simple works like this:

  1. We start with a list of all clues,
  2. Shuffle the clues list,
  3. We try to find a clue that can be removed from our clue list (a clue can be removed if we can solve a puzzle with the remaining clues).
  4. When no more clues can be removed from the list we have found a puzzle and we stop.
  5. If a clue was taken from the list we repeat steps from step 2.

Well that’s it happy puzzling 😉

What do you think of this post?
  • Awesome (0.0%)
  • Interesting (0.0%)
  • Useful (0.0%)
  • Boring (0.0%)
  • Sucks (0.0%)

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

What do you think of this post?
  • Awesome (0.0%)
  • Interesting (0.0%)
  • Useful (0.0%)
  • Boring (0.0%)
  • Sucks (0.0%)

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 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 😉

What do you think of this post?
  • Awesome (0.0%)
  • Interesting (0.0%)
  • Useful (0.0%)
  • Boring (0.0%)
  • Sucks (0.0%)

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

What do you think of this post?
  • Awesome (0.0%)
  • Interesting (0.0%)
  • Useful (0.0%)
  • Boring (0.0%)
  • Sucks (0.0%)

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.

What do you think of this post?
  • Awesome (0.0%)
  • Interesting (0.0%)
  • Useful (0.0%)
  • Boring (0.0%)
  • Sucks (0.0%)

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

What do you think of this post?
  • Awesome (0.0%)
  • Interesting (0.0%)
  • Useful (0.0%)
  • Boring (0.0%)
  • Sucks (100.0%)

“”Zebra/Einstein puzzle is basically a constraint problem, where you have to find a unique solution that satisfy all constraints.
Its fun and can be easily solved on paper.””

I think my zebra puzzle generator is now making some interesting puzzles, so I decided to
post one of them, I tried make the generated text more natural, but my English is not very good and I don’t want to change it too much or I might change the meaning of constrains…
so here it goes:

  • The norwegian lives next to the person that smokes dunhill
  • The swede lives immediately to the left of the house with a horse.
  • The white house is in the middle.
  • The in the middle house they drink beer.
  • The person that drinks coffee lives immediately to the left of the house with a zebra.
  • The person that has cats lives immediately to the left of the house with a dog.
  • The red house is next to the house where they drink milk.
  • They have birds in the blue house.
  • The person who smokes blend lives immediately to the left of the house with cats.
  • They have a zebra in the green house.
  • The english lives immediately to the left of the house where they smoke pallmall.
  • The person that smokes bluemaster lives in the middle.
  • The german lives next to the house where they drink water.
  • The person that smokes pallmall lives immediately to the left of the house where they smoke blend.
  • The dane lives in the middle.
  • The person that drinks tea is next to the house where they drink coffee.

Who lives in the yellow house and who smokes prince?

Code…

Now I just need to clean up a bit my code and soon I probably make a release on github.

What do you think of this post?
  • Awesome (0.0%)
  • Interesting (0.0%)
  • Useful (0.0%)
  • Boring (0.0%)
  • Sucks (100.0%)

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

What do you think of this post?
  • Awesome (0.0%)
  • Interesting (0.0%)
  • Useful (0.0%)
  • Boring (0.0%)
  • Sucks (0.0%)

“”Zebra/Einstein puzzle is basically a constraint problem, where you have to find a unique solution that satisfy all constraints.
Its fun and can be easily solved on paper.””

I tried some ideias from my last post to generate some zebra puzzles, and I got some results:
I think the puzzles are still to easy, but I will post some here hopping they are at least fun :) [Let me know in the comments]…

Ah, to solve the puzzles you must assume that there is:

  • there is five houses : yellow, blue, red, green, white
  • there is five drinks : water, tea, milk, coffee, beer
  • there is five people : norwegian, dane, english, german, swede
  • there is five smokes : dunhill, blend, pallmall, prince, bluemaster
  • there is five animals: cats, horse, birds, zebra, dog

Puzzle 1

The milk is in the middle.
The milk is immediately to the left of norwegian
The milk is immediately to the left of tea
The beer is immediately to the left of horse
The horse is immediately to the left of dog
The green is immediately to the left of beer
The red is immediately to the left of green
The red is next to water
The white is immediately to the left of horse
The blue is immediately to the left of pallmall
The white is same position as german
The white is same position as dunhill
The english is next to swede
The beer is immediately to the left of prince
The water is immediately to the left of cats
The english is immediately to the left of bluemaster
The birds is next to english

Puzzle 2

The coffee is in the middle.
The coffee is immediately to the left of norwegian
The coffee is immediately to the left of milk
The beer is immediately to the left of dog
The dog is immediately to the left of birds
The yellow is immediately to the left of beer
The white is immediately to the left of yellow
The white is next to water
The green is immediately to the left of dog
The red is immediately to the left of prince
The green is same position as english
The green is same position as blend
The german is next to dane
The beer is immediately to the left of bluemaster
The water is immediately to the left of horse
The german is immediately to the left of pallmall
The zebra is next to german

Puzzle 3

The milk is immediately to the left of dunhill
The beer is immediately to the left of water
The german is next to zebra
The white is immediately to the left of milk
The beer is in the middle.
The yellow is immediately to the left of horse
The milk is immediately to the left of horse
The beer is immediately to the left of swede
The yellow is same position as english
The yellow is same position as prince
The horse is immediately to the left of cats
The coffee is immediately to the left of dog
The dane is next to german
The german is immediately to the left of bluemaster
The blue is immediately to the left of white
The green is immediately to the left of blend
The coffee is next to blue

The Algorithm

I am using a very naive algorithm and it takes almost 16 minutes to generate a puzzle, I still need to try other things before posting the code.

So the algorithm goes something like this:

  1. Generate a random solution,
  2. Generate a list of all possible constrains,
  3. Search for the constrain that can reduce possibilities to a maximum,
  4. Save that constrain and try the remaining constrains: using previews method,
  5. Apply saved constrains before try new constrains,
  6. Keep doing this until a solution is found, the saved constrains are the result.

Things that I think it would improve the result:

  • Apply saved constrains every time a new constrain is successfully applied, so that all deduction are taken in to account,
  • When constrains have same weight choose random,
  • When random selecting constrains with same weight favour the type of constrains with less occurrences in the result,
  • Suffle result, because constrains are tried by order there is a chance that puzzles look alike.

Right now I am not very concerned with the time that takes to generate the puzzle and more concerned with generating nice puzzles to play.

That’s it, happy puzzling…

What do you think of this post?
  • Awesome (0.0%)
  • Interesting (0.0%)
  • Useful (0.0%)
  • Boring (0.0%)
  • Sucks (0.0%)

The Poor Man JavaScript Prolog: Generate zebra puzzle!

What do you think of this post?
  • Awesome (0.0%)
  • Interesting (0.0%)
  • Useful (0.0%)
  • Boring (0.0%)
  • Sucks (0.0%)

Update: This post is outdated and you can now find this project at github zebrajs.

“”Zebra/Einstein puzzle is basically a constraint problem, where you have to find a unique solution that satisfy all constraints.
Its fun and can be easily solved on paper.””

On my previews post “The Poor Man JavaScript Prolog: solving zebra puzzle!” I solved zebra puzzle in JS, but the fun part is to generate the zebra puzzles alikes.

Generating a puzzle is more challeging than just solving it because you need to anwser a important question: how can I generate a fun or hard puzzle that people will enjoy playing?

Using some ideas of the solver from my previews post I constructed a program to generate zebra puzzles but while it generates correct puzzles (with a unique solution) they tend to be too easy with lots of redundant constrains.

How it works?

First I generate a random solution like this:

var colors  = [v({value:"yellow"})    , v({value:"blue"})   , v({value:"red"})     , v({value:"green"})  , v({value:"white"})];
var drinks  = [v({value:"water"})     , v({value:"tea"})    , v({value:"milk"})    , v({value:"coffee"}) , v({value:"beer"})];
var people  = [v({value:"norwegian"}) , v({value:"dane"})   , v({value:"english"}) , v({value:"german"}) , v({value:"swede"})];
var smokes  = [v({value:"dunhill"})   , v({value:"blend"})  , v({value:"pallmall"}), v({value:"prince"}) , v({value:"bluemaster"})];
var animals = [v({value:"cats"})      , v({value:"horse"})  , v({value:"birds"})   , v({value:"zebra"})  , v({value:"dog"})];

var _solution = {
        houses: shuffle(colors),
	drinks: shuffle(drinks),
	people: shuffle(people),
	smokes: shuffle(smokes),
	animal: shuffle(animals)
};

Basically I generate grid with values in random position, example:

houses: yellow green red blue white 
drinks: tea water beer milk coffee 
people: swede norwegian english dane german 
smokes: prince bluemaster blend pallmall dunhill 
animal: zebra birds cats horse dog 

Next I generate a list with all possible constrains, my program uses 4 types of constrains:

  1. X is immediately to the left of Y,
  2. X is next to Y,
  3. X is at same position as Y.
  4. X is at the middle.

So from my previews example I would generate a list more or less like this:

[left_of(yellow, green), left_of(yellow, birds), ... left_of(blue, white), ... middle(birds) ...] 

Now the difficult part is to select from the constrains set a subset that generates a unique solution and at the same time is difficult, my program for now is just concerned with generating a unique solution, so the implementation is very simple:

  1. Generate the Set of all possible constrains, lets call it C,
  2. Order C in a random order (suffle(C)),
  3. Solve the puzzle by trying constrains in C by order, if constrain when applied doesn’t have any effect just ignore it otherwise save it on result list,
  4. Repeat step 2, until solution is found.

So the solving function looks like this:

function paths (state, constrains, res) {
	res = res || [];
	var change = false;
	
	constrains.forEach(function (c) {
            if (c.constrain(c.x, c.y, state)) {
               if (res.indexOf(c) === -1) {
	          res.push(c);
	       }
	       tryValues(state);
               change = true;
            }
	});
	
	change && paths(state, shuffle(constrains), res);

	return res;
};

function tryValues (state) {
	var change = false;
	for (var t in state) {
		state[t].forEach (function (v) {
			v.tryValues();
		});
	}
};

The try values is one of the new features added to variables, it checks for possible values of the variable by running all variable constrains, for example:

lets say that I have five houses a, b, c, d and e.
The variables a and e have this possible values [yellow, green],
and b, c, d have this possible values: [yellow, blue, red, white, green]

Since a, b, c, d and e must have distinct values we can assume that b, c, d possible values
are in fact: [blue, red, white].

The tryValues works by applying all possible values to a variable and it does this to all variable constrains, when all constrains are successfully unified with a value then the value is ok else its not a possible value.

from the above example lets try:

  1. b=yellow
  2. a=green
  3. Since e cant be the same as b and a, then possible values for e=[], so b can’t be yellow.

The tryValues is a very expensive function. So if I just want to solve the zebra puzzle I put this function after all constrains are executed because tryValues would be executed with much more constrains so less values to try. But to generate the puzzle I want my program to find the solution by using less constrains, so I always run it immediately after a successful constrain to make sure that all deduction are made before try other constrain.

Generated solutions

Here is an example of a generated solution:

=== constrains === 
Total: 32
The dane is in the middle.
The water is immediately to the left english
The zebra is immediately to the left birds
The red is immediately to the left dane
The beer is same position as english
The pallmall is immediately to the left dunhill
The blend is in the middle.
The dane is immediately to the left german
The tea is immediately to the left water
The red is next to horse
The red is same position as cats
The blue is immediately to the left dunhill
The green is immediately to the left beer
The pallmall is immediately to the left dog
The blend is immediately to the left pallmall
The red is immediately to the left horse
The milk is in the middle.
The milk is immediately to the left dunhill
The english is immediately to the left horse
The beer is immediately to the left pallmall
The water is same position as birds
The blue is same position as dane
The norwegian is immediately to the left cats
The water is immediately to the left blend
The english is same position as blend
The blue is same position as horse
The cats is next to water
The water is same position as bluemaster
The green is next to english
The green is immediately to the left english
The yellow is next to norwegian
The red is next to dane

== Solution ==
houses: yellow green red blue white 
drinks: tea water beer milk coffee 
people: swede norwegian english dane german 
smokes: prince bluemaster blend pallmall dunhill 
animal: zebra birds cats horse dog 

The first problem is the redundant constrains, for example:

  1. “The green house is next to english”
  2. “The green house is immediately to the left english”

The second constrain make the first one useless since
“next to” is like this: “green english” or “english green”
and “left to” is like this: “green english”

This is one of the obvious, but there are others more subtle…

Other problems are related to the question:

How to generate fun or hard to solve puzzles?

I am still figuring out this part.

But heres what I think:

  • The result should have a max limit of allowed constrains, for the following reasons:
    1. A big list of constrains may not be very appealing to people,
    2. After a certain number of constrain any added constrain is probably redundant,
    3. It reduces significantly the search space.
  • Would size be a factor to a difficult level?
    • Less constrains make me think that there is more deduction’s involved,
      but not sure if this is true, but searching for the min solution seems a good idea.

    Update:

  • Constrain variety, from the point of view of a “player” it might be more pleasant to read from a constrain list that as more variety. This is probably does kind of parameters that could be used to untie decisions.

So considering the above parameters I think what I need to do is just make a strategy to sort constrains so the “better” ones are tried first.

I also need to check how to avoid redundancy.

Thats it, please leave your ideas on the comments, I searched for an algorithm to do this but cant find any…

Happy codding ;).

What do you think of this post?
  • Awesome (0.0%)
  • Interesting (0.0%)
  • Useful (0.0%)
  • Boring (0.0%)
  • Sucks (0.0%)

The Poor Man JavaScript Prolog: solving zebra puzzle!

What do you think of this post?
  • Awesome (20.0%)
  • Interesting (20.0%)
  • Useful (20.0%)
  • Boring (20.0%)
  • Sucks (20.0%)

Update: This post is outdated and this project can now be found at github zebrajs

Zebra/Einstein puzzle is basically a constraint problem, where you have to find a unique solution that satisfy all constraints.
Its fun and can be easily solved on paper.

The Poor Man JavaScript Prolog its what I call a Variable Object implementation in JavaScript that can do two important things:

  • Unify: variable unification,
  • Not Unify: constrain variable to not unify with other variable.

My first solution of zebra puzzle, like many others out their, was kind of a brute force approach it wasn’t complete brute force because the defined constrains
make the program to fail earlier and try other options and also because the constrains or facts will fill some of the values.

I was thinking in the problem from the wrong perspective, I should have used a more constrain satisfaction approach.

For example, I can start with 5 vars representing the houses, and all vars start with all the possible house values: [“red”, “green”, “white”, “yellow” “blue”];
Using constrains I will start removing values from the variables until I end up with only one value per variable.

Using js Variable this can be done with defining a domain and not_unify.

So, first I start the initial state like this:

function getVars (domain) {
	var res = [];

	for (var i=0; i

All variables have a domain and are constrained to be distinct.

To solve the zebra puzzle, I defined the following functions:

  • same_pos (x, y, state): x and y are at same position (column),
  • position(x,p,state): x are at possible positions p,
  • left_of (y,x, state): y is left of x,
  • next_to (x, y, state): x is next to y,

After this functions are defined I can define constrains like this:

var state = initState();

var constrains = [
// The Zebra puzzle, a.k.a. Einstein's Riddle, is a logic puzzle which is to be solved programmatically. It has several variants, one of them this:

//  There are five houses.
//  The English man lives in the red house.
function () {return same_pos("english", "red", state);},

//  The Swede has a dog.
function () {return same_pos("swede", "dog", state);},

//  The Dane drinks tea.
function () {return same_pos("dane", "tea", state);},

//  They drink coffee in the green house.
function () {return same_pos("coffee", "green", state);},

//  The man who smokes Pall Mall has birds.
function () {return same_pos("pallmall", "birds", state);},

//  In the yellow house they smoke Dunhill.
function () {return same_pos("yellow", "dunhill", state);},

//  The man who smokes Blue Master drinks beer.
function () {return same_pos("bluemaster", "beer", state);},

//  The German smokes Prince.
function () {return same_pos("german", "prince", state);},

//  In the middle house they drink milk.
function () {return position("milk", [1, 2, 3], state);},

//  The Norwegian lives in the first house.
function () {return position("norwegian", [0], state);},

//  The green house is immediately to the left of the white house.
function () {return left_of("green", "white", state);},

//  The man who smokes Blend lives in the house next to the house with cats.
function () {return next_to("blend", "cats", state);},

//  In a house next to the house where they have a horse, they smoke Dunhill.
function () {return next_to("dunhill", "horse", state);},

//  The Norwegian lives next to the blue house.
function () {return next_to("norwegian", "blue", state);},

//  They drink water in a house next to the house where they smoke Blend. 
function () {return next_to("water", "blend", state);},

function () {return at_least_one(state); }
// ---
// The question is, who owns the zebra? 
];

The last constrain (function () {return at_least_one(state); }) is a special function, and its there to check if a variable as one possible value that is not
in any other variable, so that would be the value of the variable, for example:

v1 = [red, green, blue, yellow, white];
v2 = .. = v5 = [green, blue, yellow, white];

So red is in v1 but not in v2 .. v5, since all variables must have a distinct value then v1=red;

To apply the constrain I made the recursive function:

function run(state) {
	var end = true;
	constrains.forEach(function (c) {
		if (c()) {
			end = false;
		};
	});
	
	end || run(state);
};

run(state);

The run function will run until no constrain can be applied any more.
Some constrains will only have effect after other constrains are applied, and some can be applied more than once.

For example left of is defined like this:

function left_of (y,x, state) {
	var xps = find(x, state);
	var yps = find(y, state);
	var change = false;
	var max = 0;
	for (var i in xps) {
		if (max < i) {max=i;}
	}
	
	var min = 4;
	for (var i in yps) {
		if (i >=max) {
			yps[i].not_unify(v(y));
			change = true;
		}
		if (min > i) {min=i;}
	}
	
	for (var i in xps) {
		if (i < =min) {
			xps[i].not_unify(v(x));
			change = true;
		}
	}
	
	return change;
};

What this constrain does is to find y and x positions since y is left of x then:

  • y position must be less than the right most position of x,
  • x position must be bigger than the left most position of y,

Exemple:
_ x x _ _
y y y y _

It will became:
_ x x _
y y _ _

I said constrain can be applied more than once, for example:
If other constrain transforms the previews example to this:
_ x x _
y _ _ _

then running the left_of constrain again will result in:
_ x _ _
y _ _ _

Well thats it 😀

Happy coding...

What do you think of this post?
  • Awesome (20.0%)
  • Interesting (20.0%)
  • Useful (20.0%)
  • Boring (20.0%)
  • Sucks (20.0%)