Za Waarudo

Welcome ~San, You're Logined!

2009-01-18T06:32:00.003Z

No comments!

NDrive and iPhone

2008-09-06T19:06:00.003+01:00

It's no good what Apple is doing to the Automotive Navigation Industry. No one really understands what's "behind the curtain", but according to what is stated in the iPhone SDK License Agreement, Section 3.3.7, and I quote:

applications may not be designed or marketed for real time route guidance

What is their intent doing this? Some say they want to prevent "rivals" from doing navigation software, but it's no fun.

I have contacted Apple using their website a long time ago, regarding these issues but they have completely ignored my questions.

Nevertheless, a video from NDrive, an example of a navigation software, running on an iPhone.

It's a shame that NDrive and other navigation software (iGo, TomTom, etc.) are not allowed to provide real-time route guidance for the iPhone, and even worse when we see no official words from Apple regarding this matter or their future plans.

Porting applications to the iPhone OS 2.0

2008-08-03T13:45:00.002+01:00

Lately I have been porting a considerably complex application using the iPhone OS 2.0 SDK. In the past, I have been developing mobile applications for WinCE, PocketPC, and Symbian. With regards to WinCE/PPC, I believe that Visual Studio is a great IDE, but a great IDE is not always the most important factor when developing mobile software. Speaking of Symbian OS (S60 platform), the most popular IDE is Carbide, built upon the Eclipse IDE platform, which I'm not really a big fan of. One very good thing about S60 is the OpenC library, an extensive collection of POSIX and other well-known C libraries, which makes it easier to port for this platform. However, in my personal experience, the development for the Symbian OS (mainly porting) was kind of traumatising when combining the IDE with the platform and the mobile hardware. First, the emulator is bad, slow and works horribly when comparing to the same application deployed in a mobile phone. Secondly, although you can do it graphically after pressing a thousand menus and buttons, you have to write a makefile-like with a lot of tricks/hacks, in order for the compilation to be successful.

Although Xcode is still not as good as Visual Studio, it is far much better in the sense that it seamlessly integrates with the iPhone Simulator, deploying and running applications in a fast and efficient manner. In terms of porting existing code to the iPhone OS 2.0, it was not very painful, mainly because there is not much of a difference between developing for the iPhone and for the MacOS X.

Summarising what I think about the 3 platforms:

WinCE/Pocket PC: Great IDE / Very specific platform. Threading and memory maps work horribly / Emulator? Does it even work? / Deployment (slow slow slow)... "90% del tiempo perdido en tonterías"

Symbian OS (S60): Complicated IDE / OpenC is a plus / Emulator? Does not work properly and it is very slow / Deployment could be more straightforward

iPhone OS 2.0 SDK: Not as full-featured as VStudio but still does a great integration with debugging and deployment / UNIX-like development, UIKit/FoundationKit and Objective-C++ are a big plus! / Fast deployment, debugging and simulation (emulation)!

The most important factor about iPhone OS 2.0 platform that makes it superb for development is that it supports Objective-C++, making it very easy to port existing UNIX applications since you can mix Objective-C with C/C++ code just by renaming the files to ".mm" (instead of Objective-C's ".m" extension).

2008-07-04T22:33:00.004+01:00

While I was googling today, I came across a hilarious video of Steve Balmer, Microsoft from January, 2007:

"500 dollars? Fully subsidised? With a plan? (...) And it doesn't appeal to business customers because it doesn't have a keyboard, which makes it not a very good email machine".

Did you notice the decreasing tone in the last part of this sentence? It sounds a bit like:

"And it doesn't appeal to business customers because it doesn't have a (...) KEYBOARD (...)".

This sounds a little off-topic especially if you didn't read the my previous post but, according to the official site:
Office 2008 for Mac Home and Student Edition $149.95
Office 2008 for Mac $399.95
Office 2008 for Mac Special Media Edition $499.95

Let me tell you this straight:

150 / 400 / 500 dollars for Office 2008 for the Mac? With "editions" (you pay for every kilogram of software you get)? And without crash recovery or undo after save features?

No thanks!

Innovations (?) in Excel 2008

2008-07-02T22:58:00.009+01:00

Lately I've been rather busy with my Master's Thesis. Because of that, I've been working a lot with charts. My choice is naturally Excel, since it produces good graphics much better than Numbers.

Before proceeding to "innovations", I would like to call your attention to the following screenshot:

Can you see what's wrong with it? Well, apparently the answer is "nothing". Yes, except Microsoft apparently considers that when users save their worksheet, they don't need an undo feature anymore!
I thought undo was meant to be used when you made an action you didn't plan or intended to, i.e. a mistake.

I don't call it a bug, I call it innovation!

Update:

After Excel 2008 crashes for your Mac, you might be rewarded with the following message:

Don't worry. Microsoft has thought of everything! You can recover it with Excel 2007 for Windows XP:

I hope Microsoft first fixes and delivers high quality products before expanding to a whole new family of products for the Mac!

GmailFS with MacPorts

2008-07-01T23:23:00.013+01:00

Hi everyone!

I've been using MacPorts for quite some time, and I have been very pleased with its simplicity, specially since I am much more used to FreeBSD's amazing ports system. For those who don't know, MacPorts is basically a system of tools that makes it easier for you and everyone to keep a great collection of UNIX software applications up-to-date, without the annoying task of managing all the dependencies or patching some software project (hence the word "port") that was intended to run on Linux or other platform, and that could easily run on a Mac just by changing a line in some file (I'm not exagerating).

These days I've become interested in GMailFS, a software package that allows you to see (technically "mount") a directory in your filesystem (inside your home directory for example) in user space (i.e., outside the kernel space), so you can mount it without any privileges. GMailFS sits on top of FUSE (Filesystem in Userspace), more specifically on top of MacFUSE which in turn was ported by Google, and allows you to see your GMail account as a set of files and directories so you can actually download and upload files to your account with a couple of drag-n-drops with Finder :)

Since I was having problems installing this on my Mac, I've seen many forums with discussions regarding the installation procedures. In the end it all involved a lot of tricks and hacks, and never worked for the latest software versions of the packages that are required to set up GMailFS.

