Archive for the ‘Snippets I’d like to share’ Category

Square root   Leave a comment


Integer square root should work only if the given number has an integer square root

import java.math.BigInteger;

public class SquareRoot {
	public static BigInteger squareRoot(BigInteger num) {
		BigInteger high = num;
		BigInteger low = BigInteger.ONE;
		BigInteger two = BigInteger.valueOf(2);
		BigInteger res;
		BigInteger mid;
		do {
			mid = high.add(low).divide(two);
			if ((res = mid.multiply(mid)).compareTo(num) < 0)
				low = mid;
			else
				high = mid;
		} while (res.compareTo(num) != 0);
		return mid;
	}

	public static double squareRoot(double d) {
		double high = Math.ceil(d);
		double low = 0;
		double mid = 0;
		do {
			mid = (high + low) / 2;
			if (mid * mid > d)
				high = mid;
			else
				low = mid;

		} while (Math.abs(mid * mid - d) > 1e-15);
		return mid;
	}
}

Posted August 21, 2011 by epicrado in Java

Unweighted Graph Traversals [Adjacency List,Adjacency matrix]   Leave a comment


#include <stdio.h>
#include <stdlib.h>
struct linkedList
{
	struct node* head;
	struct node* tail;
	int size;
};
struct node
{
	int content;
	struct node* next;
};
void enqueue(int n,struct linkedList* q)
{
	struct node* new = malloc(sizeof(struct node));
	new->content = n;
	new->next = 0;
	if(!q->size)
	{
		q->head = new;
		q->tail = new;
	}
	else
	{
		q->tail->next = new;
		q->tail = new;
	}
	q->size++;

}
void push(int n,struct linkedList* s)
{
	struct node* new = malloc(sizeof(struct node));
	new->content = n;
	new->next = s->head;
	s->head = new;
	s->size++;
}
int pop(struct linkedList* s)
{
	struct node* t = s->head;
	int temp = t->content;
	s->head = s->head->next;
	s->size--;
	free(t);
	if(!s->size)
		s->tail = 0;
	return temp;
}
struct linkedList* newLinkedList()
{
	struct linkedList* r = malloc(sizeof(struct linkedList));
	r->size = 0;
	return r;
}
char isEmpty(struct linkedList* s)
{
	return !s->size;
}
void print(struct lminkedList l)
{
	struct node* t = l.head;
	while(t)
	{
		printf("%d ",t->content);
		t = t->next;
	}
}
void reGround(struct linkedList*l)
{
	l->head = 0;
	l->tail = 0;
	l->size = 0;
}
//Depth first search using stack and adjacency list
void dfsStackAdList(struct linkedList** adlist,int first,int n)
{
	int i;
	char* v = (char*)malloc(n);
	struct node* t;
	for(i=0;i<n;i++)
		v[i] = 0;
	struct linkedList* stack = newLinkedList();
	push(first,stack);
	while(!isEmpty(stack))
	{
		i = pop(stack);
		v[i] = 1;
		printf("%d ",i);
		t = adlist[i]->head;
		while(t)
		{
			if(!v[t->content])
				push(t->content,stack);
			t = t->next;
		}
	}
}
//Breadth first search using stack and adjacency list
void bfsAdList(struct linkedList** adlist,int first,int n)
{
	int i;
	char* v = (char*)malloc(n);
	struct node* t;
	for(i=0;i<n;i++)
		v[i] = 0;
	struct linkedList* queue = newLinkedList();
	enqueue(first,queue);
	while(!isEmpty(queue))
	{
		i = pop(queue);
		v[i] = 1;
		printf("%d ",i);
		t = adlist[i]->head;
		while(t)
		{
			if(!v[t->content])
				enqueue(t->content,queue);
			t = t->next;
		}
	}
}
//DFS for adjacency list using recursion
void dfsRecAdList(struct linkedList** adlist,int target,int n,char* v)
{
	struct node* t;
	v[target] = 1;
	printf("%d ",target);
	t = adlist[target]->head;
	while(t)
	{
		if(!v[t->content])
			dfsRecAdList(adlist,t->content,n,v);
		t = t->next;
	}
}
void dfsAdMatrixRec(char** map,int cur,char* v,int n)
{
	int i;
	v[cur] = 1;
	printf("%d ",cur);
	for(i=0;i<n;i++)
		if(map[cur][i]&&!v[i])
			dfsAdMatrixRec(map,i,v,n);
}
void dfsAdMatrixStack(char** map,int start,int n)
{
	int i,c;
	char* v = (char*)malloc(n);
	for(i=0;i<n;i++)
		v[i] = 0;
	struct linkedList* s = newLinkedList();
	push(start,s);
	while(!isEmpty(s))
	{
		c  = pop(s);
		v[c] = 1;
		printf("%d ",c);
		for(i=0;i<n;i++)
		{
			if(!v[i]&&map[c][i])
				push(i,s);
		}
	}
}
void bfsAdMatrixQueue(char** map,int start,int n)
{
	int i,c;
	char* v = (char*)malloc(n);
	for(i=0;i<n;i++)
		v[i] = 0;
	struct linkedList* q = newLinkedList();
	enqueue(start,q);
	while(!isEmpty(q))
	{
		c  = pop(q);
		v[c] = 1;
		printf("%d ",c);
		for(i=0;i<n;i++)
		{
			if(!v[i]&&map[c][i])
				enqueue(i,q);
		}
	}
}
int main()
{
	int i;
	struct linkedList** adList = (struct linkedList**) malloc(5*sizeof(struct linkedList*));
	for(i=0;i<5;i++)
		adList[i] = newLinkedList();
	char* v = (char*) malloc(5);
	char** map = (char**) malloc(5*sizeof(char*));
	for(i=0;i<5;i++)
		map[i] = (char*) malloc(5);
	map[0][1] = 1;
	map[0][3] = 1;
	map[3][4] = 1;
	map[3][2] = 1;
	map[4][2] = 1;
	bfsAdMatrixQueue(map,0,5);
	return 0;
}

