filet gem just released!

We finally found some time to finish the work on the gem for acceptance testing - filet. It's available via our employer github account: https://github.com/xing/filet

filet is a dsl for acceptance testing on top of Test::Unit.

Hope you'll find it useful!

How to re-implement a cartesian product algorithm

Yes. So did I waste my time, or not? Of course not. I just got a big slap in my programming face. Un pollazo. I over-implemented a cartesian product, without even noticing it. But it's fantastic, I can learn every day :)
I was even showing it around to my friends at work. They didn't notice too! Maybe this algorithm could be used for something else. But I have no fucking clue where :D
Of course I learned a lot, but still, feel a bit stupid. Do not overdo and read more - that is the lesson of today!

Ou programming... my dear...

Fast! iterative algorithm for generating permutations from sets' single elements

I like it. I like this one. Last algorithm for this problem (here) was O(n^3). Now it's O(n). It may mean two things: first one was very shitty, or that the second one is really good. Probably both are true.

I came back home, without a laptop. With one hand holding the Algorithms book (I really recommend that one) and with notebook and a pen in the other. I choose notebook and pen. It did the trick.

I know I masturbate on that issue, but it's fun. After some furious paper programming I got here:


I asked myself 3 questions at the beginning:

1. How many times "1" will be first?
2. How many times "4" will be in the result?
3. How many times "5" will be in the result?"

I wanted to answer that questions without the use of any offset indexes kept in memory in other array. Keep it simple: what do I know about my input data?
So my answers were like that:

1. If I take all the sizes of following tables and multiply them, I'll get 12.
2. Always, cause it's a single element array, so 36 (total possible permutations.
3. The same as answer number one. 6 times in cycle of 3, 18.

The main conclusion was that I can fill the results array column by column instead of row by row. All permutations will be fully calculated at once, at the very end. No gathering the permutation by permutation and then pushing it to the results. No no no, that needs indexes and traveling across the array many times. This idea dropped the complexity from O(n^3) to O(n).

Cycles, subcycles, offsets. The most important thing was to calculate a proper index in the result table and stick the current argument element exactly there (IBID). No more talk, code is below and benchmark is on the gist comment.

Iterative algorithm for generating permutations from sets' single elements

My friend asked on facebook for a iterative algorihm that would generate all possible strings from given sets in a way that for ex. given {a,b,c}, {d,e}, {f} should produce {adf, aef, bdf, bef, cdf, cef}.



There is still a recursive call moved to bump_next method. I'm trying to get rid of that one and make it fully iterative.
That was much fun doing it, as it has some tricky parts. Probably faster algorithm for that already exists, but I couldn't find any. Lots of fun.

Do you find this post helpful?

I remember the last November. I tried to export my photos from Picassa. My requirements were: keep the folders structure and the changes I made with the Picassa tools. Anyone would do it faster than me, because in Picassa you can export only one folder at the time. But I didn't want to do it sequentially. I was looking for an automated tool to handle this process. Unfortunately I didn't found one. Querying Google for an answer showed that many people failed searching for this functionality.

So I expressed my frustration.

It is funny and sad to see that 10 out of 10 people found this answer helpful.
Reasons:

1. How could my answer possibly help anyone?
2. If it actually didn't help them, then the functionality of the "Was that helpful?" button is ambiguous. It works more like voting on stackoverflow. Actually, as a side-effect of it's ambiguousness, it works exactly like voting, saying: Yeah! Damn right! We feel the same! which has nothing to do with answering the problem itself.
3. People frustrated by software seem to solidarize, ready to support someone who expresses their own frustration.

For me, the important conclusion from that silly story is that I would never use "Was that helpful?" on any of my applications. The question, I guess, should be more narrow, for instance Did that answer helped you to solve your problem? or Did this answer your question?. I think it's an issue for social informatics study.

Croissant equation and Prolog.

Computacional geometry and computer graphics are subjects I rarely play with, but I like their connection with the real matter. Today in CosmoCaixa museum I found mathematical equation for a croissant. That was quite amazing - full exhibition devoted for math and equations describing natural shapes. I see croissants often in Spain and I have to admit that I never thought about their shape as a mathematical expression.


This can be ordered like that:


This can be expressed as:



and be calculated with use of:
I wouldn't recommend to find solutions for this equation in Ruby, so the example is in ECLiPSe CLP. It is a great tool (environment) for solving contraint logic problems. It's also fun. For me.

RSpec like DSL in Test::Unit for acceptance testing.

I have project where I have to use Test::Unit. Fine, but I am used to RSpec DSL, especially when it comes to user stories (features). So, here is simple module that shows how you easily can use RSpec-like expressions in default testing framework.


Just save that module in a file that will be required by your test helper and include in you test unit spec.


With Test::Unit::Feature you have a simple DSL. Soon we'll publish in on github as a gem. Now it works with Ruby 1.8.7 and Rails 2.3.10. I didn't test it with the latest stuff.

Done with Jorge :)