IMPORTANT!

Snipt is going open source. We've toyed with this idea for quite a while, and have finally decided it's the right way to move forward.

A few things:
  • The entire Snipt source code will be released on GitHub under the 3-clause BSD License on Friday, September 10th.
  • While we'd like to think we're perfect, we realize we're only human. By open sourcing the software that runs this website, certain bugs or security flaws may be discovered that could compromise the privacy of your snipts.
  • Only the Lion Burger team will be able to push commits to the Snipt.net site. Contributors should send a pull request to add new features or submit patches.
  • By using this site, you agree not to be too angry or take any legal action against Lion Burger should this whole thing go up in flames some day.
  • Follow us on Twitter for updates.
I agree, close this message
Sign up to create your own snipts, or login.

Latest 100 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.