For these reasons I decided to stick with MacPorts (which I believe is a much cleaner and elegant way to manage sofware). Since there was no GMailFS port in MacPorts, not even support for most dependencies, I got in contact with the development team (thanks Raim), and provided feedback enough so a port with all the dependencies for GMailFS was created :)

For those who might be wondering how to get GMailFS working with MacPorts:

Download a fresh copy of MacPorts from here

Update your MacPorts tree of ports by opening a terminal and issuing the command sudo port sync

Install GMailFS by issuing the command sudo port install gmailfs

Please make sure you have python2.5 selected by default, if you don't know or don't have, you can try the following:

Install python_select by issuing the command sudo port install python_select

Select python2.5 as the default python interpreter sudo python_select python25

Along the way you will be asked for your password in your Terminal, after you issue a sudo command. This is equivalent to MacOS X's GUI prompt for a password every time you install an application with some installer.

Then you can just create a hidden GMailFS configuration file in your home directory as ~/.gmailfs with a content similar to:


[connection]
# The proxy URL
#proxy = http://user:pass@proxyhost:port
# or just 
#proxy = http://proxyhost:port

# The number or retries for the proxy connection.
#retries = 3

[account]
username = your_username
password = your_password_in_plaintext

[filesystem]
fsname = zOlRRaXPTOzOlRRa

[references]
# reference = filesystem:username:password

[logs]
# Change this to DEBUG for verbose output (useful for debugging)
level = INFO

# if you'd like logs to go to stdout, comment out this variable.
# For logging to, say, stderr, use /dev/stderr of your system's
# equivalent for it
logfile = /dev/stderr

After this, you can mount your GMailFS issuing a command like:

mount -ovolname=gmail,ping_diskarb -t gmailfs /opt/local/share/gmailfs/gmailfs.py path_for_the_directory_where_you_want_to_mount_your_gmailfs

After you have mounted the filesystem, you can copy files from and to it, and you will see your gmail account populated with "weird" emails. That's where the string zOlRRaXPTOzOlRRa I used in the sample configuration file above comes in (by the way, you can change this string to anything else): GMailFS will keep emails in your account with subjects containing the word zOlRRaXPTOzOlRRa. Since such emails in your Inbox can become distracting, you can filter them out by archiving them with a GMail filter like the following:

Please note that I added __g__zOlRRaXPTOzOlRRa__h__ instead of just zOlRRaXPTOzOlRRa, since the real email in your inbox will contain a word with a prefix and suffix, making the word become like this.

Have fun!

Assorted (not so known) tips on MacOSX

2008-06-28T16:25:00.009+01:00

I just came across these two tips recently, so you can find them either officially documented or in public forums like I did.

Tip #1: Dashboard widgets on your Desktop

Dashboard is one of those features that I believe are not very well explored in terms of desktop interaction, in MacOSX. I mean, many times it happened me (and I believe with most of you) to play a bit with some dashboard widgets but quickly end up forgetting about their existence, since one needs to change between dashboard mode and desktop mode. This tip I found out about a couple of days ago, when I first came across with a software review of Amnesty Singles. This piece of software basically allows you to transform any widget into a "standard" application. Nevertheless, if you are not willing to pay for such great software, there is quick and dirty tip that pretty much does the same thing (original link):

Preparation (1st time):

Open Terminal (just type "Terminal" in Spotlight, or alternately open Applications->Utilities->Terminal)

While in Terminal, type: defaults write com.apple.dashboard devmode YES

Logout, for the previous command to take effect, and Login again.

Everytime you want to add a widget to your desktop:

Press F12 to open Dashboard.

Press the mouse down to drag the widget of your choice.

Without releasing the mouse button, press F12 again to return to desktop mode.

When in desktop, you may release the mouse button and the widget will remain in your desktop!

Everytime you want to remove a widget from your desktop:

Press the mouse down to drag the widget of your choice.

Without releasing the mouse button, press F12 again to open Dashboard.

When in Dashboard, you may release the mouse button and the widget will return to it!

Not everything is perfect with this method. For instance, the widget will remain "always on top" and there is no way to minimise it to the Dock temporarily. The best thing you can do with most of them is to "reduce" their window size. This is why you should consider paying for Amnesty Singles if you are not satisfied with these limitations.

Tip #2: MacBook/Pro with open/closed lid, built-in display off (not dimmed) and external display (external USB keyboard not required)

Many of you usually prefer an external display, especially if you use your MacBook/Pro in a daily basis. Either because you find it distracting when using an external display or if you don't need your built-in display and want to save its life, you might find this tip useful. The option of whether to leave the lid open or closed is up to you, but the main reason to leave it open is to make the MacBook/Pro ventilate better. Some people even argue that with older Mac laptops such as PowerBooks, leaving the lid closed might cause it to melt under heat.

Ok, so here's the tip (original link):

First, make sure to connect your MacBook/Pro's power adaptor to a power source, if it's not already.

Plug in your external monitor to your MacBook/Pro. Turn the monitor on, if it's not already.

After a while, if an image does not appear in your external monitor, go to System Preferences->Displays and click a button entitled Detect Displays. An image should appear in your external monitor.

Now, the image that appears in your external monitor should represent either a mirrored desktop or an extended desktop. It is essencial that your MacBook/Pro is set to Mirrored Mode. If it is not, press F7 once and it should turn to "Mirrored Mode".

Close the lid of your MacBook/Pro and it will go to sleep

Now, plug in any USB device (e.g., an external keyboard, a mouse, a pen drive will also do it). If you already have an external mouse or keyboard attached to your laptop, you just need to press some key or button. This will make your MacBook/Pro awake from sleep and use the external screen as the main display.

When the external display shows your Desktop again or your MacBook/Pro prompts for a password (if you activated this security feature for protection), then you can open the lid, if you want your laptop to dissipate better.

Voilá! Your built-in display is turned off (not dimmed), your MacBook/Pro is not sleeping, and you can either use its built-in keyboard and mouse pad if you don't want to use an external USB mouse/keyboard like many forums advocate as necessary!

If you want to turn your built-in display back again:

Go to System Preferences->Displays and click a button entitled Detect Displays. The built-in screen should turn on again.

Directory Utility and remote NFS mounts on Mac OS X Leopard

2008-06-08T13:30:00.010+01:00

