Ramin Rakhamimov

func_reverse_strings.c top

/*****************************************************************
 * func_reverse_string.c
 * 
 * Reverses the order of the command line arguments
 * using an in-place reverse algorithm
 *
 * OUTPUT:
 *    $ func_reverse_string hello world, is it a nice day?
 *    day? nice a it is world, hello
 *
 * Author:
 * Ramin Rakhamimov
 * ramin32 at gmail dot com
 * http://raminrakhamimov.com
 ****************************************************************/
#include <stdio.h>
#include <stdlib.h>

void swap(char **str1,char **str2){
    char *temp = *str1;
    *str1 = *str2;
    *str2  = temp;
}

void reverse_strings(char **strings,int num){
    int i;
    for(i=1;i<num/2+1;i++)
        swap(strings+i,strings+num-i);
    
}

print_all(char **strings,int num){
    int i;
    for(i=1;i<num;i++)
        printf("%s ",strings[i]);
    puts("");
}

int main(int argc,char **argv){
    if(argc <= 1 ){
        printf("Not enough arguments!\n");
        exit(1);
    }

    reverse_strings(argv,argc);

    print_all(argv,argc);
}

combinations.py top

##################################################################################
# combinations.py
#
# Description: Python implementation of the combinationtion algorithm using 
#              bitwise manipulation. Iterates through all bits up to 2^len(list), 
#              selecting elements with matching indeces to bits.
#
# Order complexity: O(n*2^n)
# 
# Usage:
#    $ python2 combinations.py abc
#
#    a
#    b
#    ab
#    c
#    ac
#    bc
#    abc
#
# Author:
# Ramin Rakhamimov
# http://raminrakhaimov.com
# ramin32 AT gmail DOT com
##################################################################################

import sys

def extract_elements(iterable, on_bits):
    return (v for i, v in enumerate(iterable) if 2**i & on_bits)

def combinations(iterable):
    bits = len(iterable) 
    for on_bits in xrange(2**bits):
        yield extract_elements(iterable, on_bits)
        
if __name__ == '__main__':
    for combination in combinations(sys.argv[1]):
        print ''.join(combination)

reverse_number.py top

####################################################
#!/usr/bin/env python
# Python implementation of reverse_number.c
# 
# Author:
# Ramin Rakhamimov
# ramin32 at gmail dot com
# http://raminrakhamimov.com
###################################################

import sys

def power_of_ten(n):
    power = 1;
    while(n):
        n = n/10
        power = power*10 
    return power/10

def reverse(n):
    reversed = 0
    while(n):
        reversed = reversed + ((n%10)* power_of_ten(n))
        n = n/10
    return reversed

print sys.argv[1]
print reverse(int(sys.argv[1]))

SimpleProducerConsumer.java top

/*******************************************************
 * SimplerProducerConsumer.java
 *
 * A simple consumer producer example, with very basic synchronization
 * methods.
 *
 *     OUTPUT:
 *     Producer put: 2276
 *     Consumer got: 2276
 *     Consumer got: 1376
 *     Producer put: 1376
 *     Producer put: 3882
 *     Consumer got: 3882
 *     Consumer got: 2387
 *     Producer put: 2387
 *     Consumer got: 1014
 *     Producer put: 1014
 *     And so on....
 *
 * Author:
 * Ramin Rakhamimov
 * ramin32 at gmail dot com
 * http://raminrakhamimov.com
 ******************************************************/ 
import java.util.Random;

public class SimpleProducerConsumer{
    static class Producer implements Runnable{
        private Service service;

        Producer(Service service){
            this.service = service;
        }
        public void run() {
            Random rand = new Random(System.currentTimeMillis());
            while(true){
                try {
                    Thread.sleep(100);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                int num = rand.nextInt(5000);
                while(!service.isEmpty());
                service.setValue(num);
                System.out.println("Producer put: " + num);

                
            }

        }
    }

    static class Consumer implements Runnable{
        private Service service;

        Consumer(Service service){
            this.service = service;
        }
        public void run() {
            while(true){
                try {
                    Thread.sleep(100);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                while(service.isEmpty());
                System.out.println("Consumer got: " + service.getValue());
            }

        }
    }

    public static class Service{
        int i;
        boolean empty = true;

        public void setValue(int i){
            this.i = i;
            empty = false;
        }
        public int getValue(){
            empty = true;
            return i;
        }

        public boolean isEmpty(){
            return empty;
        }
    }

    public static void main(String[] args){
        Service service = new Service();
        Thread consumerThread = new Thread(new Consumer(service));
        Thread producerThread = new Thread(new Producer(service));

        consumerThread.start();
        producerThread.start();
    }
}

longest_char_sequence.c++ top

/*******************************************************
 * longest_char_sequence.c++
 *
 * Determines the longest char sequence of an input string.
 * 
 * OUTPUT:
 *   [ramin@archlinux cpp]$ ./longest_char_sequence  abbcccccdde
 *   Max sequence: c
 *
 *
 * Author:
 * Ramin Rakhamimov
 * ramin32 at gmail dot com
 * http://raminrakhamimov.com
 ******************************************************/ 

#include <iostream>
#include <cstring>

int main(int argc, char *argv[])
{
    if(argc != 2)
        std::cerr << "Usage: " << argv[0] << " <char_sequence> \n";
    
    int size = strlen(argv[1]);

    char currentChar = argv[1][0];
    char currentCharSize = 1;
    int maxCharSize = currentCharSize;
    char maxChar = currentChar;
    for(int i = 1; i <= size; i++)
    {
        char ch = argv[1][i];
        if(ch != currentChar)
        {
            if(currentCharSize > maxCharSize)
            {
                maxChar = currentChar;
                maxCharSize = currentCharSize;
            }
            currentChar = ch;
            currentCharSize = 1;
        }
        else
            currentCharSize++;
    }

    std::cout << "Max sequence: " << maxChar << std::endl;
}

reverse_string.c top

/*******************************************************
 * reverse_string.c
 *
 * Reverses the first string given on the command line.
 *
 * Author:
 * Ramin Rakhamimov
 * ramin32 at gmail dot com
 * http://raminrakhamimov.com
 ******************************************************/ 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void swap(char *a,char *b) {
    char temp = *a;
    *a = *b;
    *b = temp;
}

char *reverse(char *str) {
    char *start = str;
    char *end = str + strlen(str)-1;

    while(start < end)
        swap(start++,end--);
    return str;
	
}
int main(int argc,char **argv) {

    if(argc != 2){
        printf("Usage %s <string>\n",argv[0]);
        exit(1);
    }
	
    char *input = argv[1];
    puts(reverse(input));
}
    




    

html5_canvas_pattern_animation.html top

<!DOCTYPE html>
<!----------------------------------------------

html5_canvas_pattern_animation.html

Animates a pattern drawing using html5 canvas.
This snippet could be used as an example for creating
the classic snake game.
 
Author:
Ramin Rakhamimov
ramin32 at gmail dot com
http://raminrakhamimov.com

------------------------------------------------>

<html lang="en">
    <head>
        <meta charset="utf-8">
        <meta http-equiv="Content-Type" content="text/html; charset=utf-8">

        <title>Canvas Animation</title>

        <style type="text/css">
            canvas { border: 2px solid black; }
            body { text-align: center; }
        </style>

