Wednesday, March 25, 2015

Simple Prolog Practice Programs

Program 1:  Using Relations.

Code:

```parent(pam, bob).
parent(tom, bob).
parent(tom, liz).
parent(bob, ann).
parent(bob, pat).
parent(pat, jim).

male(tom).
male(bob).
male(pat).
male(jim).
female(pam).
female(liz).
female(ann).

father(X, Y):-male(X), parent(X, Y).
mother(X, Y):-female(X), parent(X, Y).
grandFather(X, Y):-male(X), parent(Z, Y), parent(X, Z).
grandMother(X, Y):-female(X), parent(Z, Y), parent(X, Z).
greatGrandFather(X, Y):-parent(Z, Y), parent(Q, Z), father(X, Q).
greatGrandMother(X, Y):-parent(Z, Y), parent(Q, Z), mother(X, Q).
stepBrother(X, Y):-father(Z, X), father(Z, Y), mother(Q, X), not(mother(Q, Y));
mother(Z, X), mother(Z, Y), father(Q, X), not(father(Q, Y)).```

Program 2: Input/Output from/to Console:

Code:

```greetings:-
write('What is your name?'),
nl,
write('Hello '),
write(X).```

Program 3: Writing a Calculator.

Code:

```calculator:-
write('Operations Supported: 1. addition 2. subtraction 3. multiplication 4. division 5. mod 6. squareRoot'),
nl,
write('What do you want to do?'),
write('Operand 1: '),

Program 4: Find the bigger number in two numbers.

Code:

```greater(X, Y):-
(X>Y->write(X), write(' is greater than '), write(Y);
(Y>X->write(Y), write(' is greater than '), write(X);
write(X), write(' is equal to '), write(Y))).```

Program 5: Find the biggest number in three numbers.

Code:

```greatestThree(X, Y, Z):-
( (X<Y;X<Z) ->
( Y<Z -> write('Z is the greatest');write('Y is the greatest'));
((X=Y,Y=Z)->write('All are equal');write('X is the greatest'))).```

Program 6: Find the factorial of a number.

Code:

```fact(0,1).
fact(N,F):-N>0, N1 is N-1,  fact(N1, F1), F is F1*N.```

Program 7: Solve the Problem of Towers of Hanoi.

Code:

```hanoi(1, A, B, _):-
write('Move disk from tower '),
write(A),
write(' to '),
write(B),
nl.

hanoi(N, A, B, C):-
N>1,
N1 is N-1,
hanoi(N1, A, C, B),
hanoi(1, A, B, C),
hanoi(N1, C, B, A).```

Program 8: Display Fibonacci series upto a specified number of elements.

```fibonacci(A, B, Upto):-
Upto>0,
Z is A+B,
write(A),
nl,
fibonacci(B, Z, Upto-1).```

Program 9: Calculate GCD of two numbers.

```gcd(X, Y):-
X=Y, write(X);
X=0, write(Y);
Y=0, write(X);
X>Y, Z is X-Y, gcd(Z, Y);
X<Y, Z is Y-X, gcd(X, Z). ```

Monday, March 16, 2015

Kruskal's Algorithm Implementation In Java [Disjoint Sets - using HashMap (With Union By Rank And Path Compression Heuristics)]

For Disjoint Sets, Refer to this previous post: http://www.codebytes.in/2015/03/disjoint-sets-tree-implementation-using.html

Source:

```import java.util.*;

