Maximal sum in a triangle (Project Euler problem 67)

The problem description is here. For a given triangle you have to find the path with the maximum path. Given an input triangle :
3
7 4
2 4 6
9 5 9 3


We can compute the maximum sum path using 2 approaches:

Solution 1 : bottom-up. Build maximum path from bottom.  From the next-to-last row, up to the first, add the maximum corresponding sub-triangle. So the initial triangle becomes iteratively:


3
7    4
11 13 15
9    5    9  3


3
20 19
11 13 15
9    5    9  3


23
20 19
11 13 15
9    5    9  3

So the maximum sum is 23, and the maximum path 

3
7 4
2 4 6
9 5 9 3

Solution 2: same result is obtained with a top-down approach. Starting from the second row, compute the maximum-sum path to every element. So the initial triangle becomes iteratively:

3
10  7
2 4 6
9 5 9 3

3
10  7
12 14 13
9 5 9 3

3
10  7
12 14 13
21 19 23 16

We get same result for the maximum sum.

Simple python Implementation for the bottom-up solution:

def get_numbers():
    #lines = open("tri_small.txt", "r")    
    lines = open("tri.txt", "r")    
    
    listOfRows = []
    
    for line in lines:
        currRow = [int(x) for x in line.split()]
        listOfRows.append(currRow)
    
    return listOfRows
    
def solve():
    row_list = get_numbers()
    length = len(row_list)
    
    for i in xrange(length-2, -1, -1) :
        len_row = len(row_list[i])                   
        for j in range(0, len_row) :
            row_list[i][j] += max(row_list[i+1][j], row_list[i+1][j+1])
        
    print row_list[0]
    return 0

How to create an offline Ubuntu repository

Debmirror program  creates a local mirror of a Deban repository. A quick way to build an offline repository, save it to to an USB drive, and use it on a computer without internet access:

1. Install the application on a computer with internet:
   

   $ sudo apt-get install debmirror
   

2. Get the key for the repository and add it to the keyring. This can be done be importing it from a debian keyring:
   

   $ gpg --no-default-keyring --keyring /home/USER/.gnupg/trustedkeys.gpg --import /usr/share/keyrings/ubuntu-archive-keyring.gpg
   

3. Download the repository (approximate sizes for different repositories can be found in the man page):
   

   $ sudo debmirror -a i386 --no-source -s main -h ro.archive.ubuntu.com -d natty,natty-updates,natty-security -r /ubuntu --progress -e http mirror
   

   This mirrors section main of Ubuntu 11.04 Natty, updates and security.   All options are explained in the man page.
   
4. Mount usb device containing the repository to the other computer:
   

   $ mount /dev/sdb1 /mnt/usb
   

5. Create a backup copy of sources.list file and modify it:
   

   $ sudo cp /etc/apt/sources.list /etc/apt/sources.list.backup
   $ sudo vim /etc/apt/sources.list
   

   Delete all content and add just:
   

   deb file:///mnt/usb/mirror natty main
   deb file:///mnt/usb/mirror natty-updates main
   deb file:///mnt/usb/mirror natty-security main
   

6. Retrieve the new list of packages from the offline repository:
   

   $ sudo apt-get update
   

7. Upgrade the repository:
   

   $ sudo apt-get upgrade
   

8. Start installing packages....
   

Use OpenSSL to sign a document

OpenSSL is an open source cryptography  library with lots of useful functions. First part, how to sign a document using DSA signature scheme. 

1. Use dsaparam to generate DSA parameters(p, q, g), used to generate keys (possibly several keys):
   openssl dsaparam 1024 > dsaparam.pem
   
2. Generate key file (contains private and public key):
   openssl gendsa dsaparam.pem -out dsa_key.pem 
   Or, if the parameters p,q,g weren't precomputed (step 1):
   openssl dsaparam -noout -out dsa_key.pem -genkey 1024
   
3. Extract public key
   openssl.exe dsa -in dsa_key.pem -pubout -out dsa_pub_key.pem
   
