Monthly Archives: April 2014

The Poor Man JavaScript Prolog: solving 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 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 (0.0%)
  • Interesting (0.0%)
  • Useful (0.0%)
  • Boring (0.0%)
  • Sucks (0.0%)

12 Balls WebSite with mathML and AngularJS

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

I started to learn AngularJS, the main motivation to learn AngularJS is to use it on my day job, where I have to build a WebGIS Application. But AngularJS seems so cool that I am thinking in use it for other projects.

Since I am still learning I decided to start with a really basic website, so I choose to updated my 12 Balls game website that is coded in php. I also took the opportunity to update some content :).

The website is static and is only using php for routing pages, so converting the site to use AngularJS templates was petty easy, I just had to make a js file with my Application and define the routes:

var balls12App = angular.module('balls12App', [
	'ngRoute'
]);

balls12App.config(['$routeProvider',
	function($routeProvider) {
	$routeProvider.
		when('/play', {
			templateUrl: 'partials/play.html'
		}).
		when('/about', {
			templateUrl: 'partials/about.html'
		}).
		when('/caanoo', {
			templateUrl: 'partials/caanoo.html'
		}).
		when('/algorithm', {
			templateUrl: 'partials/algorithm.html'
		}).
		when('/todo', {
			templateUrl: 'partials/todo.html'
		}).
		when('/downloads', {
			templateUrl: 'partials/downloads.html'
		}).
		otherwise({
			redirectTo: '/play'
		});
}]);

Now on my index.html page I added the following code:



... Import JS and Angular dependencies ...






...
   
...

The routes that we defined for ball12App will be rendered on the ng-view, Angular knows that he has to use ball12App because we defined the ng-view inside the
ng-app=”balls12App”, so I guess this would be the scope for ng-view?

So this is how it works on my website, when I go to the link balls12/, the route / is not defined in js file so it will use the otherwise rule, witch is

otherwise({
   redirectTo: '/play'
});

And the link is rewritten as http://fsvieira.com/balls12/#/play, now the /play route is defined in the js file like this:

when('/play', {
    templateUrl: 'partials/play.html'
}).

So the ng-view content is replaced by the template content ‘partials/play.html’ (in this case just a static page ๐Ÿ˜€ ).

And thats it. AngularJS can do much much more but I wanted to start with a really simple exercise.

Also I think its cool that Angular uses anchors to do this routing stuff.

Note: You can download the full website here: balls12/#/downloads.

MathML

I almost forget about this, I written about the 12 balls algorithm using MathML, you can see it here.

And right now I know one thing: I hate MathML, is hard to write and its ugly, maybe with some css gets better but it is still a pain to write.

So my advice if you are thinking in writing stuff in MathML use a latex to MathML converter, I found this online converter http://www.mathtowebonline.com/ and its pretty good!

Have fun!

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

Another Great Useless Page :D

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

I made another (Great) useless page, here it is The Square

The page uses a table to draw the squares, I also tried with divs not sure what gives better performance but my firefox is pretty slow and if I increase
the number of squares it stops responding, the chrome/chromium has better performance but I didn’t do any benchmark.

Anyway I was bored :( … Now I am much more relaxed ๐Ÿ˜€

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… (Sudoku Optmization)

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.

On the previews post I presented a implementation to solve Sudoku using some ideas from Prolog. On my test case I said that it takes ~26 seconds to solve and ~3 minutes to find all possible solutions.

In this post I will present a simple and efficient optimization that have a huge impact on the solver performance.

For example my test case takes now only ~0.2 seconds to solve and ~4 seconds to find all possible solutions.

The optimization is very simple, we want to reduce the number of fails and tries by
selecting a good candidate.

A good candidate would be a position with few possible numbers to try, meaning it would be the most restricted.
Example:

 1  2  3   4  5  6   7  8  9
[_, _, _] [3, _, _] [_, _, _] A 
[8, _, _] [_, _, _] [_, 2, _] B
[_, 7, _] [_, 1, _] [5, _, _] C
	
[4, _, _] [_, _, 5] [3, _, _] D
[_, 1, _] [_, 7, _] [_, _, 6] E
[_, _, 3] [2, _, _] [_, 8, _] F
	
[_, 6, _] [5, _, _] [_, _, 9] G
[_, _, 4] [_, _, _] [_, 3, _] H
[_, _, _] [_, _, 9] [7, _, _] I

Lets consider 9B not equal restrictions = [2, 5, 6, 8, 9],
so possible values would be [1, 3, 4, 7].

Lets now consider 8C not equal restrictions = [1, 2, 3, 5, 7, 8] so
possible values would be [4, 6, 9], so 8C is a better candidate then 9B.

We continue to check empty positions until we find the one with the higher number of not equal restrictions or the one with less possible values.

After having the best candidate we try possible values and we repeat the process until we find a solution or fail.

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