Multiply

def multiply (x, y):
 if(y < 0 and x > 0):
  return -multiply(x, -y) 
 if(x < 0 and y > 0):
  return -multiply(-x, y)
 if(x < 0 and y < 0):
  return multiply(-x, -y)
 if(y == 0 or x == 0):
  return 0 
 else:
  return x + multiply(x, y - 1)

The Fibonnaci Series

Here we have a relatively fast, though memory intensive, program to find the N^th Fibonnaci Number. This uses Prof. Edsgar W Dijkstra's algorithm as described in this paper. In brief the idea is:

F(2n-1) = F(n-1)² + F(n)²
F(2n) = ( 2 F(n-1) + F(n) ) F(n)

Without further ado, here we are:

# Program to compute the Nth term of the Fibonacci series.
# Rohit Krishna Kumar
# A big list to store the numbers we have already generated
fib_list = [None] * 10**5

def fib(n):
    if(n == 1):
        return 1
    if(n == 0):
        return 0
    if(fib_list[n] != None):
        return fib_list[n]
    # By definition: Fib(n) = Fib(n-1) + Fib(n-2)            
    if(fib_list[n-1] != None and fib_list[n-2] != None):
        fib_list[n] = fib_list[n-1] + fib_list[n-2]
        return fib_list[n]
    # In Honour Of Fibonnaci. Dijikstra's method.
    if(n % 2 == 0):
        fib_list[n] = (2 * fib((n/2) -1 ) + fib(n/2))*fib(n/2)
        return fib_list[n]
    else:        
        fib_list[n] = ((fib(((n+1)/2) - 1))**2 + (fib((n+1)/2))**2)
        return fib_list[n]

Reversing lists

There is more than one way to do a thing, and more than one language :)

Program 1
Language: Python

def reverse(l):
    if(l==[]):
        return []
    else:
        return (reverse(l[1:])+list(a[0]))

Program 2
Language: Python

def reverse(l):
    return l[::-1]

Program 3
Language: Python

a=range(10)
a.reverse()

Program 4
Language: elisp (!!)