        <script type="application/javascript">
            window.onload = function() 
            {
                var canvas = document.getElementById('rope-canvas');

                if (canvas && canvas.getContext) {
                    var context = canvas.getContext('2d');
                    if (context) {
                        context.lineWidth = 4;

                        function animate(context, x, y, xInc, yInc) 
                        {
                            context.strokeStyle = "#369";

                            context.beginPath();

                            context.moveTo(x, y);
                            x = x + xInc;
                            y = y + yInc;
                            context.lineTo(x, y);

                            context.stroke();
                            context.closePath();

                            if (x > canvas.width || x < 0)
                            {
                                xInc *= -1;
                            }
                            if (y > canvas.height || y < 0)
                            {
                                yInc *= -1;
                            }
                            window.setTimeout(function(){animate(context, x, y, xInc, yInc);}, 5);
                        }

                        animate(context, canvas.width/2, 0, 1, 1);

                    }
                }
            }
        </script>
    </head>
    <body>
        <canvas id="rope-canvas" height="300px" width="500px"></canvas>  
    </body>
</html>

count_sort.c top

/******************************************************************************
 * count_sort.c
 *
 * A C implementation of counting sort found in CLR (section 8.2, 2nd edition)
 * Note: Array sizes are stored in first index.
 *
 *      OUTPUT:
 *	ramin@desktop:~$ gcc count_sort.c && ./a.out 
 *	original array:
 *	9 2 3 4 3 2 2 4 5 1 3 4 
 *	c: 
 *	0 0 0 0 0 0 0 0 0 
 *	c with counts:
 *	1 3 3 3 1 0 0 0 1 
 *	c after processing:
 *	1 4 7 10 11 11 11 11 12 
 *	b sorted:
 *	1 2 2 2 3 3 3 4 4 4 5 9 
 *	
 * Author:
 * Ramin Rakhamimov
 * ramin32 at gmail dot com
 * http://raminrakhamimov.com
 *****************************************************************************/

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

int find_max(int *);
void print_array(char *, int *);
int* create_hash_table(int *);

int main(int argc, char** argv)
{
    int a[] = {-1111,9,2,3,4,3,2,2,4,5,1,3,4};
    a[0] = sizeof(a) / sizeof(int); 
    print_array("original array:", a);
    int *c = create_hash_table(a);
    print_array("c: ", c);
    int i;

    for(i = 1; i < size(a); i++)
        c[a[i]]++;
    print_array("c with counts:", c);
    for(i = 2; i < size(c); i++)
        c[i] = c[i] + c[i - 1];
    print_array("c after processing:", c);

    int *b = create_hash_table(c);

    for(i = 1; i < size(a); i++)
    {
        b[c[a[i]]] = a[i];
        c[a[i]]--;
    }
    print_array("b sorted:", b);

}

int size(int *a)
{
    return a[0];
}

void print_array(char *str, int a[])
{
    int i;
    puts(str);
    for(i = 1; i < size(a); i++)
        printf("%d ",a[i]);
    printf("\n");
}

int find_max(int a[])
{
    int max = a[1];
    int i;
    for(i = 2; i < size(a); i++)
        if(max < a[i])
            max = a[i];
    return max;
}

int *create_hash_table(int *a)
{
    int size = find_max(a) + 1; 
    int *result = malloc(sizeof(int) * size);
    result[0] = size;
    int i;
    for(i = 1; i < size; i++)
        result[i] = 0;
    return result;
}

perms.c++ top

/*******************************************************
 * perms.c++
 *
 * Returns a permutation of the first command line argument.
 * Uses boost shared_ptr and the STL.
 * 
 * OUTPUT:
 *      [ramin@home cpp]$ ./perms abc
 *      abc
 *      bac
 *      bca
 *      acb
 *      cab
 *      cba
 *      
 * Author:
 * Ramin Rakhamimov
 * ramin32 at gmail dot com
 * http://raminrakhamimov.com
 ******************************************************/ 

#include <iostream>
#include <vector>
#include <algorithm>
#include <boost/tr1/memory.hpp>

using std::vector;
using std::string;
using std::cout;
using std::cerr;
using std::tr1::shared_ptr;


typedef shared_ptr<vector<string> > string_vector;

string_vector perms(string input);
void println(string s) {cout << s << std::endl;}
string_vector insert_everywhere(string input, char ch);


int main(int argc, char *argv[])
{
    if(argc != 2)
    {
        std::cerr << "Usage: " << argv[0] << " <sequence>\n";
        abort();
    }

    string input(argv[1]);
    string_vector result = perms(input);
    for_each(result->begin(), result->end(), println);
}


string_vector perms(string input)
{

    string_vector result(new vector<string>());
    if(input.size() == 1)
    {
        result->push_back(input);
        return result;
    }

    char head = input[0];
    string tail = input.substr(1,input.size()-1);

    string_vector tail_perms = perms(tail);
    vector<string>::iterator it = tail_perms->begin();
    while(it != tail_perms->end())
    {
        string_vector char_inserted_string_vector = insert_everywhere(*it,head);
        result->insert(result->end(), char_inserted_string_vector->begin(), char_inserted_string_vector->end());
        it++;
    }
    return result;
}

string_vector insert_everywhere(string input, char ch)
{
    string_vector result( new vector<string>(input.size() + 1, input));
    for(int i = 0; i <= input.size(); i++)
        result->at(i).insert(i,sizeof(char), ch);
    return result;
}

bit_counter.c top

/***************************************************************
 * bit_counter.c
 *
 * Counts the number of bits that are on in a integer given
 * on the command line.
 *
 *   OUTPUT:
 *   ramin@debian:~/c_programs$ ./bit_counter 5
 *   5 has 2 bits turned on.
 *   ramin@debian:~/c_programs$ ./bit_counter 6
 *   6 has 2 bits turned on.
 *   ramin@debian:~/c_programs$ ./bit_counter 10
 *   10 has 2 bits turned on.
 *   ramin@debian:~/c_programs$ ./bit_counter 16
 *   16 has 1 bits turned on.
 *   ramin@debian:~/c_programs$ ./bit_counter 15
 *   15 has 4 bits turned on.
 *   ramin@debian:~/c_programs$ ./bit_counter 3
 *   3 has 2 bits turned on.
 * 
 * Author:
 * Ramin Rakhamimov
 * ramin32 at gmail dot com
 * http://raminrakhamimov.com
 * ************************************************************/
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv){
    int numb = atoi(argv[1]);
    int orig = numb;
    int count = 0;
    int bit_value = 1;

    if(argc != 2){
        fprintf(stderr,"Usage: %s <numb>\n",argv[0]);
        exit(1);
    }

    while(numb > 0){
        if(numb & 1)
            count++;
        numb >>= 1;
    }

    printf("%d has %d bits turned on.\n",orig,count);
}

fib.c top

/****************************************
 * fib.c
 *
 * Optimized version of recursive fib.
 * Runs in O(n) time.
 *
 * Author:
 * Ramin Rakhamimov
 * ramin32 at gmail dot com
 * http://raminrakhamimov.com
 ****************************************/

#include <stdio.h>

int fib(int);
int fib_helper(int, int, int);

int main(int argc, char** argv)
{
    printf("%d\n", fib(atoi(argv[1])));
}

int fib(int n)
{
    int prev1 = 0;
    int prev2 = 1;
    return fib_helper(n, prev1, prev2);
}

int fib_helper(int n, int prev1, int prev2)
{
    if(n <= 0)
        return prev2;

    return fib_helper(n-1, prev2, prev1 + prev2);
}

reverse_number.c top

/*****************************************************************
 * reverse_number.c
 *
 * Reverses a number given from the command line using 
 * only numerical operations.
 * 
 * OUTPUT:
 *      [ramin@home c_programs]$ ./a.out 723895238
 *      832598327
 *
 *
 * Author:
 * Ramin Rakhamimov
 * ramin32 at gmail dot com
 * http://raminrakhamimov.com
 *****************************************************************/

#include <stdio.h>
#include <stdlib.h>

long long power_of_ten(int n){
    long power = 1;
    while(n/=10)
        power *= 10;
    return power;
}

int reverse_number(int num){
    int reversed_number = 0;
    do{
        reversed_number += num%10*power_of_ten(num);
    }while(num/=10);
    return reversed_number;
}
int main(int argc,char **argv){
    if(argc != 2){
        fprintf(stderr,"Usage: %s <number>\n",argv[0]);
        exit(1);
    }

    printf("%d\n",reverse_number(atoi(argv[1])));
    
}

add.c++ top

/*******************************************************
 * add.c++
 *
 * Adds two integers from the command line.
 * 
 * OUTPUT:
 *      [ramin@home c_programs]$ add 100 500
 *      600
 *
 * Author:
 * Ramin Rakhamimov
 * ramin32 at gmail dot com
 * http://raminrakhamimov.com
 ******************************************************/ 
#include <iostream>
#include <sstream>
using namespace std;

int main(int argc,char **argv){
    if(argc != 3){
        cerr << "Usage: " << argv[0] << " <num1> <num2>\n";
        exit(1);
    }

    int first,second;
    stringstream(argv[1]) >> first;
    stringstream(argv[2]) >> second;
    cout << first+second << endl;
}

bridge_flashlight_puzzle.py top

############################################################################################################################
# bridge_flashlight_puzzle.py
#
# Bridge Flashlight Puzzle Python Solution
#
# There are 4 men who want to cross a bridge. They all begin on the same side.
# You have 17 minutes to get all of them across to the other side. It is night. 
# There is one flashlight. A maximum of two people can cross at one time.
# 
# Any party who crosses, either 1 or 2 people, must have the flashlight with them. 
# The flashlight must be walked back and forth, it cannot be thrown etc.
# 
# Each man walks at a different speed. A pair must walk together at a rate of the slower man's pace.
# 
# Man 1: 1 minute to cross.
# Man 2: 2 minutes to cross.
# Man 3: 5 minutes to cross.
# Man 4: 10 minutes to cross.
# 
# For example, if Man 1 and Man 4 walk across first, 10 minutes have elapsed when they get to the other side of the bridge. 
# If Man 4 returns with the flashlight, a total of 20 minutes have passed, and you have failed the mission.
#
# Usage:
#	 $ python bridge_flashlight_puzzle.py
#        (1, 2, 5, 10) ()
#	 (10, 5) (1, 2)
#	 (10, 5, 1) (2,)
#	 (1,) (2, 10, 5)
#	 (1, 2) (10, 5)
#	 () (10, 5, 1, 2)
#
#
# Author: 
# Ramin Rakhamimov
# ramin32 AT gmail DOT com
# http://raminrakhamimov.com
############################################################################################################################

from itertools import combinations
from time import sleep
        
def find_bridge_path(a, b=tuple(), count=0, max_minutes=17, from_a=True, path=tuple()):

