Summing 2dArray using Recursion

This algortihm uses summing a 1d array using recursion - see -



/*
* Thid programme uses Binary Sum  algo to recursively calculate sum of 2d array using recursion
*/

public class BinarySum {
public static void main(String args[]) {

int array[][] = { { 1, 2 }, { 3, 4 }, { 5, 6 }, { 7, 8 }, { 9, 10 } };

int sum = binarySum2d(array, array.length, array[0].length);

System.out.println(sum);
}

// evalauate each row recursively and send to binarySum1d for calculating
// sum
private static int binarySum2d(int[][] array, int rows, int columns) {

if (rows == 0)
return 0;

// calculate sum for each row
return binarySum2d(array, rows - 1, columns)
+ binarySum1d(array[rows - 1], 0, columns);

}

// computing binary sum of 1d array using recursion
public static int binarySum1d(int array[], int startIndex, int length) {

if (length == 1)
return array[startIndex];
else
return binarySum1d(array, startIndex, (int) Math.ceil(length / 2.0))
+ binarySum1d(array,
startIndex + (int) Math.ceil(length / 2.0),
(int) Math.floor(length / 2.0));
}

}

Recursion - Summing an 1-d array using binary sum

public class BinarySum {

public static void main (String args[]){

int array[] = {1,2,3,4,5,6,7,8};

int sum  =  binarySum(array , 0 , array.length);

System.out.println(sum);

}

//computing binary sum using recursion

public static  int binarySum(int[] array ,int startIndex , int length) {

if(length == 1 )

return array[startIndex];

else

return  binarySum(array,startIndex,(int)Math.ceil(length/2.0)) +                binarySum(array,startIndex+(int)Math.ceil(length/2.0),(int)Math.floor(length/2.0));

}

}

Recursion trace for binarySum(array , 0 ,  8)

Insertion Sort on Doubly Linked List

InsertionSort on doubly linked list 

The classes for Doubly linked list are implemented here 

To understand it in better way  take an analogy from arrays insertion sort  -

 see Insertion sort on arrays  here


  for(i = 1  ; i  < array.length ; ++i)
  {
   for( j = i - 1 ; j >= 0 && array[j+1] < array[j] ; --j )
   {
   //swap array[j+1] and array[j]
   }
  
  }
  
  Derving Analogy for doubly linked list from arrays for Insertion sort algo
         DNode pivot - array[i] or array[j+1]
         DNode ins - array[j]
         DNode ins.index - j
 
        while(list.hasPrev(ins) && ins.getData().compareTo(pivot.getData()) > 0 ) -  while(j>=0 and array[j] > array[j+1])
 

public void insertionSort(DblyLinkedList list)
{
//if the size of list is smaller than or equal to one , then its already sorted
if(list.getSize() <= 1)
{
return ;
}

// a pivot node which will be compared everytime with the sorted list 
// to its left to get its proper place in list 
DNode pivot  ;

//insertion point 
DNode ins ; 

//end of run
DNode end  = list.getFirst();

DNode lastNode = list.getLast();

while(end != lastNode)
{

pivot  = end.getNext(); // get the next pivot node , this is the node to be insertion sorted

list.removeNode(pivot); // remove pivot from the list to place it in right order

ins  = end ; // start searching to left from the end of sorted run
while(list.hasPrev(ins) && ins.getData().compareTo(pivot.getData()) > 0 )
{
//loop to left to find appropriate insertion  place for the pivot
ins  = ins.getPrev() ; //move to left
}
list.insertAfter(ins, pivot); // insert the pivot at right place

// if we added pivot just after end of sorted run in this case i.e the pivot
// is already at its right place , increment end marker
if(ins ==  end )  end = end.getNext();
}




}

UVa 10194 - Football (aka Soccer)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.UnsupportedEncodingException;
import java.util.Arrays;
import java.util.HashMap;


