Project Euler 5 by Exhaustion in Python

30 June, 2009

Here is my solution to the 5th problem of Project Euler, solved via exhaustion in Python. Please note that I am aware that this problem is more preferably solved by factoring, but programatic exhaustion can be “fun.” With a few added print statements, a file around 3 GB large could be outputted from this 4 kilobyte program.

This program is Python 3-compatible. To make it compatible with earlier versions, remove the parentheses from the final print statement. It is released under the CC BY-SA (Creative Commons Attribution-ShareAlike license).

5. What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?

divisors = range(1, 21)
i = 1

while i:
\t for x in divisors:
\t\t if i % x != 0:
\t\t\t break

\t if i % x == 0 and x == 20:
\t\t answer = i
\t\t i = -1

\t i = i + 1


Top New Features in gedit 2.26

25 April, 2009

The three main new features in gedit 2.26, which came along with Ubuntu’s new Jaunty Jackalope release are a fullscreen mode (which I personally find slightly lacking – only the text view is shown) and better use of the status bar in terms of being able to select the syntax highlighting language and tab width very quickly. All of these are really nice additions to the program, and I’m glad to see that gedit’s becoming more and more full-featured.

A screenshot of the new gedit version, 2.26.

A screenshot of the new gedit version, 2.26.

Working with User Information in Linux

21 April, 2009

At certain times, it can be of advantage to have access to a user’s information, be it their home directory, their full name, their password, their system hardware, etc. This sort of information can be used to automatically customize programs according to the name of the user that started them or certain makeshift security methods.

Available User Information
If we take a look at /usr/include/pwd.h, we’ll see the following structure (with genuine comments):

/* The passwd structure.  */
struct passwd
  char *pw_name;        /* Username.  */
  char *pw_passwd;        /* Password.  */
  __uid_t pw_uid;        /* User ID.  */
  __gid_t pw_gid;        /* Group ID.  */
  char *pw_gecos;        /* Real name.  */
  char *pw_dir;            /* Home directory.  */
  char *pw_shell;        /* Shell program.  */

In Linux and most Unix systems, pw_gecos is the user’s real name, although you may encounter pw_comment every now and then.

Saying Hello
Let’s write a program that says “hello” to the user and tells them what their home directory is. We’ll need to include the following headers:

#include <sys/types.h>    // defines special types
#include <pwd.h>    // defines the passwd structure
#include <stdio.h>    // standard I/O

Now, let’s write the main function and define some basic variables:

int main ()
    uid_t uid = getuid();
    struct passwd *user_info;
    user_info = getpwuid(uid);

