Html5: Mobile, web, desktop!!

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

On the past days I been playing with different tools/frameworks to make html5 applications, actually I want to code once deploy everywhere kind of thing.

And I discover this awesome tools:

Ionic Framework

The Ionic Framework let you make applications in html5 that you can deploy on the web and mobile.

The ionic framework is made on top of other existing technologies like cordova and angular.js, hammer.js and it provides a lot additional features, its easy
to make a clean UI that will look good on mobile and web.

Obviously if you use specific mobile features they will not work on the web, but its easy to make fall-back code to deal with this limitations.

I made two applications, available on Android App Store and online, you see them here.

Node-Webkit

The node-webkit lets you make standalone application to run on desktop (linux, windows, mac OS),
its also easy to deploy application on the web (but with no access to node modules).

The node-webkit is node and webkit running in the same thread, this is great because you can use any node module seamless on your html5 application
letting you access for example local file system.

I started an application with node webkit, and it easy really easy to work with. I think my next experiment would be using ionic with node-webkit and get an application working on the web, mobile and desktop.

Grunt: The JavaScript Task Runner

I just wanted to mention the Grunt Tool because it is really handy that can be used to automate many development processes and already have some nice ready to use scripts: For example there is a node-webkit script to automate the process of packaging for multiple platforms.

Well that鈥檚 it :D, 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鈥檛 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 (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%)

The Poor Man JavaScript Prolog…

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.

I have been playing a fun game based on Zebra/Einstein puzzle.

So my first idea was to do a puzzle generator, and I started to think that Prolog would be a nice tool for the job, but since I like JavaScript much more, I ended up doing other exercise: basically I wanted to get the features that I like in Prolog in JavaScript with a nice JavaScript flavor.

One of the features that I like in Prolog is variable unification and also backtracking, I actually tried a lot of ways to store “facts”, backtracking and other stuff, but
in the end it just puts a complex and restrictive layer to the code.

So I just implemented a Variable Object/Class that does two important things:

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

As a test I implemented a Sudoku solver:

First I setup my test case, I found this one on the Internet, they say its one of the most hard Sudokus ever made and I believe them it takes ~26 seconds to solve and ~3 minutes to find all possible solutions, in this case it found only one solution.

var grid = [
  // 1    2    3    4    5    6    7    8    9
  [v(), v(), v(5), v(3), v(), v(), v(), v(), v()], // 1
  [v(8), v(), v(), v(), v(), v(), v(), v(2), v()], // 2
  [v(), v(7), v(), v(), v(1), v(), v(5), v(), v()], // 3
	
  [v(4), v(), v(), v(), v(), v(5), v(3), v(), v()], // 4
  [v(), v(1), v(), v(), v(7), v(), v(), v(), v(6)], // 5
  [v(), v(), v(3), v(2), v(), v(), v(), v(8), v()], // 6
	
  [v(), v(6), v(), v(5), v(), v(), v(), v(), v(9)], // 7
  [v(), v(), v(4), v(), v(), v(), v(), v(3), v()], // 8
  [v(), v(), v() , v(), v(), v(9), v(7), v(), v()], // 9
];

Now I must initialize the grid constrains, with some help functions:

function distinct (grid, sx, sy, ex, ey) {
	ex += sx;
	ey += sy;

	for (var x=sx; x < ex; x++) {
		for (var y=sy; y < ey; y++) {
			for (var x1=sx; x1 < ex; x1++) {
				for (var y1=sy; y1 < ey; y1++) {
					if (!((x===x1) && (y===y1))) {
						grid[x][y].not_unify(grid[x1][y1]);
					}
				}
			}
		}
	}
};

function sudokuConstrains (grid) {
	// squares
	for (var i=0; i<9; i+=3) {
		for (var j=0; j<9; j+=3) {
			distinct (grid, i, j, 3, 3);
		}
	}

	// rows
	for (var i=0; i<9; i++) {
		distinct (grid, 0, i, 9, 1);
	}

	// col
	for (var i=0; i<9; i++) {
		distinct (grid, i, 0, 1, 9);
	}
	
	return grid;
}

