Code Packet

From Progteam

Revision as of 23:21, 23 October 2008 by Mlc413 (Talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

This should really be split into many articles, but for now, it's all spewed here.

Contents

Area and Centroid

//Requires Graham.java
import java.awt.*;  //Point
import java.util.*; //Vector, Iterator

public double Area(Vector hull){
	//this will calculate the area of any polygon
	//with it's points listed clockwise or
	//counterclockwisein hull.
	//It will even work for cancave polygons
	Point p, p2;
	Iterator i = hull.iterator();
	double area = 0;
	if (hull != null && !hull.isEmpty()){
		i = hull.iterator();
		p = (Point)i.next();
		while (i.hasNext()){
			p2 = (Point)i.next();
			area += p.x * p2.y; // area of polygon
			area -= p.y * p2.x; // formula
			p = p2;
		}
		//last edge
		p2 = (Point)CH.get(0);
		area += p.x * p2.y; // area of polygon
		area -= p.y * p2.x; // formula
		area /= 2.0;
	}
	return Math.abs(area);
}
	
public Point Centroid(Vector hull){
	//this will calculate the centroid of any polygon
	//with it's points listed clockwise or
	//counterclockwise in hull.
	//A centroid is the "center of mass" of a polygon.
	//That is, the aveage point.
	Point p, p2, centroid;
	centroid = new Point(0,0);
	Iterator i = hull.iterator();
	double area = 0;
	if (hull != null && !hull.isEmpty()){
		i = hull.iterator();
		p = (Point)i.next();
		while (i.hasNext()){
			p2 = (Point)i.next();
			centroid.x+=(p.x+p2.x)*(p.x*p2.y-p2.x*p.y); //centroid
			centroid.y+=(p.y+p2.y)*(p.x*p2.y-p2.x*p.y); //formula
			p = p2;
		}
		//last edge
		p2 = (Point)CH.get(0);
		centroid.x+=(p.x+p2.x)*(p.x*p2.y-p2.x*p.y); //centroid
		centroid.y+=(p.y+p2.y)*(p.x*p2.y-p2.x*p.y); //formula
		centroid.x /= 6*Area(hull);
		centroid.y /= 6*Area(hull);
	}
	return centroid;
}

Closest Points

// Find closest pair of points in the plane
// Only needed if naive O(n^2) algorithm is too slow 
// Requires MergeSort (should be included with this)
// by Prof. Sartaj Sahni or his students?

public class ClosestPoints
{
   // top-level nested classes
   /** point in 2D */
   public static class Point
   {
      // data members
      double x, y;    // point coordinates

      // constructor
      public Point(double theX, double theY)
      {
         x = theX;
         y = theY;
      }
   }

   /** point with id, implements Comparable using x-coordinates */
   public static class Point1 extends Point
                       implements Comparable
   {
      // data member
      int id;         // point identifier
     
      // constructor
      public Point1(double theX, double theY, int theID)
      {
         super(theX, theY);
         id = theID;
      }

      public int compareTo(Object x)
      {
         double xx = ((Point1) x).x;
         if (this.x < xx)
            return -1;
         if (this.x == xx)
            return 0;
         return 1;
      }
   
      public boolean equals(Object x)
         {return this.x == ((Point1) x).x;}
   }

   /** point with an integer field, implements Comparable using y-coordinates */
   public static class Point2 extends Point
                       implements Comparable
   {
      int p;          // index to same point in array X

      // constructor
      public Point2(double theX, double theY, int theP)
      {
         super(theX, theY);
         p = theP;
      }

      public int compareTo(Object x)
      {
         double xy = ((Point2) x).y;
         if (this.y < xy)
            return -1;
         if (this.y == xy)
            return 0;
         return 1;
      }
   
      /** @return true iff this.y == x.y */
      public boolean equals(Object x)
         {return this.y == ((Point2) x).y;}
   }

   /** pairs of points and their distance */
   public static class PointPair
   {
      // data members
      Point1 a;       // one of the points
      Point1 b;       // the other point
      double dist;   // distance between a and b

      // constructor
      public PointPair(Point1 theA, Point1 theB, double theDist)
      {
         a = theA;
         b = theB;
         dist = theDist;
      }
   }
   
   /** @return distance between points u and v */
   public static double dist(Point u, Point v)
   {
      double dx = u.x - v.x;
      double dy = u.y - v.y;
      return Math.sqrt(dx * dx + dy * dy);
   }
   
   /** @param x[l:r] points sorted by x-coordinate, r > l
     * @param y[l:r] points sorted by y-coordinate
     * @param z[l:r] is used for work space
     * @return closest pair of points in x[l:r] */
   private static PointPair closestPair(Point1 [] x, Point2 [] y,
                                    Point2 [] z, int l, int r)
   {
      if (r - l == 1)  // only two points
         return new PointPair(x[l], x[r], dist(x[l], x[r]));
   
      if (r - l == 2)
      {// three points
         // compute distance between all pairs
         double d1 = dist(x[l], x[l + 1]);
         double d2 = dist(x[l + 1], x[r]);
         double d3 = dist(x[l], x[r]);
         // find closest pair
         if (d1 <= d2 && d1 <= d3)
            return new PointPair(x[l], x[l + 1], d1);
         if (d2 <= d3)
            return new PointPair(x[l + 1], x[r], d2);
         else
            return new PointPair(x[l], x[r], d3);
      }
   
      // more than three points, divide into two
      int m = (l + r) / 2;    // x[l:m] in A, rest in B
   
      // create sorted-by-y lists in z[l:m] & z[m+1:r]
      int f = l,      // cursor for z[l:m]
          g = m + 1;  // cursor for z[m+1:r]
      for (int i = l; i <= r; i++)
         if (y[i].p > m) z[g++] = y[i];
         else z[f++] = y[i];
   
      // solve the two parts
      PointPair best = closestPair(x, z, y, l, m);
      PointPair right = closestPair(x, z, y, m + 1, r);
   
      // make best closer pair of the two
      if (right.dist < best.dist)
         best = right;
   
      MergeSort.merge(z, y, l, m, r);   // reconstruct y
   
      // put points within best.d of midpoint in z
      int k = l;                        // cursor for z
      for (int i = l; i <= r; i++)
         if (Math.abs(x[m].x - y[i].x) < best.dist)
            z[k++] = y[i];
   
      // search for closer category 3 pair
      // by checking all pairs from z[l:k-1]
      for (int i = l; i < k; i++)
      {
         for (int j = i + 1; j < k && z[j].y - z[i].y < best.dist; j++)
         {
            double dp = dist(z[i], z[j]);
            if (dp < best.dist) // closer pair found
               best = new PointPair(x[z[i].p], x[z[j].p], dp);
         }
      }
      return best;
   }
   
   /** @return closest pair of points in array x 
     * @return null if fewer than two points in x */
   public static PointPair closestPair(Point1 [] x)
   {
      if (x.length < 2) return null;
   
      // sort on x-coordinate
      MergeSort.mergeSort(x);
   
      // create a point array sorted on y-coordinate
      Point2 [] y = new Point2 [x.length];
      for (int i = 0; i < x.length; i++)
         // copy point i from x to y and index it
         y[i] = new Point2(x[i].x, x[i].y, i);
      MergeSort.mergeSort(y);  // sort on y-coordinate
   
      // create a temporary array
      Point2 [] z = new Point2 [x.length];
   
      // find closest pair
      return closestPair(x, y, z, 0, x.length - 1);
   }
   
   /** test program */
   public static void main(String [] args)
   {
      // define the input stream to be the standard input stream
      MyInputStream keyboard = new MyInputStream();

      System.out.println("Enter number of points");
      int n = keyboard.readInteger();
      Point1 [] x = new Point1 [n];

      for (int i = 0; i < n; i++)
      {
         System.out.println("Enter point " + (i + 1));
         double xcoord = keyboard.readDouble();
         double ycoord = keyboard.readDouble();
         x[i] = new Point1(xcoord, ycoord, i + 1);
      }

      PointPair best = closestPair(x);
      System.out.println("Closest points are " + best.a.id +
                         " and " + best.b.id);
      System.out.println("Their distance is " + best.dist);
   }
}

Euclid

//GCD, LCM, DIOPHANTINE AX+BY=GCD, CHINESE REMAINDER THEOREM
//This code can be changed, very easily, to handle longs 
//For ACM-ICPC Programming Teams
//Kevin Lawler, kevin.lawler@cs.nyu.edu

import java.util.*;
import java.io.*;

public class Euclid
{

//GREATEST COMMON DIVISOR
public int gcd(int a, int b) 
{ 
   if(a < 0) a *= -1;
   if(b < 0) b *= -1;
  
   if (a < b) {int t = a; a = b; b = t;} 

   if (b == 0) return a;
   else return(gcd(b, a % b));
}

//LEAST COMMON MULTIPLE, uses fact ab = gcd(a,b)*lcm(a,b)
public int lcm(int a, int b) 
{
  if (a == 0 || b == 0)
   return 0;

  int t = (a / gcd(a,b)) * b;
  if (t<0) t *= -1;
 
  return t;
}

//Solves DIOPHANTINE EQUATIONS of the form ax + by = gcd(a,b),
//including negative inputs. Returns String "x,y"

public String dio(int a, int b)
{ if(a == 0 && b == 0) return "0,0";
  if(a == 0) return new String("0," + gcd(a,b) / b);                                  
  if(b == 0) return new String(gcd(a,b) / a + ",0");

  int [] q = new int [99]; //we can do this because (long) size is capped
  int [] r = new int [99]; //copy-paste
  int [] x = new int [99];
  int [] y = new int [99];
  int [] n = new int [99];

  if (a >= 0) n[0] = a;
   else n[0] = -a;
  if (b >=0) n[1] = b;
   else n[1] = -b;
 
  x[0] = 1; y[0] = 0;
  x[1] = 0; y[1] = 1;
    
  int i;
  for(i=0; n[i+1] != 0; i++)
  { q[i+1] = n[i] / n[i+1];
    r[i+1] = n[i] % n[i+1];
    n[i+2] = r[i+1];
    if(i > 0)
    { x[i+1] = x[i-1] - (q[i] * x[i]);
      y[i+1] = y[i-1] - (q[i] * y[i]);
    }   
  } 

 if(a < 0) x[i] *= -1;
 if(b < 0) y[i] *= -1;

 return new String(x[i] + "," + y[i]);
}

//CHINESE REMAINDER THEOREM: solves simultaneous linear congruences, i.e.,
//where n = v_0 mod m_0, n = v_1 mod m_1, etc.
//Handles positive, pairwise coprime mods. Will try, but might
//return -1, on anything else. vals.length obviously == mods.length.

public int crt(int [] vals, int [] mods)  //Relies on LCM & DIO  
{
  int n = 0;
  int bigprod = 1;
  
  for (int i=0; i < mods.length; i++)
   bigprod = lcm(bigprod, mods[i]);  

  for (int i=0; i < vals.length; i++) // Handles negative vals
   if (vals[i] < 0)
    vals[i] = mods[i] + vals[i];


  for (int i=0; i < mods.length; i++)
  { String [] str = dio(bigprod / mods[i], mods[i]).split(",");
    int inverse = Integer.parseInt(str[0]);   //Long.parseLong(str[0]);
    n += (bigprod/mods[i]) * inverse * vals[i];
    n %= bigprod;
  }


for (int i=0; i < mods.length; i++)
 if (n % mods[i] != vals[i] % mods[i])
  return -1;

return n;
}




public void doStuff() throws Exception
{
  //BufferedReader fin = new BufferedReader(new FileReader("euclid.in"));
  //PrintWriter fout = new PrintWriter(new FileWriter("euclid.out"));

  Random r = new Random();
  
  for (int k=0; k <= 20; k++)
  {
    int i = r.nextInt(101);
    int j = r.nextInt(101);
    System.out.println(i + "," + j + " gcd:" + gcd(i,j) + ", lcm:" + lcm(i,j) + ", dio:" + dio(i,j));
  }

  int [] v = {6, 5, 2};
  int [] m = {10, 11, 13};
  System.out.println(crt(v, m));

  int [] u = {3, 2}; //no soln
  int [] n = {9, 6};
  System.out.println(crt(u, n));

  int [] x = {2, 3, 2}; 
  int [] y = {3, 5, 7};
  System.out.println(crt(x, y));



  //fin.close();
  //fout.close();

}


public static void main (String [] args) throws Exception
{Euclid e = new Euclid(); e.doStuff();}

}

Pre-Flow Algorithm

// Pre-Flow algorithm implemented by Chien-I Liao
// Problem: Given a directed graph, a source node s and a sink node t
//          Find the maximum flow value from s to t
// Input: g is the adjacency matrix of the graph
//        s is the index of sourse node
//        t is the index of sink node
//        N in the number of nodes
// Return Value: The maximum flow value, 
//               the flow matrix is recored in local matrix f[][]

import java.io.*;
import java.util.*;

class Main{
	int flow(int [][] g, int s, int t, int N){
		int [] h= new int[N];
		int [] c= new int[N];
		int [][] f= new int[N][N];
		int [][] e= new int[N][N];
		int [] ne= new int [N];
		int i,j,tot,node,next,r;
		int [] q = new int [N*N*10];
		int st,ed;
		for(i=0;i<N;i++){
			h[i]=c[i]=ne[i]=0;
			for(j=0;j<N;j++)
				f[i][j]=0;
		}
		for(i=0;i<N;i++){
			for(j=0;j<N;j++){
				if(g[i][j]>0){
					e[i][ne[i]]=j;
					ne[i]++;
				}
			}
		}
		h[s]=N;
		tot=0;
		st=ed=0;
		for(i=0;i<ne[s];i++){
			tot+=g[s][e[s][i]];
			if(c[e[s][i]]==0 && e[s][i]!=t){
				q[ed]=e[s][i];
				ed++;
			}
			c[e[s][i]]+=g[s][e[s][i]];
			f[s][e[s][i]]+=g[s][e[s][i]];
			f[e[s][i]][s]-=g[s][e[s][i]];
		}
		c[s]=-tot;
		while(st!=ed){
			node=q[st];
			st++;
			while(c[node]>0){
				next=Integer.MAX_VALUE;
				for(i=0;i<N;i++){
					if(h[node]-h[i]==1 && g[node][i]>f[node][i]){
						if(c[i]==0 && i!=s && i!=t){
							q[ed]=i;
							ed++;
						}
						r=g[node][i]-f[node][i];
						if(c[node]<r)
							r=c[node];
						f[i][node]-=r;
						f[node][i]+=r;
						c[node]-=r;
						c[i]+=r;
					}
					else if(h[node]<=h[i] && h[i]<next &&  node!=i)
						next=h[i];
				}
				if(c[node]==0)
					break;
				else
					h[node]=next+1;
			}
		}
		return c[t];
	}

	void doStuff(){
		Scanner in = new Scanner(System.in);
		int V = in.nextInt();
		int [][] g = new int [V][V];
		for(int i=0;i<V;i++){
			for(int j=0;j<V;j++){
				g[i][j] = in.nextInt();
			}
		}
		System.out.println(flow(g,0,V-1,V));
	}
	public static void main(String argv[]) throws Exception{
		Main my = new Main();
		my.doStuff();
	}
}

Convex Hull

//CONVEX HULL
import java.util.*; //Vector, Stack, Iterator

    private static Vector Graham(Vector points){
        //Order points.size()*(2+log(points.size()) : logorithmic time
        Stack hull = new Stack();
        if (points.isEmpty()) return hull;
        Iterator i;
        Point anchor, next, top;
        anchor = getAnchor(points);
        QuickSort(anchor,points,0,points.size()-1); //n*lg(n) comparisons
        int i=1; //points.get(0) = anchor
        //remove colinear in anchor
        while( i < points.size()-1 ){ //n comparisons
            top = (Point)points.get(i);
            next = (Point)points.get(i+1);
            if ( angle( anchor , top , next ) == 0){
                if ( top == farther(anchor,top,next) ){
                    points.remove(next);
                }else{
                    points.remove(top);
                }
            }else{
                i++;
            }
        }
        if ( points.size() < 3 ){
            hull.addAll(points);
            return hull;
        }
        //find hull
        i = points.iterator();
        hull.push(anchor);
        hull.push(i.next());
        hull.push(i.next());
        while (i.hasNext()){ //n comparisons
            next = (Point)i.next();
            top = (Point)hull.pop();
            while ( angle((Point) hull.peek(), top, next ) >= 0 )
                top = (Point)hull.pop();
            //if top and next are colinear we take next, it is farther
            hull.push(top);
            hull.push(next);
        }
        return hull; //counterclockwise order
    }
    
    private static Vector Jarvis(Vector points){
        //Order points.size()*hull.size() : best case - linear , worst case - quadratic
        Vector hull = new Vector();
        if (points.isEmpty()) return hull;
        Point anchor, now, test;
        anchor = getAnchor(points);
        int turn;
        do{
            hull.addElement(anchor);
            now = (Point)points.get(0);
            for (int i=1;i<points.size();i++){ //n comparisons
                test = (Point)points.get(i);
                turn = angle(anchor,now,test);
                if ( turn < 0 ){
                    now = test;
                }else if ( turn == 0 ){
                    //take the farther
                    now = farther(anchor,now,test);
                }
            }
            //now is the point with the lowest polar coordinate to anchor
            anchor = now;
        }while( !anchor.equals(hull.get(0)) ); //h loops
        return hull; //counterclockwise order
    }

    private static int angle(Point a, Point b, Point c){
        //Order 1 : constant time
        //reorient as if a were the origin
        Point p1 = new Point( b.x - a.x , b.y - a.y );
        Point p2 = new Point( c.x - a.x , c.y - a.y );
        //compute the cross product
        int cp = p2.x*p1.y - p1.x*p2.y;
        //positive, right turn; negative, left turn; zero, colinear
        return cp; //signed area
    }
    
    private static Point getAnchor(Vector points){
        //Order points.size() : linear time
        //always the lowest, rightmost in a tie
        Point anchor, tmp;
        Iterator i = points.iterator();
        anchor = (Point)i.next();
        while ( i.hasNext() ){
            tmp = (Point)i.next();
            if ( anchor.getY() > tmp.getY() ){
                anchor = tmp;
            }else if ( anchor.getY() == tmp.getY()
                    && anchor.getX() > tmp.getX() ){
                anchor = tmp;
            }
        }
        return anchor;
    }
    
    private static void QuickSort(Point anchor, Vector S, int first, int last){
        // Order (last - first)*log(last-first) : logarithmic time
        //recursively sorts S between index first and last (called by Graham)
        //if anchor == getAnchor(S) then the result is that the points in S
        //are in polar order with respect to anchor and with anchor first.
        Point pivot;
        int scanDown, scanUp;
        if (first >= last){
            return;
        }
        pivot = (Point)S.get(last);
        if (pivot == anchor){
            //pivot cannot be the anchor, so put anchor in front and get new pivot
            pivot = (Point)S.set(first, S.set(last, S.get(first)));
        }
        scanUp = first;
        scanDown = last-1;
        while ( scanUp <= scanDown ){
            while ( scanUp <= scanDown && angle(anchor,(Point)S.get(scanUp),pivot) <= 0 ){
                scanUp++;
            }
            while ( scanUp <= scanDown && angle(anchor,(Point)S.get(scanDown),pivot) > 0 ){
                scanDown--;
            }
            if (scanUp < scanDown){
                //swap elements
                S.set(scanDown, S.set(scanUp, S.get(scanDown)));
            }
        }
        //insert the pivot
        S.set(last, S.get(scanUp));
        S.set(scanUp, pivot);
        if ( scanUp-first < last-scanUp ){
            //sort the smaller partition first (keeps stack small)
            QuickSort(anchor,S,first,scanUp-1);
            QuickSort(anchor,S,scanUp+1,last);
        }else{
            QuickSort(anchor,S,scanUp+1,last);
            QuickSort(anchor,S,first,scanUp-1);
        }
    }
    
    private static Point farther(Point anchor, Point a, Point b){
        //Order 1 : constant time
        //three colinear points
        //returns a or b farther from anchor
        double d1 = a.getX()-anchor.getX();
        double d2 = b.getX()-anchor.getX();
        if ( d1 < 0 ) d1 *= -1;
        if ( d2 < 0 ) d2 *= -1;
        if (d1 == d2){
            d1 = a.getY()-anchor.getY();
            d2 = b.getY()-anchor.getY();
            if ( d1 < 0 ) d1 *= -1;
            if ( d2 < 0 ) d2 *= -1;
        }
        if (d1 > d2)
            return a;
        return b;
    }

Graph

//GRAPH ALGORITHMS:
//SINGLE SOURCE SHORTEST PATH WITH FEWEST HOPS, COMPONENT BREAKDOWN,
//MINIMUM SPANNING TREE, "PATH FROM X TO Y?"
//For ACM-ICPC Programming Teams
//Kevin Lawler, kevin.lawler@cs.nyu.edu

//All these work on doubly-scripted adjacency matrices
//of varying types. Graphs are directed unless otherwise noted.
//Undirected graphs should be symmetric along the diagonal (no laziness)

import java.io.*;
import java.util.*;

public class Graph
{


//Returns an int [] where each index contains
//the component# of the corresponding vertex.
//component#s start numbering from 0 (vertex 0).
//This easily extends to paths, connectedness, etc.
public int [] components(boolean [][] g)
{
  int v = g.length;
  int [] c = new int [v];
  int curcom = -1;  
  for (int i=0; i < v; i++)
    c[i] = -1;

  for(int i=0; i < v; i++)
  { if (c[i] < 0)
    { curcom++;
      ArrayList a = new ArrayList();      
      a.add(new Integer(i));
      while(! a.isEmpty())
      { int guy = ((Integer) a.remove(0)).intValue();
	c[guy] = curcom;
        for (int j=0; j < v; j++)
         if (g[guy][j] && c[j] < 0)
           a.add(new Integer(j));
      }
    }
  }
return c;
}

public boolean isPath(boolean[][] g, int x, int y)
{
   int v = g.length;
   boolean [] visited = new boolean[v];
   visited[x] = true;
   ArrayList a = new ArrayList();
   a.add(new Integer(x));

   while(! a.isEmpty())
   {
     int cur = ((Integer) a.remove(0)).intValue();
     for (int i = 0; i < v; i++)
     { if(g[cur][i] && !visited[i])
         {visited[i] = true;
          a.add(new Integer(i));
	 }
     }     
     if (visited[y]) return true;
   }
   
  return false;
}


//Returns ArrayList of v-1 Strings of edges "weight,v1,v2"
//Assumes: int graph is connected & undirected
//Assumes: unconnected edges have weight Integer.MAX_VALUE
public ArrayList minSpanTree(int [][] z) 
{
  int v = z.length;
  int [][] g = new int[v][v];
  for (int i=0; i < v; i++)
  for (int j=0; j < v; j++)
  g[i][j] = z[i][j];

  boolean [][] dumb = new boolean [v][v];
  boolean [] used = new boolean [v];

  ArrayList w = new ArrayList();
  ArrayList e = new ArrayList();

  for(int i=0; i < v; i++)
  for(int j=i+1; j < v; j++) //ASSUME SYMMETRIC
   w.add(new Integer(g[i][j]));    
     
  Collections.sort(w);

  while(e.size() < v - 1)
  { int weight = ((Integer)w.remove(0)).intValue();
    int m = 0;
    while( g[m/v][m%v] != weight)
     m++;
    if (!isPath(dumb, m/v, m%v))
     {
      e.add(new String(weight + "," + (m/v) + "," + (m%v)));
      dumb[m/v][m%v] = true;
      dumb[m%v][m/v] = true;
     }     
    g[m/v][m%v] = Integer.MAX_VALUE;
    g[m%v][m/v] = Integer.MAX_VALUE;
  }

  return e;
}


//SINGLE SOURCE ALL DESTINATIONS DIRECTED SHORTEST PATH
//Returns an AL of Strings of size of set reachable from source 
//Each string i (start 0) contains a smallest weighted path,
//of the fewest hops, of the form:
//"DISTANCEOFPATH,source,p1,p2,...,i"
//Will not terminate on negative cycles
public ArrayList shortestPaths(int [][] g, int source)
{
  int v = g.length;
  int [] best = new int [v];
  int [] hops = new int [v];
  int [] previous = new int [v];

  for(int i =0; i < v; i++)
   best[i] = Integer.MAX_VALUE;

  best[source] = 0;
  hops[source] = 0;
  previous[source] = -1;
  
  ArrayList q = new ArrayList();
  q.add(new Integer(source));

  while(! q.isEmpty())
  {
    int curnode = ((Integer)q.remove(0)).intValue();     
    for (int i=0; i < v; i++)
    {
      if(g[curnode][i] < Integer.MAX_VALUE)
      if(best[curnode] + g[curnode][i] < best[i]
         || ( best[curnode] + g[curnode][i] == best[i]
         &&   hops[curnode] + 1 < hops[i] ))
       {
         q.add(new Integer(i)); 
         previous[i] = curnode;
         best[i] = best[curnode] + g[curnode][i];         
         hops[i] = hops[curnode] + 1;
       }
    }    
  } 

  ArrayList paths = new ArrayList();
 
  for (int i=0; i < v; i++)
  if(best[i] < Integer.MAX_VALUE)
  { int t = i;
    String str = (new Integer(best[i])).toString();
    str = str + "," + (new Integer(source)).toString();
  
    java.util.Stack s = new java.util.Stack(); //not Sahni Stacks...
    while(previous[t] != -1)
    { s.push(new Integer(t)); 
      t = previous[t];      
    }
   
    while(!s.empty()) 
     str = str + "," + s.pop().toString();
    paths.add(str);
  }   

  return paths;

}


public void doStuff() throws Exception
{ //BufferedReader fin = new BufferedReader(new FileReader("graph.in"));
  //PrintWriter fout = new PrintWriter( new FileWriter("graph.out"));

  boolean [][] g = new boolean[15][15];

  System.out.println(g.length); //g.length == 15;

  g[0][1] = true;
  g[0][2] = true;
  g[3][4] = true;
  g[4][5] = true;
  g[5][6] = true;
  g[5][7] = true;
  g[8][9] = true;
  g[10][10] = true;

  int [] c = components(g);

  for (int i=0; i < c.length; i++)
  System.out.println("Vertex " + i + " in component " + c[i]);

  System.out.println("Is path from 3 to 7?: " + isPath(g, 3, 7));
  System.out.println("Is path from 7 to 8?: " + isPath(g, 7, 8));

  int [][] h = new int [15][15];
  
  for (int i=0; i < 15; i++)
  for (int j=0; j < 15; j++)
   h[i][j] = Integer.MAX_VALUE;
  
  h[0][1] = 2;
  h[1][2] = 101;
  h[2][3] = 102;
  h[3][4] = 103;
  h[4][5] = 104;
  h[5][6] = 5;
  h[6][7] = 8;
  h[7][8] = 105;
  h[8][9] = 106;
  h[9][10] = 107;
  h[10][11] = 108;
  h[11][12] = 109;
  h[12][13] = 110;
  h[13][14] = 111;
  h[0][9] = 1;
  h[1][9] = 1;
  h[2][9] = 7;
  h[3][9] = 4;
  h[4][9] = 5;
  h[5][9] = 6;
  h[8][9] = 20;


  ArrayList t = minSpanTree(h);

  for (int i=0; i < t.size(); i++)
   System.out.println(t.get(i));
 
  System.out.println();

  ArrayList w = shortestPaths(h, 0);
  
  for (int i=0; i < w.size(); i++)
  System.out.println(w.get(i));


  //fin.close();
  //fout.close();
}

public static void main (String [] args) throws Exception
{Graph f = new Graph(); f.doStuff();}

}

Knapsack


//        0/1-KNAPSACK SOLVER
//Modification for 'unlimited' item 0/1-Knapsack:
//add d duplicates of each item i to the input,
//where d = (capacity / weight_i) - 1
//For ACM-ICPC Programming Teams
//Kevin Lawler, kevin.lawler@cs.nyu.edu

import java.io.*;
import java.util.*;

public class Knapsack
{

//Input is sack's capacity and AL of Strings of form "weight,profit"
//Returns a String of the form (items numbered from 0 on):
// "TOTALPROFIT,included_1, included_2,...,included_k"
public String solveSack(int capacity, ArrayList items)
{
   int n = items.size();
   int [] w = new int [n];
   int [] p = new int [n];
   
   for(int i=0; i < n; i++)
   { String[] str = ((String) items.get(i)).split(",");
     w[i] = Integer.parseInt(str[0]);
     p[i] = Integer.parseInt(str[1]);
   }
  
  int [][] table = new int[n][capacity + 1];  // PLUS 1 THROUGHOUT
  for(int i= w[0]; i < capacity + 1; i++) //w[0] != 0, chum!!!
   table[0][i] = p[0];

 for (int i=1; i < n; i++)
 for (int j=0; j < capacity + 1; j++)
 {
   if(j < w[i]) table[i][j] = table[i-1][j];  
   else
    table[i][j] = Math.max(table[i-1][j], p[i] + table[i-1][j-w[i]]);
 }

 String soln = new String(new Integer(table[n-1][capacity]).toString());

 java.util.Stack s = new java.util.Stack();

 for (int i=n-1; i > 0; i--) //TRACEBACK
  if(table[i-1][capacity] != table[i][capacity])
   { s.push(new Integer(i));
     capacity -= w[i];
   }

 if (table[0][capacity] > 0)
  s.push(new Integer(0));

 while(!s.empty())
  soln = soln + "," + ((Integer) s.pop()).toString();

 return soln;
}

public void doStuff() throws Exception
{ //BufferedReader fin = new BufferedReader(new FileReader("knapsack.in"));
  //PrintWriter fout = new PrintWriter(new FileWriter("knapsack.out"));

  ArrayList a = new ArrayList();

  a.add(new String("6,2"));
  a.add(new String("3,2"));
  a.add(new String("5,6"));
  a.add(new String("4,5"));
  a.add(new String("6,4"));

  for (int i=0; i <= 24; i++)
  System.out.println(i + ": " + solveSack(i, a));


  //fin.close();
  //fout.close();
}

public static void main (String [] args) throws Exception
{Knapsack k = new Knapsack(); k.doStuff(); }
}

Hungarian Algorithm

// Hungarian Algorithm to solve maximum matching problem
// Input:
// N = size of matrix
// S[N][N] = score matrix 
// S[i][j] = score gained when pairing girl i with boy j
// Match[N] = store the result of pairing 
// Output:
// return maximum total score
// The matching result will be stored in Match[N],
// i.e. Match[i]=j means you should pair girl i with boy j

import java.io.*;
import java.util.*;

class Main{
	int Hungarian_Algorithm(int N, int [][] S, int [] Match)
	{
		int i,j;
		int [][] g = new int [N][N];
		int [] u = new int[N];
		int [] v = new int[N];
		int [] s = new int[N];
		int [] t = new int[N];
		int ns=0;
		int nt=0;
		int [] use1 = new int [N];
		int [] use2 = new int [N];
		int [] from1= new int [N];
		int [] from2= new int [N];
		int [] match1 = new int [N];
		int [] match2 = new int [N];
		int MAX,oldMAX;
		int temp,pt1,pt2;
		int MINover;
		int total;

		for(i=0;i<N;i++){						// precaculate u[i] and v[i]
			u[i]=v[i]=0;
			for(j=0;j<N;j++){
				if(S[i][j]>u[i])
					u[i]=S[i][j];
			}
		}
		while(true){
			for(i=0;i<N;i++){					// initialize match graph
				for(j=0;j<N;j++){
					if(S[i][j]==u[i]+v[j])
						g[i][j]=1;
					else
						g[i][j]=0;
				}
			}
			MAX=0;
			for(i=0;i<N;i++){
				use1[i]=use2[i]=0;
				from1[i]=from2[i]=match1[i]=match2[i]=-1;
			}
			for(i=0;i<N;i++){					// Greedy Method for bipartite matching
				for(j=0;j<N;j++){
					if(use2[j]==1)
						continue;
					if(g[i][j]==1){
						match1[i]=j;
						match2[j]=i;
						use1[i]=1;
						use2[j]=1;
						MAX++;
						break;
					}
				}
			}
			while(true){							// Find augamenting path to improve matching
				ns=0;
				nt=0;
				oldMAX=MAX;
				for(i=0;i<N;i++){
					from2[i]=-1;
					if(use1[i]==0){
						s[ns]=i;
						ns++;
					}
					t[i]=0;
				}
				for(i=0;i<ns;i++){
					for(j=0;j<N;j++){
						if(g[s[i]][j]==1 && use2[j]==0){
							pt1=s[i];pt2=j;use2[j]=1;
							while(use1[pt1]==1){
								temp=match1[pt1];
								match1[pt1]=pt2;
								match2[pt2]=pt1;
								pt2=temp;
								pt1=from2[temp];
							}
							use1[pt1]=1;
							match1[pt1]=pt2;
							match2[pt2]=pt1;
							MAX++;
							i=ns;
							j=N;
							break;
						}
						if(g[s[i]][j]==1 && from2[j]==-1){
							t[nt]=j;
							nt++;
							from2[j]=s[i];
							s[ns]=match2[j];
							ns++;
						}
					}
					if(i==ns)
						break;
				}
				if(MAX==oldMAX)
					break;
			}
			if(MAX==N){								// Maximum achieved
				for(i=0;i<N;i++)
					Match[i]=match1[i];
				break;
			}
			for(i=0;i<N;i++){						// Find MINover to decrease total score
				use1[i]=1;
				use2[i]=0;
			}
			for(i=0;i<ns;i++)
				use1[s[i]]=0;
			for(i=0;i<nt;i++)
				use2[t[i]]=1;
			MINover=Integer.MAX_VALUE;
			for(i=0;i<N;i++)
				for(j=0;j<N;j++)
					if(use1[i]==0 && use2[j]==0 && u[i]+v[j]-S[i][j]<MINover)
						MINover=u[i]+v[j]-S[i][j];
			for(i=0;i<ns;i++)						// Update u[i] and v[i]
				u[s[i]]-=MINover;
			for(i=0;i<nt;i++)
				v[t[i]]+=MINover;
			total=0;
			for(i=0;i<N;i++){
				total+=u[i];
				total+=v[i];
			}
		}
		total=0;
		for(i=0;i<N;i++){
			total+=u[i];
			total+=v[i];
		}	
		return total;
	}

	void doStuff(){
		Scanner in = new Scanner(System.in);
		int i,j;
		while(in.hasNextInt()){
			int N=in.nextInt();
			int [][] map = new int[N][N];
			for(i=0;i<N;i++)
				for(j=0;j<N;j++)
					map[i][j]=in.nextInt();
			int [] match = new int [N];
			System.out.println("Score : " + Hungarian_Algorithm(N,map,match));
			System.out.print("Pairs formed :");
			for(i=0;i<N;i++)
				System.out.print(" ("+i+","+match[i]+")");
			System.out.println();
		}
	}
	public static void main(String argv[]) throws Exception{
		Main my = new Main();
		my.doStuff();
	}
}

Merge Sort


/** iterative merge sort */

public class MergeSort
{
   /** sort the elements a[0 : a.length - 1] using
     * the merge sort method */
   public static void mergeSort(Comparable [] a)
   {
      Comparable [] b = new Comparable [a.length];
      int segmentSize = 1;
      while (segmentSize < a.length)
      {
         mergePass(a, b, segmentSize); // merge from a to b
         segmentSize += segmentSize;
         mergePass(b, a, segmentSize); // merge from b to a
         segmentSize += segmentSize;
      }
   }

   /** merge adjacent segments from x to y */
   public static void mergePass(Comparable [] x, Comparable [] y,
                                int segmentSize)
   {
      int i = 0;   // start of the next segment
      while (i <= x.length - 2 * segmentSize)
      {// merge two adjacent segments from x to y
         merge(x, y, i, i + segmentSize - 1, i + 2 * segmentSize - 1);
         i = i + 2 * segmentSize;
      }
   
      // fewer than 2 full segments remain
      if (i + segmentSize < x.length)
         // 2 segments remain
         merge(x, y, i, i + segmentSize - 1, x.length - 1);
      else
         // 1 segment remains, copy to y
         for (int j = i; j < x.length; j++)
            y[j] = x[j];
   }
   
   /** merge two adjacent segments from c to d */
   public static void merge(Comparable [] c, Comparable [] d,
                 int startOfFirst, int endOfFirst, int endOfSecond)
   {
      int first = startOfFirst,       // cursor for first segment
          second = endOfFirst + 1,    // cursor for second
          result = startOfFirst;      // cursor for result
   
      // merge until one segment is done
      while ((first <= endOfFirst) && (second <= endOfSecond))
         if (c[first].compareTo(c[second]) <= 0)
            d[result++] = c[first++];
         else
            d[result++] = c[second++];
   
      // take care of leftovers
      if (first > endOfFirst)
         for (int q = second; q <= endOfSecond; q++)
             d[result++] = c[q];
      else
         for (int q = first; q <= endOfFirst; q++)
             d[result++] = c[q];
   }
   
   /** test program */
   public static void main(String [] args)
   {
      Integer [] a = {new Integer(3),
      new Integer(2), new Integer(4),
      new Integer(1), new Integer(6),
      new Integer(9), new Integer(8),
      new Integer(7), new Integer(5),
      new Integer(0)};

      // output elements to be sorted
      System.out.println("The elements are");
      for (int i = 0; i < a.length; i++)
         System.out.print(a[i] + " ");
      System.out.println();

      // sort the elements
      mergeSort(a);

      // output in sorted order
      System.out.println("The sorted order is");
      for (int i = 0; i < a.length; i++)
         System.out.print(a[i] + " ");
      System.out.println();
   }
}

Permutation

//Implementation of 'Generating All Permutations in Lexicographical Order'
//Found in Knuth, fascicle 2b - http://www-cs-faculty.stanford.edu/~knuth/fasc2b.ps.gz
//For ACM-ICPC Programming Teams
//Kevin Lawler, kevin.lawler@cs.nyu.edu

import java.io.*;
import java.util.*;

public class Perm
{

public void swap(ArrayList a, int x, int y)
{   Comparable temp = (Comparable) a.get(x);
    a.set(x, a.get(y));
    a.set(y, temp);
}


//note: this is a void, it makes "a" the next permutation lexicographically
public void nextperm (ArrayList a)  
{
  int n = a.size() - 1; 

  int j = n - 1;

  while (j > -1 && ((Comparable) a.get(j)).compareTo((Comparable) a.get(j+1)) >= 0)
   j--;

  if (j == -1) //In reverse lexicographical order
  {  for (int p=0; p <= (n / 2); p++)                //swap everything
      swap(a, p, n-p);
     return;
  }

   int l = n;  //The letter /ELL/ follows, not the numeral 1
   
   while (l > 0 && ((Comparable) a.get(j)).compareTo((Comparable) a.get(l)) >= 0)
    l--;	

   swap(a,j,l);

   int k = j + 1; //j + one
   l = n;
   while(k < l)
   { swap(a, k, l);
     k++;
     l--;
   }
}

public boolean inreverse(ArrayList a)
{int j = a.size() - 2;
 
 while (j > -1 && ((Comparable) a.get(j)).compareTo((Comparable) a.get(j+1)) >= 0)
   j--;

  if (j < 0)
   return true;
  return false;
}

public int fac(int n)
{
  if (n==1 || n == 0) return 1;
  else return (n * fac(n-1));
}

public void doStuff() throws Exception //exhibits fooling around with nextperm
{
	//BufferedReader fin = new BufferedReader(new FileReader("perm.in"));
	//PrintWriter fout = new PrintWriter(new FileWriter("perm.out"));

	ArrayList a = new ArrayList();

 	for (int i=0; i < 4; i++)
	  a.add(new Character((char)('A' + i)));

	System.out.println(a); //initial permutation
        
	for (int i=0; i < fac(4) + 2; i++) // will show THREE after reverse order 
        { 
          nextperm(a);
          System.out.println(a);
        }

        System.out.println("\n\n\n");
        a.clear();
       
        a.add(new Character('D'));
        a.add(new Character('C'));
        a.add(new Character('C'));
        a.add(new Character('B'));
        a.add(new Character('B'));
        a.add(new Character('B'));

        Collections.sort(a); //How To Sort an ArrayList

	System.out.println(a);

        while(!inreverse(a))
        { nextperm(a);
	  System.out.println(a);
        }

	System.out.println("And the wraparound...");

	nextperm(a);
	System.out.println(a);

	//fin.close();
	//fout.close();
}


public static void main (String [] args) throws Exception
{Perm c = new Perm(); c.doStuff();}

}


Personal tools