One of the graphical utilities I usually like to use on Mac OS X Leopard, in order to avoid unnecessary command-line tasks, is Directory Utility.

Directory Utility allows you to easily manage local/remote services and file systems. With this tool you can mount remote NFS file systems from *BSD, Linux and other UNIX-based Operating Systems. Although it only takes one command-line call to mount a remote filesystem, that's already very well documented in many Operating System manuals, so that is not the purpose of this post.

If you are wondering how to do it, or having problems doing it, you should launch Directory Utility first. You can access it through the Applications->Utilities folder or you can use Spotlight for that purpose (typing "Directory Utility").
If you want to add a mount, click in the following order after Directory Utility window appears:

The following dialog appears, and you should fill the fields in a similar way to the following:

If you are wondering what -P is, it's basically an indication to use a reserved socket port number. Many people claim this flag prevents connectivity problems associated to Directory Utility and NFS.

If your Mac does not verify your NFS mount and you are positively sure you entered everything correctly, then it's probably because you are connecting to a NFS server that only works with UDP protocol. You can either click Don't verify button while Directory Utility is searching for the NFS server; or, if you are the administrator of the NFS server, you can add support for TCP transports by appending the -t flag when you call nfsd. After you restart the NFS server and retry adding the mount, Directory Utility will probably be able to verify it successfully.

Google Treasure Hunt 2008, 4th and last Puzzle

2008-06-04T00:26:00.014+01:00

Two days ago, the 4th and last puzzle of GTH2008 was announced by Google, I suppose at 23:15 UTC/GMT.

I have to confess I didn't solve this problem in one shot. The first half of it was done before I got stoned of drowsiness! The second half was solved after a few hours of sleep. Shame on me... the problem was not difficult at all, and I'm not saying this because I have already solved it! It really was simple...

It can be said that the last puzzle could be, in my opinion, made up of two small puzzles:

first, how to deal with prime number generation and/or how to perform primality tests (quickly!)

second, how to sum the numbers correctly and find the smallest prime sum of consecutive prime numbers (quickly and hopefully without any mistake!)

I spent like 4 hours solving the whole puzzle in the first half but invested most of it in the first "small" puzzle. My solution for the first "small" puzzle was already fast enough for the problem at hand but I always got the program asking for **more and more** prime numbers... I was generating like millions and millions of prime numbers and even so it never seemed to find a result... My question was for the numbers [11, 83, 183, 631, 1037]. I thought that the sum of each set of 11, 83, 183, 631, and 1037 consecutive prime numbers to be simultaneously equal and a prime number itself would be the reason why it was taking so many prime numbers...

In the second half, after a deserved time sleeping, I decided to "attack" the second "small" puzzle when I immediately noticed a big mess.

Forth problem

When I decided to follow the ancient algorithm of the Sieve of Eratosthenes to pre-compute all the prime numbers up to a specified integer, I could see that second "small" puzzle was "lagging" the whole thing and not the first...

According to the reasoning I used in the algorithm to find the smallest sum of prime numbers, we must keep an eye on the current "smallest sum possible". This is to say that, if we start with two sets (call it "strings") of 3 and 7 consecutive prime numbers the initial smallest sum possible is defined by the first 7 primes (equals 41) because it is impossible for the sum of 7 consecutive prime numbers to be less than the first 7 primes.

Trying to put it simply:
The algorithm tries to shift every string of consecutive prime numbers (a string of length 3, and a string a length 7) by one prime number to the right if the sum of that string is smaller than the current "smallest sum possible". If a string is found whose sum is greater than the current "smallest sum possible", then it means the current "smallest sum possible" kind of "overflowed" and it is not possible to find two strings of length 3 and 7 whose sums are equal and up to the current "smallest sum possible". When this "overflow" happens, the current "smallest sum possible" must be updated to the minimum of the sums of the current strings.

Code for the solution

The following solution is written in C++ and sacrifices a lot of memory. As you will see, it even stores whether odd numbers, zero and one are prime or not which is not needed, as I didn't care much about it... Another problem with the program is that it does not ensure the defined MAX_NUMBER of prime numbers is enough to solve the problem, nor it tests that condition. If it is not enough, you will get a beautiful "segmentation fault", "bus error" or other crash =) Just set the value high enough paying attention to memory limits. The default value of 10000000 should be more than enough for all or most problems for the 4th puzzle.
~~Nevertheless, the program computes the solution for [11, 83, 183, 631, 1037] and others in about 4 seconds~~.

Update:
I've just updated my solution removing support for biging library as it is not required at all! My solution now takes a total of 0.233 seconds to print the result (0.221172 seconds for the prime generation up to 8000000 plus 0.00250829 seconds for the second "small" puzzle):

$ time ./sumprimes
Precalculating...
348513 primes pre-calculated
Took 0.224782 seconds
Result: *******
Took 0.00254872 seconds

real 0m0.233s


/**
 * Google Treasure Hunt 2008 - Question 4
 * by Mário Freitas (imkira at gmail dot com)
 */

// standard libraries
#include 
#include 

#import 

// support for big integers
#include "BigInteger.hh"
#include "BigIntegerUtils.hh"

// please change as desired
#define MAX_NUMBER  8000000
#define NUM_NTH_PRIMES 5000000

// number of strings
#define NUM_STRINGS 5

typedef unsigned long long Counter;

// sarifice space for prime numbers...
bool gIsPrime[MAX_NUMBER+1];
Counter gMaxNumber(MAX_NUMBER);
Counter gMaxNthPrime(NUM_NTH_PRIMES);
Counter gNthPrimes[NUM_NTH_PRIMES+1];
Counter gSumIndices[NUM_STRINGS];
Counter gSumLengths[NUM_STRINGS];
Counter gSumTotals[NUM_STRINGS];