sudokuConstrains(grid);

In the code above I say that rows, columns and 3x3 squares have distinct values, I use
the not_unify variable method to do this.

Next I wrote a function to try all possible values, if a value fail to unify then the function returns and try other value, a kind of lame backtracking system, every time the function tries a unification the affected variables are saved and then restored. If a result is found a callback function is called with the resulting grid:

function it (grid, i, j, callback) {
	if (i === grid.length) {
		callback(grid);
	}
	else {
		if (grid[i][j].getValue() !== undefined) {
			if (j === grid[i].length-1) {
				it(grid, i+1, 0, callback);
			}
			else {
				it(grid, i, j+1, callback);
			}
		}
		else {		
		   [v(1), v(2), v(3), v(4), v(5), v(6), v(7), v(8), v(9)]
                     .forEach(function (v) {
				grid[i][j].save();
				if (grid[i][j].unify(v)) {
					if (j === grid[i].length-1) {
						it(grid, i+1, 0, callback);
					}
					else {
						it(grid, i, j+1, callback);
					}
				}
				
				grid[i][j].load();
			});
		}
	}
};

Now I just need to call it:

it (grid, 0, 0, print);

Print is the callback function, to print the results.

The zebra solution has a small problem it prints the correct solution but prints it
many times :( … But it only takes ~0.6 seconds to solve 馃榾

Variables

The variables use a very simple algorithm:

  • All variables have two arrays, one for unifiable variables and other to not unifiable variables
  • Unification is successful if:
    • Variable/value is not in the not unifiable array (recursive),
    • At least one of the variables to be unified is not initialized or both variables have same value.
    • If unification is successful the variable is inserted in unifiable array.
  • Not Unification is successful if:
    • Variable/value is not in the unifiable array (recursive),
    • At least one of the variables to be not unified is not initialized or variables have different value.
    • If not unification is successful the variable is inserted in not unifiable array.

Thats all 馃槈 Happy codding…

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

JavaScript to Lambda-Calculus: GaloJS

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

Good news everyone 馃榾 …

The GaloJS is now able to convert a simple JavaScript function to lambda-calculus and can execute alpha conversion and beta (normal) reduction.

As a test I use the factorial function:

 function fac(n) {
   if (n === 0) {
     return 1;
   }
   else {
     return n * fac(n-1);
   }
 }

Well the function is not well defined because it doesn’t guarantee that n is a positive integer, but I want to keep things simple.

So GaloJS is now capable to convert the function to lambda-calculus and it looks like this:

 fixpoint 位fac.位n. (
     (=== n (位f.位x.x)) 
        (位f.位x.f (x)) 
        (* n (fac (- n (位f.位x.f (x))))))

You are probably thinking that I am cheating with the === and * and fixpoint, but no I actually defined a “std lib” for it, and it goes like this:

((位fixpoint.((位false.((位true.((位nand.((位!.((位&&.((位||.
((位isZero.((位pred.((位*.((位+.((位-.((位< =.((位===.

(fixpoint (位fac.(位n.((((=== n) (位f.(位x.x))) (位f.(位x.(f x)))) 
((* n) (fac ((- n) (位f.(位x.(f x))))))))))

) (位m.(位n.((&& ((<= m) n)) ((<= n) m)))))
) (位m.(位n.(isZero ((- m) n)))))) 
(位m.(位n.((n pred) m))))) (位m.(位n.((n succ) m))))) 
(位m.(位n.(位f.(m (n f))))))) 
(位n.(位f.(位x.(((n (位g.(位h.(h (g f))))) (位u.x)) (位u.u))))))) 
(位n.((n (位x.false)) true)))) (位p.(位q.((nand (! p)) (! q)))))) 
(位p.(位q.(! ((nand p) q)))))) 
(位p.((nand p) p)))) 
(位p.(位q.((((p q) false) false) true))))) 
(位x.(位y.x)))) 
(位x.(位y.y)))) (位f.((位x.(f (x x))) (位x.(f (x x))))))

Seems complicated but it isn't, its just messy, basically what I do is "bind" a "function" to a name by nesting "functions", for example the fixpoint is defined here as a Y combinator (can you find it in the above lambda expression? lol):

(位fixpoint.body) (位f.(位x.f (x x)) (位x.f (x x)))

So on beta reduction all fixpoint occurrences in the body will be replaced by the Y combinator, so if the body is:

 fixpoint 位fac.位n. (
     (=== n (位f.位x.x)) 
        (位f.位x.f (x)) 
        (* n (fac (- n (位f.位x.f (x))))))

It will became:

 (位f.(位x.f (x x)) (位x.f (x x))) 位fac.位n. (
     (=== n (位f.位x.x)) 
        (位f.位x.f (x)) 
        (* n (fac (- n (位f.位x.f (x))))))

Alpha Conversion

Alpha conversion is basically variable rename, like this:

(位x.(位y.x)) => rename x to a => (位a.(位y.a))
(位x.(位y.x)) => rename y to a => (位a.(位a.x))

Alpha conversion has been a pain to implement, not that its incredible difficult its just tricky and because I want to use it in beta reduction I am still fuzzy on how should my alpha conversion behave in some cases.

Variable Capture

I think variable capture is when a substitution of a free variable results in a bound variable (the free variable is captured).

For example: (位x.(位y.x f)) alpha conversion x to f will result in the capture of free variable f as a bound variable (位f.(位y.f f)).

Other example can be:
(位x.(位y.x)) alpha conversion x to y, x is a bound variable but is free where the alpha conversion will occur (位y.x) ,so the conversion will result in (位y.(位y.y)).

The problem with variable capture is that if the substitution is made it will change the
meaning of the original expression.

for example: (位x.(位y.x f)) 1 => (位y.1 f) but renaming x to f => (位f.(位y.f f) and then do the same as before (位f.(位y.f f) 1 => (位y.1 1) =/= (位y.1 f).

In this cases, by definition, alpha conversion is not possible but we can avoid variable capture by renaming bound variables:

(位x.(位y.x)) => rename y to y1 => (位x.(位y1.x)) 
=> rename x to y => (位y.(位y1.y))

Beta Reduction

There is a couple of beta reduction strategy’s, I think beta normal reduction is
guarantied to find a lambda-expression that cant be reduced no more if such expression
exists, for example if I try beta normal reduction on my factorial example without arguments it will expand to infinity because it will always be able to apply Y combinator but if I give it a argument (a church numeral) it will reduce to factorial result (a church numeral),
this is because the Y combinator will disappear when the stop condition (n===0) is true.

Variable Capture

Variable capture can occur in beta reduction and must avoided (using bound variable renaming) to complete beta reduction.

For example:

 
(位x.(位y.x)) y a 
=> (位y.y) a 
=> a 

witch is wrong, the reduction should be like this:

(位x.(位y.x)) y a 
=> (位y1.y) a 
=> y 

A more complex example:

(位x.(位y.x)) (位x.(位y.y)) (位x.(位y.x)) 
=> (位y.(位x.(位y.y))) (位x.(位y.x)) 
=> (位x.(位y.y))

In this case I think there is no need to rename variables, because there is no variable
capture, all substitutions have bound variables.

One last example:

(位x.(位y.x)) (x y) z
=> (位y.x y) z
=> x z

witch is wrong, it should be:

(位x.(位y.x)) (x y) z
=> (位y1.x y) z
=> x y

GaloJS: factorial beta normal reduction

The following are some examples of beta reduction of factorial:

fac (位f.位x.x) // (位f.位x.x) church numeral 0, fac 0
=> (位f.位x.f x) // result 1  
fac (位f.位x.f x) // fac 1 
=> * (位f.位x.f x) (fac 0) 
=> * (位f.位x.f x) (位f.位x.f x) 
=> (位f.位x.f x)  // result 1
fac (位f.位x.f (f x)) // fac 2 
=> * (位f.位x.f (f x)) (fac 1) 
=> * (位f.位x.f x) (位f.位x.f x) 
=> (位f.位x.f (f x))  // result 2
fac (位f.位x.f (f (f x))) // fac 3 
=> * (位f.位x.f (f (f x))) (fac 2) 
=> * (位f.位x.f x) (位f.位x.f (f x)) 
=> (位f.位x.f (f (f (f (f (f x))))))  // result 6

Unfortunately GaloJS doesn’t produce such easy to read outputs,
a intermediate step looks more like this mess:

=> fac 3
...
(位f.(位x.(f (f (f (f (f (f ((位u.x) ((((位x.((位fac.(位n.(((((位m.(位n.(((位p.(位q.((位p.(((位p.(位q.((((p q) (位x.(位y.y))) (位x.(位y.y))) (位x.(位y.x))))) p) p)) (((位p.(位q.((((p q) (位x.(位y.y))) (位x.(位y.y))) (位x.(位y.x))))) p) q)))) (((位m.(位n.((位n.((n (位x.(位x.(位y.y)))) (位x.(位y.x)))) (((位m.(位n.((n (位n.(位f.(位x.(((n (位g.(位h.(h (g f))))) (位u.x)) (位u.u)))))) m))) m) n)))) m) n)) (((位m.(位n.((位n.((n (位x.(位x.(位y.y)))) (位x.(位y.x)))) (((位m.(位n.((n (位n.(位f.(位x.(((n (位g.(位h.(h (g f))))) (位u.x)) (位u.u)))))) m))) m) n)))) n) m)))) n) (位f.(位x.x))) (位f.(位x.(f x)))) (((位m.(位n.(位f.(m (n f))))) n) (fac (((位m.(位n.((n (位n.(位f.(位x.(((n (位g.(位h.(h (g f))))) (位u.x)) (位u.u)))))) m))) n) (位f.(位x.(f x))))))))) (x x))) (位x.((位fac.(位n.(((((位m.(位n.(((位p.(位q.((位p.(((位p.(位q.((((p q) (位x.(位y.y))) (位x.(位y.y))) (位x.(位y.x))))) p) p)) (((位p.(位q.((((p q) (位x.(位y.y))) (位x.(位y.y))) (位x.(位y.x))))) p) q)))) (((位m.(位n.((位n.((n (位x.(位x.(位y.y)))) (位x.(位y.x)))) (((位m.(位n.((n (位n.(位f.(位x.(((n (位g.(位h.(h (g f))))) (位u.x)) (位u.u)))))) m))) m) n)))) m) n)) (((位m.(位n.((位n.((n (位x.(位x.(位y.y)))) (位x.(位y.x)))) (((位m.(位n.((n (位n.(位f.(位x.(((n (位g.(位h.(h (g f))))) (位u.x)) (位u.u)))))) m))) m) n)))) n) m)))) n) (位f.(位x.x))) (位f.(位x.(f x)))) (((位m.(位n.(位f.(m (n f))))) n) (fac (((位m.(位n.((n (位n.(位f.(位x.(((n (位g.(位h.(h (g f))))) (位u.x)) (位u.u)))))) m))) n) (位f.(位x.(f x))))))))) (x x)))) (((位m.(位n.((n (位n.(位f.(位x.(((n (位g.(位h.(h (g f))))) (位u.x)) (位u.u)))))) m))) (((位m.(位n.((n (位n.(位f.(位x.(((n (位g.(位h.(h (g f))))) (位u.x)) (位u.u)))))) m))) (位f.(位x.(f (f (f x)))))) (位f.(位x.(f x))))) (位f.(位x.(f x))))) f))))))))))
...
=> (位f.(位x.(f (f (f (f (f (f x))))))))

Not very pretty, but it works :D.

GaloJS: Future work

GaloJS only converts very simple functions, it doesn’t support imperative programming,
this means it doesn’t know how to deal with statements.

So this will be a challenging and interesting problem to solve, I think it can be
done with monoids or monads.

Other thing that I want to do is investigate what useful things can be done with what I already have, bottom line is that it will be a nice lambda-calculus teaching tool :D.

What do you think? Let me now in the comments.

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