Number of paths in square grid (Project Euler problem 15)

Description of the problem (from here ):
Starting in the top left corner of a 22 grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a 2020 grid?


A: We can observe that:

•  every path has exactly 2*n moves, every move being either right or down (backtracking isn't allowed)
• in every 2*n path there are n moves down and n moves right. 

So, the number of all the distinct possibilities is the number of ways we can arrange n right moves from 2*n positions:

Number of digits in Fibonacci term (Project Euler problem 25)

Q: The question from the problem 25  is to find the first term in the Fibonacci sequence to contain 1000 digits. 


A: The answer comes from wiki: 


Since F_n is asymptotic to , the number of digits in  is asymptotic to . As a consequence, for every integer d > 1 there are either 4 or 5 Fibonacci numbers with d decimal digits.


So, 1000/0.2090 is approximately  4784, and the first Fibonacci term with 1000 digits is the 4782th term.

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