void buildPrimesErastothenes ()
{
 Counter lNumber = 2, j, lTwo = 2;
 
 // initialize array to true
 memset(&gIsPrime, 1, sizeof(gIsPrime));
 gIsPrime[0] = gIsPrime[1] = false;
 
 // do not care about even numbers, zero or one...
 // just calculate if an integer is prime or not!
 while ((lNumber * lNumber) <= gMaxNumber)
 {
  j = lNumber * lTwo;
  
  while (j <= gMaxNumber)
  {   
   gIsPrime[j] = false;
   j += lNumber;
  }
  
  ++lNumber;
  
  while ((lNumber <= gMaxNumber) && (!gIsPrime[lNumber]))
  {
   ++lNumber;
  }
 }
 
 j = 0;
 
 // calculate an array which contains the Nth prime numbers
 for (Counter i = 0; i <= gMaxNthPrime; ++i)
 {
  if (gIsPrime[i])
  {
   gNthPrimes[j] = i;
   ++j;
  }
 }
 
 std::cout << j << " primes pre-calculated\n";
}

Counter sumConsecutivePrimes (Counter aNth, Counter aLength)
{
 Counter lSum = 0, i = aNth;
 
 aLength = i + aLength;
 
 while (i < aLength)
 {
  lSum += gNthPrimes[i];
  ++i;
 }
 
 return lSum;
}

int main (int argc, char *argv[])
{
 Counter lOne = 1, lMinimumSum, lNewMinimumSum;
 int i = 0, j = 0;
 uint64_t t0, t1, t;
 mach_timebase_info_data_t info;
 double nano, seconds;
 
 // precalculate prime numbers up to MAX_NUMBER
 printf("Precalculating...\n");
 t0 = mach_absolute_time();
 buildPrimesErastothenes();
 t1 = mach_absolute_time();
 t = t1 - t0;
 
 mach_timebase_info(&info);
 nano = 1e-9 * ( (double) info.numer) / ((double) info.denom);
 seconds = (double)t * nano;
 
 std::cout << "Took " << seconds << " seconds" << std::endl;

 // initialize the size of each string
 gSumLengths[0] = 11;
 gSumLengths[1] = 83;
 gSumLengths[2] = 183;
 gSumLengths[3] = 631;
 gSumLengths[4] = 1037;
 
 t0 = mach_absolute_time();
 // initialize the sums and starting offsets of all strings of consecutive primes 
 for (i = 0; i < NUM_STRINGS; ++i)
 {
  gSumIndices[i] = 0;
  gSumTotals[i] = sumConsecutivePrimes(gSumIndices[i], gSumLengths[i]);
 }
 
 // calculate the initial "smallest sum possible"
 lMinimumSum = gSumTotals[NUM_STRINGS-1];
 
 // while the sums are not simultaneously equal and a prime number...
 while ((j != 0) || (!gIsPrime[gSumTotals[NUM_STRINGS-1]]))
 {
  i = j = 0;
  for (i = 0; i < NUM_STRINGS; ++i)
  {
   // keep the "smallest sum possible"
   lNewMinimumSum = lMinimumSum;
   
   // the sum of the string is too small?
   if (gSumTotals[i] < lMinimumSum)
   {
    // remove the leftmost element of the sum
    gSumTotals[i] -= gNthPrimes[gSumIndices[i]];
    // shift the string to the right
    ++gSumIndices[i];
    // add the new rightmost element to the sum
    gSumTotals[i] += gNthPrimes[gSumIndices[i] + gSumLengths[i] - lOne];
    // a mismatch was found...
    ++j;
   }
   else
   // the sum of the string overflowed?
   if (gSumTotals[i] > lMinimumSum)
   {
    // find the minimum "smallest sum possible" of the current strings
    if (lNewMinimumSum == lMinimumSum)
    {
     lNewMinimumSum = gSumTotals[i];
    }
    else
    if (gSumTotals[i] < lNewMinimumSum)
    {
     lNewMinimumSum = gSumTotals[i];
    }
    
    // a mismatch was found...
    ++j;
   }
   
   // update the "smallest sum possible"...
   lMinimumSum = lNewMinimumSum;
  }
 }
 t1 = mach_absolute_time();
 t = t1 - t0; 
 
 // print the result!
 std::cout << "Result: " << gSumTotals[NUM_STRINGS-1] << std::endl;

 mach_timebase_info(&info);
 nano = 1e-9 * ( (double) info.numer) / ((double) info.denom);
 seconds = (double)t * nano;
 
 std::cout << "Took " << seconds << " seconds" << std::endl;

 exit(0);
}

Google Treasure Hunt 2008, 3rd Puzzle

2008-06-01T23:56:00.010+01:00

The 3rd puzzle was announced today.
I don't know why but I have the feeling I liked the first problem the most. I suppose the correct labelling for each puzzle type would be:

Robot Maze: computer-science

Product of sums: low-level UNIX trivia

Routing table: networking

What will be the 4th and last puzzle about? Maybe a mix of all the three topics?

Quoting the last post at Google Blog:
The fourth and final puzzle will be released at 1212448500

And after solving the 3rd problem:

Your answer was correct! Congratulations, you're part-way there.
There will more questions over the coming weeks, and the first person to answer them all correctly will win a prize, so keep trying!

If I am not mistaken, the number 1212448500 points to June 3, 2008 at 00:15:00 (like... tomorrow ???)
Update: The time is expressed as GMT+1, equivalent to 23:15:00 GMT+0.

I feel a bit sorry for getting to know about this contest only one month after it was launched - since I'm not used to reading the Official Google Blog - so it's already too late for me to think about prizes... but I feel like it was kind of fun to solve such problems :)

Like the first two problems, I'll be posting the solution to the third, although I believe you won't need much help solving it by yourself:

Third Problem

A "pseudo-algorithm" for the mechanism which describes the path taken by a network packet from a known node (call it S - source) to another node (call it D - destination) should be:

1- Start at node S

2- First, add the current network node to the path. If D is the current network node the algorithm outputs the path and ends since the packet was just delivered to D. Otherwise advance to the next step.

3- Iterate each routing table entry:

4- D matches the Nth entry's network? Set the current node as the Nth entry's target gateway and Jump to step 2

5- D does *not* match any of the routing table entries? Set the current node as the current default gateway and Jump to step 2

Update:
Just for those who might be wondering how to calculate network addresses using netmasks (/24 etc.), I used ipcalc.

Reviving an old project! Well, kind of...

2008-05-30T18:50:00.004+01:00

