Tag Archives: programming

Analyzing chess.com tournaments

This year at ProFUSION we started to create chess tournaments to play using chess.com so we have fun not only coding but playing this game. However it’s even more fun when we put both together: chess and code :-)!

During the second tournament we realized chess.com was missing a nice feature: to allow participants to predict who would be the champion based on the current championship status and future results. To show the current state, Chess.com presents us with a table like this:

Not the missing games with a “_”. What we would like is to predict who can still win the tournament based on these missing games. One trick here is how to calculate the tie break, but it’s really straightforward to implement once we understand the formula:

So, for each sum up the result of each game multiplied by the current score of the opponent (“opp” in the formula above) the game was played against.

With that in mind I wrote a small tool, ccs, to allow you to predict the next results:

$ ./ccs.py data/example2.html 
css> state
Number of players: 8

                  1.      2.      3.      4.      5.      6.      7.      8.      |  Score | Tie Break
-------------------------------------------------------------------------------------------------------
1. demarchi        X      1 1     1 0     1 0     0       1 1     1 1     1 1     |     10 |        54
2. ulissesf       0 0      X      1 1     0 1     1       1 1     1 1     1 1     |     10 |        52
3. lfelipe        1 0     0 0      X      1 1     1 1     1 0     1 1     1 1     |     10 |        52
4. hdante         1 0     0 1     0 0      X      1 0     0 1     1 1     1 1     |      8 |        38
5. Gastal         1       0       0 0     1 0      X      1 1     1 1     1 1     |      8 |        34
6. marinatwp      0 0     0 0     1 0     0 1     0 0      X      1 1     1 1     |      6 |        22
7. yanwm          0 0     0 0     0 0     0 0     0 0     0 0      X      1 1     |      2 |         0
8. antognolli     0 0     0 0     0 0     0 0     0 0     0 0     0 0      X      |      0 |         0
ccs> push 1x5=1
Simulation added: demarchi beats Gastal
Number of players: 8

                  1.      2.      3.      4.      5.      6.      7.      8.      |  Score | Tie Break
-------------------------------------------------------------------------------------------------------
1. demarchi        X      1 0     1 1     1 0     0 1     1 1     1 1     1 1     |     11 |        62
2. lfelipe        1 0      X      0 0     1 1     1 1     1 0     1 1     1 1     |     10 |        53
3. ulissesf       0 0     1 1      X      0 1     1       1 1     1 1     1 1     |     10 |        52
4. hdante         1 0     0 0     0 1      X      1 0     0 1     1 1     1 1     |      8 |        39
5. Gastal         1 0     0 0     0       1 0      X      1 1     1 1     1 1     |      8 |        35
6. marinatwp      0 0     1 0     0 0     0 1     0 0      X      1 1     1 1     |      6 |        22
7. yanwm          0 0     0 0     0 0     0 0     0 0     0 0      X      1 1     |      2 |         0
8. antognolli     0 0     0 0     0 0     0 0     0 0     0 0     0 0      X      |      0 |         0
ccs>

Ccs parses the pairings table created by chess.com (given you saved it somewhere and passed as argument to the tool) and then gives you a “ccs> ” prompt, waiting for commands. Type ‘help’ to see the list of available commands. Basically it allows you to a. see the current state of the game (‘state’ command) and b. push and pop result simulations (sigh! ‘push’ and ‘pop’ commands).

A nice feature that I’d like to introduce soon is to export to a big svg with all the state transitions, marking leaf nodes when there’s a champion. I’m also releasing the source as open source, so anybody wanting to help can implement it :-). Code is available on my github: https://github.com/lucasdemarchi/ccs. GPL-2 as usual.

What can we predict in the example above?

  1. No matter the pending games, gastal can not win anymore, since he will reach at most 54 as tie break, leaving lfelipe with 56. That also implies lfelipe would be the champion if gastal wins all his pending games;
  2. If demarchi wins his last game he wins the tournament, with score=11 and tie-break=62. If ulissesf also wins, he will have the same score, but his tie-break will be 60, pushing demarchi’s tie-break to 64.
  3. If ulissesf wins and demarchi loses, ulissesf is the champion.