4. Generate sha1 hash of a file.
   openssl dgst -sha1 foo.txt | awk '{print $2}' > foo.txt.sha1
   
5. Sign the hash
   openssl dgst -dss1 -sign dsa_key.pem text.txt.sha1 >foo.txt.sig
   
6. Verify the signature (using public key)
   openssl dgst -dss1 -verify dsa_pub_key.pem -signature foo.txt.sig foo.txt.sha1
   

Links:

1.  DSA key processing man page
2. OpenSSL command-line Howto

Creating shared libraries

• Intro
  Shared libraries are libraries that are loaded by programs when they start. To function properly, some conventions must be followed, related to library names and location:
1. A shared library has a special name called the ``soname'', with the prefix ``lib'', the name of the library, the phrase ``.so'', followed by a period and a version number that is incremented whenever the interface changes (libmyfunctions.so.1)
2. A fully-qualified soname is simply a symbolic link to the shared library's ``real name''. (libmyfunctions.so.1 -> libmyfunctions.so.1.0.1)
3. A shared library also has a ``real name'', which is the filename containing the actual library code. The real name adds to the soname a period, a minor number, another period, and the release number. The last period and release number are optional. The minor number and release number support configuration control by letting you know exactly what version(s) of the library are installed. ( libmyfunctions.so.1.0.1 )
• Creating and testing
  Files used are the same as in the static library example (add.c, mult.c, foo.c, myfunctions.h).
  

  $ gcc -fPIC -g -c -Wall add.c mult.c
  $ gcc -shared -Wl,-soname,libmyfunctions.so.1 -o libmyfunctions.so.1.0.1 add.o mult.o -lc
  $ ln -sf libmyfunctions.so.1.0.1 libmyfunctions.so
  $ ln -sf libmyfunctions.so.1.0.1 libmyfunctions.so.1
  $ export LD_LIBRARY_PATH=.:$LD_LIBRARY_PATH
  $ gcc -Wall -L. foo.c -lmyfunctions -o foo
  

  More about library placement on filesystem and  LD_LIBRARY_PATH environment variable here.
  
• Dynamic loading and un-loading of shared libraries
  Libraries can be loaded and unloaded during the execution of the program, creating a plugin architecture. It's important to understand the linkage and when/how to use extern "C" {...}. The C++ compiler mangles the name of C++ functions, but also the C variable names (info here). To list symbols names use nm utility (nm libmyfunctios.so). The source of the main program, that will be compiled with g++:
  foo.cpp:
  

  #include <stdio.h>
  #include <stdlib.h>
  #include <dlfcn.h>
  
  int main(int argc, char **argv) 
  {
     void *lib_handle;
     int (*fn)(int, int);
     
     char *error = NULL;
  
   int sum = 0;
  
     /* Load library */
     lib_handle = dlopen("libmyfunctions.so", RTLD_LAZY);
     if (!lib_handle) 
     {
        fprintf(stderr, "dlopen error: %s\n", dlerror());
        exit(1);
     }
  
     /* Load symbol */ 
     *(void **) (&fn) = dlsym(lib_handle, "add");
     /* see dlsym man page for this casting reason */
     if ((error = dlerror()) != NULL)  
     {
        fprintf(stderr, "dlsym error: %s\n", error);
        exit(1);
     }
  
     sum = (*fn)(0x11,0x22);
     printf("Sum: %d\n", sum);
  
     dlclose(lib_handle);
  
     return 0;
  }
  

  To compile and check it:
  

  $ g++ -rdynamic foo.cpp -ldl
  $ ./a.out
  

  More information on dlsym function and binding parameters used in dlopen(RTLD_LAZY, RTLD_GLOBAL and RTLD_NOW) on the man page.
  
• Dynamic library loading on windows
  
• Links:  
  
  • Shared Libraries
    
  • Static and dynamic libraries  
  • Name mangling
  • extern "C" linkage
  • dlsym man page

Create static library with GCC