class Main {


// a static inner class implementing Comparable
// the "natural ordering " this class is applied on the objects as teams
static class Team implements Comparable<Team>
{
String teamName;
//match result  attributes for each team
int wins, loses, ties, played, scored, against, points, diff;

//constrcutor
public Team(String name)
{
this.teamName = name;
this.wins = 0;
this.loses = 0;
this.ties = 0;
this.played = 0;
this.scored = 0;
this.against = 0;
this.points = 0;
this.diff = 0;
}

//function to update match result attributes for each team
public void update(int gScored , int gAgainst )
{
++this.played;
//update team result as per win , tie or lost of a match
if(gScored > gAgainst)
{
++this.wins;
this.points += 3 ;
}
else if(gScored == gAgainst)
{
++this.ties;
++this.points;
}
else
{
++this.loses;
}
this.scored += gScored;
this.against += gAgainst;
this.diff = this.scored - this.against;

}



//"natural ordering" comparator for objects of this class as per specs of football tournament
// this would be used by Collections.sort() or Arrays.sort()
//for natural order sorting in ascending order
/*
*@specs
*"
*Teams are ranked according to these rules (in this order):
* Most points earned.
     * Most wins.
   *  Most goal difference (i.e. goals scored - goals against)
     * Most goals scored.
     * Less games played.
     * Lexicographic order. 
     *
*"
*/
public int compareTo(Team t) {
if (this.points != t.points)
return t.points - this.points;
if (this.wins != t.wins)
return t.wins - this.wins;
if (this.diff != t.diff)
return t.diff - this.diff;
if (this.scored != t.scored)
return t.scored - this.scored;
if (this.played != t.played)
return this.played - t.played;
return this.teamName.toLowerCase().compareTo(t.teamName.toLowerCase());

}

}

public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in,
"ISO-8859-1"));
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out,
"ISO-8859-1"));
//flag to show a new line after first output
boolean first = true;
int cases  =  Integer.parseInt(in.readLine());

while(cases-- > 0 )
{
String tournName = in.readLine();
int ttlTeams = Integer.parseInt(in.readLine());

//create an array of Team objects , for teams in tournament
Team teams[] =  new Team[ttlTeams];

//hashmap for team and corresponding id 
HashMap<String , Integer> teamId = new HashMap<>();

//read all team names , fill the hashmap teamId and teams[] array of Team objects
for(int i = 0 ;i < ttlTeams ; ++ i)
{
String teamName = in.readLine();
teamId.put(teamName, i);
teams[i] = new Team(teamName);
}

int matchesPlayed = Integer.parseInt(in.readLine());

//for each match played , evaluate the result as per specs
for( int m = 0 ; m < matchesPlayed ; ++m )
{
String matchSummary = in.readLine();
String parts[] = matchSummary.split("[#@]");
//get the team names , goals and ids
String team1 = parts[0];
String team2 = parts[3];
int g1 = Integer.parseInt(parts[1]);
int g2 = Integer.parseInt(parts[2]);
int id1 = teamId.get(team1);
int id2 = teamId.get(team2);

//update the game result for the team playing this match
teams[id1].update(g1, g2);
teams[id2].update(g2, g1);
}

//sort the team[] array as per natural ordering of specs
Arrays.sort(teams);

//show the newline space between each result
if (first)
{
first = false;
}
else
{
out.println();
}
 
//show the result
out.println(tournName);
for (int i = 0; i < ttlTeams; ++i) {
out.println((i + 1) + ") " + teams[i].teamName + " "
+ teams[i].points + "p, " + teams[i].played + "g ("
+ teams[i].wins + "-" + teams[i].ties + "-"
+ teams[i].loses + "), " + teams[i].diff + "gd ("
+ teams[i].scored + "-" + teams[i].against + ")");
}
}
out.flush();
in.close();
System.exit(0);


}
}

Java - A basic ActionListener

//main class
import javax.swing.JFrame;;
public class Main {