Back in 2006, when I was a ~~3rd-year~~ 4th-year student at the Faculty of Engineering, University of Porto, I was involved in one of the academic assignments I liked most for a course subject entitled Software Engineering Laboratory. It was a project involving 4 teams, each responsible for developing a module of a sole system. We called it SU which basically stands for Software Understanding.

I have kind of "revived" part the project. I mean, I have downloaded most of the required software in order to be able to run SU, including but not limited to Postgres, outdated versions of Ruby, Ruby on Rails and other modules...

I have decided to record a screencast because I thought it was kind of funny to remember it again and also to make you all know about it. I did not include a voice track in the screencast because I didn't want to spend much time preparing the script.

You will also notice that there are some typos, translation errors, and some serious usability issues that should have been solved.

Well, I hope you enjoy it!

Google Treasure Hunt 2008

2008-05-23T15:36:00.010+01:00

Just some days ago I found out about Google Treasure Hunt 2008, a fun series of questions to exercise problem-solving skills regarding computer science, networking, and low-level UNIX trivia. I just solved the first two problems, and I will be posting my solutions below, so be please do not read if you still plan on solving them (**spoilers below**).

First problem
The first problem is about a robot and a rectangular grid (with variable dimensions). The robot starts in the top-left corner and must proceed to the bottom-right corner by moving only to the right or downwards (i.e, it cannot move back to the left or upwards). Our mission is to answer how many possible paths can the robot take given the dimensions of the grid.

After I solved the problem, I was curious for other solutions, and googled a bit. Interestingly, most people correctly found the relationship of this problem with the sequences obtained by the Pascal's Triangle. In fact, I couldn't remember this fact, so I tried a more "visual" and "computer science" oriented approach.

The first attempt was to code the algorithm for moving right/down until the robot reached the bottom-right corner for a 50x57 grid. I ran the program but I noticed my naive approach would take me an infinite time to get an answer because the program would never return from recursion...

For the second attempt, I realized the number of possible paths from the cell at [X1, Y1] to the goal cell could be expressed as a constant number: the sum of the paths to the right and downwards (number of paths from [X1 + 1, Y1] plus number of paths [X1, Y1+1]). For that purpose, I created a matrix where the results are stored when they are first calculated. If they are found already calculated, there is no need to proceed to the goal, we can just use that result and sum it to the current subtotal. This made the program result immediately, instead of taking infinite time even for very large grids. I submitted this result to the Google Treasure Hunt 2008 website, but it was not correct. I decided to debug the program and I found out that the subtotals integers were being overflowed, because the answers to the problem indeed involved big numbers that neither 32 nor 64 bit would be enough to hold them. To solve this issue, I used Matt McCutchen's C++ Big Integer Library and converted my "unsigned long long" (64 bit number) to a BigUnsigned object, so that I could deal with virtually unlimited precision integers capable of storing a large sum, which is the case of the robot in a maze. Google Treasure Hunt 2008 accepted my submission after this change.

Second problem

The second problem involved downloading a zip file containing directories and text files. Our mission can be described by the following steps:

Finding each file whose relative path name matches a certain pattern

Reading a certain line (e.g.: 1st,2nd,3rd,4th, ... depending on the pattern) which should hold a number in text format (not binary)

Sum each set of numbers for each pattern (e.g. sum all numbers in the 3rd line for all *foo*.pdf path names, sum all numbers in the 5th line for all *bar*.rtf path names)

Answer: The result of multiplying all sums together (i.e.: sum1 * sum2 * ... * sumN) for all N patterns

Well, I believe the second problem could just involve UNIX shell scripting, but I did not want to mess with complicated expressions, filters or pipes... I decided to take a different approach from the first problem, and writing the solution in the Ruby language, which is easy to code, read and understand, and combined it with the UNIX find command to search for files that match a certain pattern, so I didn't have to deal with that. I realised that searching for just "*foo*.pdf" files would not be enough because the "*foo*" pattern would not match directories as required, just filenames, so many files would be ignored with such call. A complete call would be find . -ipath "*foo*" -iname "*.pdf" so the command would retrieve both "foo/bar/x.pdf" and "bar/foo.pdf", not just the latter.

Code for the solutions

Problem 1

Save the file as robot.cpp, download and extract the bigint library to the same directory and compile the program with:
g++ -Wall robot.cpp bigint/BigInteger.o bigint/BigIntegerUtils.o bigint/BigUnsigned.o bigint/BigUnsignedInABase.o -I bigint -o robot. You can call the program as ./robot 50 57 for a 50x57 grid.


/**
 * Google Treasure Hunt 2008 - Question 1
 * by Mário Freitas (imkira at gmail dot com)
 */

// standard libraries
#include 
#include 

// support for big integers
#include "BigInteger.hh"
#include "BigIntegerUtils.hh"

typedef BigUnsigned Counter;

Counter **gMatrix;
long gNumMatrixColumns, gNumMatrixRows;

inline Counter move (int x, int y)
{
 // number of paths already calculated?
 if (gMatrix[x-1][y-1] != Counter(0))
 {
  // we don't need to calculate it again, we can return it
  return gMatrix[x-1][y-1];
 }

 // number of paths for each direction
 Counter lNumRightPaths = 0, lNumDownPaths = 0;
 
 // can it move right?
 if (x < gNumMatrixColumns)
 {
  lNumRightPaths = move(x+1, y);
 }
 
 // can it move down?
 if (y < gNumMatrixRows)
 {
  lNumDownPaths = move(x, y+1);
 }
 
 // remember this result for the following iterations
 gMatrix[x-1][y-1] = lNumRightPaths + lNumDownPaths;
 
 // and return it
 return gMatrix[x-1][y-1];
}