public class Kruskal {
static class EDGE implements Comparable<EDGE>{
char from, to;
int weight;
EDGE(char f, char t, int w){
from = f;
to = t;
weight = w;
}

@Override
public int compareTo(EDGE o) {
return weight<o.weight?-1:(weight>o.weight?1:0);
}

@Override
public String toString(){
return "["+from+", "+to+"]";
}
}

private static Map<Character, Character> PARENT;
private static Map<Character, Integer> RANKS; //to store the depths

public static void initialize(char[] universe){
PARENT = new HashMap<>();
RANKS = new HashMap<>();
for(char x:universe){
PARENT.put(x, x);
RANKS.put(x, 1);
}
}

public static char FindSet(char item){
char parent = PARENT.get(item);
if(parent==item)return item;
else return FindSet(parent);
}

public static void Union(char setA, char setB){
char pA, pB;
while((pA = PARENT.get(setA))!=setA){setA = pA;}
while((pB = PARENT.get(setB))!=setB){setB = pB;}

int rankFirst = RANKS.get(setA), rankSecond = RANKS.get(setB);
if(rankFirst>rankSecond){
PARENT.put(setB, setA);
updateRanksUpward(setB);
}else if(rankSecond>rankFirst){
PARENT.put(setA, setB);
updateRanksUpward(setA);
}else{
PARENT.put(setB, setA);
updateRanksUpward(setB);
}
}

public static void updateRanksUpward(char current){
int currentDepth = RANKS.get(current);
char currentsParent = PARENT.get(current);
int parentsDepth = RANKS.get(currentsParent);
if(!(currentDepth<parentsDepth || currentsParent == current)){
RANKS.put(currentsParent, currentDepth+1);
updateRanksUpward(currentsParent);
}
}

public static void main(String[] args){
//Test data
//CLRS Example p632
char[] vertices = new char[]{'a','b','c','d','e','f','g','h','i'};
EDGE[] edges = new EDGE[14];
edges[0] = new EDGE('a','b',4);
edges[1] = new EDGE('a','h',8);
edges[2] = new EDGE('b','h',11);
edges[3] = new EDGE('b','c',8);
edges[4] = new EDGE('h','g',1);
edges[5] = new EDGE('h','i',7);
edges[6] = new EDGE('c','i',2);
edges[7] = new EDGE('i','g',6);
edges[8] = new EDGE('g','f',2);
edges[9] = new EDGE('f','c',4);
edges[10] = new EDGE('c','d',7);
edges[11] = new EDGE('f','d',14);
edges[12] = new EDGE('f','e',10);
edges[13] = new EDGE('d','e',9);

//Call Kruskal Algorithm
Kruskal(vertices, edges);
}

//CLSR p631 Algorithm
public static ArrayList<EDGE> Kruskal(char[] vertices, EDGE[] edges){
//Initialize A = empty set
ArrayList<EDGE> mst = new ArrayList<>();

//for each vertex v belongs to G.V MAKE-SET(v)
initialize(vertices);

//sort the edges of G.E into non decreasing order by weight w
Arrays.sort(edges);

//For each edge (u,v) belongs to G.E taken in non decreasing order by weight
for(EDGE edge:edges){
//If (find-set(u)!=find-set(v)
if(FindSet(edge.from)!=FindSet(edge.to)){
//A = A union (u, v)
//UNION(u, v)
Union(edge.from, edge.to);
}
}
//Display contents
System.out.println("MST contains the edges: "+mst);
return mst;
}
}```

Output:

MST contains the edges: [[h, g], [c, i], [g, f], [a, b], [f, c], [c, d], [a, h], [d, e]]

For practice, try solving : http://www.spoj.com/problems/CSTREET/

Disjoint Sets Tree Implementation [Path Compression+Union by Rank] using HashMap Java

Tutorial: https://www.youtube.com/watch?v=UBY4sF86KEY (10 mins)

Java Implementation (Without Union by Rank and Path Compression):

```import java.util.*;

public class DisjointSets {
private static Map<Character, Character> PARENT;

public static void initialize(char[] universe){
PARENT = new HashMap<>();
for(char x:universe){
PARENT.put(x, x);
}
}

public static char Find(char item){
char parent = PARENT.get(item);
if(parent==item)return item;
else return Find(parent);
}

public static void Union(char setA, char setB){
PARENT.put(PARENT.get(setA), setB);
}

public static void main(String[] args) throws Exception{
char universe[] = {'a', 'b', 'c', 'd', 'e'};
initialize(universe);
//Set parent of d to b
Union('d', 'b');
System.out.println("Item d is in the set "+Character.toUpperCase(Find('d')));
//Set parent of b to e
Union('b', 'e');
System.out.println("Item d is in the set "+Character.toUpperCase(Find('d')));
}
}```

Output:

Item d is in the set B
Item d is in the set E

Implementation With Union By Rank (attach lesser rank node to greater one) and Path Compression (Union of roots):

```import java.util.*;

