Sign up to create your own snipts, or login.

Public snipts » lijamez's snipts The latest snipts from lijamez.

showing 1-2 of 2 snipts
  • ∞ Deterministic Linear Time k-Select 
    import java.util.HashSet;

public class Main 
{
	/*
	 * BSelect by Blum, Floyd, Pratt, Rivest, Tarjon (1972)
	 * Written by James Li
	 * Thanks to professor Will Evans
	 */
	
	/*
	 * Pseudocode:
	 * 
	 * BSelect(A,k):
	 * 	If |A| == 1 return A[1]
	 * 	p = GoodPivot(A)
	 * 	S = { A[i] | A[i] < p }
	 * 	L = { A[i] | A[i] > p }
	 * 	If |S| >= k return BSelect(S,k)
	 * 	else if |S| == k-1 return p
	 * 	else return BSelect(L, k-|S|-1)
	 * 
	 * GoodPivot(A):
	 * 	Divide A into n/5 groups of 5 elements each
	 * 	Find the median of each group
	 * 	Use BSelect to find the median, p, of the n/5 medians
	 * 	Return p
	 */
	
	public static void main (String[] args)
	{
		Integer[] input = { -1,5,8,-3,4,7,2,90 }; //Some arbitrary Integer array
		int k = 8;
		System.out.println("The " + k + "th largest element in the input is " + BSelect(input, k));
	}
	
	/**
	 * Finds the median of an array in O(n^2) time.
	 * @param array An array of distinct integers
	 * @return The median
	 */
	static int median(Integer[] array)
	{
		if (array.length == 1)
		{
			return array[0];
		}
		int smallerCount = 0;
		
		for (int i = 0 ; i < array.length ; i++)
		{
			for (int j = 0 ; j < array.length ; j++)
			{
				if (array[i] < array[j])
				{
					smallerCount++;
				}
			}
			
			if (smallerCount == (array.length - 1)/2)
			{
				return array[i];
			}
			
			smallerCount = 0;
		}
		
		return -9999; //should never happen
		
	}
	
	/**
	 * Finds an integer that's somewhat close to the median of array. Runs in O(n) time.
	 * @param array An array of distinct integers
	 * @return An integer x in the array such that there are >= array.length/4 values greater than x and >= array.length/4 values less than x
	 */
	static int GoodPivot(Integer[] array)
	{		
		
		if (array.length == 1)
		{
			return array[0];
		}
			
		//Divide A into n/5 groups of 5 elements each
		int numGroups = array.length / 5;
		if (array.length % 5 > 0)
		{
			numGroups++;
		}
		
		Integer[] groupMedians = new Integer[numGroups];
		
		for (int i = 0 ; i < numGroups ; i++)
		{
			Integer[] subset;
			
			if(array.length % 5 > 0)
			{
				if (i == numGroups - 1)
				{
					subset = new Integer[array.length % 5];
				}
				else
				{
					subset = new Integer[5];
				}
			}
			else
			{
				subset = new Integer[5];
			}
			
			
			for (int j = 0; j < subset.length ; j++)
			{
				subset[j] = array[5*i+j];
				
			}
			
			//Find the median of each group
			groupMedians[i] = median(subset);
			
		}
		
		//Use BSelect to find the median, p, of the n/5 medians
		int goodPivot = BSelect(groupMedians, groupMedians.length/2 );
		
		return goodPivot;
		
	}
	
	/**
	 * BSelect by Blum, Floyd, Pratt, Rivest, Tarjon (1972)
	 * Finds the k-th largest value in array in O(n) time.
	 * @param array An array with distinct integers.
	 * @param k A number from 1 to array.length (inclusive)
	 * @return The k-th largest value in array
	 */
	static int BSelect(Integer[] array, int k)
	{
		if (array.length == 1)
		{
			return array[0];
		}
		
		int pivot = GoodPivot(array);
		
		HashSet<Integer> S = new HashSet<Integer>();
		HashSet<Integer> L = new HashSet<Integer>();
		
		for (int i = 0; i < array.length ; i++)
		{
			if (array[i] < pivot)
			{
				S.add(array[i]);
			}
			else if (array[i] > pivot)
			{
				L.add(array[i]);
			}
		}
		
		if (S.size() >= k)
		{
			return BSelect(S.toArray(new Integer[0]) ,k);
		}
		else if (S.size() == k-1)
		{
			return pivot;
		}
		else
		{
			return BSelect(L.toArray(new Integer[0]) , k - S.size() - 1);
		}

	}

}

    copy | embed

    0 comments - tagged in  posted by lijamez on Dec 03, 2009 at 6:37 a.m. EST
  • ∞ Conway's Game of Life in C++ 
    #include <iostream>
