Thursday, September 08, 2011

Vala language introduction on IRC

Hi,
I've lately held an talk on IRC about the Vala programming language for the Ubuntu App Developer Week. I've introduced the basics of the Vala language and its features.
You can read the log of the talk here.

Tuesday, August 09, 2011

Probability of a union of independent events algorithm

Lately I was looking for a copy 'n paste algorithm to calculate the probability of a union of independent events that are not mutually exclusive (aka inclusion-exclusion principle in probability). Unfortunately I couldn't find any algorithm for such a basic problem.
Therefore, I decided to write the following naive algorithm which is fast enough for my purposes (O(n2) in time and space, where n is the number of events), and share with everyone:

You can find the code snippet here, sorry for not embedding it in the blog post but blogger is really boring me with snippets having broken layout.

The idea behind the dynamic programming approach starts from this observation:

Let A, B and C be independent non mutually exclusive events. Then:

P(A or B or C) = P(A) + P(B) + P(C) - P(A)P(B) - P(A)P(C) - P(B)P(C) + P(A)P(B)P(C)

Let me simplify the expression using A instead of P(A):

P(A or B or C) = A+B+C - AB - AC - BC + ABC

Notice that AB+AC+BC = A(B+C) + BC. In general:

AB+AC+AD+...+AZ + BC+BD+....+BZ = A(B+C+D+...+Z) + B(C+D+...+Z)

ABC+...+ABZ + ACD+...+ACZ+...+AYZ + BCD+...+BYZ = A(B(C+D+...+Z)+C(D+...+Z)+...+YZ) + B(C(D+...+Z)+...+YZ)

That's exactly where we exploit the dynamic programming to avoid recalculating the same expressions twice.

Edit: My effort was totally useless given that for independent events this is equivalent to 1 - (1 - pA)(1 - pB)..., which can be calculated in linear time. I even used this formula once and forgot about it :-(

Saturday, July 23, 2011

Give my luck back, Firefox 5!

Today I've upgraded to firefox 5, special thanks to Debian developer for packaging it. So far, everything works well and better than before, except two things (one of which I managed to tweak):
  1. The tabs bar is higher than before. This means that the mouse must move more to reach them. This has been solved. Thanks for allowing me to put the tabs bar below back again.
  2. The address bar no more involves "I feel lucky" search. The feature was awesome, because I often write a partial website name and I get most of the time to the right page without actually typing the whole name. Also, since we already have a search bar on the top-right, why was this feature removed? It's kind of duplicated now.
So, dear readers, do you know of any add-on so that I can have "I feel lucky" search back, before I write one? Having it on the top-right bar is good as well.

Edit: The solution is to open about:config and set the keyword.URL value to "http://www.google.com/search?btnI=745&q=" (without quotes). Thanks to Giuseppe for the hint.

Saturday, July 09, 2011

Python/Ruby like generators in Vala

Hello,
the post below is copied straight from here.

Here I'll show a cool snippet code making use Vala async functions and iterators for emulating Python/Ruby generators. Creating a generator is as simple as extending the Generator class and implementing the generate() method.

abstract class Generator {
    private bool consumed;
    private G value;
    private SourceFunc callback;

    public Generator () {
        helper ();
    }

    private async void helper () {
        yield generate ();
        consumed = true;
    }

    protected abstract async void generate ();

    protected async void feed (G value) {
        this.value = value;
        this.callback = feed.callback;
        yield;
    }

    public bool next () {
        return !consumed;
    }

    public G get () {
        var result = value;
        callback ();
        return result;
    }

    public Generator<G> iterator () {
        return this;
    }
}

class IntGenerator : Generator<int> {
    protected override async void generate () {
        for (int i=0; i < 10; i++) {
            yield feed (i);
        }
    }
}

void main () {
    var gen = new IntGenerator ();
    foreach (var i in gen) {
        message ("%d", i);
    }
}

You can find the above code snippet here as well.

Tuesday, July 05, 2011

Why I'm still using Emacs

Hello,
I'm using emacs since a long time by now. Everytime I ask myself why I'm using it, given emacs certainly isn't the easiest environment for programming. So, I often tried to replace emacs with other IDEs or editors, using several extensions and so on, but I still miss these killer features in a single editor:
  • Pressing a key (whatever it is, TAB in emacs) correctly/smartly indent the row according to the current language.
  • Split view, horizontal and vertical
  • No horizontal scrollbar, rather wrap the text
  • Opening/closing files without either opening a dialog or using the mouse
  • Search, search and replace (also with regexp variant) without opening any dialog
  • Switching between buffers using the longest-common-subsequence matching, without using the mouse (i.e. I don't care about file tabs, but about switching among them fast)
  • Indent entire code regions
  • Vala, C, Python, Java, Shell, Autoconf/Automake, Make and Javascript support

So, I'm not using emacs because I love it, but because it's actually the only editor with the above features.

What I'm looking for? I'm looking for a new editor/IDE, less complex, easier to customize, having the above features plus smart completion and symbol browser.
Emacs can have completion and symbol browser as well, but managing those buffers such as speedbar suck a little, things get complicated to use and to customize.

If anybody knows of such an editor, please let me know :)

Thursday, June 02, 2011

Writing binary files with bash

Hello,
I'm trying to see if I'm able to write some binary file using bash. So, when writing a binary file you often want to write a number into binary format. I ended up with this simple function for writing numbers in little endian:

function num2bin() {
printf $(printf %.$(($2*2))x\\n $1|
sed 's/\([0-9a-f][0-9a-f]\)/\\x\1/g')|
awk -F '' '{ printf $4$3$2$1 }'
}


The first parameter is the number to write, the second is the number of bytes (up to 4). For example "num2bin 40 4" will output a 4-byte long string containing the number 40 in little endian.

How do we use it? I wrote an example script for creating a wav file with noise (according to wav specifications) that you can read here.

Let me know if you have a simpler version of the num2bin function.

Friday, May 27, 2011

Complete variables with cd command in bash

Hello,
lately I've been searching for a way to complete variables containing directories with the "cd" command in bash. This is very helpful if you have something like "cd $mydir/". This is not actually working in debian bash-completion.
Then I've realized that other commands such as "ls" actually expand variables. I looked for some "complete" combo used for "ls" but not for "cd" in /etc/bash_completion and I came out with the following:

complete -F _longopt -o default cd

Luckily, this is exactly the command needed to enable variable expansion with the "cd" command. Put that in your .bashrc after loading bash_completion and you're done.

Sunday, May 22, 2011

Enforce facebook chat through SSL

Hello,

since a few days facebook is supporting SSL for the chat. The problem is that it can't be enabled.

Until facebook enables this you can use the SSLGuard plugin for firefox, which enforces SSL for a list of web sites, including all facebook pages and the chat as well.

We have some good ideas for sslguard that we'd like to get in for the next releases... stay tuned.

Saturday, May 14, 2011

Valag 1.2 released

Hello,
I've just released the 1.2 version of Valag, the graph generator for analyzing Vala code trees. Only relevant change is the fact that it now builds against libvala-0.14.

More information and download at the Valag homepage.

Thursday, February 24, 2011

Bubble sort for prolog

Hello again,
this time I've found a version of bubble sort here. I wanted to provide my version, which is less iterative and, I think, more intuitive. What it does is, simply, bubble until it's sorted:

bubblesort(L1, L2) :- bubblesort2(L1,L2,unsorted),!.
bubblesort2(L,L,sorted).
bubblesort2(L1,L2,unsorted) :- bubble(L1,L3,C), bubblesort2(L3,L2,C).
bubble([],[],sorted).
bubble([X],[X],sorted).
bubble([X,Y|L], [X|L1], C) :- X <= Y, bubble([Y|L],L1,C).
bubble([X,Y|L], [Y|L1], unsorted) :- X > Y, bubble([X|L],L1,_).

Yes, the exam is tomorrow so I will finally stop annoying you readers ;)