The uid_t type was defined in <sys/types.h> and getuid() is defined in unistd.h. This function is declared as uid_t getuid(void); and it returns the user identity (UID) of the user that started the process.geteuid() can be use to return the user’s effective identity (EUID – the user’s second UID that defines what resources processes begun by the user has permission to access. [1 We then create a pointer to the passwd structure to be able to access the members denoted above.

The getpwuid() method is defined in <pwd.h> and gets the password file entry given a certain UID – in this case, that of the user that started the process. A password entry can also be returned based on a user’s login name; in this case, getpwnam(const char *name) is used.

Now, do the following to get the user’s real name and their home directory:

    printf("Hello, %s!\n", user_info->pw_gecos);
    printf("Your home directory is %s.\n", user_info->pw_dir);

Don’t forget the -> notation. It is very common in certain frameworks, most notably Qt. Remember that a->b is equivalent to (*a).b .

We can now wrap up the program and compile it.

    return 0;

Here are two different results:

$ ./a.out
Hello, Patrick Braga!
Your home directory is /home/patrick.

# ./a.out
Hello, root!
Your home directory is /root.

Getting System Information

Sometimes, especially in applications that include networking capabilities, it is useful to know the name of the OS a user is running, the release, and the version. One can also find out the name of the host and the type of hardware it’s running on (i386, i686, etc). With this information, an application can be optimized to run more properly on the specified OS or on the specified hardware type.

#include <unistd.h>
#include <sys/utsname.h>

The <unistd.h> file includes two important functions: int gethostname (char *name, size_t namelen) and long gethostid(void). <sys/utsname.h> includes the uname function and the returned utsname structure.

Here are the most important members of the utsname struct. with original comments intact:

/* Structure describing the system and machine.  */
struct utsname
    /* Name of the implementation of the operating system.  */
    char sysname[_UTSNAME_SYSNAME_LENGTH];

    /* Name of this node on the network.  */
    char nodename[_UTSNAME_NODENAME_LENGTH];

    /* Current release level of this implementation.  */
    char release[_UTSNAME_RELEASE_LENGTH];

    /* Current version level of this release.  */
    char version[_UTSNAME_VERSION_LENGTH];

    /* Name of the hardware type the system is running on.  */
    char machine[_UTSNAME_MACHINE_LENGTH];

    // ...

Let’s expand the above program to include the following statements (don’t forget to include the necessary headers):

    struct utsname uts;
    uname(&uts); // this is the function that returns the uts struct

    printf("Your computer is running %s on %s hardware.\n",
        uts.sysname, uts.machine);
    printf("You are currently running kernel v%s.\n", uts.release);

Here are two different results:

$ ./a.out
Hello, Patrick Braga!
Your home directory is /home/patrick.
Your computer is running Linux on i686 hardware.
You are currently running kernel v2.6.27.21-170.2.56.fc10.i686.

# ./a.out
Hello, root!
Your home directory is /root.
Your computer is running Linux on i686 hardware.
You are currently running kernel v2.6.27.21-170.2.56.fc10.i686.

Note that the system and hardware information remain intact throughout the users – the user-specific information remains the same.

Using Finger

It’s great to be able to access this information in a C program, but what about in a shell script, remotely logged into a shell, or whenever you need it quickly from the command line? The finger command allows us to do that. There are four options for finger:

  1. -s displays the user’s login name, real name, idl and login times, office location, and office phone numbers.
  2. -l (default) displays everything shown in -s and any information in certain hidden files in the user’s home directory
  3. -p displays -l information without information from said certain hidden files in ~/
  4. -m prevents matching user names to their login names

The mentioned hidden files are (in the home directory ~/) .nofinger (denies the user’s existence to requests outside the local host), .project (a one-line file of whatever project the user is working on), .plan (a multi-line file of the user’s plan of things to do), and .pgkey. Remember, in Unix systems, it’s perfectly all right that files carry no extension.

Needless to say, the possibilities for using this sort of information are vast, from making a user’s experience more enjoyable to fine-tuning an application’s services to fit the user’s hardware.

How system() Works

20 April, 2009
#import <stdlib.h>


You’ve probably used or heard of the system() function. How it works is actually quite simple. Although I doubt the following code is safer than anything the Clib authors could write (they have many more years of experience than I do), it’s an interesting example of how system() works and how to use forked child processes in an application.

While you can continue to safely use system(), using the following fork/exec combination allows you to have a finer degree of control over the child process’ input and output, as well as the shell it’s run in (thanks to LordFrith for this information).

Before trying out the following code, make sure you have at least a basic handle on Linux processes.

What system() Does

This is what system() essentially does:

  1. fork the existing process into a child process
  2. override the child process with the desired command

You should already know how to do the first step (if you don’t, see the above link) – something like this:

     pid_t child_process;
     child_process = fork ();

Overriding a Process With Another

So, onto the second step. To override a process with another, you simply need to use one of the exec functions. If you use one of these in the parent process, the whole process will be stopped and overriden with the other designated process. Forking a child process before using an exec function allows the original program to continue running.

#include <unistd.h>

I find the most useful exec functions are execl and execv. You can check the header for more of these functions (execlp, execle, execvp, etc), but here are the declarations for those two:

int execl(const char *path, const char *arg0, ..., (char*)0);
int execv(const char *path, char *const argv[]);

If we wanted to use one of these functions to list the root directory, we could do it either of the following ways:

     execl("/bin/ls", "ls", "/", 0);

     char *const ls_argv[] = {"ls", "/", 0);
     execv ("/bin/ls", ls_argv);

Execv is more useful if you plan on reusing certain arguments (speaking of which, don’t forget to include a program name at index 0 of your array!)

Writing an nsystem() Function

Let’s try to replicate system() in terms of what it can do. Let’s call it nsystem (for “new system()”). Start off with including all the needed headers and writing a function declaration:

#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>

void nsystem (char *path, char *args[])

Fork a child process:

  pid_t child_pid = fork ();

Now, add a check to make sure we replace the current process only if the current process is a child:

  if ((int)child_pid == 0)

Note how the if statement checks if the child’s PID is 0. This because when the child is forked, it is the currently running process. It does not have a child of its own (hence no PID). Replace the child process with whatever the user calls if and only if it is the child process that is being run (put this in place of the commented ellipsis with this):

     execv (path, args);

Now, let’s embed the nsystem function in a real program to make sure it works:

int main (int argc, char *argv[])
    char *path = "/bin/ls";
    char *args[] = {"ls", "/", 0};

    nsystem (path, args);
    return 0;

Here’s the output after compiling:

$ ./a.out
bin   dev  home  lost+found  mnt  proc    sbin     srv  tmp  var
boot  etc  lib     media         opt  root    selinux  sys  usr

If wanted, the program could even be further extended to allow the user to run a command, or it could be implemented within another application to have a finer degree of control over overrun child processes.

Waiting on Child Processes

A big problem with the above example is that the parent process doesn’t wait on the child process. Things can get really messy if the parent process finishes before its child. You may have noticed at times that you would have needed to press return before the program ended, sometimes the ls command printed things out oddly, and sometimes it ran just like it should. This is because the parent process didn’t wait for the child process to finish. At times they exit together, and at times one may exit before another, and one could even exit incorrectly. Let’s fix up the code a bit so it runs correctly every time.

It’s very simple. Simply replace the else statement with this:

else if ((int) getpid != 0)
    int status_value;
    child_pid = wait (&status_value);

There is one major question that needs to be answered about the above code: why did we declare a “useless” integer? The status_value integer can be used, if wanted, in extending the function to return the child process’ exit value. The macros to do that are defined in <sys/wait.h> and are WIFEXITED(status_value), WEXITSTATUS(status_value), WIFSIGNALED(status_value), WTERMSIG(status_value), WIFSTOPPED(status_value), and WSTOPSIG(status_value).

Understanding Linux Processes

19 April, 2009

For more on waiting on child processes and using the exec functions, see the next article, How system() works.

In Linux and other Unix systems, a process consists of code (usually loaded as read-only memory), data, and memory occupied by said data that has been allocated a process identifier (PID) and that can reference certain memory locations known as “address spaces.” Such POSIX process may contain various programs which, in turn, may be made up of various threads. Allocated PIDs are usually numbered over 2 (the PID 1 is typically reserved for the init process).

Let’s retake that running code normally is loaded as read-only memory to avoid writing over the code. This means that, for example, given any C function, various different processes can call it safely.

The ps Command
Now, let’s take a look at the ps (“process snapshot”) command. The following are probably the most-used options used:

ps -ef (every process, full format)
ps ax    (every process with a status code)

Here’s an excerpt of what ps -ef gave me:

root         1     0  0 16:22 ?        00:00:00 /sbin/init
patrick   4040  4011  0 17:09 pts/1    00:00:00 vi
patrick   4042  3827  0 17:09 pts/2    00:00:00 bash
patrick   4076  4042  0 17:09 pts/2    00:00:00 ps -ef

UID stands for user ID (remember, Unix systems are multiuser systems), not to be confused with UUID, or “unique ID.” CMD is the command that’s being run. STIME is the system time at which the process started. TIME is the CPU time, that is, the amount of time used by the process to process CPU instructions.

Now, here’s an excerpt of my ps ax output:

    1 ?        Ss     0:00 /sbin/init
 4040 pts/1    S+     0:00 vi
 4042 pts/2    Ss     0:00 bash
 4083 pts/2    R+     0:00 ps ax

Notice the Status column. The following are the most common STAT codes displayed by ps:
S    Sleeping (waiting for input)
s    Session leader
R    Running
l    Multithreaded
T    Stopped
D    Waiting for input/output to complete.

Killing (or Terminating) a Process
To kill a process using its PID, use the kill command. To kill one via its command name, use either killall or pkill. For example, let’s kill the running Vi process as shown above. There are two simple ways to do this:

kill 4040
killall vi

Both yield the same result; Vi prints out the following:
Vim: Caught deadly signal TERM

If you want to kill all processes being run by a certain user group, use killall -g [group name]. Be careful when using killall, though. On certain systems, it does just that – kill all processes. However, with pkill, it may kill all processes that have the passed argument as a substring on certain systems.

Using getpid and fork
If you want to be able to mess around with an application’s own process, the most important functions are getpid and fork. The getpid function returns the running PID, and fork duplicates the currently running process as a child process. Both are defined in unistd.h and important types related to processes are defined in sys/types.h .

Here’s an example program that clones itself into a child process for five seconds (written in a serif font, just like Stroustrup recommends it).

#include <stdio.h>
#include <unistd.h>
#include <sys/types.h>

int main(int argc, char *argv[])
     pid_t child_pid;
     child_pid = fork ();
     printf ("Parent PID: %d\nChild PID:%d\n", (int) getpid(), (int) child_pid);
     sleep (5);
     return 0;

Here’s a sample output of the program and its corresponding ps ax entries:

$ ./a.out
Parent PID: 2770
Child PID:0
Parent PID: 2769
Child PID:2770

$ ps ax
 2769 pts/0    S+     0:00 ./a.out
 2770 pts/0    S+     0:00 ./a.out

Note how there are two outputs. The first one is the child process’ output and the latter is the parent process’ output.(Remember, in order to have enough time to check the processes’ statuses, add sleep(5); right after the printf call.)

Snow Leopard Will Be Seen at WWDC

27 March, 2009
Apple’s Mac WWDC page gives it away that Snow Leopard and its technologies will take stage at WWDC. Quoting directly from the page,
Provide state-of-the-art media playback, capture, and manipulation of rich media with QuickTime X.
It is important to note that QuickTime X is a Snow Leopard (10.6)-only technology.

Picked up my Cocoa Book

1 March, 2009

Last night (29 February 2009) I went over to a local bookstore to pick up my long-awaited copy of “Cocoa Programming for Mac OS X” (3rd edition). The cover is really nice with multiple textures, but I was surprised at how the 3rd edition is just about as thick as the second edition. I ventured into the table of contents for comparison, and I found out that the following chapters were removed:

  • Using NSTextView
  • AppleScript
  • Creating Frameworks
  • GNUstep
  • Creating Interface Builder Palettes
I understand why the palettes and GNUstep chapters were removed (Interface Builder no longer uses Palettes and GNUstep is somewhat dormant at the moment). In return, a few other chapters were added, most notably on web services, Core Data, and Core Animation.
Of course, it’s not just chapters added that counts – a lot of new things have been written, new challenges have been added, and it really seems like a much better book.