Posted July 25, 2011 by epicrado in C

Audioclip grabber   Leave a comment


call Sound.getClip(String path); with the path of the sound file

import java.applet.AudioClip;
import java.io.File;
import java.net.MalformedURLException;
public class Sound
{
	public static String getUrl(File f)
	{
		String url = f.getAbsolutePath();
		String res = "";
		for (int i = 0; i < url.length(); i++)
		{
			if (url.charAt(i) == '\\')
			{
				res += '/';
			} else
				res += url.charAt(i);
		}
		url = "file:///" + res;
		return url;
	}

	public static AudioClip getClip(String path) throws MalformedURLException
	{
		return java.applet.Applet.newAudioClip(new java.net.URL(
				getUrl(new File(path))));
	}

}

Posted July 17, 2011 by epicrado in Java

Sum,Min,Max,Mergesort for array   Leave a comment


I was just learning pointers to functions and i wrote those snippets

#include <stdio.h>
#include <stdlib.h>
//Sums two integers a and b
int sum(int a,int b)
{
	return a+b;
}
//returns the minimum of two integers a and b
int min(int a,int b)
{
	return (a<b)?a:b;
}
//returns the maximum of two integers a and b
int max(int a,int b)
{
	return (a>b)?a:b;
}
//Recursive function takes a pointer to function operation and returns
//the result of performing such an operation on an array
int func(int i,int*a,int top,int (*operation)(int x,int y))
{
	if(i==top-1)
		return a[i];
	else
		return operation(a[i],func(i+1,a,top,operation));
}
//iterative function takes a pointer to function operation and returns
//the result of performing such an operation on an array
int func_iter(int *a,int top,int (*operation)(int x,int y))
{
	int i;
	int res = a[0];
	for(i=1;i<top;i++)
	{
		res = operation(res,a[i]);
	}
	return res;
}
//returns the maximum of an array
int max_a(int*a,int len)
{
	return func(0,a,len,&max);
}
//returns the minimum of an array
int min_a(int*a,int len)
{
	return func(0,a,len,&min);
}
//returns the sum of an array
int sum_a(int *a,int len)
{
	return func(0,a,len,&sum);
}
//returns the maximum of an array iterative
int sum_a_iter(int *a,int len)
{
	return func_iter(a,len,&sum);
}
//returns the minimum of an array iterative
int min_a_iter(int*a,int len)
{
	return func_iter(a,len,&min);
}
//returns the max of an array iterative
int max_a_iter(int*a,int len)
{
	return func_iter(a,len,&max);
}
//returns factorial of n recursive
int factorial(int n)
{
	if(!n)
		return 1;
	else
		return n*factorial(n-1);
}
//returns the factorial of n iterative
int factorial_iterative(int n)
{
	int i;
	int res = 1;
	for(i=2;i<=n;i++)
		res*=i;
	return res;
}
//ascending order function required for merge sort algorithm
int ascending(int a,int b)
{
	return a<b;
}
//descending order function required for merge sort algorithm
int descending(int a,int b)
{
	return a>b;
}
//Merger sorter should be called with pointer to order function
//weather the result should be sorted ascending or descending order
void mergeSort(int*array,int len,int(*order_fn)(int a,int b))
{
	if(len!=1)
	{
		int*a,*b,i,j,mid,top;
		mid = len/2;
		a = (int*) malloc(mid*sizeof(int));
		b = (int*) malloc((len-mid)*sizeof(int));
		for(i=0;i<mid;i++)
			a[i] = array[i];
		for(i=0;i+mid<len;i++)
			b[i] = array[i+mid];
		mergeSort(a,mid,order_fn);
		mergeSort(b,len-mid,order_fn);
		i = j = top = 0;
		while(i<mid&&j<len-mid)
			if(order_fn(a[i],b[j]))
				array[top++] = a[i++];
			else
				array[top++] = b[j++];
		for(;i<mid;i++)
			array[top++] = a[i];
		for(;j<len-mid;j++)
			array[top++] = b[j];
	}
}

int main()
{
	int i;
	int a[7] = {1,-2,3,632,4,5,7};
	mergeSort(a,7,&ascending);
	for(i=0;i<7;i++)
		printf("%d ",a[i]);
	//OUTPUTS -2 1 3 4 5 7 632
	return 0;
}

Posted July 16, 2011 by epicrado in C