ISourceCode

Make the frequent cases fast and the rare case correct

Monthly Archives: June 2011

ACM – Jolly Jumpers – Python

Problem taken from here

A sequence of n > 0 integers is called a jolly jumper if the absolute values of the difference between successive elements take on all the values 1 through n-1. For instance,
1 4 2 3
is a jolly jumper, because the absolutes differences are 3, 2, and 1 respectively. The definition implies that any sequence of a single integer is a jolly jumper. You are to write a program to determine whether or not each of a number of sequences is a jolly jumper.

Sample Input

1 4 2 3
1 4 2 -1 6
Sample Output

Jolly
Not jolly

CODE:

import math
n = 4
inp = [1,4,2,3]
out = []
for i in range(1,n):
        out.append(math.fabs(inp[i]-inp[i-1]))
out.sort()
val = 0
for i in range(1,n):
        if out[i-1] == i:
                val = val+1
if val == n-1:
        print "jolly"
else:
        print "not jolly"

OUTPUT:
$ python jolly.py
jolly

For:
n = 5
inp = [1,4,2,-1,6]

$ python jolly.py
not jolly

Thanks for reading !

ACM – Variant of Balanced Partition Problem – Python

Problem take from ACM and is a variant of the Balanced Partition Problem

Tug of War

A tug of war is to be arranged at the local office picnic. For the tug of war, the picnickers must be divided into two teams. Each person must be on one team or the other; the number of people on the two teams must not differ by more than 1; the total weight of the people on each team should be as nearly equal as possible.

Sample Input
100
90
200
Sample Output

190 200

CODE:

import math
import random

n=5
arr = [100,100,100,90,200]

total=indexA=indexB=i=j=sideA=sideB=0

for p in range(0,n):
	total = total+arr[p]

split=n/2

a = b = [0]*n
arr.sort()

while indexA< split :
	indexA = indexA+1
	a[indexA] = arr[i]
	
	if(indexA< split):
		indexA=indexA+1
		a[indexA] = arr[n-i-1]
		sideA = sideA+arr[n-i-1]
	sideA =sideA+arr[i]
	i=i+1
	j=i

while indexB < n-split :
	indexB=indexB+1
	b[indexB] = arr[j]
	sideB = sideB+arr[j]
   	j=j+1

t1 = split - 1
t2 = split

sideA = sideA + (b[t2]-a[t1])
sideB = sideB + (a[t1]-b[t2])

if split%2 == 0 :
	print "side A has total of:", sideA
	print "side B has total of:", sideB
else:
	sideA = min(sideA, sideB)
	sideB= max(sideA, sideB)
	print "side A has total of:", sideA
	print "side B has total of:", sideB

OUTPUT:
$ python tug.py
side A has total of: 290
side B has total of: 300

For

n=4
arr = [100,100,90,200]
$ python tug.py
side A has total of: 290
side B has total of: 200

For

n=3
arr = [100,90,200]
$ python tug.py
side A has total of: 190
side B has total of: 200

Thanks for Reading!

Wagner–Fischer algorithm – To find Levenshtein distance ( C program )

The Wagner–Fischer algorithm is a dynamic programming algorithm that measures the Levenshtein distance between two strings of characters.

For example, the Levenshtein distance between “kitten” and “sitting” is 3, since the following three edits change one into the other, and there is no way to do it with fewer than three edits:

kitten → sitten (substitution of ‘s’ for ‘k’)
sitten → sittin (substitution of ‘i’ for ‘e’)
sittin → sitting (insertion of ‘g’ at the end).

Computing the Levenshtein distance is based on the observation that if we reserve a matrix to hold the Levenshtein distances between all prefixes of the first string and all prefixes of the second, then we can compute the values in the matrix by flood filling the matrix, and thus find the distance between the two full strings as the last value computed.

                k 	i 	t 	t 	e 	n
	0 	1 	2 	3 	4 	5 	6
s 	1 	1 	2 	3 	4 	5 	6
i 	2 	2 	1 	2 	3 	4 	5
t 	3 	3 	2 	1 	2 	3 	4
t 	4 	4 	3 	2 	1 	2 	3
i 	5 	5 	4 	3 	2 	2 	3
n 	6 	6 	5 	4 	3 	3 	2
g 	7 	7 	6 	5 	4 	4 	3

CODE:

/* http://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm */
#include <stdio.h>
#include <math.h>
int d[100][100];
#define MIN(x,y) ((x) < (y) ? (x) : (y))
main()
{
	int i,j,m,n,temp,tracker;
	char s[] = "kitten";
	char t[] = "sitting";
	m = strlen(s);
	n = strlen(t);

	for(i=0;i<=m;i++)
		d[0][i] = i;
	for(j=0;j<=n;j++)
		d[j][0] = j;

	for (j=1;j<=m;j++)
	{
		for(i=1;i<=n;i++)
		{
			if(s[i-1] == t[j-1])
			{
				tracker = 0;
			}
			else{
				tracker = 1;
			}
			temp = MIN((d[i-1][j]+1),(d[i][j-1]+1));
			d[i][j] = MIN(temp,(d[i-1][j-1]+tracker));
		}
	}
	printf("the Levinstein distance is %d\n",d[n][m]);

}

