Monday, June 29, 2009

Sudoku Random Field Generator

The task is simple, to fill up a 9x9 field by the sudoku game rules.

Generally it's not a rocket science and there are lots of simple solutions. For example filling up the field with shifted sequences. Say you have a sequence of numbers from 1 to 9, then you might generate a valid field like that.

1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6

2 3 4 5 6 7 8 9 1
5 6 7 8 9 1 2 3 4
8 9 1 2 3 4 5 6 7

3 4 5 6 7 8 9 1 2
6 7 8 9 1 2 3 4 5
9 1 2 3 4 5 6 7 8

As you see, the principle is simple, you start with your basic sequence, and then shift it by 3 positions inside 3x3 box, and by one position between the levels. The principle will still work if you start with any randomly sorted sequence of unique numbers.

3 5 6 2 7 4 1 9 8
2 7 4 1 9 8 3 5 6
1 9 8 3 5 6 2 7 4

5 6 2 7 4 1 9 8 3
7 4 1 9 8 3 5 6 2
9 8 3 5 6 2 7 4 1

6 2 7 4 1 9 8 3 5
4 1 9 8 3 5 6 2 7
8 3 5 6 2 7 4 1 9

After that you might shuffle columns and rows in scope of boxes to make the field more random, you even might shuffle the 3x3 rows and columns as well to have even better results.

But this thing is not really serious and kinda boring. The problem is that all your numbers are grouped by three numbers and those groups in different orders will appear all over the field. And this might be used for cheating. Say you open one of the sequences 4 1 9 and then wherever you open any of those three numbers you immediately know the numbers next to it.

Well for smarty pants like you and me, we need something different, something bigger, better and more bad ass.

After several coups of coffee I've come to the following algorithm.

1. We generate our field row by row
2. For each cell in a row, depends on the other existing numbers in the 3x3 box or the column, we generate a list of options
3. Out of the list of options for each cell we randomly select a value
3.1 When we convert a list of the options into a row we watch for intersections with other options and choose the most optimal collection

For example we have the following thing

1 5 6 9 8 7 4 3 2
9 2 3 4 6 5 8 7 1
8 7 4 3 1 2 6 9 5

4 9 7 6 3 1 5 2 8
5 3 2 7 4 8 1 6 9
? ? ? ? ? ? ? ? ?
----------------------
The options will be following

6 1 1 2 2 9 3 4 3
6 8 5 5 7 4
8 9 7

----------------------
Out of the options we might create sequences

6 1 8 2 5 9 7 4 3
6 8 1 5 2 9 4 7 3
......

This way we will have no patterns and truly random valid sudoku field.

The only problem is that it is not exactly working.

As it's a random process, for each valid field there will be about 5-10 cases when there will be no ability to create a correct sequence. But despite the "not exactly" prefix, the algorithm is actually working and creates beautiful truly random fields.

And then you have a choice. Think about the algorithm by yourself and try to make it work every time, or you can make your computer think through the algorithm several times until a fully covered field will pop up.

Yes, I know, for a piece of software it sounds cheesy, but in reality there are not much calculations in the algorithm and make it running 5-10 times is not a big deal, it takes just a few milliseconds in javascript. Besides, if you need a speed, you can always cache the fields and shuffle them later as you shuffle the fields generated by patterns.

And for the grand finale here is a possible solution in JavaScript + RightJS

....
// generates randomly distributed field
generateGrid: function() {
var numbers = '123456789'.split('').map('toInt');
var matrix = numbers.map(function() { return []; });

for (var x=0; x < 9; x++) {
var options = [];

for (var y=0; y < 9; y++) {
var col_numbers = numbers.map(function(i) { return matrix[i-1][y]; });
var box_numbers = numbers.map(function(i) {
var box_x = (x/3).floor() * 3 + ((i-1) % 3);
var box_y = (y/3).floor() * 3 + ((i-1)/3).floor();

return matrix[box_x][box_y];
});

options.push(numbers.without.apply(numbers, col_numbers.concat(box_numbers)));
}

matrix[x] = this.sequenceFromOptions(options);

// drop and start over if there sequence was damaged
if (matrix[x].compact().length < 9)
return this.generateGrid();
}

return matrix;
},

sequenceFromOptions: function(options) {
for (var i=0; i < 9; i++) {
this.cleanOptions(options);

options[i] = [options[i].random()];
for (var j=i+1; j < 9; j++) {
options[j] = options[j].without(options[i][0]);
}
}

return options.map('first');
},

cleanOptions: function(options) {
for (var i=0; i < 9; i++) {
if (options[i].length == 1) {
for (var j=0; j < 9; j++) {
options[j] = options[j].length == 1 ? options[j] : options[j].without(options[i][0]);
}
}
}
}
....

Saturday, June 20, 2009

How Not To Create Rails Plugin

Another day I needed to handle some task which included communication with a SPARQL service. Quick google search gave me a reference to the ActiveRDF project, which claims to be the thing for ruby and rails.

But the thing is that the darn thing ain't work. As the matter of fact, you won't be able even run the example from the official site. I'm not complying, used the python sparql-wrapper to accomplish the task, but this project is a good example how you should not create a Rails plugin.

And here some tips and lessons you can learn out of it.

1. Location and Versioning Control System

The project was started at the https://launchpad.net service, under the bazaar versioning control system. That's probably a progressive thinking, but still a big mistake.