Saturday, February 19, 2011

Aptitude string for downgradable packages

Hello,
I'm lately doing some tests with Debian experimental packages thus I often upgrade some packages to experimental and downgrade them back to unstable.
WARNING: Downgrading in Debian is not supported etc.

aptitude search "?narrow(?installed,?archive(experimental))" -F %p|\
sed
's,\([^ ]*\),\1/unstable,'|xargs echo


This will give you a list of experimental packages installed on your system each concatenated with "/unstable". The output can go straight to "aptitude install". I don't directly use "xargs aptitude install" because it's not interactive.

Tuesday, February 15, 2011

Matrix transpose with Prolog

Hello,
an exam exercise requires me to write a matrix transpose method. I've written one and it took a little before I was able to define it completely in 4 rules.
I'm curious then I've found this on stackoverflow: the approach is to calculate first transposed column, then shift by one column and calculate the transpose of that new matrix.
This was one of the first solutions I've thought but I haven't realized it because I'm too lazy to create a rule for calculating the shifted matrix.

My approach is iterative thus less intuitive:
trans(M1, M2) :- trans2(M1, M1, [], M2, 0), !.

trans2([A|_], _, _, [], N) :- length(A, N).
trans2(M, [], H1, [H1|R1], N) :- N1 is N+1, trans2(M, M, [], R1, N1).
trans2(M, [H|R], L, [H1|R1], N) :- nth0(N, H, X),
append(L, [X], L1), trans2(M, R, L1, [H1|R1], N).

Ok, apart the fact that I haven't got the time to beautify it, the code will iterate columns and for each column it calculates a row of the transposed matrix (yes, exactly what you expect a transpose method to do :P). The key is "passing" around the nth column we're looking at.
After we finish calculating a row, we restart from the first row but looking at the nth+1 column. Recursion ends when there are no more resulting rows, i.e. when we reached the end of the columns.

Wednesday, February 09, 2011

Bluetooth simple one-line device connection pairing with Bluez

Hello,
I've written a simple Python script using the Bluez (version 4.66) stack (thanks to http://shr-project.org/trac/wiki/Using) with this usage:

python connect.py MACADDRESS PIN MOUNTPOINT

Snippet code for connect.py is here. If the device is paired, it will be removed and unmounted.

Disconnection is as easy with:

python disconnect.py MACADDRESS MOUNTPOINT

Snippet code for disconnect.py is here.

Feel free to use the code also for other services, in this case my primary concern was to mount the file system.

Rubik's Cube 3D Game in Vala/Clutter

Hello,
I've written a simple program for playing with a Rubik's Cube using Vala and Clutter.

It features:
  • high simplicity in rotating cube slices and rotating the cube itself in a very natural manner
  • shuffle the cube
  • autosave the game

Download and more usage information at the homepage... have fun :)

Friday, January 14, 2011

Base64 and Quoted-Printable GConverters for GMua

Hello,
lately I'm writing GMua for educational purposes and for evaluating Vala, whose purpose is to simplify writing Mail User Agents or simple scripts, ala Java Mail.
It currently parses IMAP (not yet complete) and has a graphical interface called Gutt (yes, inspired by Mutt) for testing.
In order to parse MIME parts with base64 or quopri content-transfer-encoding I chose to implement a couple of GConverter (will use GMime a day, maybe when they switch to gio, not yet needed) in Vala that you can find here:
I'm pretty sure there are bugs in these converters, by the way I wanted to share them :)