OUTPUT:
$ ./a.exe
the Levinstein distance is 3

References: Wikipedia entry for Levenshtein distance.

Thanks for reading !

The Game of Euclid – Python way to find out who wins !

In 1969, Cole and Davie developed a two-player game based on the Euclidean algorithm, called The Game of Euclid,which has an optimal strategy.The players begin with two piles of a and b stones. The players take turns removing m multiples of the smaller pile from the larger. Thus, if the two piles consist of x and y stones, where x is larger than y, the next player can reduce the larger pile from x stones to x − my stones, as long as the latter is a non negative integer. The winner is the first player to reduce one pile to zero stones.Wikipedia

Two players,A and B play, starting with two natural numbers(stones), the first player A, subtracts any positive multiple of the lesser of the two numbers from the greater of the two numbers, provided that the resulting number must be non negative. Then the second player B, does the same with the two resulting numbers, then A, etc., alternately, until one player is able to subtract a multiple of the lesser number from the greater to reach 0, and thereby wins. For example, the players may start with (25,7):

25 7

11 7

4 7

4 3

1 3

1 0
One of the readers has rectified an issue with my previous code. I am displaying the code given by him

#Author : Rohit Saxena 
    def egame(x,y):
        if x < y:
            return egame(y,x)
        elif x % y == 0:
            return True
        elif x - y < y:
            return not egame(y,x-y)
        else:
            return True
     
    x = int(raw_input("Enter number of stones for pile 1 : "))
    y = int(raw_input("Enter number of stones for pile 2 : "))
     
    print "Player %s wins" % "A" if egame(x,y) else "B"

OUTPUT:

devgru@ubuntu:~$ python egame.py
Enter number of stones for pile 1 : 25
Enter number of stones for pile 2 : 7
Player A wins

Thanks for Reading !

Algorithm to find the Lexicographical Next Permutation of a Number or a String – Code in Python

Firstly I am back to writing. I hope to put many articles and code here in the coming weeks.

Problem statement is simple: We need to find the next permutation of a number or string.

For example 112 has next permutation of 121
and a string for example chin has next permutation of chni.

The code has explanation.

def NextPerm(s):
	Len = len(s)
	# char at the end of string

	EndChar = s[Len-1]
	

	for i in range (Len-2,-1,-1):

		# compare with char to left of the last char

		c = s[i]

		# if smaller, then it has to be substituted

		if(c < EndChar):

		# left to the char under check is remaining the same and put into buffer

			buff = s[:i]
			#print buff

			# find next biggest digit on the right starting from end and notice the last char is the smallest)

			for j in range(Len-1,i,-1):

				# check if the digit is bigger

				if(s[j] > c):

					break

			# Add the char to buffer

			buff = buff + s[j]
			

			# book keep the index
			index = j

				

			# add remaining chars in ascending order(reverse order) and put also insert C in its index

				 

			for j in range(Len-1,i,-1):

				# check if the the char was used to replace 'c' 

				if(j == index):

					# if yes, keep 'c' in its place

					buff = buff + c

				else:

					# else copy next char

					buff = buff + s[j]

						

			return(buff)

			

		# last char is stored for the loop process

		EndChar = c

		

		# if char are in descending order its the biggest permutation

	return("its already the biggest permutation")

input = raw_input("Enter any number or string : ")

print "The next perm is :",NextPerm(input)

OUTPUT:

labuser@ubuntu:~$ python NextPerm.py
Enter any number or string : abc
The next perm is : acb
labuser@ubuntu:~$ python NextPerm.py
Enter any number or string : acb
The next perm is : bac
labuser@ubuntu:~$ python NextPerm.py
Enter any number or string : bac
The next perm is : bca
labuser@ubuntu:~$ python NextPerm.py
Enter any number or string : bca
The next perm is : cab
labuser@ubuntu:~$ python NextPerm.py
Enter any number or string : cab
The next perm is : cba
labuser@ubuntu:~$ python NextPerm.py
Enter any number or string : cba
The next perm is : its already the biggest permutation
labuser@ubuntu:~$
labuser@ubuntu:~$ python NextPerm.py
Enter any number or string : 112
The next perm is : 121
labuser@ubuntu:~$ python NextPerm.py
Enter any number or string : 121
The next perm is : 211
labuser@ubuntu:~$ python NextPerm.py
Enter any number or string : 211
The next perm is : its already the biggest permutation
labuser@ubuntu:~$

Thanks for reading ! Watch out for more articles this month.

Follow

Get every new post delivered to your Inbox.