    if count > max_minutes:
        return
    
    if not a and count <= max_minutes:
        return path

    if from_a:
        for c in combinations(a, 2):
            a1 = tuple(set(a) - set(c))
            b1 = b + c
            new_path = find_bridge_path(a1, b1, count + max(c), max_minutes, not from_a, path + ((a1, b1),))
            if new_path:
                return new_path
    else:
        for i in b:
            a1 = a + (i,)
            b1 = list(b)
            b1.remove(i)
            b1 = tuple(b1)
            new_path = find_bridge_path(a1, b1, count + i, max_minutes, not from_a, path + ((a1, b1),))
            if new_path:
                return new_path
            

a = (1, 2, 5, 10)
path = find_bridge_path(a, max_minutes=17, path=(a,))

for traversal in path:
    print traversal

fraction.c++ top

/*******************************************************
 * fraction.c++
 *
 * ADT representation of a fraction with intuitive overloaded operators.
 * Also allows direct IO with object
 * ie: 
 *     Fraction f;
 *     cin >> Fraction
 *     cout >> Fraction;
 *
 * Author:
 * Ramin Rakhamimov
 * ramin32 at gmail dot com
 * http://raminrakhamimov.com
 ******************************************************/ 
#include <iostream>

class Fraction{
    private:
        int num;
        int denom;
    public:
        Fraction(){}
        Fraction(int num,int denom){
            this->num = num;
            this->denom = denom;
        }
        Fraction operator+(Fraction other){
            int num = this->num * other.denom + other.num * this->denom;
            int denom = this->denom * other.denom;

            return Fraction(num,denom);
        }
        Fraction operator-(Fraction other){
            int num = this->num * other.denom - other.num * this->denom;
            int denom = this->denom * other.denom;
            return Fraction(num,denom);
        }
        void operator=(Fraction other){
            this->num = other.num;
            this->denom = other.denom;
        }
        Fraction operator*(Fraction other){
            int num = this->num * other.num;
            int denom = this->denom * other.denom;
            return Fraction(num,denom);
        }
        Fraction operator/(Fraction other){
            int num = this->num * other.denom;
            int denom = this->denom * other.num;
            return Fraction(num,denom);

        void simplify(){
            for(int i=num;i >0;i--){
               if(num % i == 0 && denom % i == 0){
                  num/=i;
                  denom/=i;
               }
            }
        }
        friend std::ostream& operator<<(std::ostream&, Fraction&);
        friend std::istream& operator>>(std::istream&, Fraction&);
};

std::ostream& operator<<(std::ostream& output, Fraction& f){
    output << "(" <<  f.num << "/" << f.denom <<")";
    return output;  
}

std::istream& operator>>(std::istream& input, Fraction& f){
    int num;
    char slash;
    int denom;
    input >> num >> slash >> denom;
    f = Fraction(num,denom);
}

int main(){
    Fraction f1,f2;
    Fraction result;
    char op;
    bool success;
    while(1){
        success = true;
        std::cout << "Enter first fraction: ";
        std::cin >> f1 ;
        std::cout << "Enter second fraction: ";
        std::cin >> f2;
        std::cout << "Enter operation (+ - * /): ";
        std::cin >> op;

        switch(op){
            case 'a':
                result = f1 + f2;
                break;
            case 's':
                result = f1-f2;
                break;
            case 'm':
                result = f1*f2;
                break;
            case 'd':
                result = f1/f2;
                break;

            default:
                success = false
                std::cout << "Wrong usage." << std::endl;
        }
        if(success)
            std::cout << f1 << op << f2 << " = " << result;
    }
}

vector.py top

##########################################################
# vector.py 
#
# Author:
# Ramin Rakhamimov
# ramin32 at gmail dot com
# http://raminrakhamimov.com
##########################################################

"""Basic Vector2d implementation"""
import math

class Vector2d():
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __add__(self, other):
        return Vector2d(self.x + other.x, self.y + other.y)

    def __sub__(self, other):
        return Vector2d(self.x - other.x, self.y - other.y)

    def __mul__(self, constant):
        return Vector2d(self.x * constant, self.y *constant)

    def normalize(self):
        magnitude = self.magnitude()
        self.x /= magnitude
        self.y /= magnitude

    def magnitude(self):
        return math.hypot(self.x, self.y)

    def __str__(self):
        return "<%s, %s>" % (self.x, self.y)

    def __repr__(self):
        return self.__str__()

    def __getitem__(self, i):
        if i == 0:
            return self.x
        elif i == 1:
            return self.y

        else:
            raise IndexError, "Only 0 and 1 are valid indices!"

    def get_list(self):
        return [self.x, self.y]

permutation.hs top

(******************************************************
 * An implementation of a permutation generator in F#.
 * Uses both high-order and regular functions.
 *
 *	 Usage:
 *
 *	 > perms [1;2;3];;
 *	 val it : int list list =
 *	   [[3; 2; 1]; [3; 1; 2]; [1; 3; 2]; [2; 3; 1]; [2; 1; 3]; [1; 2; 3]]
 *	 > perms [1;2;3;4];;
 *	 val it : int list list =
 *	   [[2; 3; 4; 1]; [2; 3; 1; 4]; [2; 1; 3; 4]; [1; 2; 3; 4]; [3; 2; 4; 1];
 *	    [3; 2; 1; 4]; [3; 1; 2; 4]; [1; 3; 2; 4]; [3; 4; 2; 1]; [3; 4; 1; 2];
 *	    [3; 1; 4; 2]; [1; 3; 4; 2]; [2; 4; 3; 1]; [2; 4; 1; 3]; [2; 1; 4; 3];
 *	    [1; 2; 4; 3]; [4; 2; 3; 1]; [4; 2; 1; 3]; [4; 1; 2; 3]; [1; 4; 2; 3];
 *	    [4; 3; 2; 1]; [4; 3; 1; 2]; [4; 1; 3; 2]; [1; 4; 3; 2]]
 * 
 * Author:
 * Ramin Rakhamimov
 * ramin32 AT gmail DOT com
 * http://raminrakhamimov.com
 ******************************************************)

// Returns a list with the specified element inserted in every possible postion
let insert_elem_into_every_index elem list = 
    let rec insert_elem_into_every_index_h elem left right acc =
        match right with
        | []    -> (left @ [elem])::acc
        | r::rs -> insert_elem_into_every_index_h elem 
                                                  (left @ [r]) 
                                                  rs 
                                                  ((left @ [elem] @ right)::acc)
    insert_elem_into_every_index_h elem [] list  []

let flatten_list list = List.fold (fun acc2 t1 -> t1 @ acc2) [] list

let rec perms l =
    let insert_into_every_permutation_at_each_index x xs =
        flatten_list (List.map (fun perm -> insert_elem_into_every_index x perm) (perms xs) )
    match l with
    | [] -> []
    | [x] -> [[x]]
    | [x;y] -> [[x;y];[y;x]]
    | x::xs -> insert_into_every_permutation_at_each_index x xs

play_with_stack.c top

/********************************************************************
 * play_with_stack.c
 *
 * Modifies a variable of the previous calling functon without
 * passing any arguments by referencing the address of a local variable
 * and moving up the stack to the exact address of the other variable.
 *
 *      OUTPUT
 *      [ramin@home ~]$ gcc play_with_stack.c && ./a.out 
 *      0xbfd55e44
 *      x in bar: 5, before call.
 *      0xbfd55e44
 *      x in bar: 599999, after call.
 *
 * Author:
 * Ramin Rakhamimov
 * ramin32 at gmail dot com
 * http://raminrakhamimov.com
 * ******************************************************************/
#include <stdio.h>
#define DIFFERENCE 8

void foo(){
    int y;
    printf("%p\n",(void *)(&y+DIFFERENCE));
    *(&y+DIFFERENCE) = 599999;
}

void bar(){
    int x = 5;
    printf("%p\n",(void *)(&x));
    printf("x in bar: %d, before call.\n",x);
    foo();
    printf("x in bar: %d, after call.\n",x);

}

int main(){
    bar();
    return 0;
}

Rational.java top

/******************************************************************
* Ramin Rakhamimov
* Description a Rational number ADT implementation.
*
* Usage:
*   [ramin@home ~/OOP]$ javac Rational.java && java Rational
*   > 100/50 * 2/1
*   4 / 1
*
*   > 20/50 + 1/50
*   21 / 50
*
*   > 33/50 - 3/50
*   3 / 5
*
*   > 33/50 - -3/50
*   18 / 25
*
*   > 20/50 + -1/50
*   19 / 50
*
*   > 1/2 / 1/2
*   1
*
*   > 1/2 * 2
* 1
*
*   > q
*   [ramin@home ~/OOP]$
*******************************************************************/
 
import java.util.Scanner;
 
public class Rational
{
  private final int numerator_;
  private final int denominator_;
 
