Removing duplicates

package duplicates;
import java.io.*;
import java.util.*;
import javax.swing.JOptionPane;
public class Nodups {
/**
* @Michael Gagala
* ver 1.0
* This program will read in a strings from an input file, and
* printed the strings in a sorted order with duplicates removed
* 15 Aug 2009
*/
public static void main(String[] args) {
String file = “”;
boolean done = false;
int count = 0;
int tsCount = 0;
ArrayList wds = new ArrayList ();
TreeSet ts = new TreeSet(wds);
do{
try{
file = JOptionPane.showInputDialog(“Enter the name of the file.”);
FileReader dataFile = new FileReader(file);
Scanner sc = new Scanner(dataFile);
while(sc.hasNext()){
String aLine = sc.next();
wds.add(aLine);
count++;
}
ts.addAll(wds);
tsCount = ts.size();
Iterator it = ts.iterator();
while(it.hasNext()){
System.out.println(it.next());
}
System.out.println(“\nThere were ” + count + ” words in the orginal file.”);
System.out.println(“\nThere were ” + tsCount + ” words in the sorted file.”);
done = true;
}//close try
catch (FileNotFoundException e){
System.out.println(“File not found, please re-enter.”);
}//close catch
}//close do
while(!done);
}//close main
}//close class

Prims.java

import java.io.*;
import java.util.*;
/**
* @Michael Gagala
* Implement Prim’s Algorithm
* 9 November2009
* ver 1.0
**/
class Graph {
int gph[][];
int vtx;
int edg;
void createGraph(String file) throws FileNotFoundException {
int vtx1;
int vtx2;
int wt;
try{
FileReader dataFile = new FileReader(file);
Scanner sc = new Scanner(dataFile);
vtx = sc.nextInt();
edg = sc.nextInt();
gph = new int[vtx + 1][vtx + 1];
for (int i = 1; i <= vtx; i++)
for (int j = 1; j <= vtx; j++)
gph[i][j] = 0;
for (int i = 1; i <= edg; i++) {
vtx1 = sc.nextInt();
vtx2 = sc.nextInt();
wt = sc.nextInt();
gph[vtx1][vtx2] = gph[vtx2][vtx1] = wt;
}
}
catch (FileNotFoundException e){
System.out.println(“Please check classpath, and re-enter.”);
}
}// close createGraph
void prim() {
int curpth[], pth[], visited[];
int current;
curpth = new int[vtx + 1];
pth = new int[vtx + 1];
visited = new int[vtx + 1];
for (int i = 1; i <= vtx; i++) {
curpth[i] = 255;
pth[i] = visited[i] = 0;
}
current = 1;
curpth[current] = 0;
visited[current] = 1;
int j = 1;
while (j != vtx) {
for (int i = 1; i <= vtx; i++) {
if (gph[current][i] != 0 && visited[i] != 1)
if (gph[current][i] < curpth[i]) {
curpth[i] = gph[current][i];
pth[i] = current;
}
}
int min = 255;
for (int i = 1; i <= vtx; i++) {
if (visited[i] != 1)
if (curpth[i] < min) {
min = curpth[i];
current = i;
}
}
visited[current] = 1;
j = j + 1;
}
int mincost = 0;
for (int i = 1; i <= vtx; i++)
mincost = mincost + curpth[i];
System.out.println(“\n The minimum cost: ” + mincost);
}// close prim
}// close Graph
public class prims {
public static void main(String[] args) throws FileNotFoundException {
try{
String file = args[0];
Graph g = new Graph();
g.createGraph(file);
g.prim();
}
catch (FileNotFoundException e){
System.out.println(“Please check classpath, and re-enter.”);
}
}// close main
}// close prims

Gambler.java

/*************************************************************************
 *  Compilation:  javac Gambler.java
 *  Execution:    java Gambler stake goal N
 *  
 *  Simulates a gambler who start with $stake and place fair $1 bets
 *  until she goes broke or reach $goal. Keeps track of the number of
 *  times she wins and the number of bets she makes. Run the experiment N
 *  times, averages the results, and prints them out.
 *
 *  % java Gambler 50 250 1000
 *  Percent of games won = 19.0
 *  Avg # bets            = 9676.302
 *
 *  % java Gambler 50 150 1000
 *  Percent of games won = 31.9
 *  Avg # bets            = 4912.13
 *
 *  % java Gambler 50 100 1000
 *  Percent of games won = 49.6
 *  Avg # bets            = 2652.352

*
 *************************************************************************/

public class Gambler { 

    public static void main(String[] args) {
        int stake = Integer.parseInt(args[0]);    // gambler's stating bankroll
        int goal  = Integer.parseInt(args[1]);    // gambler's desired bankroll
        int T     = Integer.parseInt(args[2]);    // number of trials to perform

        int bets = 0;        // total number of bets made
        int wins = 0;        // total number of games won

        // repeat N times
        for (int t = 0; t < T; t++) {

            // do one gambler's ruin simulation
            int cash = stake;
            while (cash > 0 && cash < goal) {
                bets++;
                if (Math.random() < 0.5) cash++;     // win $1
                else                     cash--;     // lose $1
            }
            if (cash == goal) wins++;                // did gambler go achieve desired goal?
        }

        // print results
        System.out.println(wins + " wins of " + T);
        System.out.println("Percent of games won = " + 100.0 * wins / T);
        System.out.println("Avg # bets           = " + 1.0 * bets / T);
    }

} 