    public static void main(String[] args) {
        ActionListnrGui alg =  new ActionListnrGui();
       
        //sets the default close operation for JFrame
        alg.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
       
        //sets the size of JFrame
        alg.setSize(350, 200);
       
        //sets the visibility of JFrame
        alg.setVisible(true);
       

    }

}


/*
   
 */
import java.awt.FlowLayout;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;

import javax.swing.JFrame;
import javax.swing.JOptionPane;
import javax.swing.JPasswordField;
import javax.swing.JTextField;

public class ActionListnrGui extends JFrame
{
    private JTextField item1;
    private JTextField item2;
    private JTextField item3;
    private JPasswordField passwordField;
   
    //constructor  initialise items to show in window and adds the action listener to each events
    // the action listener takes object of action handler
    public ActionListnrGui(){
     // this sets the title of JFrame
             super("this is title");
           
             //set the layout
             setLayout(new FlowLayout());
           
             //initialise items and add them  to window
             item1 =  new JTextField(10); add(item1);
             item2 =  new JTextField("blood on the dance floor"); add(item2);
             item3 =  new JTextField("no matter how much u try , u cant edit this",20); item3.setEditable(false) ; add(item3);
           
             passwordField = new JPasswordField("my pass is 123 "); add(passwordField);
           
             //the object of class implementing ActionListener
             theHandler handler =  new theHandler();
           
             //add specified ActionListener object to each field  to recieve action event
             //this finally handles the events
             item1.addActionListener(handler);
             item2.addActionListener(handler);
             item3.addActionListener(handler);
             passwordField.addActionListener(handler);
           
           
           
           
    }

    //inner class that handles listener
    private class theHandler implements ActionListener {
        //called automatically when an event fires aka actionlistener functionality done
        public void actionPerformed(ActionEvent event)
        {
            String string = "";
           
            //find the particular  event fired after press of enter key over text boxes items
            //and save the entered text using event.getActionCommand()
            if(event.getSource() == item1)
                string = String.format("field 1 :  %s" , event.getActionCommand() );
            else if(event.getSource() == item2)
                string = String.format("field 2 :  %s" , event.getActionCommand() );
            else if(event.getSource() == item3)
                string = String.format("field 3 :  %s" , event.getActionCommand() );
            else if ( event.getSource() ==  passwordField )
                string = String.format("passsword field is :  %s" , event.getActionCommand() );
               
                //show the message on screen
                JOptionPane.showMessageDialog(null, string);
        }
       
       
    }   

   
}   
           

UVa 146 - ID Codes

/*
 * @author Divyanhsu
 * @mail divyanshu17x@gmail.com
 * @place GNDU RC SATHIALA
 * @date 29 / 07 / 2014
 * @judge uva.onlinejudge.org
 * @verdict Accepted
 * @problem  UVa 146 - ID Codes
 * @problemType  next permutation
 */

 import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
 class  Main {
     public static void main(String args[]) throws IOException{
         BufferedReader reader =  new BufferedReader(new InputStreamReader(System.in)) ; 
           
            //read the code
            String code = reader.readLine();
           
           
           
            //evaluate next permutation of code string  until a sentinel # is read
            while(!code.equals("#"))
            {
                //Linked list of character read from right
                LinkedList <Character> charsReadList = new LinkedList<>();
               
                //flag  to find any rightmost character
                //greater then any right most character before it
                boolean found = false ;
               
                char charArray[]  = code.toCharArray();
               
                //iterator variable
                int i = 0 ;
               
                //loop through the right most character of string
                for( i = code.length() - 1 ; !found && i >= 0 ; --i )
                {
                    char currentChar = charArray[i];
                   
                    //create an iterator for linked list of read characters
                    Iterator<Character> iter =  charsReadList.iterator();
                   
                    //loop until we  find the  rightmost read character from list
                    //to be greater then current read character
                    // or all chars of list are compared
                    while( !found && iter.hasNext() )
                    {
                        char x = iter.next();
                        if(x > currentChar )
                        {
                            //turn the flag on
                            found = true ;
                           
                            //place the compared character from list in place of current read character
                            charArray[i] = x ;
                           
                            //remove the compared character from list
                            iter.remove();
                           
                           
                        }
                    }
                   
                    //add the read  current character to list
                    charsReadList.add(currentChar);
                   
                   
                }
               
                if(found)
                {
                    //shift the iterator variable i at index just\
                    //before the index of current character read
                    //which has been replaced by right most charcter greater then it
                    i += 2 ;
                   
                    //sort the read characters list
                    Collections.sort(charsReadList);
                   
                    Iterator<Character> iter = charsReadList.iterator();
                   
                    //place the read charatcer list starting from position i
                    while(iter.hasNext())
                    {
                        charArray[i++] = iter.next();
                    }
                   
                    //print the next permuation string
                    String nextPerm = "";
                    for(int m = 0 , length = charArray.length ; m < length ; ++m)
                    {
                        nextPerm += charArray[m];
                    }
                    System.out.println(nextPerm);
                   
                }
                else
                {
                    //else print no  next permuatation successor found
                    System.out.println("No Successor");
                }
               
                //read the next case
                code = reader.readLine();
            }
           
            reader.close();
   
     }
 }



   