using namespace std;

//The Grid class of the game of life. The grid is a 2D array.
class Grid {
	int width, height;
	bool grid [1000][1000];
public:
	Grid(int, int);
	void nextFrame();
	void printFrame();
};

Grid::Grid(int a, int b) {
	height = a;
	width = b;
	
	//Presets of alive cells. Change these to whatever you wish.
	grid[0][1] = true;
	grid[1][2] = true;
	grid[2][0] = true;
	grid[2][1] = true;
	grid[2][2] = true;
	
}

/**
 Checks how many surrounding cells are alive for a cell and changes it depending on the game of life rules.
 The changes are stored in a temporary 2D array. Then, it is copied to the main grid array. 
**/
void Grid::nextFrame() {
	
	int numSurrounding = 0;
	bool tempGrid [height][width];
	
	for (int i = 0; i < height ; i++)
	{
		for (int j = 0; j < width ; j++)
		{
			if ( (i+1) < height && grid[i + 1][j] == true )
			{
				numSurrounding++;
			}
			if ( (i-1) >= 0 && grid[i - 1][j] == true )
			{
				numSurrounding++;
			}
			if ( (j+1) < width && grid[i][j+1] == true )
			{
				numSurrounding++;
			}
			if ( (j-1) >= 0 && grid[i][j-1] == true )
			{
				numSurrounding++;
			}
			if ( (i+1) < height && (j+1) < width && grid[i+1][j+1] == true )
			{
				numSurrounding++;
			}
			if ( (i+1) < height && (j-1) >= 0 && grid[i+1][j-1] == true )
			{
				numSurrounding++;
			}
			if ( (i-1) >= 0 && (j+1) < width && grid[i-1][j+1] == true )
			{
				numSurrounding++;
			}
			if ( (i-1) >= 0 && (j-1) >= 0 && grid[i-1][j-1] == true )
			{
				numSurrounding++;
			}
			
			if (numSurrounding < 2 || numSurrounding > 3)
			{
				tempGrid[i][j] = false;
			}
			else if (numSurrounding == 2)
			{
				tempGrid[i][j] = grid[i][j];
			}
			else if (numSurrounding == 3)
			{
				tempGrid[i][j] = true;
			}
			
			numSurrounding = 0;
			
		}
	}
	
	for (int i = 0 ; i < height ; i++ )
	{
		for (int j = 0 ; j < width ; j++ )
		{
			grid[i][j] = tempGrid[i][j];
		}
	}
}

//Prints the grid into the console.
void Grid::printFrame() {
	for (int i = 0; i < height ; i++ )
	{
		for (int j = 0 ; j < width ; j++ )
		{
			if ( grid[i][j] == true )
			{
				cout << "x";
			}
			else
			{
				cout << " ";
			}
			
			if ( (j + 1) >= width )
			{
				cout << endl;
			}
		}
	}
}


int main () {	
	int inputHeight, inputWidth;
	string kbd;

	cout << "The Game of Life in C++ by James Li\n\n" ;
	cout << "How many rows? (up to 1000)" << endl;
	cin >> inputHeight;
	cout << "How many columns? (up to 1000)" << endl;
	cin >> inputWidth;
	
	Grid life(inputHeight, inputWidth);
	life.printFrame();
	cout << endl;
	
	do {
		kbd = "";
		cout << "Enter \"y\" for next cycle, anything else to quit... ";
		cin >> kbd;
		cout << endl;
		
		life.nextFrame();
		life.printFrame();
		cout << endl;
	} while (kbd == "y");
	
	cout << "Goodbye." << endl;
	
	return 0;
}

    copy | embed

    0 comments - tagged in  posted by lijamez on Apr 25, 2009 at 7:45 p.m. EDT
Sign up to create your own snipts, or login.