PowersOfTwo.java

/*************************************************************************
 *  Compilation:  javac PowersOfTwo.java
 *  Execution:    java PowersOfTwo N
 *  
 *  This program takes a command-line argument N and prnts a table of
 *  the powers of 2 that are less than or equal to 2^N.
 *
 *  % java PowersOfTwo 5
 *  0 1
 *  1 2
 *  2 4
 *  3 8
 *  4 16
 *  5 32
 *
 *  % java PowersOfTwo 6
 *  0 1
 *  1 2
 *  2 4
 *  3 8
 *  4 16
 *  5 32
 *  6 64
 *
 *  Remarks
 *  ------------
 *  Only works if 0 <= N < 31 since 2^31 overflows an int.
 *
 *************************************************************************/

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

        // read in one command-line argument
        int N = Integer.parseInt(args[0]);

        int i = 0;                // count from 0 to N-1
        int powerOfTwo = 1;       // the ith power of two

        // repeat until i equals N
        while (i <= N) {
            System.out.println(i + " " + powerOfTwo);  // print out the power of two
            powerOfTwo = 2 * powerOfTwo;               // double to get the next one
            i = i + 1;
        }

    }
}

Factors.java

/*************************************************************************
 *  Compilation:  javac Factors.java
 *  Execution:    java Factors N
 *  
 *  Computes the prime factorization of N using brute force.
 *
 *   % java Factors 81
 *   The prime factorization of 81 is: 3 3 3 3 
 *
 *   % java Factors 168
 *   The prime factorization of 168 is: 2 2 2 3 7
 *
 *   % java Factors 4444444444
 *   The prime factorization of 4444444444 is: 2 2 11 41 271 9091 
 *
 *   % java Factors 4444444444444463
 *   The prime factorization of 4444444444444463 is: 4444444444444463
 * 
 *   % java Factors 10000001400000049
 *   The prime factorization of 10000001400000049 is: 100000007 100000007 
 *
 *   % java Factors 1000000014000000049
 *   The prime factorization of 1000000014000000049 is: 1000000007 1000000007
 *
 *   % java Factors 9201111169755555649
 *   The prime factorization of 9201111169755555649 is: 3033333343 3033333343 
 *
 *   Can use these for timing tests - biggest 3, 6, 9, 12, 15, and 18 digit primes
 *   % java Factors 997
 *   % java Factors 999983
 *   % java Factors 999999937
 *   % java Factors 999999999989
 *   % java Factors 999999999999989
 *   % java Factors 999999999999999989
 *
 *   Remarks
 *   -------
 *   - Tests i <= N / i instead of i <= N for efficiency.
 *
 *   - The last two examples still take a few minutes.
 *
 *   - Tests i <= N / i instead of i * i <= N  to stave off overflow
 *     and enable us to factor 9201111169755555649; otherwise program
 *     goes into infinite loop. However, i * i <= N is almost twice
 *     as fast on some systems.
 *
 *************************************************************************/

public class Factors {

    public static void main(String[] args) { 

        // command-line argument
        long n = Long.parseLong(args[0]);

        System.out.print("The prime factorization of " + n + " is: ");

        // for each potential factor i
        for (long i = 2; i <= n / i; i++) {

            // if i is a factor of N, repeatedly divide it out
            while (n % i == 0) {
                System.out.print(i + " "); 
                n = n / i;
            }
        }

        // if biggest factor occurs only once, n > 1
        if (n > 1) System.out.println(n);
        else       System.out.println();
    }
}

Harmonic.java

/*************************************************************************
 *  Compilation:  javac Harmonic.java
 *  Execution:    java Harmonic N
 *  
 *  Prints the Nth harmonic number: 1/1 + 1/2 + ... + 1/N.
 * 
 *  % java Harmonic 10
 *  2.9289682539682538
 *
 *  % java Harmonic 10000
 *  9.787606036044348
 *
 *************************************************************************/

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

        // command-line argument
        int N = Integer.parseInt(args[0]);

        // compute 1/1 + 1/2 + 1/3 + ... + 1/N
        double sum = 0.0;
        for (int i = 1; i <= N; i++) {
            sum += 1.0 / i;
        }

        // print out Nth harmonic number
        System.out.println(sum);
    }

}

Converting an integer to binary string - Binary.java

/*************************************************************************
 *  Compilation:  javac Binary.java
 *  Execution:    java Binary n
 *  
 *  Prints out n in binary.
 * 
 *  % java Binary 5
 *  101
 *
 *  % java Binary 106
 *  1101010
 *
 *  % java Binary 0
 *  0
 * 
 *  % java Binary 16
 *  10000
 *
 *  Limitations
 *  -----------
 *  Does not handle negative integers.
 *
 *  Remarks
 *  -------
 *  could use Integer.toBinaryString(N) instead.
 *
 *************************************************************************/

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

        // read in the command-line argument
        int n = Integer.parseInt(args[0]);

        // set v to the largest power of two that is <= n
        int v = 1;
        while (v <= n/2) {
            v = v * 2;
        }
  
        // check for presence of powers of 2 in n, from largest to smallest
        while (v > 0) {

            // v is not present in n 
            if (n < v) {
                System.out.print(0);
            }

            // v is present in n, so remove v from n
            else {
                System.out.print(1);
                n = n - v;
            }

            // next smallest power of 2
            v = v / 2;
        }

        System.out.println();

    }

}