Doubly Linked List using Java

An implementation of basic classes required for  Doubly Linked List using Java

class - DNode  -  the class to initialise node objects for the list

           DblyLinkedList -  the class to build ours doubly linked list

The sentinels for the list are - head and trailer

Code is well commented for visualising the whole  scenario  

 /*
 * @class Dnode for creating nodes  of a doubly linked list
 */
public class DNode {
  
    // node's data
     private String data ;
    
     // node's next and previous pointer variables
     private DNode next , prev ;
    
     //constructor initialisng the node
     public DNode(DNode next ,  DNode prev , String data ){
         this.next = next;
         this.prev = prev ;
         this.data = data;
        
     }
    
     //getters and setters for a  node
     public DNode getNext()
     {
         return this.next;
     }
     public DNode getPrev()
     {
         return this.prev;
     }
     public String  getData()
     {
          return this.data;
     }
     public void  setNext(DNode newNext)
     {
          this.next = newNext;
     }
     public void  setPrev(DNode newPrev)
     {
          this.next = newPrev;
     }
     public void setData(String newData)
     {
         this.data = newData;
     }
  

-------------------------------------------------

  /*
 *  @class DblyLinkedList for creating a doubly linked list using objects of DNode class as nodes
 */
public class DblyLinkedList {
    //header and trailer sentinels of a list
    //the header and trailer have their previous and
    //next node object pointer variables as null respectively
    private DNode head ,trailer ;
    private static int size ;
   
    //constructor initialise the doubly linked list
    //with size zero and head and trailer sentinels pointing eachother
    public DblyLinkedList()
    {
         DblyLinkedList.size = 0;
         this.head =  new DNode(null,null,null);
         this.trailer =  new DNode(null ,head , null );
         this.head.setNext(trailer);
    }
   
    //returns the total nodes in list
    public int getSize()
    {
        return DblyLinkedList.size;
    }
   
    //returns whether the list is empty
    public boolean isEmpty()
    {
        return ( DblyLinkedList.size == 0 );
    }
   
    //returns the first node of list
    public DNode getFirst() throws IllegalStateException
    {
        if(isEmpty()) throw new IllegalStateException("The list is empty ");
        return head.getNext();
    }
   
    //returns the last node of list
    public DNode getLast() throws IllegalStateException
    {
        if(isEmpty()) throw new IllegalStateException("The list is empty ");
        return trailer.getPrev();
    }
   
    // returns the node before a given node v
    // error occurs if the given node v is head
    //returns the first node of list
    public DNode getNext(DNode v) throws IllegalStateException
    {
        if(v == head) throw new IllegalStateException("Cannot move past the header itself");
        return v.getNext();
    }
   