  public Rational(int numerator, int denominator)
  {
    int gcd = euclidGcd(numerator, denominator);
    numerator_ = numerator / gcd;
    denominator_ = denominator / gcd;
  }
 
  public Rational(int numb)
  {
    this(numb, 1);
  }
 
  public static Rational constructRational(String rational)
  {
    String[] tokens = rational.split("/");
    if(tokens.length == 1)
      return new Rational(Integer.parseInt(tokens[0]));
    else if(tokens.length == 2)
      return new Rational(Integer.parseInt(tokens[0]), Integer.parseInt(tokens[1]));
    else
      throw new RuntimeException("Incorrect input");
 
  }
  public Rational add(Rational other)
  {
    int newNumerator = (numerator_ * other.denominator_) +
    (other.numerator_ * denominator_) ;
    int newDenominator = denominator_ * other.denominator_;
    return new Rational(newNumerator, newDenominator);
  }
 
  public Rational sub(Rational other)
  {
    return add(new Rational(-other.numerator_, other.denominator_));
  }
 
  public Rational mult(Rational other)
  {
    return new Rational(numerator_ * other.numerator_,
        denominator_ * other.denominator_);
  }
 
  public Rational div(Rational other)
  {
    return mult(new Rational(other.denominator_, other.numerator_));
  }
 
  public static int euclidGcd(int x, int y)
  {
    if(y == 0)
      return x;
    return euclidGcd(y, x % y);
  }
 
  public String toString()
  {
    if(numerator_ == denominator_)
      return "1";
    if(denominator_ == 1)
      return numerator_ + "";
    return String.format("%s/%s", numerator_, denominator_);
  }
 
  public static void main(String...args)
  {
    while(true)
    {
      System.out.print("> ");
      Scanner scanner = new Scanner(System.in);
 
      try
      {
        String firstInput = scanner.next();
        if(firstInput.startsWith("q") || firstInput.startsWith("Q"))
          return;
        Rational r1 = constructRational(firstInput);
        char op = scanner.next().charAt(0);
        Rational r2 = constructRational(scanner.next());
 
        switch(op)
        {
          case '+':
            System.out.println(r1.add(r2));
            break;
          case '-':
            System.out.println(r1.sub(r2));
            break;
          case '*':
            System.out.println(r1.mult(r2));
            break;
          case '/':
            System.out.println(r1.div(r2));
            break;
          default:
            System.err.println("Incorrect input!");
        }
        System.out.println();
      }
      catch(Exception e)
      {
        System.err.println("Usage: [operand] [operator] [operand]");        
      }
    }
  }
}

BallAquarium.java top

/*************************************************************
 * BallAquarium.java
 * An aquarium of balls jumping around in random directions
 * at random speeds.
 *
 * Author:
 * Ramin Rakhamimov 
 * ramin32 at gmail dot com
 * http://raminrakhamimov.com
 *************************************************************/

import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.Timer;
import java.awt.event.ActionListener;
import java.awt.event.ActionEvent;
import java.awt.Point;
import java.awt.Graphics;
import java.awt.Color;
import java.awt.Dimension;
import java.util.Random;

public class BallAquarium extends JPanel implements ActionListener
{
    private Ball[] balls;
    private final int size;

    public BallAquarium(int size)
    {
        this.size = size;
    }

    public void actionPerformed(ActionEvent evt)
    {
        repaint();
    }

    @Override
        public void paintComponent(Graphics g)
        {
            if(balls == null)
            {

                balls = new Ball[size];
                for(int i = 0; i < size; i++)
                    balls[i] = Ball.generateBall(this.getWidth(), this.getHeight());
            }

            g.clearRect(0,0, this.getWidth(), this.getHeight());
            for(Ball b:balls)
            {
                b.draw(g);
                b.updatePosition(this.getWidth(), this.getHeight());
            }

        }

    public static void main(String...args)
    {

        // Init aquarium
        int balls = 200;
        BallAquarium aquarium = new BallAquarium(balls);
        aquarium.setPreferredSize(new Dimension(500,500));

        // Set up frame with aquarium
        JFrame frame = new JFrame("Ball Aquarium");
        frame.add(aquarium);
        frame.pack();
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.setVisible(true);

        // Set up timer
        int delay = 30; //milliseconds
        new Timer(delay, aquarium).start();
    }
}

class Ball
{
    private static final Random RANDOM = new Random(System.currentTimeMillis());
    private static final int DIAMETER = 15;
    private static final int[] INCREMENTS = new int[]{1,-1};

    private int xIncrement;
    private int yIncrement;
    private int xPos;
    private int yPos;
    private Color color;

    private Ball(){}
    public static Ball generateBall(int maxX, int maxY)
    {
        Ball b = new Ball();

        b.xIncrement = INCREMENTS[RANDOM.nextInt(1)] * RANDOM.nextInt(10) + 1;
        b.yIncrement = INCREMENTS[RANDOM.nextInt(1)] * RANDOM.nextInt(10) + 1;
        b.xPos = RANDOM.nextInt(maxX-DIAMETER);
        b.yPos = RANDOM.nextInt(maxY-DIAMETER);
        b.color = new Color(RANDOM.nextInt(255), RANDOM.nextInt(255), RANDOM.nextInt(255));

        return b;
    }

    public void updatePosition(int maxX, int maxY)
    {
        if(xPos + DIAMETER > maxX || xPos < 0)
            xIncrement *= -1;
        if(yPos + DIAMETER > maxY || yPos < 0)
            yIncrement *= -1;

        xPos += xIncrement;
        yPos += yIncrement;
    }

    public void draw(Graphics g)
    {
        g.setColor(color);
        g.fillOval(xPos, yPos, DIAMETER, DIAMETER);
    }
}

push_notifications.py top

#################################################################
# Push notifications with Flask, EventSource and redis
#
# 1. Run python push_notifications.py 
# 2. Open a bunch of browsers pointing to http:localhost:5000/
# 3. Open up each browser's console window.
# 4. Hit submit in one, the rest should update.
#
# Author: Ramin Rakhamimov
# http://raminrakhamimov.com
# ramin32@gmail.com
#################################################################

import flask, redis

app = flask.Flask(__name__)
red = redis.StrictRedis(host='localhost', port=6379, db=0)

def event_stream():
    pubsub = red.pubsub()
    pubsub.subscribe('notifications')
    for message in pubsub.listen():
        print message
        yield 'data: %s\n\n' % message['data']


@app.route('/post', methods=['POST'])
def post():
    red.publish('notifications', 'Hello!')
    return flask.redirect('/')


@app.route('/stream')
def stream():
    return flask.Response(event_stream(), mimetype="text/event-stream")

@app.route('/')
def index():
    return '''
<html>
<head>
    <script>
        var source = new EventSource('/stream');
        source.onmessage = function (event) {
             console.log(event.data);
        };
    </script>
</head>
<body>
    <form method="POST" action="/post">
        <input type="submit"/>
    </form>
</body>
</html>

'''

if __name__ == '__main__':
    app.debug = True
    app.run(threaded=True)

MaximumPath.java top

/***************************************************************
 * MaximumPath.java
 *
 * Description: Finds maximum path from root to leaf of a tree 
 *          where adjacent nodes share 1 child. 
 * Complexity: O(n)
 *
 * Author: 
 * Ramin Rakhamimov
 * http://raminrakhamimov.com
 ***************************************************************/

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.io.FileNotFoundException;
import java.io.File;

public class MaximumPath
{
    private static final String INPUT_FILE="triangle.txt";

    public static void main(String... args) throws FileNotFoundException
    {
        final List<List<Integer>> integerLists = loadIntegerLists(INPUT_FILE);
        System.out.println(maximumPathSum(integerLists));
    }

    public static List<List<Integer>> loadIntegerLists(String inputFile) throws FileNotFoundException
    {
        final List<List<Integer>> integerLists = new ArrayList<List<Integer>>();
        final Scanner scanner = new Scanner(new File(inputFile));
        while(scanner.hasNextLine())
        {
            integerLists.add(parseIntLine(scanner.nextLine()));
        }
        return integerLists;
    }

