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,
 read(X),
 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?'),
 read(O),
 write('Operand 1: '),
 read(X),
   (O='squareRoot'->Answer is sqrt(X), write(Answer);
   write('Operand 2: '),read(Y),
    (O='addition'->write('Addition specified'),Answer is X+Y, write(Answer);
     (O='subtraction'->Answer is X-Y, write(Answer);
         (O='multiplication'->Answer is X*Y, write(Answer);
          (O='division'->Answer is X/Y, write(Answer);
        (O='mod'->Answer is mod(X,Y), write(Answer))))))).

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). 

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)
                    mst.add(edge);
                    //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}

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)

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

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