Since I am demarchi on the table above, now what I have to do is either win the last game or convince Gastal to give up his pending games :-).

BlueZ to move to standard D-Bus interfaces

During the last week I was in Recife, Brazil, together with Henrique Dante, Ulisses Furquim and other fellows attending the BlueZ meeting. We discussed several topics, among them the upcoming BlueZ 5 API. That discussion started by Johan and Marcel saying BlueZ would not move to DBus.Properties and DBus.ObjectManager anymore for the next version. Main reason being that BlueZ now will have more frequent releases than it had in past and therefore there wasn’t enough time to convert the API. However I and Luiz von Dentz already had an almost working solution: I implemented DBus.Properties and he did the DBus.ObjectManager, so we received the news with much regret.

Since these changes break the API, not accepting them now means we’d need to wait for BlueZ 6 in order to have these interfaces, which expected to happen only on later next year. Thus we argued that and Marcel Holtmann challenged us to make a demo on Wednesday. Challenge accepted! After working one night to put the implementations together and finish the DBus.PropertiesChanged signal we could present such a demo. And it worked without any issues. To say the truth we only converted 2 interfaces (Adapter and Manager), but that was enough to convince them we can finish this in time for BlueZ 5.0. Or at least that’s what we hope. Final consensus: this change is back on track for the upcoming major release of BlueZ.

Now we are polishing the implementation and start sending the patches. The first patch set was already sent and hopefully soon all the others will reach BlueZ’s mailing list.

So, why is this important? By implementing these interfaces, that are part of the D-Bus specification, it becomes much easier to write client code to talk to bluetoothd and since D-Bus bindings already have implementations for them it’s much less error prone, too. At the same time we are aiming to simplify the code needed in bluetoothd to support our use-cases, so for both people who write bluetoothd and for those who write client applications this will be beneficial.

ANNOUNCE: codespell 1.0

I’m glad to announce codespell 1.0! After 3 RCs and patches submitted to several projects, I thought it was stable enough to call it 1.0. You can download the 1.0 version below:

http://packages.profusion.mobi/codespell/codespell-1.0.tar.bz2

See my previous post if you are willing to know what codespell is or read the README file inside the package.

I have already filled a TODO file with ideas for the next version. They came to mind after I’ve generated a giant patch for the Linux kernel. It is the biggest patch I’ve ever produced with codespell. Really, I think it’s the biggest patch I’ve produced ever. I hope Linus accept that patch as is because without the changes I’m planning for codespell 1.1, it’s a pain to fix some corner cases.

Some people are sending me suggestions and more misspellings to my email. I appreciate those emails and seeing they are successfully using codespell in other projects. If you want a faster way to have your changes incorporated into codespell, you may also send patches through git-send-email or just use my repository on github to send me pull requests.

UPDATE (04/11/2011): Linus accepted the patch. There’s also a discussion with further improvements for codespell on LKML.

On typos and misspellings

This week I’m in a release mood, so I’m releasing several projects I’m involved with. If you lost the first two, checkout dietsplash 0.3 and genslide 0.3 (though the announcement was in Portuguese).

After developing for several projects I’ve noticed most of them contain typos and misspellings. Even if this does not directly affect the source quality (unless the misspellings are in documentation), if we left the comment there, we’ve left it for a reason: because we want the reader of that code to stop and read it. It’s particularly good to have the correct spelling of each word when there are people from several parts of the word that maybe do not have English as their mother tongue (as I don’t). This way we can be more sure the correct message is being given through code, comments  and documentation.

Thinking a bit on this I made some bash and awk scripts to fix misspellings based on the list of common misspellings available on wikipedia. I’ve successfully sent patches for projects like the Linux kernel, ConnMan, oFono and EFL. After some of them were accepted and after I decided to run the scripts again, I noticed how slow they were (if you are curious what they did, you can google on the oFono mailing list, in which I explain the scripts). So, I started a new, very short project: codespell. Measuring against the Linux kernel tree, it runs circa 20x faster than the previous scripts. Its current version is 1.0-rc1 and I’d like to have some more testers before I release the final 1.0.

Codespell is designed to fix misspellings in source code, but it can be applied to any type of text files. When possible, codespell will automatically fix the misspelling. Otherwise it will give some suggestions about possible changes. For example, running against the Linux kernel tree, it gives me several lines like below:

drivers/target/target_core_transport.c:2528: competion  ==> competition, completion

drivers/edac/cpc925_edac.c:186: MEAR  ==> wear, mere, mare

WARNING: Decoding file drivers/hid/hid-pl.c

WARNING: using encoding=utf-8 failed.

WARNING: Trying next encoding: iso-8859-1WARNING: Decoding file drivers/hid/hid-pl.cWARNING: using encoding=utf-8 failed. WARNING: Trying next encoding: iso-8859-1

drivers/net/niu.c:3276: clas  ==> class  | disabled because of name clash in c++

FIXED: ../kernel/drivers/scsi/aacraid/aacraid.h

FIXED: ../kernel/drivers/scsi/lpfc/lpfc_sli.c

FIXED: ../kernel/drivers/scsi/aacraid/aacraid.hFIXED: ../kernel/drivers/scsi/lpfc/lpfc_sli.c

(This is all in beautiful colored lines! Test it to see the true output)

The first two illustrate some changes that cannot be automatically done because that misspelling is a common one for more than one word. So, codespell gives you the file and line where they occur.

The WARNINGs are related to the encoding of the file. Codespell will default to parse files in UTF-8 encoding, which will handle ‘ascii’ as well. If it fails to decode any line, it will try the next available encoding, i.e. ISO-8859-1. Using these two encodings I have successfully ran codespell with all the projects I care about.

Codespell allows some changes to be disabled. This is shown by the “clas => class” fix, that are not always safe to do because of name clash with C++ code.

The lines prefixed with “FIXED” show the files that were automatically fixed. In current Linus’ master branch, this resulted in:

2545 files changed, 5007 insertions(+), 5007 deletions(-)

These were the automatic fixes, that may contain some false positives. The funniest one is the on found in Documentation/DocBook/kernel-hacking.tmpl:

/*
* Sun people can’t spell worth damn. “compatability” indeed.
* At least we *know* we can’t spell, and use a spell-checker.
*/
As can be seen by the number above, this is not really true ;-).
So, there it’s: codespell 1.0-rc1. Get it. Test it. Report problems. Tell me about projects that were successfully patched.

Criando imagens customizadas de endereços de email

Endereços de email são muitas vezes mascarados na web para que não sejam facilmente obtidos por programas que tem por objetivo enviar spam. É relativamente fácil escrever um programinha que fica vasculhando a web em busca de endereços de email, cadastrá-los em um banco de dados e depois utilizá-los como quisermos. Para que isso não ocorra, várias vezes nos deparamos com endereços de email passados como “joao AT gmail DOT com” ou alguma coisa do tipo.  Outra técnica muito utilizada é transformá-lo em uma imagem. Dessa forma o programinha malicioso que a princípio era fácil se torna bem mais difícil.

Eu acho que hoje em dia temos bons programas de anti-spam, o que torna os métodos acima não tão relevantes. Porém, acredito que converter o endereço de email em uma imagem o deixa bonito. Veja por exemplo a minha página de contatos. Fazer imagens desse tipo apara domínios conhecidos como “gmail.com”, “hotmail.com” e “yahoo.com” é bem fácil: vários sites permitem que você escolha um desses domínios e escreva o seu email. Um que eu gostei foi o do freetechjournal, pois tem vários domínios ali dos serviços de email mais populares. É fácil encontrar serviços semelhantes que permitem alguma customização.

Procurei bastante na web algum site que permitisse criar um email com uma imagem de domínio customizada, porém não achei nenhum. Como é uma operação bem simples, resolvi fazer um script em python para isso. Estou disponibilizando o iconifymail, que contém também a imagem usada para a empresa em que trabalho, ProFUSION, que pode servir como base para que você faça a sua própria imagem (obrigado, Marina). O uso é bem simples, basta passar como primeiro argumento a imagem a ser utilizada como domínio e, como segundo, o seu endereço de email (sem o domínio). Algumas coisas eu deixei hard-coded no script, mas creio que seja fácil adaptá-lo para o tamanho de imagem que você quiser. O resultado final é o que pode ser visto abaixo e também na minha página de contatos:

Essa é a versão 0.1 do iconifymail, open source, disponibilizado sob GPLv3. Se você quiser contribuir, pode usar os repositórios git: oficial ou mirror.

WebKit

After some time working with the EFL port of WebKit, I’ve been nominated as an official webkit developer. Now I have super powers in the official repository :-), but I swear I intend to use it with caution and responsibility. I’ll not forget Uncle Ben’s advice: ”with great power comes great responsibility”.

I’m preparing a post to talk about WebKit, EFL, eve (a new web browser based on WebKit + EFL) and how to easily embed a browser in your application. Stay tuned.

TinyOS

As I did with previous projects I had at my university, I’d like to share another one: it’s a project using TinyOS. It’s mainly intended for education purposes, so if you are trying to learn TinyOS, it’s a good example to look at.

What does it do?

It’s a platform to monitor temperature and humidity of various rooms in a house. All sensors must collect data every X seconds and send them to sink, a predefined node. Sink can also change the value X and sensors may not reach sink in a single hop, so nodes have to use their own routing protocol to send forward data from other nodes to sink.

If you are interested in this project, send me an email and so I could help you to understand it. I think it’s a good exercise to look at source code and discover which routing protocol I was talking about (before reading the README file).

As I think I won’t modify this code anymore, rather than put it in my git repository I made a .tar.bz2 which is available here: House Monitor source code.

Compiler’s compiler version

Today I was just wondering… what’s the version of the compiler which compiled my compiler. Quite a strange question to make myself and I really don’t know where this curiosity came from.

Looking in Wikipedia:

Early compilers were written in assembly language. The first self-hosting compiler — capable of compiling its own source code in a high-level language — was created for Lisp by Tim Hart and Mike Levin at MIT in 1962.[2] Since the 1970s it has become common practice to implement a compiler in the language it compiles, although both Pascal and C have been popular choices for implementation language. Building a self-hosting compiler is a bootstrapping problem — the first such compiler for a language must be compiled either by a compiler written in a different language, or (as in Hart and Levin’s Lisp compiler) compiled by running the compiler in an interpreter.

Interesting, don’t you think? So let’s see the version of your compiler’s compiler. If you use GCC, it will put a comment in section named (surprise!) .comment. Generate the assembly correspondent to a C source code and you are going to see in the end of the file an entry like this:

.size   main, .-main
.ident  “GCC: (GNU) 4.4.1″
.section        .note.GNU-stack,”",@progbits

So, let’s play with our already compiled compiler. First we have to check the compiler version:

[lucas@skywalker tmp]$ gcc -v
Using built-in specs.
Target: i686-pc-linux-gnu
Configured with: ../configure –prefix=/usr –enable-shared –enable-languages=c,c++,fortran,objc,obj-c++ –enable-threads=posix –mandir=/usr/share/man –infodir=/usr/share/info –enable-__cxa_atexit –disable-multilib –libdir=/usr/lib –libexecdir=/usr/lib –enable-clocale=gnu –disable-libstdcxx-pch –with-tune=generic
Thread model: posix
gcc version 4.4.1 (GCC)

Ok! Version 4.4.1. Let’s use the readelf command to see the content of .comment section:

[lucas@skywalker tmp]$ readelf -p .comment /usr/bin/gcc

String dump of section ‘.comment’:
[     1]  GCC: (GNU) 4.4.0 20090630 (prerelease)
[    29]  GCC: (GNU) 4.4.0 20090630 (prerelease)
[    51]  GCC: (GNU) 4.4.1

[    63]  GCC: (GNU) 4.4.1

(…)

[   237]  GCC: (GNU) 4.4.1
[   249]  GCC: (GNU) 4.4.1
[   25b]  GCC: (GNU) 4.4.0 20090630 (prerelease)
[   283]  GCC: (GNU) 4.4.1
[   295]  GCC: (GNU) 4.4.0 20090630 (prerelease)

I didn’t understand if it’s 4.4.1 or 4.4.0, i.e. if it was used a prior version to compile the current version or if current was recompiled afterwards with this new compiler produced.  Testing random binaries in /usr/bin seems to produce similar effects, having more than one version.

So… no answers yet. Any clues?