All the Rails crowd currently, more or less lives on git and github. The reason is obvious, all the people in one place, it is easy to participate in the projects using quick forking and merging. No need to register and set up your account. You do it once and have them all.

I had some experience with launchpad, it's a pretty good system, and if I would start some specific project for Ubuntu, I would probably thought about launchpad, but for Rails related project, if you want the people to participate you should go to github.

2. Implementation

The implementation as well a good example how not to write ruby code.

First of all when you creating an actual plugin or gem, global classes is the last thing which you should do. There should be the only one global name and this is the name of your project. All the rest of the things should be under the namespace.

The second is the API and what the users need to write in order to make it working in their application. With such a beautiful and powerful language as Ruby is, it is quite a shame to make people call the factory method directly. None of the actual rails part do that. There so much opportunities for all the meta-programming magic and you end up calling classes creation manually.

They should do it simultaneously to the existing things, like ActiveRecord or ActiveResource. As the matter of fact they probably should not start a standalone project in the first place and create some extension for the ActiveRecource project, they might make it to the rails codebase and that's huge. Much better than having another rails plugin.

But anyway, with a badly structured project, even if someone would like to participate and help it, that would be really hard and usually almost impossible to change anything, because there are already people who use the project as is, and people don't like to update their application code.


3. Support

I don't think I should mention such basic things, that when you have year and a half old bugs in your bug-tracker, even bugs where people already posted solutions and patches and you still didn't fix the problem, that's quite suck. As well as I should not mention such simple thing like keeping your code actually working, at least with the examples you have got on the front page.

The thing is that despite the fact that you are creating an open-source project and by the license you are not responsible for anything, you actually creating a project for people. Yes I know 90% of OOS just show-off projects by rookies just out of the university. But if you want the people to take you seriously you should support your projects.

Even if you don't want to work on the project anymore and there are no one else, you probably should say something, like "sorry guys the thing didn't fly and I have better things to do". Yes that suck, but that's understandable, and responsible.

If you didn't do that, people will still come and kill their time with your buggy code and will be left pretty much alone. You should warn your customers about such things, because everyone has different situations, someone probably would be happy to spend some hours to make a dead thing walking, but someone might be on a deadline and would expect your project actually working and probably would switch to something else if was warned.


The End

So the thing is simple. Bad location, bad implementation and bad support. This is more than enough to kill almost any project in any area. Think about it when you start your own.

Thursday, June 18, 2009

RightJS The First Public Version

After months and months of hesitations and struggling against my own perfectionistic habits I've eventually released the first version of my javascript library called RightJS.

Basically it's the fastest and compactest JavaScript framework at the day. And the coolest one too. Sure.

Well... Whatever. I wish the thing a long happy live and lots of ass-kicking experience.

Amen.

http://rightjs.org

Friday, June 12, 2009

Dynamic IFrames As Form Targets

Sometimes you need to submit a form through some hidden iframe, usually when you're trying to monkey an ajax request for a file uploading.

Usually you just render an iframe element along with the form in the html code and assign the target attribute of the form. Something like this

<form target="my-iframe">.....</form>
<iframe name="my-iframe"></iframe>

It works, but in cases when you try do the same thing dynamically with javascript. Say to wire some additional fancy callbacks or something. Say like that.

var iframe = document.createElement('iframe');
document.body.appendChild(iframe);
iframe.id = iframe.name = 'my-iframe';
window['my-iframe'].onload = function() {...};

var form = document.getElementById('my-form');
form.target = iframe.id;
form.submit();

This thing looks generally correct, but unfortunately won't work.

I'm not sure why, but I do know the way how to deal with it.

The trick is simple, dirty and cross-browsing. Just how we like it.

var div = document.createElement('div');
document.body.appendChild(div);
div.innerHTML = '<iframe id="my-iframe" name="my-iframe"></iframe>';
var iframe = document.getElementById('my-iframe');
iframe.addEventListener('load', function() {....}, false);
// or for IE
iframe.attachEvent('onload', function() {....});

var form = document.getElementById('my-form');
form.target = iframe.id;
form.submit();

This thing is perfectly works in all the modern browsers and old IEs.

And for the end, there is even better way. Try the new RightJS framework. Then the same thing will look like this.

$('my-form').send();

This is pretty much it. Have a good one.

Tuesday, June 9, 2009

Filenames Encoding Conversion Under Linux

If you need to mass-convert filenames from one encoding to another, say you are migrating from one distro to another and need to move the legacy data, you can do that with the convmv util.

# apt-get install convmv
# convmv -f cp1251 -t utf8 -r --notest /dir/name

Integers To Binary Or Hex Conversion In Ruby

There are some tips on how you convert integers to binary or hex numbers forth and backwards.

irb(main):019:0> 30.to_s(2)
=> "11110"
irb(main):020:0> 30.to_s(10)
=> "30"
irb(main):021:0> 30.to_s(16)
=> "1e"

irb(main):027:0> '11110'.to_i(2)
=> 30
irb(main):028:0> '30'.to_i(10)
=> 30
irb(main):029:0> '1e'.to_i(16)
=> 30

Tuesday, June 2, 2009

RightJS Visual Effects

Continuing having fun with RightJS. I've just published some basic visual effects library on the official site and created some simple playground where you can try this and that. Check it out, there are some fancy stuff.

http://rightjs.org/fx-demo