int main (int argc, char *argv[])
{
 // correct command line syntax?
 if (argc != 3)
 {
  printf("Usage:  \n");
  exit(1);
 }
 
 // read number of columns and rows
 gNumMatrixColumns = strtol(argv[1], (char **)NULL, 10);
 gNumMatrixRows = strtol(argv[2], (char **)NULL, 10);
 
 // correct number of columns and rows?
 if ((gNumMatrixColumns <= 0) || (gNumMatrixRows <= 0))
 {
  printf("Invalid number of columns or rows\n");
  exit(1);
 }
 
 // create the matrix
 gMatrix = new Counter*[gNumMatrixColumns];
 for (int i = 0; i < gNumMatrixColumns; ++i)
 {
  // the default constructor should set the numbers to 0
  gMatrix[i] = new Counter[gNumMatrixRows];
 }
 
 // there is only one path from the goal cell to itself (i.e, by not moving)
 // this is used as the first stopping point for the recursive algorithm
 gMatrix[gNumMatrixColumns-1][gNumMatrixRows-1] = 1;
 
 // start at 1,1, move towards the goal and print the number of paths
 std::cout << move(1, 1) << std::endl;
 
 // destroy the matrix
 for (int i = 0; i < gNumMatrixColumns; ++i)
 {
  delete[] gMatrix[i];
 }
 delete[] gMatrix;
 
 exit(0);
}

Problem 2

Save the file as filesums.rb inside the directory that is created after extracting the zip file you downloaded from Google Treasure Hunt 2008. Change the sum_patterns code structure to reflect the patterns and line numbers for the problem in question. Run the program by calling ruby ./filesums.rb


#! /usr/bin/ruby
# Google Treasure Hunt 2008 - Question 2
# by Mário Freitas (imkira at gmail dot com)

# list of patterns:
# => line: the line number where to obtain the sum
# => find_file_pattern: the find command syntax that retrieves a list of files matching a pattern
sum_patterns = [
  { :line => 3, :find_file_pattern => 'find . -ipath "*foo*" -iname "*.pdf"' },
  { :line => 5, :find_file_pattern => 'find . -ipath "*zzz*" -iname "*.rtf"' }
]

# the product is initialized to 1
sums_product = 1

# iterate each file pattern
sum_patterns.each do |sum_pattern|
  # sum for current file pattern is initialized to 0
  current_sum = 0
  
  # find the list of files that match the current file pattern
  IO.popen(sum_pattern[:find_file_pattern]) do |pipe|
    
    # read the list of files that match the current file pattern
    file_paths = pipe.readlines
    
    # iterate each file
    file_paths.each do |file_path|
      # read the line where the sum is stored
      some_number = IO.readlines(file_path.chomp)[sum_pattern[:line] - 1]
      
      # increment the sum unless the line did not exist
      current_sum += some_number.to_i unless some_number.nil?
    end
  end
  
  sums_product *= current_sum
end

puts "The product of sums is #{sums_product}"

Master Thesis on Visualisation Paradigms for 3D Map-Based Mobile Services

2008-05-04T15:19:00.003+01:00

Right now, I'm partially undergoing supervised practical training at NDrive Navigation Systems, SA, and simultaneously writing my Master's Thesis with this title.

The main goal of my thesis is to find a theoretical explanation to what should be the best visualisation paradigm for 3D map-based mobile maps. There are many works and surveys about this and that aspect, but there are no general theories that unify all visualisation aspects involved in all kinds of tasks maps are used for such as navigation and exploration.

I'm also developing a prototype to materialise the concepts and ideas that will support my theory for 3D map-based mobile maps. The prototype runs on UNIX, Symbian OS and PocketPC/WinCE platforms using OpenGL ES 1.1 for the graphics API. I believe it will be a breakthrough in the navigation systems industry. I have to say the results are looking very promising and I'm very excited with it, although I cannot disclose anything for the time being :)

It's kind of unfortunate that I only have 20 weeks to do everything alone (writing the thesis, making the prototype, an other paperwork). I wish I had more time for this...

Yahoo will be Microsoft's

2008-02-21T09:25:00.004Z

This is my prediction. I've been thinking about this for quite a long time, and I have enough confidence to predict that Yahoo will accept Microsoft's proposal. Why? So much has already been told out there - in many of the most highly respectable sites on the Internet and even newspapers all over the world - whose main ideas are completely opposite to each other, and therefore I have a theory of my own about the outcome of this "billion dollar game".
Yahoo is doing like Oh come on Microsoft... you have a great chance to take us over and you won't like Google screwing us all... Maybe I should show you some signs of being interested on some "News Corp" and get a higher bid from you... Come on... I will start saying my employees will fear of being fired and dislike your proposal... I even did my best to raise our stock price while yours was dropping...

Seriously... it's a game between both companies. I've never heard so much about Yahoo these past 2 months... I bet many kids out there never even heard about Yahoo in the first place, since we're all so much used to Google anyway... Google takes pride in what they do and I don't believe they really need Yahoo so much... Microsoft has a golden chance to enter this new market...
More updates are sure to come!

Update (22 Feb, 2008):
Bill Gates made recently the following statements: "We have a strategy for competing in the search space that Google dominates today, that we'll pursue that we had before we made the Yahoo offer, and that we can pursue without that. It involves breakthrough engineering. We think that the combination with Yahoo would accelerate things in a very exciting way, because they do have great engineers, they have done a lot of great work. So, if you combine their work and our work, the speed at which you can innovate and get things done is just dramatically more rapid. So, it's really about the people there that want to join in and create a better search, better portal for a very broad set of customers. That's the vision that's behind saying, hey, wouldn't this be a great combination."
Does this support my opinion that they need each other as they share a common vision and ideologies, and a same wish to fight Google "threat"?

Blu-ray did it?

2008-01-06T17:41:00.001Z

The first time I heard about Blu-ray was from Sony. 2 or 3 years ago, I first heard them trying to "sell" the world a new format for high definition video, during the early stages of the Playstation 3's inception, while marketing their Blu-ray players. At the same time, Toshiba's HD DVD format looked more attractive to most people and even companies.
Although I'm still uncertain if the format "war" is already over or not, as of the 4th of January 2008, Sony seems to have won the competition after Warner Bros' public announcement: the company will drop support for HD DVD in favor or Blu-ray. If all the other major film producers follow Warner Bros' steps, in favor of a more globalized/generalized format, what will Toshiba do?
Can we say this war is over?

Update (08 Jan, 2008):

It was surprising for me how quickly this happened, but as of today Paramount Pictures, another major film production company, announced in the Financial Times that it is "poised to drop support of the HD DVD", in favor of the Blu-ray format, 4 days after Warner Bros announced their decision. It's unquestionable that Paramount Pictures made up their mind, in order to compete in the market with the same standards, even after once having signed an exclusivity agreement with the HD-DVD consortium, dropping Blu-Ray format.
More updates are sure to come!