(defun consx (l x)
  "like cons but first arg is a list"
  (if (eq l '())
      (list x)
    (cons (car l) (consx (cdr l) x))))

(defun reverse(l)
  "reverse a list"
  (if (eq l '())
      ()
    (consx (reverse (cdr l)) (car l))))

(reverse '(1 2 3))

The quest for the ninja monkey.

I rechristened the site name, in the hopes of reviving something which was lost. Behold for I give you the random permutation.
Language: Python

# Deutsche bank's online banking page uses a O(n^3) algorithm to generate a
# random character array.
# This is a O(n) way to do the same, for any array.

def randomPermute(array):
    import random
    for i in range(len(array)):
        randIndex=random.randint(i,len(array)-1)                               
        (array[i],array[randIndex])=(array[randIndex],array[i])
    return array

# Lets experiment with the english alphabet
import string
print randomPermute(list(string.ascii_letters[:26]))

Hello World Web Server

/* The Hello World web server. Type http://localhost:2001 in your
   web browser after running this program. */

#include <stdio.h>
#include <string.h>
#include <sys/types.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <arpa/inet.h>

#define SOURCE_PORT 2001 /* Use a large port number. */
#define SIZE 1024

/* This is used to initialize an address with a port */

void initaddr(struct sockaddr_in * s,char *hostname,int port) {
  s->sin_family=AF_INET;
  s->sin_port=htons(port);
  inet_aton(hostname,&s->sin_addr);
  memset(&s->sin_zero,0,8);
}

int main() {
  struct sockaddr_in source_addr,new_addr;
  int sockfd;
  int newfd;
  char message[SIZE];
  int sin_size=sizeof(struct sockaddr_in);
  sockfd=socket(PF_INET,SOCK_STREAM,0);
  initaddr(&source_addr,"127.0.0.1",SOURCE_PORT);
  bind(sockfd,(struct sockaddr *)&source_addr,sin_size);
  listen(sockfd,1);
  while(newfd=accept(sockfd,(struct sockaddr *)&new_addr,&sin_size)) {
    recv(newfd,message,SIZE,0);
    strcpy(message,"Hello world!!\n");
    send(newfd,message,strlen(message),0);
    close(newfd);
  }
  close(sockfd);
}

Multithreading

/* An attempt at multithreading using POSIX threads library. */
/* Pretty much useless */
/* Compile with gcc filename.c -lpthread */

#include <stdio.h&rt;
#include <pthread.h&rt;

int val=0;
int exited=0;

/* Takes input and displays the value of val. */
void *input_thread(void *ptr) {
  char ch='d';
  while(ch!='q') {
    scanf("%c",&ch);
    switch(ch) {
    case 'd':
      printf("Val:%d\n",val);
      break;
    case 'q':
      break;
    }
  }
  exited=1;   /* Should be kept under lock, but is not. */
}
/* Keeps on incrementing val */
void *compute_thread(void *ptr) {
  while(!exited) 
    val=(val+1)%0xffff;  /* Keep it low. This again should have been under lock. */
}
int main() {
  pthread_t i_thread,c_thread;
  pthread_create(&i_thread,NULL,input_thread,(void *)0);
  pthread_create(&c_thread,NULL,compute_thread,(void *)0);
  /* Wait for both threads to exit before exiting main */
  pthread_join(i_thread,NULL);
  pthread_join(c_thread,NULL);
  return 0;
}

Eating up all your memory

// Wasting my hate.
int main() {
  long double *x;
  while(1) 
    x=new long double;
}

Result:

Abort!
Exiting due to signal SIGABRT
Raised at eip=00005afe
eax=00092204 ebx=00000120 ecx=00000000 edx=00000000 esi=00000054 edi=000123a4
ebp=000922b0 esp=00092200 program=C:\DOCUME~1\ROXTAR~1.DEM\A.EXE
cs: sel=01a7  base=02980000  limit=2cf2ffff
ds: sel=01af  base=02980000  limit=2cf2ffff
es: sel=01af  base=02980000  limit=2cf2ffff
fs: sel=017f  base=0000e1b0  limit=0000ffff
gs: sel=01bf  base=00000000  limit=0010ffff
ss: sel=01af  base=02980000  limit=2cf2ffff
App stack: [000923a4..000123a4]  Exceptn stack: [00012304..000103c4]

Call frame traceback EIPs:
0x00005a24
0x00005afe
0x00004f2b
0x0000bae4
0x0000bb1e
0x0000b9cd
0x0000aeb3
0x000015fa
0x00004738

Windows ran out of virtual memory within 2 minutes of the run.

Anagram Checker

/* Program to check whether one string is a permutation of another.
   Google sample problem, Cochin October 2005. */
/* Author: Rohit Krishna Kumar */
/* Home page: http://www.geocities.com/rohitkkumar */

#include 
#include 
#define SIZE 10
int main() {
  char str1[SIZE],str2[SIZE];
  int len1,len2;
  int i,j,k;
  int flag=0;
  printf("Enter the first string: ");
  scanf("%s",str1);
  printf("Enter the second string: ");
  scanf("%s",str2);
  len1=strlen(str1);
  len2=strlen(str2);
  if(len1!=len2) {  /* Obviously */
    printf("Strings are not permutations of each other.\n");
    return 0;
  }
  /* This loop checks if each character in one string 
     is present in the other string. As soon as it finds 
     one character it deletes it from both the strings and
     continues. */
  for(i=0;i<len1;i++) {
    flag=0;
    for(j=0;j<len2;j++) {
      if(str1[i]==str2[j]) {
 for(k=i;k<len1;k++) /* Delete the character from str1 */
   str1[k]=str1[k+1];
 for(k=j;k<len2;k++) /* Delete the character from str2 */
   str2[k]=str2[k+1];
 len1--;   /* Decrease the length of both strings. */
 len2--;
 flag=1;
 i=0;
 j=0;
 break;
      }
    }
    if(!flag) {   /* One character in one string is not there
       in the other */
      printf("Strings are not permutations of each other.\n");
      return 1;
    }
  }
  printf("Strings are permutations of each other.\n");
}

Code to HTML

This python program replaces the special HTML characters (present in code) with their HTML codes. The listing below has been made from the program itself :)

print "Enter the file to read: "
name=raw_input()
in_file=file(name,"r")
buffer=in_file.read()
buffer=buffer.replace("&","&");
buffer=buffer.replace("\"",""");
buffer=buffer.replace("<","&lt;")
buffer=buffer.replace(">","&gt;")
out_file=file(name+".html","w+");
out_file.write(buffer);

My very own vector class

// A simple program to implement a *vector* like class which doubles its size
// whenever it is about to overflow.
// Inspired from Amortized time analysis. (although I still haven't understood
// what it is all about ;) )
// Author: Rohit Krishna Kumar
// Home page: http://www.geocities.com/rohitkkumar

#include 
using namespace std;
const int MAX=4;
template 
class Array {
  T *list;
  int max_size;
  int cur_size;
public:
  Array(void);
  void insert(T);
  T remove(void);
  void display(void);
  ~Array();
};

template 
Array::Array() {
  max_size=MAX;
  list=new T[max_size];
  cur_size=0;
}

// Inserts the element at the last position

template 
void Array :: insert(T val) {
  if(cur_size == max_size) {
    T *temp=new T[max_size*2]; // Allocate more memory
    max_size<<=1;  // Update the amount of memory allocated
    for(int i=0;i

T Array :: remove(void) { // Doesn't perform any deallocation
  if(cur_size!=0)
    return list[--cur_size];
  else 
    return -1;   // List empty
}

template  
void Array :: display(void) {
  for(int i=0;i<<<" ";
  cout<

Array :: ~Array() {
  delete[] list;
}

int main() {
  // Do a test run :)
  Array a;
  for(int i=0;i<1000000;i++)
    a.insert(i);
  for(int i=0;i<1000000;i++)
    cout<<<" ";
}