    public static List<Integer> parseIntLine(String line)
    {
        Scanner intScanner = new Scanner(line);
        List<Integer> integerList = new ArrayList<Integer>();
        while(intScanner.hasNextInt())
        {
            integerList.add(intScanner.nextInt());
        }
        return integerList;
    }

    public static int maximumPathSum(List<List<Integer>> integerLists)
    {
        if(integerLists.size() == 0)
            return 0;

        int maximumPathSum = integerLists.get(0).get(0);
        int prevMaxIndex = 0;
        for(int i = 1; i < integerLists.size(); i++)
        {
            int leftChild = integerLists.get(i).get(prevMaxIndex);
            int rightChild = integerLists.get(i).get(prevMaxIndex + 1);

            if(leftChild > rightChild)
            {
                maximumPathSum += leftChild;
            }
            else
            {
                maximumPathSum += rightChild;
                prevMaxIndex++;
            }
        }
        return maximumPathSum;
    }

}

web_crawler.py top

#!/usr/bin/env python

########################################################
# web_crawler.py
# 
# A very naive web crawler.
# simply permutes over all possible ip cominations
# Prints title of each valid ip to stdout and index.txt
#
# Author:
# Ramin Rakhamimov
# ramin32 at gmail dot com
# http://raminrakhamimov.com
########################################################

import urllib2
import BeautifulSoup
#import pickle

ONE_BYTE = 256

index_file = open('index.txt', 'a')
#cache_file = open('ip_cache.txt', 'rw')

#ip_cache = pickle.load(cache_file)



# permute all ip bytes (permute backwards for more interesting results)
for i in reversed(xrange(ONE_BYTE)):
    for j in reversed(xrange(ONE_BYTE)):
        for k in reversed(xrange(ONE_BYTE)):
            for l in reversed(xrange(ONE_BYTE)):
                address = 'http://%s.%s.%s.%s' % (i, j, k, l)
                print 'Trying ip: %s' % address

                try:
                    url = urllib2.urlopen(address, timeout=5)
                    contents =  url.read()
                    print 'Contents: %s' % contents

                    soup = BeautifulSoup.BeautifulSoup(contents) 

                    url_title = ''.join(soup.html.head.title.string, '\n')

                    # log results
                    print 'URL title: %s ' % url_title
                    index_file.write(url_title)