    //inserts a given node z before a given node v
    // error occurs if v is a header
    public void insertBefore(DNode v ,DNode z) throws IllegalArgumentException
    {
        DNode u = v.getPrev(); // may throw an IllegalArgumentException
        z.setNext(v);
        z.setPrev(u);
        u.setNext(z);
        v.setPrev(z);
        DblyLinkedList.size++;
       
    }
    //inserts a given node z after a given node v
    // error occurs if v is a trailer
    public void insertAfter(DNode v ,DNode z)
    {
        DNode w = v.getNext(); // may throw an IllegalArgumentException
        z.setNext(w);
        z.setPrev(v);
        v.setNext(z);
        w.setPrev(z);
        ++DblyLinkedList.size;
       
    }
   
    // inserts a given node at head
    public void insertAtHead(DNode z)
    {
        insertAfter(head,z);
    }
   
    // insert a given node at tail
    public void insertAtTail(DNode z)
    {
        insertBefore(trailer,z);   
    }
   
    //removes a given node v from list
    // error occurs if v is a among sentinels head or trailer
    public void removeNode(DNode v)
    {
        DNode u =  v.getPrev();// may throw an IllegalArgumentException
        DNode w  = v.getNext();// may throw an IllegalArgumentException
       
        //make u and w point eachother
        u.setNext(w);
        w.setPrev(u);
       
        //null out pointer references of given node v to remove it
        v.setNext(null); v.setPrev(null);
       
        //decrement the size of list
        --DblyLinkedList.size;
       
    }
   
    //returns whether a given node z has a previous node
    public boolean hasPrev(DNode z)
    {
        return ( z != head ) ;
    }
   
    //returns whether a given node z has a next node
    public boolean hasNext(DNode z)
    {
        return ( z != trailer ) ;
    }
   
    // returns a string representation of  the list
    public String toString()
    {
        String s = "[ ";
        DNode v = head.getNext();
       
        while(v != trailer)
        {
            s +=  v.getData();
            v = v.getNext();
            if( v != trailer )
            {
                s += " ," ;
            }
            else
            {
                s += " ]" ;
                break;
            }
        }
        return s;
    }
   
  }

A woman of substance...

It’s 8:48 PM by my watch. I’m sitting alone in my room working on a project. Mom and dad are not here at home as they had to attend some function of a distant relative. So, tonight it’s just the two of us. “Shreya, dinner is ready. Come out within 2 minutes!” her voice echoes into my ear. I shut down my laptop and get up lazily, slide into my slippers and come out of the room into the dining area. There I see her, setting the table. She is placing plates and cutlery on the table: her old and wrinkled hands moving mechanically like they have been moving for the past fifty years. Her face seems expressionless. But as I get closer, I realize that she is humming something in an almost inaudible tone. Perhaps it’s some prayer that she’s singing. She normally does that when she does not have anything much to say- a situation that has been frequently occurring since after grandpa died. My grandmother. That’s who she is.
I have grown up seeing her- every day of my life. When I was a kid, she used to read out to me, the stories of ‘panchtantra’ in a hope that I incorporate at least some, if not all of those good moral values. And after the story followed her customary kiss on my forehead and then a wide smile would stretch across her face: a smile so profound that I won’t trade the world for that.
When I started going to school and even during my early teenage years, I never thought much of her. She would prepare lunch for me and be waiting for me to come from school. Then she would ask my about how my day went and mostly, our conversation would wind up with that. Clearly, I was more obsessed with my own ‘hormonal changes’ at that time. 
But things changed.
The death of my grandfather was an apocalypse for the entire family. Personally it was my first ever acquaintance with death. So, yes it had a great impact on me. But there was something else too that changed my outlook- forever. It was my grandma’s reaction to his death. She had been widowed. But she hardly showed it. She did not shed a single tear. All the time, she used to have that serene, tranquil look on her face like that of a child in deep sleep. Since that time, I have felt immense respect for her. I hated myself for not taking her seriously and thinking of her as someone ‘secondary’. Even though it was evident that grandpa’s death affected her the most, yet she seemed to be completely at peace with the whole mishap. A strong lady- that’s who she is: my grandmother.

Now I have started going to college in another town, therefore I don’t get to see her a lot. It’s only during days like these when I come home during vacations that I actually get to spend some quality time with her. No, it’s not like I sit down with her and literally talk. Mostly, I just sit by her side and in my silence, offer her a solace. That’s why I refused to go to that function with my parents. I don’t want her to go to bed alone. I love her for being an epitome of affection for me ever since I opened my eyes. I respect her for showing great strength when ‘strength’ was the last thing to be found anywhere.
And I simply cannot imagine my past, present or future without her!

As we sit down and silently feed ourselves, I’m overwhelmed by my thoughts about her. There is an air of warm silence enveloping the room. It’s comforting. And from grandma’s face, I can see that it’s comforting for her as well. There are no words, gestures or expressions: just emotions floating from one half of the soul to its remaining half sitting right across the table.

UVa 11340 - Newspaper

/*

 * @author Divyanshu

 * @mail divyanshu17x@gmail.com

 * @place GNDU RC SATHIALA

 * @date 28 / 07 / 2014

 * @judge uva.onlinejudge.org

 * @verdict Accepted

 * @problem 11340 - Newspaper

 * @problemType  Direct Mapping

 */

import java.io.*; 

import java.util.*; 