1. Info
   Multiple object modules can be packed together into a single file called static library. It can be then passed to the linker. The linker builds the executable and copies the object modules from the library that are referenced by the program.
   
   The static library was developed to workaround the disadvantages of linking a whole dynamic library (a program would contain the code for the whole library (waste of space) and also when it's loaded into memory, the memory will contain code for all the function in the library(waste of memory)). With a static library, at link time the linker will copy only the object modules that are referenced by the application (This reduces the size of executable on disk and also on memory!)
   
2. Creating the library
   
   • Building the library from 2 initial source files:
     mult.c
     

     /* no bounds checking*/
     int mult(int a, int b) {
         return a*b;
     }
     

     add.c
     

     /* no bounds checking*/
     int add(int a, int b) {
         return a+b;
     }
     

     The 2 files are compiled with gcc -Wall -c add.c mult.c
     
     Library is created with ar rcs libmyfunctions.a add.o mult.o
     More details on parameters for the ar utility with man ar. Also, to list the content of the archive the command ar -t libmyfunctions.a is useful.
     
3. Linking
   
   • One way: gcc -o executable-name prog.c -L/path/to/library-directory -lmyfunctions
     
   • Or: gcc -o executable-name foo.c libmyfunctions.a
     
4. Testing
   foo.c
   

   #include <stdio.h>
   
   #include "myfunctions.h"
   
   int main() {
       printf("%d", add(1,3));
       
       return 0;
   }
   

   myfunctions.h
   

   #ifndef  __MYFUNCTIONS_H__
   #define  __MYFUNCTIONS_H__
   
   int add(int a, int b);
   int mult(int a, int b);
   
   #endif  /* MYFUNCTIONS_H */
   

   Compiling and running:
   

   $ gcc -o foo foo.c -L. -lmyfunctions
   $ ./foo
   

Move/add swap partition in Ubuntu

    To see the amount of existing swap space:

cat /proc/meminfo |grep -i swap

The output should be something like below. Full explanation of /proc/meminfo here.

SwapCached:  2244 kB
SwapTotal:  1052248 kB
SwapFree:  1043908 kB

 If you want to add a new swap partition, or delete the existing one and create another:

sudo swapoff -a
sudo mkswap /dev/sda3
#Edit fstab to add the UUID given by sudo blkid command. Then:
sudo swapon -a
#Check
swapon -s

References:

1. /proc/meminfo Explained 

Partition/Disk imaging with CloneZilla

    CloneZilla it's a free and open source software for partition imaging and disk cloning. Some features I liked:

1. It supports ext4 partitions
2. It's possible to do all the steps from command line (do imaging/restoring in unattended mode)
3. The image file can be located on the local disk, on external USB drive, on an ssh server, samba server or NFS server

The complete list of features and limitations on the site.

I used CloneZilla Live, a bootable Linux based on Debian, on an USB stick, using Method A. Till now I restored one Ubuntu ext4 partition and one NTFS with Windows. 

Tips (from faqs):

• Restore *.ntfs-img.* images into a partition manually:
  If the image is /home/partimag/YOURIMAGE/hda1.ntfs-img.aa, hda1.ntfs-img.ab..., and you want to restore the image to /dev/sda2.
  Before you do it, make sure the partition size of /dev/hda2 is equal to or larger than the original partition size of hda1 image.
  Then
  file /home/partimag/YOURIMAGE/hda1.ntfs-img.aa
  (to see it's gzip, bzip or lzop image). For gzip, then you can run
  cat /home/partimag/YOURIMAGE/hda1.ntfs-img.* | gzip -d -c | ntfsclone --restore-image -o /dev/hda2 -
  
• Restore an image of a partition to different partition:
  
  1. Make sure the destination partition is larger than the original one.
  2. Rename all the files /home/partimag/my-image-new/sda4* as /home/partimag/my-image-new/sda2* (the original was sda4, now it's sda2)
  3. Modify the content of /home/partimage/my-image-new/parts, replace sda4 with sda2.

ToDO:

• Test the unattended automated mode.