Update (10 Jan, 2008):
According to Variety, it seems that Universal's exclusivity contract to backing HD-DVD format has ended. This and the fact that Paramount had found a clause in their contract with the HD-DVD consortium that allows them to escape the exclusivity obligation, could mean that the outcome of the "high definition video format war" may be already as good as over, since the Blu-ray backers are already too much and too powerful.

Update (17 Feb, 2008):
The death of HD-DVD was made official, after Wal-Mart decided it would no longer carry HD-DVD media. Although it seems that the winner of this "battle" was Sony, it is still questionable wether Blu-Ray will be successful or not...

Recruiting processes for internships at Portugal

2008-01-04T22:15:00.000Z

I don't know much about the rest of the world concerning internships for university students (though I'm a bit curious about it) but here at Europe, and Portugal in particular, most (?) "integrated master" programmes in Engineering specify a requirement for students before they can get their master's degree: to write a thesis or to apply to a company/organization's project and make an internship. When taking the latter into consideration, the "funny" part comes when the companies implement their respective recruiting process, in order to recruit students for internships. That's what I'm going to talk about, here, after what I've experienced, and after what I've seen happening with friends and colleagues of mine.
Some of the things that happened were simply ridiculous, others ironic, most of them just regular, and just one of them I can call it simply "splendid". Obviously, I will not spoil any companies' names here, but rather draw out some conclusions and personal opinions about the maturity and efficiency of the recruiting processes and also take the companies' reputation into account.
All started a month before (If I'm not mistaken) the list of projects for internships came out, when there were already a couple of companies that were trying to recruit students for internship programmes. From the beginning, the first of those companies was very professional: they sent several emails to students, made phone calls, sent letters, offered flight tickets to Lisbon and payed lodgings expenses for students who went there to apply for an exam, in order to be able to join the internship programme of that company. The students that couldn't pass the test also heard the "why" and "what could be better" from the persons who interviewed them. I admit this was one of the companies that was highly regarded as very professional, and was far much better than my expectations. At the same time, there was also a huge company (also as in famous) whose recruiting process standards and maturity levels didn't live up too much for my expectations: first they didn't personally contact the students to announce themselves like "We're from _company here_"; second, they made their recruiting process solely based on the students' resumes, this means no interviews, no tests, nothing; and, finally, they didn't spend 15 minutes writing an email to the students who were not selected. Absolutely ridiculous. The last one of the companies that started recruiting a little before the lists came out, made a big show off at the presentation to the students, as it is regarded as a very powerful international company. Students were happy to think they had the chance to apply for that company, but that company made a big mistake in my opinion: they pressed the students too much. They demanded a YES/NO from the students who were selected by them and asked them to immediately start working 1 month before the internship is supposed to initiate, when students are preparing for exams. To the students who were refused, they sent a poorly written email stating something like "I'm sorry you were not huuuuh.... selected. Sincerely, _signature here_". The students asked them for a delay, but the company said that they were going on Christmas vacations and they couldn't wait any longer (1 week before the lists with all the companies came out). Most of the students said no, and few said yes. The 3rd of January, 2008 I found out they are still looking for students. After watching most of my friends saying "NO", who happen to be great students and very competent in my opinion, I doubt that this "technique" that the company enforced had any positive effect at all! Guess what? Most of those students already selected the company where they're going to work, which does not have the same reputation but shows much more expertise than these so called "big international companies". There were some companies who sent emails to the students stating something like "You'll have to be present at the interview at 9 o'clock AM at _Cú-de-Judas_" instead of asking them if that's fine for them by phone, since email may not always be the fastest way to contact someone during the Christmas' and New Year's period. I don't know the best equivalent expression for "Cú-de-Judas" (in Portuguese) but it's like a place/location no one ever heard of, not even the postman knows where it is (as in far and unknown)!
All of this just to say that (just my opinion), from what I could experience, the "big" and "famous" factors for companies do not actually mean they employ a professional recruiting process. It's not a matter of 1+1=2.

"The Top 10 Reasons:  The Ruby Programming Language : Sucks!"

2008-01-04T00:25:00.000Z

Today, while I was surfing the web, I came across one of the most interesting presentations I ever found, as far as I can remember (don't trust my memory, please). Not just because it's about the Ruby programming language, which I really like very much, but also due to the design and sarcasm that was put into the presentation.
The presentation is from RubyConf 2003, by Yukihiro Matsumoto (a.k.a "Matz") - the creator of Ruby - and can be found at slideshare:

| View | Upload your own

"Transfer time is less than 109 minutes with a 28.8 modem"

2007-12-15T21:04:00.000Z

This was the message I was presented with, when I was sending a file to a friend of mine through Microsoft Messenger (v6.0.3 for Mac). This kind of messages is what I consider to be an interesting point of discussion about how interfaces are designed and often forgotten.
Of course this kind of message was always there, either in this application or in another, but the fact that I never payed too much attention to it makes me think that this kind of message was never relevant in the first place (at least for me). It would be considerably more interesting if the information was appropriate and adapted to the current situation, i.e., if it wants to go further and guess how much time it will take to perform a file transfer, at least should do it by using any of the following strategies (in my opinion):

"Learning" the connection speed from past transfers;

Simply calculating the speed based on connection settings specified by the user (like many video/audio streaming or P2P software);

"Asking" the operating system how fast is the connection speed;

By giving some sort of estimation using a connection speed as a base for comparison.

Messenger decided to follow the last option, and unfortunately either the persons who did it, already understood how useful that message was that they even forgot it is still there... or they still use 28.8 modems in 2007...

Of course this was only a starting point of discussion, and many follow this example. There are many software applications nowadays that are very feature-rich but so feature-fat that developers often forget about the user interface designing challenges and issues. Developers often focus on how their software is so feature-rich that if they applied a GUI profiler to analyze the user interaction with their software, like web developers do with web loggers, they would notice how many mistakes are performed and how much (big) the part of the software that is completely unused due to the lack of interest and effort on how interfaces are designed.
Some people say software should be feature-rich, if it is to be useful; others say that it should be simple, and easy to use; and others, like myself, think that it should be a mix of both worlds: it should be feature-rich, yet hiding all that is unnecessary for the current condition of use.

Diabetes classification

2007-12-09T23:10:00.000Z

The purpose of my current assignment at university is to correctly find an automatic way to perform a diagnosis based on some patient attributes and test results. The field of Knowledge Discovery and Data Mining has always fascinated me namely the challenges that are imposed to us when we decide to take an analysis like this first of mine.
The diagnosis is about Diabetes Mellitus, a common disease which affects millions of people in the whole world. Much is already known about it and much is already scientifically documented by the World Health Organization, so there's no big deal what we are to discover except the fun we get by looking at the results.

The most interesting rule I got because of its simplicity, and the one I would like to share with you, may be taken as a "warning" (or a joke if you wish) and I can only speculate if the rule is true or not. The rule states the following:
If your Body Mass Index (BMI in SI units) is higher than 27.3 and you're at least 29 then you are diabetes positive.

For reference, the formula for BMI is simply to divide (your weight (kg)) for your (height (m) raised to the power of 2)). For instance, if you are 1.7m and 65kg the result should be approximately 22.49.
Additionally, the table that maps ranges to categories is the following:

Category - BMI range
Starvation- less than 15
Underweight - from 15 to 18.5
Normal - from 18.5 to 25
Overweight - from 25 to 30
Obese - from 30 to 40
Morbidly Obese - greater than 40

Of course this rule is very simple, and you shouldn't take it seriously, of course.
It is interesting however that it yielded an accuracy of 70% in my data set and the only thing I can speculate is that it may be revelatory of a pre-diabetic state or even a natural tendency for most (?) patients.

24 hours Web Development on Rails

2007-11-19T22:57:00.000Z

I'm currently attending the Masters Degree in Informatics and Computing Engineering at FEUP and there's an amazing thing (NOT really now that I think about it again...) that I have to do preferably until the 23th of this month: developing a so called "home page".
I'm going to use the Ruby on Rails' Agile Web Development approach for the time being and I'll try to get everything up until there... if not, then I will use my trump card, which in portuguese language would be called "desenrascanço". I would really like to be able to translate this word but I don't really don't know that... sorry :) I already have something for the web page like the visual design, so... still much work left to do :)
More updates, about my crusade against time dealing with Rails and making a web page in 24 hours, coming soon...

Update at 22:06 (+1 day)
Well, it seems I got something working. One of the challenges was localization support, since I will be supporting 3 languages. I didn't spend too much time looking for rails plugins that provide localization support, but the ad hoc approach looked like a charm :) I pretty much used filters which select the correct language texts based on the current language.
Gotta go! I have a lot of localization still left to do!

DSAI 2007 - Software Development for Enhancing Accessibility and Fighting Info-exclusion

2007-11-09T23:27:00.000Z

Today, I had the best experience of my life about being aware of a software quality attribute, often forgotten or not simply taken into account when developing or planning software, called Accessibility. I would even subjectively speculate that, although Accessibility is a subgroup of a larger group called Usability, the former one is so vast and complex that may have a life of its own.

I was invited to participate in the organization of a workshop and its presentation to address the problem of Usability and Accessibility of mobile communication/navigation devices.

Instead of describing in full detail the ideas/issues that came from brainstorming and many of the concepts which I've acquired by participating in this event, I will just present a list of them along with a brief comment for each:

Always consider an inclusive-design approach, i.e., if you consider your software product will have to work with all kinds of people with disabilities (e.g., visual impaired, paraplegic, etc.), your product will naturally perform superb with all kinds of users, in terms of user interaction and experience;
Even people who don't have any kind of disabilities can be often considered temporarily in that situation (e.g., imagine the scenario where you're driving a car: normally you are naturally less able to talk and listen to the other passengers in the car; your vision orientation is often directed to the front; you cannot often take your feet off the car's brake or accelerator or remove one or two hands from the steering wheel... In this situation, what's the difference between a person without and a person with disabilities? Almost none);
Allow the user to "blindly" interact with the navigation device and the reality that is presented to him, without even having to physically touch the device, by using the screen or hardware buttons (e.g., using speech recognition to instruct the device or ask from it information about the reality);
When visual interaction is desired, it is of extreme importance to correctly but also easily have a matching between what can be observed from the reality and from the device display;
and many other ideas/problems, so I placed the presentation online, for you to enjoy it :)