                except urllib2.URLError, AttributeError:
                    print "Nothing Found!"
index_file.close()

fib.pl top

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% fib.pl
% 
% Prolog implementation of fib that runs in linear time.
% Author: Ramin Rakhamimov
% http://raminrakhamimov.com
% ramin32 AT gmail DOT com
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

fib(0,0).
fib(1,1).
fib(2,2).
fib(F,R) :- fib(F,3,1,2,R).

fib(F,F,_,Y,R) :- R is Y, !.
fib(F,I,X,Y,R) :-
  I1 is I + 1,
  X1 is Y,
  Y1 is X + Y,
  fib(F,I1,X1,Y1,R).
  

longest_palindrome.c top

/**********************************************************************************
 * find_longest_palindrome.c
 *
 * Finds the longest palindrome from a string given
 * as the second argument on the command line.
 *
 *   OUTPUT:
 *   [ramin@home c_programs]$ ./a.out kldsfsedudejdfmooooomlkjsmomsakmomdgksahdf
 *   mooooom
 *
 * Author:
 * Ramin Rakhamimov
 * ramin32 at gmail dot com
 * http://raminrakhamimov.com
 * ******************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int find_max(int *arr,int num){
    int index=0;
    int i;
    for(i=1;i<num;i++)
        if(arr[index] < arr[i])
            index = i;
    return index;
}

int main(int argc,char **argv){
    if(argc != 2){
        fprintf(stderr,"Usage: %s <string>\n",argv[0]);
        exit(1);
    }
    int i,count;

    int size = strlen(argv[1]);
    int *index_array = malloc(sizeof(int)*size);

    for(i=0;i<size;i++){
        count=0;
        while( (i-count) >= 0 && (i+count) < size){
            if(argv[1][i-count] != argv[1][i+count]){
                break;
            }
            index_array[i] = count;
            count++;
        }
    }

    int max_index = find_max(index_array,size);

    for(i = max_index - index_array[max_index];i<=max_index+index_array[max_index];i++)
        putchar(argv[1][i]);
    puts("");
}

nth_fib.py top

#####################################
# nth_fib.py
# Returns the nth fibannaci number
#
# Author:
# Ramin Rakhamimov
# ramin32@gmail.com
# http://raminrakhamimov.com
#####################################
import sys

fibs = [0,1]
def fib(n):
    global fibs
    if n > len(fibs) - 1:
        fibs.append(fibs[-1] + fibs[-2])
        return fib(n)
    return fibs[n]

print fib(int(sys.argv[1])-1)

Reverse.java top

/************************************************************
 * Reverse.java
 *
 * Reverses the first string passed through the cmdline.
 *
 * Author:
 * Ramin Rakhamimov
 * ramin32 at gmail dot com
 * http://raminrakhamimov.com
 ***********************************************************/

public class Reverse
{
    public static void main(String... args)
    {
        StringBuilder str = new StringBuilder(args[0]);
        int start = 0;
        int end = str.length() - 1;
        while(start < end)
        {
            char temp = str.charAt(start);
            str.setCharAt(start,str.charAt(end));
            str.setCharAt(end, temp);
            start++;
            end--;
        }
        System.out.println(str);

    }
}

NKnightTour.pl top

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% NKnightTour.pl 
%
% Description: Prolog implementation of a N-Knights-Tour finder.
% Example:
%   ?- grid(5,5,Grid),knight_tour(Grid,[3,3],Tour),write(Tour),length(Tour,Length). 
%   [[3, 3], [1, 2], [2, 4], [4, 5], [5, 3], [4, 1], [2, 2], [1, 4], [3, 5], [5, 4], 
%   [4, 2], [2, 1], [1, 3], [2, 5], [4, 4], [5, 2], [3, 1], [2, 3], [1, 1], [3, 2], 
%   [5, 1], [4, 3], [5, 5], [3, 4], [1, 5]]
%
%   Grid = [[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [2, 1], [2, 2], [2|...], [...|...]|...],
%   Tour = [[3, 3], [1, 2], [2, 4], [4, 5], [5, 3], [4, 1], [2, 2], [1|...], [...|...]|...]
%   Length = 25
% Author: 
% Ramin Rakhamimov
% ramin32 AT gmail DOT com
% http://raminrakhamimov.com
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

difference(Xs,Ys,D) :- 
  findall(X,(member(X,Xs),not(member(X,Ys))),D).

knight_move([X,Y]) :-
  L = [1,-1,2,-2],
  member(X,L),
  member(Y,L),
  abs(X,X1), abs(Y,Y1),
  X1 =\= Y1.

execute_move([X1,Y1],[X2,Y2],[Xmove,Ymove]) :-
  Xmove is X2 - X1,
  Ymove is Y2 - Y1.
  
valid(Grid,From,To) :-
  member(To,Grid),
  execute_move(From,To,Move),
  knight_move(Move).

grid(Width,Height,Grid) :- 
  findall([X,Y],(between(1,Width,X),between(1,Height,Y)),Grid).

knight_tour(Grid,StartMove,Tour) :- 
  knight_tour(Grid,StartMove,[StartMove],Tour).

knight_tour(Grid,_,A,Tour) :-
  difference(Grid,A,Difference),
  Difference = [],
  reverse(A,Tour).
knight_tour(Grid,StartMove,A,Tour) :-
  valid(Grid,StartMove,EndMove),
  not(member(EndMove,A)),
  A1 = [EndMove|A],
  knight_tour(Grid,EndMove,A1,Tour).

all_subsets.py top

########################################################################
# all_subsets.py
#
# Description: Prints out all possible subsets of an arrayay. Uses a binary 
#	       counter to extract combinations from the original arrayay by 
#	       using bitwise AND between the index and each on bit.
#
# Usage:       $ python all_subsets.py
#	       [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3], [4],
# 	       [1, 4], [2, 4], [1, 2, 4], [3, 4], [1, 3, 4], [2, 3, 4], 
#	       [1, 2, 3, 4]]
#
# Author:
# Ramin Rakhamimov
# ramin32 AT gmail DOT com
# http://raminrakhamimov.com
#######################################################################

def extract_subset_by_bits(array, on_bits):
	return [array[i] for i in xrange(len(array)) if (2**i) & on_bits]

def all_subets(array):
	bits_for_array = 2**len(array)
	return [extract_subset_by_bits(array, i) for i in xrange(bits_for_array)]

if __name__ == '__main__':
	print all_subets([1,2,3,4])

.git top

void_stack.c top

/************************************************************************
 * void_stack.c
 *
 * A generic stack container that can work with int's double's and
 * string's all at the same time.
 *
 *      OUTPUT:
 *      Enter type (d,f,s) or q to quit> d
 *      Enter int> 123
 *      Enter type (d,f,s) or q to quit> s
 *      Enter string> hello world!
 *      Enter type (d,f,s) or q to quit> s
 *      Enter string> C is nice!
 *      Enter type (d,f,s) or q to quit> f
 *      Enter float> 4.5589
 *      Enter type (d,f,s) or q to quit> d
 *      Enter int> 9978
 *      Enter type (d,f,s) or q to quit> q
 *      You entered:
 *      9978
 *      4.558900
 *      C is nice!
 *      hello world!
 *      123
 *
 *
 * Author:
 * Ramin Rakhamimov
 * ramin32 at gmail dot com
 * http://raminrakhamimov.com
 * ********************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef enum {INT,DOUBLE,STRING} type;

typedef struct node{
    void *data;
    type t;
    struct node *prev;
}node;

/**********************************************************************
 * 
 * returns an initialized chunk of memory, if type is a string then 
 * str_size must be strlen(string);
 * otherwise any numb may be passed.
 * The memory segment is then initialized to the value in data.
 *
 **********************************************************************/
void *get_init_mem(type t,void *data,int str_size){
    int *int_mem;
    double *double_mem;
    char *char_mem;

    if(t == INT){
        int_mem = malloc(sizeof(int));
        *int_mem = *((int *)data);
        return int_mem;
    }
    else if(t == DOUBLE){
        double_mem = malloc(sizeof(double));
        *double_mem = *((double *)data);
        return double_mem;
    }
    else if(t == STRING){
        char_mem = malloc(str_size + 1);
        strcpy(char_mem,data);
        return char_mem;
    }
    return NULL;
}


void push(node **stack,void *data,type t){
    int str_size;
    if(t == STRING)
        str_size = strlen(data);
    else
        str_size = 0;

    node *prev_node = *stack;
    *stack = malloc(sizeof(node));
    (*stack)->data = get_init_mem(t,data,str_size); 
    (*stack)->t = t;
    (*stack)->prev =  prev_node;
}

node *pop(node **stack){
    if(*stack == NULL)
        return NULL;
    node *current_node = *stack;
    *stack = (*stack)->prev;
    return current_node;
}

//prints the contents of a node containing int,double or string
void print_node(node n){
    if(n.t == INT){
        printf("%d\n",*((int *)n.data));
    }
    else if(n.t == DOUBLE){
        printf("%f\n",*(double *)n.data);

    }
    else if(n.t == STRING){
        printf("%s",(char *)n.data);
    }
}

//Free's a node and its contents.
void free_node(node *current_node){
    free(current_node->data);
    free(current_node);
}

int main(){
    node *stack = NULL;
    node *current_node;
    int numb;
    char ch;
    double decimal;
    char str_buffer[80];

    //Interactively push int's, double's or string's
    do{
        printf("Enter type (d,f,s) or q to quit> ");
        scanf(" %c",&ch);
        getchar();   //<--Eat up \n from scanf
        switch(ch){
            case 'd':
                printf("Enter int> ");
                scanf("%d",&numb);
                push(&stack,&numb,INT);
                break;
            case 'f':
                printf("Enter float> ");
                scanf("%lf",&decimal);
                push(&stack,&decimal,DOUBLE);
                break;
            case 's':
                printf("Enter string> ");
                fgets(str_buffer,79,stdin);
                push(&stack,str_buffer,STRING);
                break;
            default:
                if(ch != 'q')
                    printf("Invalid input\n");
                break; 
        }
    }while(ch != 'q');

    //Return if stack is NULL
    if(stack == NULL) return 0;

    //pop and print all pushed elements.
    printf("You entered:\n");
    while(current_node = pop(&stack)){
        print_node(*current_node);
        free_node(current_node);
    }

    return 0;
}

mode_finder.c++ top

/**************************************************************
 * mode_finder.c++
 *
 * Finds a mode in a list of integers
 *
 * Author:
 * Ramin Rakhamimov
 * ramin32 at gmail dot com
 * http://raminrakhamimov.com
 * ***********************************************************/

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using std::cout;
using std::cin;
using std::endl;
using std::vector;
int main()
{
    vector<int> grades;
    int x;

    //Get the numbers
    while(cin >> x)
        grades.push_back(x);
    //Sort them in increasing order
    sort(grades.begin(),grades.end());

    int mode = grades[0];
    int temp_mode = mode;
    int count = 1;
    int temp_count = count;

    //Count the number of times a number appears consecutively
    //Keep track of the greatest count
    for(int i=1;i<grades.size();i++){
        if(temp_mode != grades[i] || i == grades.size()-1){
            if(temp_count > count){
                count = temp_count;
                mode = temp_mode;
            }
            temp_count =0;
            temp_mode = grades[i];
        }
        temp_count++;
    } 

    cout << mode << " appeared " << count << " times.\n";
}

fib.py top

#!/usr/bin/env python

#############################################################################
# An implementation of the classical fib routine 
# with memoization added for drastic improvements
# in running time.
# 
# As demonstrated the running time goes from linear to constant in just a few
# runs, compared to the ridiculous exponential of the original procedure.
#
# [ramin@laptop ~]$ ./fib.py
# Memoized Fib: 1.59740447998e-05 ms.
# Stupid Fib: 0.0057201385498 ms.
# Memoized Fib: 1.71661376953e-05 ms.
# Stupid Fib: 0.00943493843079 ms.
# Memoized Fib: 1.90734863281e-05 ms.
# Stupid Fib: 0.0152130126953 ms.
# Memoized Fib: 1.69277191162e-05 ms.
#
# Author:
# Ramin Rakhamimov
# ramin32 at gmail dot com
# http://raminrakhamimov.com
#############################################################################

import time

fib_cache = {}

def memoized_fib(x):
    if fib_cache.has_key(x):
        return fib_cache[x]
    
    if(x < 2):
        return x
    
    fib_cache[x] = memoized_fib(x - 1) + memoized_fib(x - 2)
    return fib_cache[x]

def stupid_fib(x):
    if(x < 2):
        return x
    return stupid_fib(x - 1) + stupid_fib(x - 2)

def time_function(msg, f):
    t = time.time()
    f()
    print msg, time.time() - t, 'ms.'

def main():
    for i in xrange(0, 20):
        time_function('Stupid Fib:', lambda: stupid_fib(i))
        time_function('Memoized Fib:', lambda: memoized_fib(i))

if __name__ == '__main__':
    main()

interesting_palindromic_ranges.py top

#################################################################
# int_palin.py
# 
# Counts interesting palindromic subranges* for each range listed 
# in an input file.
#
# *An interesting palindromic subrange is a range of numbers where
# there are even amount of palindromic occurances, ie: (33,44). 
#
# Input:
#	1 2
#	1 7
#	87 88
#	
# Output:	
#	1
#	12
#	1
#
# Author:
# Ramin Rakhamimov
# ramin32 AT gmail DOT com
# http://raminrakhamimov.com
################################################################
import sys
from itertools import combinations, chain

def palindrome(s):
    return s == s[::-1]

def count_palindromes(start, end):
    return sum([palindrome(str(i)) for i in xrange(start, end + 1)])

def even_palindromes(start, end):
    return count_palindromes(start, end) % 2 == 0

def interesting_ranges(ranges):
    return sum(even_palindromes(*r) for r in ranges)

def main():
    with open(sys.argv[1], 'rb') as source_file:
        for line in source_file:
            start, end = line.split()
            numbers = xrange(int(start), int(end) + 1)
            ranges = chain(zip(numbers, numbers), combinations(numbers, 2))
            print interesting_ranges(ranges)

if __name__ == '__main__': main()

largest_palin.py top

##########################################################
# largest_palin.py 
#
# Finds the largest palindrome that is a product of 2 
# 3 digit numbers.
#
# Author:
# Ramin Rakhamimov
# ramin32 at gmail dot com
# http://raminrakhamimov.com
##########################################################

def is_palindrome(x):
    return str(x) == str(x)[::-1]

if __name__ == '__main__':
    digit_range = xrange(999,99,-1)  

    palindromes = [i*j for i in digit_range
                       for j in digit_range 
                       if is_palindrome(i*j)]

    print max(palindromes)

cnf_sat_finder.py top

#!/usr/bin/env python

###############################################################################
# cnf_sat_finder.py
#
# CNF-Satisfiable solution finder.
#
# Description:
# Permutes through all the boolean variations from 0 till 2^n
# Plugs in each boolean permutation into the cnf expression 
# until a solution is found.
#
# cnf expressions are represented as a list of tuples 
# containing either of the following 2 lambda functions:
#   negate = lambda b: not b
#   identify = lambda b: b
# 
# These cnf expressions are randomly generated in to which the boolean 
# permutations are plugged into to evaluate its truthiness.
#
############################################################################### 
# 
# 
# Usage: 
#   cnf_sat_finder.py <cnf size> <number of cnf tuples>
#
# Example:
#   [ramin@laptop py_projects]$ ./cnf_sat_finder.py 3 3
#   Generated CNF Expression:
#       (identify(X) or identify(X) or identify(X)) and
#       (identify(X) or negate(X) or identify(X)) and
#       (identify(X) or negate(X) or identify(X))
#   Solution:
#       (identify(False) or identify(False) or identify(True)) and
#       (identify(False) or negate(False) or identify(False)) and
#       (identify(False) or negate(False) or identify(False))
#   Solution took 0.00402617454529 sec to compute running 64 iterations
#   Architecture run on: 
#   Linux laptop 2.6.29-ARCH #1 SMP PREEMPT Tue Apr 7 12:47:56 UTC 2009 i686
#   
#
#
#
# Author:
# Ramin Rakhamimov
# ramin32 at gmail dot com
# http://raminrakhamimov.com
#################################################################################

import sys
import random
import time
import math
import itertools
import os

"""Negates the input."""
negate = lambda b: not b

"""Returns the identify of the input."""
identify = lambda b: b

def for_loop(start, end):
    """loop for long values."""
    while start < end:
        yield start
        start += 1

def generate_cnf_tuple(cnf_size):
    """Generates a cnf list."""
    operators = (negate, identify)
    return [random.choice(operators) for i in xrange(cnf_size)]

def generate_random_cnf_expression(cnf_size, expression_size):
    """Creates a list of cnf lists of given size."""
    return [generate_cnf_tuple(cnf_size) for i in xrange(expression_size)]

def create_boolean_groups(x, max_size, cnf_size):
    """Constructs binary groups of the cnf size taken from splitting 
    the binary string representation of x."""

    # strip the 0b hex header and pad with 0's
    raw_binary = bin(x)[2:].zfill(max_size)                   
    # map 0's and 1's to booleans
    booleans = [{'0': False, '1':True}[b] for b in raw_binary] 
    # split booleans list into tuples of cnf size
    binary_groups = group_split(booleans, cnf_size)            
    return binary_groups

def group_split(seq, size):
    """Splits the given sequence into groups of size."""
    return [seq[i:i+size] for i in xrange(0, len(seq), size)]


def evaluate_cnf_with_booleans(cnf_exp, boolean_groups):
    """Plugs in the binary string into the cnf expression 
    evaluating to true or false."""
    return all(any(f(b) for f,b in itertools.izip(cnf,booleans)) 
               for cnf, booleans in itertools.izip(cnf_exp, boolean_groups))

def solve_cnf(cnf_exp, cnf_size):
    """Returns first cnf-sat match using bruteforce."""
    size = len(cnf_exp) * cnf_size
    iterations = 0
    for i in for_loop(0, 2**size):
        boolean_groups = create_boolean_groups(i, size, cnf_size)
        if evaluate_cnf_with_booleans(cnf_exp, boolean_groups):
            return boolean_groups, iterations
        iterations += 1
    return None, iterations


def operator_str(operator, param='X'):
    """Returns a pretty string of the function."""
    if operator == identify:
       return 'identify(%s)' % param 
    elif operator == negate:
        return 'negate(%s)' % param 

    raise ValueError('input %s not negate or identify' % str(operator))

def create_cnf_string(cnf, booleans):
    if booleans == None:
        booleans = itertools.repeat('X')
    return " or ".join(operator_str(op, param) for op, param in  itertools.izip(cnf, booleans))

def parentecize(inner_part):
    return "".join(('(',inner_part ,')'))

def cnfize(cnf, booleans):
    return parentecize(create_cnf_string(cnf, booleans))

def pretty_print(cnf_exp, solution=itertools.repeat(None)):
    print '\t' + " and\n\t".join( cnfize(cnf, booleans) for cnf, booleans in itertools.izip(cnf_exp, solution))
    
def main():
    random.seed(time.time())
    try:
        cnf_size = int(sys.argv[1])
        input_size = int(sys.argv[2])
    except IndexError:
        print 'Usage: cnf_sat_finder.py <cnf size> <number of cnf tuples>'
        sys.exit(1)

    
    generated_cnf_expression = generate_random_cnf_expression(cnf_size, input_size)
    print 'Generated CNF Expression:'
    pretty_print(generated_cnf_expression)
    
    before = time.time()
    solution, iterations = solve_cnf(generated_cnf_expression, cnf_size)
    print 'Solution:'
    pretty_print(generated_cnf_expression, solution)
    print 'Solution took %s sec to compute running %s iterations' % (time.time() - before, iterations)
    print 'Architecture run on: \n%s' % ' '.join(os.uname()) 
        
if __name__ == '__main__':
    main()

permutations.py top

###################################################
# permutations.py
#
# Desc: Prints permutations of each line in a file.
#
# Input: 
#   abc
#   123
#   bc
# Output:
#   abc,bac,bca,acb,cab,cba
#   123,213,231,132,312,321
#   bc,cb
#
# Author:
# Ramin Rakhamimov
# http://raminrakhamimov.com
# ramin32 AT gmail DOT com
###################################################
import sys

def insert_everwhere(iterable, item):
    for i in xrange(len(iterable)+1):
        new_list = list(iterable)
        new_list.insert(i, item)
        yield new_list

 
def permutations(iterable):
    if len(iterable) <= 1:
        yield iterable
        raise StopIteration

    sub_permutations = permutations(iterable[1:])
    first = iterable[0]

    for sub_permutation in sub_permutations:
        for perm in insert_everwhere(sub_permutation, first):
            yield ''.join(perm)
        
if __name__ == '__main__':
    with open(sys.argv[1], 'rb') as source:
        for line in source:
            print ','.join(permutations(line.strip()))
        

ArrayUtil.java top

/************************************************************************
 * Ramin Rakhamimov
 *
 * Name: ArrayUtil.java
 * Description: An Array utility class.
 * **********************************************************************/

import java.util.Random;

public class ArrayUtil
{
    private static final Random random_ = new Random(System.currentTimeMillis());

    private ArrayUtil(){}  // <-- Make uninstantiable.

    public static int[] copyArray(int array[])
    {
        int arrayCopy[] = new int[array.length];
        for(int i = 0; i < array.length; i++)
            arrayCopy[i] = array[i];

        return arrayCopy;
    }

    public static void selectionSort(int array[])
    {
        for(int i = 0; i < array.length; i++)
        {
            int minIndex = i;
            for(int j = i + 1; j < array.length; j++)
            {
                if(array[j] < array[minIndex])
                    minIndex = j;
            }

            swapInts(array, i, minIndex);
        }

    }

    public static int partition(int array[], int start, int end)
    {        

    	int rangeSize = end - start;
    	if(rangeSize <= 1)
    		return start;
    	
    	int pivotIndex = start + random_.nextInt(rangeSize);
        int pivot = array[pivotIndex]; 
   
        start--; // Even out start to be 1 less, end is naturally 1 more.
        
        while(true)
        {
        	while(array[++start] <= pivot);
        	while(array[--end] >= pivot);
        	if(start < end)
        		swapInts(array, start, end);
        	else
        		return end;
        }        
    }

    private static void quickSort(int[] array, int start, int end)
    {
        if(end - start <= 1 || array.length <= 1)
            return;

        int pivot = partition(array, start, end);
        quickSort(array, start, pivot);
        quickSort(array, pivot, end);
    }

    public static void quickSort(int[] array)
    {
        quickSort(array, 0, array.length);
    }

    public static boolean linearSearch(int[] array, int key)
    {
        for(int i: array)
        {
            if(i == key)
                return true;
        }
        return false;
    }


    public static int binarySearch(int[] array, int key)
    {
        if(array.length <= 0)
            return -1;

        int start = 0;
        int end = array.length - 1;
        while(start < end)
        {
            int midPoint = (end + start)/2;
            if(key < array[midPoint])
                end = midPoint - 1;
            else if(key > array[midPoint])
                start = midPoint + 1;
            else if(key == array[midPoint])
                return midPoint;
            else 
            	return -1;
        }
        
        return -1;
    }

    public static void swapInts(int[] array, int i, int j)
    {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static int[] getRandomArray(int size, int range)
    {
        int[] array = new int[size];
        for(int i = 0; i < size; i++)
            array[i] = random_.nextInt(range);
        return array;
    }

    public static void printArray(String msg, int[] array)
    {
        System.out.println(msg);
        for(int i = 0; i < array.length; i++)
            System.out.print(array[i] + " ");

        System.out.println();
        System.out.println();
    }
}

find_suming_numbers.py top

#!/usr/bin/env python2
###############################################################
# find_summing_numbers.py
#
# Description: 
# find 2 indeces within an array that sum up to a given number.
#
# Running Time:
# O(n)
#
# Usage:
#    $ python2 find_suming_numbers.py 
#    Random Array: [34, -35, 61, 19, -18, -43, 66, 77, -41, 84, -66, -70, -29, 
#    78, -85, -3, -40, 53, -31, -21, 84, -57, 33, 58, -99, 90, 73, 22, -9, 91, 
#    83, 70, 84, 46, 88, -45, -92, -11, 72, -95, 67, 100, -72, 36, 39, -58, -4, 
#    -41, 21, -23, -99, 7, -100, 51, -88, 63, 77, 60, 12, 42, 56, -28, 73, 73, 
#    -49, -51, -89, -95, 42, 37, 40, 5, -87, -4, 53, -9, -95, -96, -61, -73, 
#    -55, 48, 13, 65, -64, -18, 3, -56, 49, -17, -27, 14, 70, 12, -49, 97, 3, 
#    -45, 23, 22]
#    12 pairs have been found.
#    (2, 37): 61 + -11 = 50
#    (7, 90): 77 + -27 = 50
#    (8, 29): -41 + 91 = 50
#    (13, 61): 78 + -28 = 50
#    (15, 74): -3 + 53 = 50
#    (16, 25): -40 + 90 = 50
#    (26, 49): 73 + -23 = 50
#    (29, 47): 91 + -41 = 50
#    (40, 89): 67 + -17 = 50
#    (43, 91): 36 + 14 = 50
#    (49, 63): -23 + 73 = 50
#    (69, 82): 37 + 13 = 50
#    
#
# Author:
# Ramin Rakhamimov
# ramin32 at gmail dot com
# http://raminrakhamimov.com
#################################################################
import random

def find_summing_numbers(array, n):
    result = []
    index_map = { item: index for index, item in enumerate(array) }

    processed_indices = {}
    for index, item in enumerate(array):
        processed_indices[index] = True
        num_to_find = n - item
        if num_to_find != item and index_map.get(num_to_find, False) not in processed_indices:
            result.append( (index, index_map[num_to_find]) )
            processed_indices[index_map[num_to_find]] = True
    return result

def main():
    range = (-100, 100)
    array_size = 100
    array = [random.randint(*range) for i in xrange(array_size)]
    print 'Random Array: %s' % array

    sum = 50
    result = find_summing_numbers(array, sum)
    print '%s pairs have been found.' % len(result)
    for pair in result:
        print '%s: %s + %s = %s' % (pair, array[pair[0]], array[pair[1]], sum)

if __name__ == '__main__':
    main()

my_pof_messages.py top

####################################################################
# my_pof_messages.py
#
# A simple script to scrape your pof messages and 
# print them to single html file. Also outputs to json.
# 
# Usage: 
# sudo pip install beautifulsoup4 requests jinja2
# python my_pof_messages.py <username> <password> <output_prefix>
# firefox output_prefix.html
#
# Author: 
# Ramin Rahkhamimov
# ramin32@gmail.com
# http://raminrakhamimov.com
#####################################################################

import requests
from bs4 import BeautifulSoup
import re
from jinja2 import Template
import json
import sys
from datetime import datetime

pof_url = lambda x: "https://www.pof.com/%s" % x
session = requests.session()
                                                           
def append_message_links(e, links):
    soup = BeautifulSoup(e.text)
    for a in soup.find_all(attrs={'href': re.compile('viewallmessages.*')}):
        links.append(pof_url(a.attrs['href']))

    next_page = soup.find('a', text='Next Page')
    return next_page and pof_url(next_page.attrs['href'])



def get_all_message_links(username, password):
    links = []
    payload = dict(username=username,
                   password=password,
                   tfset="300",
                   callback="http%3a%2f%2fwww.pof.com%2finbox.aspx",
                   sid="ikdnixh1pblvis1dlqaa0mb3") 

    e = session.post(pof_url("processLogin.aspx"), data=payload)
    next_page = append_message_links(e, links)
     
    while next_page:
        e = session.get(next_page)
        next_page = append_message_links(e, links)
    return set(links)

def clean_string(string):
    return string.encode('ascii', 'ignore')

def to_date(date_string):
    return datetime.strptime(date_string, '%m/%d/%Y %I:%M:%S %p')

def parse_all_messages(links):
    messages = []
    for link in links:
        comment_page = session.get(link)
        soup = BeautifulSoup(comment_page.text)
        for message in soup.find_all(attrs={'style': re.compile('width:500px.*')}):
            user = soup.find('span', 'username-inbox')
            user_image_url = soup.find('td', attrs={'width':"60px"}).img.attrs['src']
            messages.append(dict(user_username=clean_string(user.text),
                                 user_url=pof_url(user.a.attrs['href']),
                                 user_image_url=user_image_url,
                                 date=user.parent.find('div').text,
                                 message=clean_string(message.text)))
    return sorted(messages, key=lambda m: to_date(m['date']), reverse=True)


def save_messages(messages, prefix):
    template = Template("""
    <html>
    <head>
        <style>
            .user, .message, .date {
                display: inline-block;
                vertical-align: top;
            }
            .message { 
                width: 500px;
                padding-left: 10px;
            }
        </style>
    </head>
    <body>
        <ol>
        {% for message in messages %}
            <li>
            <a href="{{message.user_url}}" class="user">
            <img src="{{message.user_image_url}}"/>
            <div>
                {{message.user_username}}
            </div>

            </a>
            <div class="message">
                {{message.message}}
            </div>
            <div class="date">
                {{message.date}}
            </div>
            </li>
        {% endfor %}
        </ol>
    </body>
    </html>
    """)

    with open('%s.html' % prefix, 'w') as f:
        f.write(template.render(messages=messages))

    with open('%s.json' % prefix, 'w') as f:
        f.write(json.dumps(messages))

if __name__ == '__main__':
    if len(sys.argv) != 4:
        print "Usage: my_pof_messages.py <username> <password> <output_prefix>"

    links = get_all_message_links(sys.argv[1], sys.argv[2])
    messages = parse_all_messages(links)
    save_messages(messages, sys.argv[3])

tree_max_depth.c++ top

/**************************************************************
 * tree_max_depth.c++
 * Recursive and Iterative (BFS) max_depth c++ implementations.
 *
 * Author:
 * Ramin Rakhamimov
 * ramin32 AT gmail DOT com
 * http://raminrakhamimov.com
 **************************************************************/

#include <iostream>
#include <algorithm>
#include <queue>


// Data member left out, for this example
struct Node {
    std::queue<const Node *>::size_type distance;
    Node *left;
    Node *right;
};

typedef std::queue<const Node *>::size_type size_type;

size_type recursive_depth(const Node *tree) {
    if(tree == 0)
        return 0;
    int left_depth = recursive_depth(tree->left);
    int right_depth =  recursive_depth(tree->right);
    return 1 + std::max(left_depth,right_depth);
}

size_type bfs_depth(Node *tree) {
    if(tree == 0)
        return 0;

    tree->distance = 1;

    std::queue<const Node *>  node_q;
    node_q.push(tree);

    size_type max_depth = 0;

    while(!node_q.empty()) {
        const Node *current_node = node_q.front();
        if(current_node->left) {
            node_q.push(current_node->left);
            size_type left_distance = current_node->distance + 1;
            current_node->left->distance = left_distance;
            max_depth = std::max(max_depth, left_distance);
        }
        if(current_node->right) {
            node_q.push(current_node->right);
            size_type right_distance = current_node->distance + 1;
            current_node->right->distance = right_distance;
            max_depth = std::max(max_depth, right_distance);
        }
        node_q.pop();
    }
    return max_depth;
}


int main() {
    Node a = {0};
    Node b = {0,&a};
    Node c = {0,&b};
    Node d = {0};
    Node e = {0,&c,&d};
    std::cout << recursive_depth(&e) << '\n';
    std::cout << bfs_depth(&e) << '\n';

}

html_grid.html top

<!DOCTYPE>
<!-- 
A simple example on how to create a grid using div's and css. 

Author:
Ramin Rakhamimov
ramin32 at gmail dot com
http://raminrakhamimov.com
-->

<html>
    <head>
        <title>Grid Example</title>
        <style type="text/css">
            body {
                color: black;
                background-color: #d8da3d 
            }
            ul
            {
                width:900px;
                list-style-type:none;
            }
            li {
                text-align:center;
                display: inline-block;
                padding:5px;
            }
            img {
                display: block;
            }
        </style>
    </head>

    <body>
        <ul>
            <script type="text/javascript">
                for(var i=0; i<20; i++) {
                    document.write('<li> \
                            <img src="http://www.geekestateblog.com/wp-content/uploads/2007/08/geek.jpg" height="100"/> \
                                username \
                            </li>');
                }
            </script>
        </ul>
    </body>

</html>