public class DisjointSetsUnionByRankPathCompression{
private static Map<Character, Character> PARENT;
private static Map<Character, Integer> RANKS; //to store the depths

public static void initialize(char[] universe){
PARENT = new HashMap<>();
RANKS = new HashMap<>();
for(char x:universe){
PARENT.put(x, x);
RANKS.put(x, 1);
}
}

public static char Find(char item){
char parent = PARENT.get(item);
//        System.out.println("Finding the parent of "+item+" is: "+parent);
if(parent==item)return item;
else return Find(parent);
}

public static void Union(char setA, char setB){
char pA, pB;
while((pA = PARENT.get(setA))!=setA){setA = pA;}
while((pB = PARENT.get(setB))!=setB){setB = pB;}

int rankFirst = RANKS.get(setA), rankSecond = RANKS.get(setB);
if(rankFirst>rankSecond){
PARENT.put(setB, setA);
System.out.println("\nRank of "+setA+" is greater than that of "+setB);
System.out.println("Setting the parent of "+setB+" to "+setA);
updateRanksUpward(setB);
}else if(rankSecond>rankFirst){
PARENT.put(setA, setB);
System.out.println("\nRank of "+setB+" is greater than that of "+setA);
System.out.println("Setting the parent of "+setA+" to "+setB);
updateRanksUpward(setA);
}else{
PARENT.put(setB, setA);
System.out.println("\nBoth "+setA+" and "+setB+" have same Ranks");
System.out.println("Setting the parent of "+setB+" to "+setA);
updateRanksUpward(setB);
}
}

public static void updateRanksUpward(char current){
int currentDepth = RANKS.get(current);
char currentsParent = PARENT.get(current);
int parentsDepth = RANKS.get(currentsParent);
if(!(currentDepth<parentsDepth || currentsParent == current)){
System.out.println("Update rank of "+currentsParent+" by child "+current);
RANKS.put(currentsParent, currentDepth+1);
updateRanksUpward(currentsParent);
}
}

public static void main(String[] args) throws Exception{
char universe[] = {'a', 'b', 'c', 'd', 'e'};
initialize(universe);

//Set parent of d to b
Union('d', 'b');
System.out.println("Item b is in the set "+Character.toUpperCase(Find('b')));
System.out.println(PARENT);
System.out.println(RANKS);

//Set parent of b to e
Union('b', 'e');
System.out.println("Item e is in the set "+Character.toUpperCase(Find('e')));
System.out.println(PARENT);
System.out.println(RANKS);

//Find the set of a
System.out.println("Item a is in the set "+Character.toUpperCase(Find('a')));
System.out.println(PARENT);
System.out.println(RANKS);

//Test 2
initialize(new char[]{'a','e','l','i','d','b','e'});
Union('a', 'e');
Union('e', 'l');
Union('l', 'i');

Union('d', 'b');
Union('b', 'e'); //(Unite the two sets that is union(a, d) - unite both sets

System.out.println(PARENT);
System.out.println(RANKS);

}
}```

Output:

Both d and b have same Ranks
Setting the parent of b to d
Update rank of d by child b
Item b is in the set D
{a=a, b=d, c=c, d=d, e=e}
{a=1, b=1, c=1, d=2, e=1}

Rank of d is greater than that of e
Setting the parent of e to d
Item e is in the set D
{a=a, b=d, c=c, d=d, e=d}
{a=1, b=1, c=1, d=2, e=1}
Item a is in the set A
{a=a, b=d, c=c, d=d, e=d}
{a=1, b=1, c=1, d=2, e=1}

Both a and e have same Ranks
Setting the parent of e to a
Update rank of a by child e

Rank of a is greater than that of l
Setting the parent of l to a

Rank of a is greater than that of i
Setting the parent of i to a

Both d and b have same Ranks
Setting the parent of b to d
Update rank of d by child b

Both d and a have same Ranks
Setting the parent of a to d
Update rank of d by child a
{a=d, b=d, d=d, e=a, i=a, l=a}
{a=2, b=1, d=3, e=1, i=1, l=1}

Tuesday, March 3, 2015

Incrementing a three digit number in the range [000-998] in Brainf*ck

I was solving a programming problem on SPOJ.com (CRYPTO2). The task was this:

You are given a three digit number. You have to add 1 to it and display the result. But you have to submit the solution in brainf*ck.

If we had to do it in C way, we would have come up with a code like this:

```#include <stdio.h>

int main(int argc, char **argv)
{
int a[] = {4,9,9};
if(a[2]==9){
a[2] = 0;
if(a[1]==9){
a[1] = 0;
a[0]++;
}else a[1]++;
}else a[2]++;
for(int i=0;i<3;++i)printf("%d",a[i]);
return 0;
}```

Translating it to BrainF*uck, it becomes:

Memory cells store these values sequentially:

flag
48 n1
48 n2 n2 n2 9 flag
48 n3 n3 n3 9 flag
48 48 48

Code:

```+>
++++++++++++++++++++++++++++++++++++++++++++++++>,<[->-<]
>>
++++++++++++++++++++++++++++++++++++++++++++++++>,<[->-<]
> [->+>+<<] >>> +++++++++ <[->-<] >> +(F)
<[[-]>-<]>>
++++++++++++++++++++++++++++++++++++++++++++++++>,<[->-<]
> [->+>+<<] >>> +++++++++ <[->-<] >> +(F)
<[[-]<<+>>>-<]>(back at flag)

[- <<<[-] <<<[- <<<[-] <<<+<<->>>>>>>>]<<<<<<<<[->>>>>+<<<<<]>>>>>>>> >>>>>>]

>
++++++++++++++++++++++++++++++++++++++++++++++++[<<<<<<<<<<<<<+>>>>>>>>>>>>>-]
<<<<<<<<<<<<<.
>>>>>>>>>>>>>>
++++++++++++++++++++++++++++++++++++++++++++++++[<<<<<<<<<<<+>>>>>>>>>>>-]
<<<<<<<<<<<.
>>>>>>>>>>>>
++++++++++++++++++++++++++++++++++++++++++++++++[<<<<<<+>>>>>>-]
<<<<<<.
```