Though written a program, we can use inbuilt lib of java - See here.

Input functions in java (UDFs)

Inputing strings
public int inputInt() throws IOException
{
    int k=0;
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String str;
    str = br.readLine();
    k = Integer.parseInt(str);
    return k;
           
}
For inputing integers
public int inputInt() throws IOException
{
    int k=0;
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String str;
    str = br.readLine();
    k = Integer.parseInt(str);
    return k;
           
}

LCS in java

/**  Reads in two strings from stdin and computes their longest
 *  common subsequence.

see inputString function here. 

------------------------------------------------------------------*/  

public class LCS {

    public static void main(String[] args) {
        String x = inputString();
        String y = inputString();
        int M = x.length();
        int N = y.length();

        // opt[i][j] = length of LCS of x[i..M] and y[j..N]
        int[][] opt = new int[M+1][N+1];

        // compute length of LCS and all subproblems via dynamic programming
        for (int i = M-1; i >= 0; i--) {
            for (int j = N-1; j >= 0; j--) {
                if (x.charAt(i) == y.charAt(j))
                    opt[i][j] = opt[i+1][j+1] + 1;
                else 
                    opt[i][j] = Math.max(opt[i+1][j], opt[i][j+1]);
            }
        }

        // recover LCS itself and print it to standard output
        int i = 0, j = 0;
        while(i < M && j < N) {
            if (x.charAt(i) == y.charAt(j)) {
                System.out.print(x.charAt(i));
                i++;
                j++;
            }
            else if (opt[i+1][j] >= opt[i][j+1]) i++;
            else                                 j++;
        }
        System.out.println();

    }

}

Input or read in java from Standard IO

Lets first see what we mean by standard stream in java. Click here.

1. Using scanner
   
   To read console input, you first construct a Scanner that is attached to the "standard input stream" System.in.
   

   Scanner in = new Scanner(System.in);
   
   

   
   
   Now you use the various methods of the Scanner class to read input. For example, the nextLine method reads a line of input.
   
   
   
   

   System.out.print("What is your name? ");
   String name = in.nextLine();
   

   
   
   Here, we use the nextLine method because the input might contain spaces. To read a single word (delimited by whitespace), call
   
   
   

   String firstName = in.next();
   
   

   
   
   To read an integer, use the nextInt method.
   
   

   System.out.print("How old are you? "); 
   int age = in.nextInt();
   

   
   
   Similarly, the nextdouble method reads the next floating-point number.
   
   Finally, add the line
   
   
   
   
   

   import java.util.*;
   

   
   
   
   
2. 
   
   Using JOptionPane
   
   
   
   
   

   String input = JOptionPane.showInputDialog(promptString)

   
   

   eg.

   
   

   String name = JOptionPane.showInputDialog("What is your name?");

   
   

   Entering Integers

   String name = JOptionPane.showInputDialog("What is your age?");
   int age = Integer.parseInt(input);
   
   Import 
   import javax.swing.*;

   
   

   Finally, whenever your program calls JOptionPane.showInputDialog, you need to end it with a call to System.exit(0). The reason is a bit technical. Showing a dialog box starts a new thread of control. When themain method exits, the new thread does not automatically terminate. Toend all threads, you call the System.exit method.

   
   
   
   
3. Using BufferedReader Its most commonly used constructor is shown here:
   
   BufferedReader(Reader inputReader)
   Here, inputReader is the stream that is linked to the instance of BufferedReader that is being created. Reader is an abstract class. One of its concrete subclasses is InputStreamReader, which converts bytes to characters. To obtain an InputStreamReader object that is linked to System.in, use the following constructor:
   InputStreamReader(InputStream inputStream)
   
   So basic step is :
   
   

   InputStreamReader inp = new InputStreamReader(System.in)
   BufferedReader br = new BufferedReader(inp);

   
   Now to read character :
   
   

   char c = br.read();

   
   To read String:
   
   

   String str = br.readLine();

   
   
   
   
   
   
   • Reading Characters
     int read( ) throws IOException
     Each time that read( ) is called, it reads a character from the input stream and returns it
     as an integer value. It returns –1 when the end of the stream is encountered. As you can
     see, it can throw an IOException.
     
     
     

     char c;
     BufferedReader br = new
     BufferedReader(new InputStreamReader(System.in));
     c = (char) br.read();
     System.out.println(c)
     

     
     
     
     
   • Reading strings
     String readLine( ) throws IOException
     
     
     

     BufferedReader br = new BufferedReader(new
     InputStreamReader(System.in));
     String str;
     str = br.readLine();
     

     
     

Formatting output in java