 class  Main {

     public static void main(String args[]) throws IOException{

            Reader.init(System.in);

            int testCases = Reader.nextInt() ;

            while(testCases-- > 0 )

            {

                // total hashtable entries

                int paidChars = Reader.nextInt();

               

                // total cents

                double ttlCents = 0;

               

                HashMap<Character , Integer> map = new HashMap<>();

               

                //loop through and fill the hashmap

                while(paidChars-- > 0 )

                {

                    // read the name value pair line and tokenize it

                    StringTokenizer st =  new StringTokenizer(Reader.reader.readLine());

                   

                    // fill the hashmap with  name  value tokens

                    map.put(st.nextToken().charAt(0), Integer.parseInt(st.nextToken()));

                   

                }

               

                //number of lines of text

                long ttlLines =  Reader.nextInt();

               

                //loop through and evaluate the characters in text for total money

                //raised by the autor of text

                while(ttlLines-- > 0 )

                {

                    String line = Reader.reader.readLine();

                    char arrayOfChars [] =  line.toCharArray();

                   

                    //for each character as key , validate the hashmap and update total dollars earned

                    for(char c : arrayOfChars)

                    {

                        if(map.containsKey(c))

                        {

                            ttlCents += map.get(c);

                        }

                    }

                }

               

           

           

                //show the dollars earned

                System.out.printf("%.2f$\n" , ttlCents/100);

            }

           

       }

   

 }

     /** Class for buffered reading int and double values */ 

     /** http://www.cpe.ku.ac.th/~jim/java-io.html */ 

     class Reader { 

          static BufferedReader reader; 

          static StringTokenizer tokenizer; 

          /** call this method to initialize reader for InputStream */ 

          static void init(InputStream input) { 

               reader = new BufferedReader(new InputStreamReader(input)); 

               tokenizer = new StringTokenizer(""); 

          } 

          /** get next word */ 

          static String next() throws IOException { 

               while (!tokenizer.hasMoreTokens()) { 

                    tokenizer = new StringTokenizer(reader.readLine()); 

               } 

               return tokenizer.nextToken(); 

          } 

          static int nextInt() throws IOException { 

               return Integer.parseInt(next()); 

          } 

          static double nextDouble() throws IOException { 

               return Double.parseDouble(next()); 

          } 

     }