The Big World Syndrome

2007-11-05T00:47:00.000Z

This is actually the worst title I could come up with for my first post in this blog.
Anyway, these past months I've been struggling to develop some decent and acceptable 3D computer graphics for embedded devices such as PDAs and PNAVs (Personal NAVigation devices) to be implemented in automobile navigation systems. Although there are not so many APIs available for this purpose (and even if there were!) there are so many challenges one has to be aware of and address, when developing applications for this kind of devices. For instance, there's no such thing as a FPU (Floating Point Unit) in most of them, which leaves us apparently with only one option, if we are to deal with high precision numbers for calculations: software floating point support. Unless you are OK with extremely low frame refresh rates, actually this is so slow that, in most cases, floating point software support is not an option. Other issues also arise from using this kind of devices, which are not relevant to this post or that I'm not (fortunately) still aware of.
The problem I've been addressing lately is what I like to call it The Big World Syndrome. If you want to get a big picture of this world, I invite you to close your eyes and imagine it for a while. Now open them... or you won't be able to read the rest of this post :) Now, think about this... If you are to represent everything in the world with an acceptable (high) precision, i.e. with an error not easily noticeable by the human eye, using very precision-limited numbers which are enough to represent the whole world but not to accommodate for all the calculations you have to perform until you reach the final result... you will eventually arrive at the same conclusion I did: that the world is to big to represent, using a "naive" approach. I'm still thinking about this issue, and I haven't still arrived at a final solution, but I'm addressing it using a little bit similar approach that has been followed by other projects like GeoVRML. I've been influenced by some of the ideas and came up with different ones. It basically defines a way to declare coordinates for the world, using not only one global coordinate system but many of them using relative coordinates. Assuming the fact that when you're looking closer at a piece of the world map, you want to view it in higher detail, using these local coordinate systems you will get much higher precision.
Of course this is just the tip of the iceberg since we will have to deal with some of the trade-offs involved.