Thursday, March 24, 2011
Tuesday, March 22, 2011
MyHashMap
import java.util.*;
public class MyHashMap {
class HashEntry {
Object key;
Object val;
HashEntry(Object key, Object val) {
this.key=key; this.val=val;
}
public String toString() {return "{"+key+","+val+"}";}
public int hashCode() {if (key!=null) return key.hashCode(); return 0;}
public boolean equals(Object o) {
if (o==null) return false;
if (key==null && ((HashEntry)o).key==null) return true;
if (key!=null && ((HashEntry)o)!=null) return key.equals(((HashEntry)o).key);
return false;
}
}
private Set[] arr; // keep the set of HashEntry
public MyHashMap(int size) {
arr = new Set[size];
}
public MyHashMap() {
this(100);
}
private int computeHash(Object key, int size) {
int h = key.hashCode() % size;
if (h < 0) h = 0 - h;
return h;
}
/** assumes params are not null */
public Object get(Object key) {
if (key==null) return null;
int h = computeHash(key, arr.length);
if (arr[h]==null) return null;
for(Iterator i=arr[h].iterator(); i.hasNext(); ) {
HashEntry next = (HashEntry) i.next();
if (next.key.equals(key)) return next.val;
}
return null;
}
/** assumes params are not null */
public boolean put(Object key, Object value) {
if (key==null) return false;
if (value==null) return false;
HashEntry e = new HashEntry(key, value);
int h = computeHash(key, arr.length);
if (arr[h] == null) {
arr[h] = new HashSet();
}
if (arr[h].contains(e)) {
arr[h].remove(e);//remove old value
}
arr[h].add(e);
return true;
}
public String toString() {
StringBuffer b = new StringBuffer();
for(int i=0; i<arr.length; i++) {
b.append("arr["+i+"]:"+arr[i]);
b.append("\n");
}
return b.toString();
}
public static void main(String[] args) {
MyHashMap map = new MyHashMap(22);
map.put("bob the builder", new Integer(77));
map.put("TomTom", new Integer(99));
map.put("Gale", new Integer(1));
map.put("birdy 23", new Integer(-3));
map.put("Food for thought", new Integer(55));
map.put("A", new Integer(4));
map.put("0123", new Integer(44));
map.put("7", new Integer(-8));
map.put("I am me", new Integer(-77));
map.put("other", new Integer(1000));
map.put("some", new Integer(100));
map.put("THING", new Integer(10));
map.put("that", new Integer(1));
map.put("can", new Integer(11));
map.put("be", new Integer(18));
map.put("HERE", new Integer(2));
map.put("IS GOING TO BE HERE", new Integer(-9999));
System.out.println("map...");
System.out.println(map.toString());
System.out.println("get('7'): "+map.get("7"));
System.out.println("get('bob the builder'): "+map.get("bob the builder"));
map.put("bob the builder", new Integer(177));
System.out.println("get('bob the builder'), is now: "+map.get("bob the builder"));
System.out.println("get('HERE'): "+map.get("HERE"));
map.put("HERE", new Integer(111111111));
System.out.println("get('HERE'), is now: "+map.get("HERE"));
System.out.println("get('TomTom'):"+map.get("TomTom"));
System.out.println("get('Not in HashMap'):"+map.get("Not in HashMap"));
System.out.println("add 50 Integer values...");
for(int i=0; i<50; i++) {
map.put("i:"+i, new Integer(i));
}
System.out.println("map...");
System.out.println(map.toString());
System.out.println("\nshow the 50 Integer values backwards...");
for(int i=49; i>=0; i--) {
System.out.print(":"+ map.get("i:"+i));
}
}
}
map...
arr[0]:null
arr[1]:null
arr[2]:null
arr[3]:null
arr[4]:[{can,11}]
arr[5]:null
arr[6]:[{IS GOING TO BE HERE,-9999}]
arr[7]:null
arr[8]:null
arr[9]:null
arr[10]:[{other,1000}, {Food for thought,55}]
arr[11]:[{7,-8}, {I am me,-77}]
arr[12]:[{HERE,2}, {some,100}]
arr[13]:[{birdy 23,-3}, {Gale,1}]
arr[14]:[{TomTom,99}]
arr[15]:[{that,1}, {be,18}]
arr[16]:[{0123,44}]
arr[17]:null
arr[18]:[{THING,10}]
arr[19]:null
arr[20]:null
arr[21]:[{A,4}, {bob the builder,77}]
get('7'): -8
get('bob the builder'): 77
get('bob the builder'), is now: 177
get('HERE'): 2
get('HERE'), is now: 111111111
get('TomTom'):99
get('Not in HashMap'):null
add 50 Integer values...
map...
arr[0]:[{i:32,32}]
arr[1]:[{i:33,33}]
arr[2]:[{i:10,10}, {i:34,34}]
arr[3]:[{i:11,11}, {i:35,35}]
arr[4]:[{can,11}, {i:12,12}, {i:36,36}]
arr[5]:[{i:13,13}, {i:37,37}]
arr[6]:[{i:14,14}, {i:38,38}, {IS GOING TO BE HERE,-9999}]
arr[7]:[{i:15,15}, {i:40,40}, {i:39,39}]
arr[8]:[{i:16,16}, {i:41,41}]
arr[9]:[{i:17,17}, {i:42,42}]
arr[10]:[{other,1000}, {i:43,43}, {i:18,18}, {Food for thought,55}]
arr[11]:[{i:0,0}, {7,-8}, {i:44,44}, {i:20,20}, {i:19,19}, {I am me,-77}]
arr[12]:[{i:21,21}, {i:45,45}, {HERE,111111111}, {i:1,1}, {some,100}]
arr[13]:[{birdy 23,-3}, {i:22,22}, {i:46,46}, {i:2,2}, {Gale,1}]
arr[14]:[{i:23,23}, {TomTom,99}, {i:47,47}, {i:3,3}]
arr[15]:[{that,1}, {i:24,24}, {i:48,48}, {i:4,4}, {be,18}]
arr[16]:[{i:25,25}, {i:5,5}, {0123,44}, {i:49,49}]
arr[17]:[{i:26,26}, {i:6,6}]
arr[18]:[{i:27,27}, {THING,10}, {i:7,7}]
arr[19]:[{i:28,28}, {i:8,8}]
arr[20]:[{i:30,30}, {i:9,9}, {i:29,29}]
arr[21]:[{i:31,31}, {A,4}, {bob the builder,177}]
show the 50 Integer values backwards...
:49:48:47:46:45:44:43:42:41:40:39:38:37:36:35:34:33:32:31:30:29:28:27:26:25:24:2
3:22:21:20:19:18:17:16:15:14:13:12:11:10:9:8:7:6:5:4:3:2:1:0
Thursday, March 17, 2011
import java.util.*;
/** Given a Data Structure having first n integers and next n chars.
* A = i1 i2 i3 ... iN c1 c2 c3 ... cN.
* Write an in-place algorithm to rearrange the elements of the array ass A = i1 c1 i2 c2 ... in cn
*
* Divide the array in four sections:[X,Y|A,B]
* With swaps modify it to the form [X,A|Y,B].
* Do recursion to solve [X|A] and [Y|B] separately, using divide and conquer.
*/
public class DivArr {
private static int num=5;
int arr[] = null;
void swap(int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public int getK(int a[]) {
int k = a.length;
int j=0;
for(; k>1; j++) {
k = k >> 1;
}
for(k=1; j>0; j--) {
k = k << 1;
} // k is now the power of 2 <= a.length
return k;
}
public void swapMiddle(int a[], int len) {
swapMiddle(a, 0, len-1);
}
/* only handles powers of 2 */
public void swapMiddle(int a[], int left, int right) {
int diff = (right-left+1)/2;
int mid = diff + left;
int leftM = left+diff/2; // middle of left side
int rightM = mid+diff/2; // middle of right side
if (leftM+1 >= rightM) return; // end cond
int i=leftM; // i walks the left part
int j=mid; // j walks the right part
for (; i<mid; i++,j++) swap(i, j);
// recursion on left side
swapMiddle(a, left, mid);
// recursion on left side
swapMiddle(a, mid, right);
}
public static void main(String[] args) {
DivArr inst = new DivArr();
if (args.length>0) num= (new Integer(args[0])).intValue();
inst.arr = new int[num];
int k = inst.getK(inst.arr);
System.out.println("k:"+k);
int j=0;
int mid= (k%2==0 ? k/2 : k/2+1);
for (; j<mid; j++) inst.arr[j]=j;
for (; j<k; j++) inst.arr[j]='A'+j-mid;
System.out.println("\nin:");
j=0;
for (; j<mid; j++) {
System.out.print(","+inst.arr[j]);
}
for (; j<k; j++) {
System.out.print(","+(new Character((char)inst.arr[j])).toString());
}
System.out.println("\n");
inst.swapMiddle(inst.arr, k); // pass reference so that it can do recursion
System.out.println("\nout:");
for (j=0; j<k; j++) {
if (inst.arr[j] < 'A') {
System.out.print(","+inst.arr[j]);
} else {
System.out.print(","+(new Character((char)inst.arr[j])).toString());
}
}
}
}
k:64
in:
,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15
,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31
,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O
,P,Q,R,S,T,U,V,W,X,Y,Z,[,\,],^,_,`
out:
,0,A,1,B,2,C,3,D,4,E,5,F,6,G,7,H
,8,I,9,J,10,K,11,L,12,M,13,N,14,O,15,P
,16,Q,17,R,18,S,19,T,20,U,21,V,22,W,23,X
,24,Y,25,Z,26,[,27,\,28,],29,^,30,_,31,`
Wednesday, March 16, 2011
k random numbers from n
import java.util.*;
/** There is a linked list of numbers of length N. N is very large and you don't know N.
* You have to write a function that will return k random numbers from the list.
* Numbers should be completely random.
*/
public class KrandN {
public class Number implements Comparable<Number> {
private int value;
Number(int v) {
value = v;
}
public int getValue() {return value;}
public String toString(){
return ""+value;
}
public int compareTo(Number other) {
return value - other.value;
}
}
public class KNumber implements Comparable<KNumber> {
private int k;
private Number num;
KNumber(int v, int k) {
this.num = new Number(v);
this.k = k;
}
public int getValue() {return num.getValue();}
public int getK() {return k;}
public String toString(){
return "[k:"+k+","+getValue()+"]";
}
public int compareTo(KNumber other) {
return k - other.k;
}
}
/* traverse the list, generating a new random number for each entry.
* remember the top k highest random numbers, and their associated entries.
* When we hit the end of the list, the numbers in the chart are the required random numbers.
*/
public PriorityQueue<KNumber> krandn(Vector<Number> list) {
PriorityQueue<KNumber> p = new PriorityQueue<KNumber>();
int size = list.size();
System.out.println("\n\nrands for k including repeats, PriorityQueue will take care of it:");
for (Number n : list) {
int r=rand.nextInt(size);
System.out.print(","+r);
KNumber k = new KNumber(n.getValue(), r);
p.add(k);
}
System.out.println("\n");
return p;
}
private static final int num=152;
private static final int maxnumk=20;
Vector<Number> list = new Vector<Number>();
public Vector<Number> shuffle(Vector<Number> list){
if (list == null || list.size() < num) {
System.out.println("\ninitialize list");
list = new Vector<Number>(); // new list
for (int i=0; i<num; i++) {
Number c = new Number(i);
list.add(c);
}
}
int [] arr = new int[num];
int j=0;
for (Number n : list) {
arr[j++] = n.getValue();
}
shuffleArr(arr);
list = new Vector<Number>(); // new list
for (int i=0; i<num; i++) {
Number c = new Number(arr[i]);
list.add(c);
}
return list;
}
Random rand = new Random();
public void shuffleArr(int [] arr){
for (int i=0; i<arr.length-1; i++) {
int rnd = i+ rand.nextInt(arr.length-i);
//swap arr[i] and a[rnd]
int tmp = arr[i];
arr[i] = arr[rnd];
arr[rnd] = tmp;
}
}
public static void main(String[] args) {
KrandN inst = new KrandN();
Vector<Number> list = null;
list = inst.shuffle(list);
System.out.println("\nout:");
for (Number n : list) {
System.out.print(","+n.toString());
}
PriorityQueue<KNumber> p = inst.krandn(list);
System.out.println("\n top k list, random k elements (up to "+maxnumk+"):");
int i = 0;
while (!p.isEmpty() && i++ < maxnumk) {
KNumber n = p.remove();
System.out.print(","+n);
}
//System.out.println("\nsorted:");
//Collections.<Number>sort(list);
//for (Number n : list) {
// System.out.print(","+n.toString());
//}
}
}
top k list, random k elements (up to 20):
,[k:1,29],[k:2,27],[k:2,105],[k:4,23],[k:6,30],[k:7,64],[k:9,102],[k:9,8],[k:9,1
7],[k:11,82],[k:12,128],[k:13,58],[k:13,135],[k:13,145],[k:13,15],[k:14,109],[k:
16,126],[k:17,111],[k:19,37],[k:19,53]
Monday, March 14, 2011
Unique
import java.util.*;
public class Unique {
private final int num=52;
int [] arr = new int[num];
public int[] uniquen(){
int cost=0;
int l = arr.length;
int [] o = new int[l]; // the values cannot exceed the length!
for(int i=0; i<l; i++) {
o[i] = -1; // init to -1
//cost++;
}
int [] newa = new int[l];
int s=0;
for(int i=0; i<l; i++) {
o[arr[i]] = arr[i]; // assumes values in arr don't exceed the length of arr
// could have done a max(arr) as the length of o instead.
cost++;
}
for(int i=0; i<l; i++) {
if (o[i] != -1) {
newa[s++] = o[i];
cost++;
}
}
int [] result = new int[s];
System.out.print("result:");
for(int k=0; k<s; k++) {
result[k] = newa[k];
System.out.print(","+result[k]);
cost++;
}
System.out.println("");
System.out.println("cost:"+cost+"\n");
return result;
}
public int[] uniquen2(){
int cost=0;
int l = arr.length;
int [] newa = new int[l];
int s=0;
for(int i=0; i<l; i++) {
for(int j=i+1; j<l; j++) {
if (arr[i] == arr[j]) j = ++i;
cost++;
}
newa[s++] = arr[i];
}
int [] result = new int[s];
System.out.print("result:");
for(int k=0; k<s; k++) {
result[k] = newa[k];
System.out.print(","+result[k]);
cost++;
}
System.out.println("");
System.out.println("cost:"+cost+"\n");
return result;
}
Random rand = new Random();
public void shuffleArr(){
for (int i=0; i<arr.length-1; i++) {
arr[i] = i/3;
}
for (int i=0; i<arr.length-1; i++) {
int rnd = i+ rand.nextInt(arr.length-i);
//swap arr[i] and a[rnd]
int tmp = arr[i];
arr[i] = arr[rnd];
arr[rnd] = tmp;
}
System.out.print("\nin:");
for(int i=0; i<arr.length; i++) {
System.out.print(","+arr[i]);
}
System.out.println("\n");
}
public static void main(String[] args) {
Unique inst = new Unique();
inst.shuffleArr();
inst.uniquen2();
inst.uniquen();
}
}
better shuffle
import java.util.*;
public class Deck {
public class Card implements Comparable<Card> {
private int value;
Card(int v) {
value = v;
}
public int getValue() {return value;}
public String toString(){
return ""+value;
}
public int compareTo(Card other) {
return value - other.value;
}
}
private final int num=52;
Vector<Card> deck = new Vector<Card>();
public Vector<Card> shuffle(Vector<Card> deck){
if (deck == null || deck.size() < num) {
System.out.println("\ninitialize deck");
deck = new Vector<Card>(); // new deck
for (int i=0; i<num; i++) {
Card c = new Card(i);
deck.add(c);
}
}
int [] arr = new int[num];
int j=0;
for (Card card : deck) {
arr[j++] = card.getValue();
}
shuffleArr(arr);
deck = new Vector<Card>(); // new deck
for (int i=0; i<num; i++) {
Card c = new Card(arr[i]);
deck.add(c);
}
return deck;
}
Random rand = new Random();
public void shuffleArr(int [] arr){
for (int i=0; i<arr.length-1; i++) {
int rnd = i+ rand.nextInt(arr.length-i);
//swap arr[i] and a[rnd]
int tmp = arr[i];
arr[i] = arr[rnd];
arr[rnd] = tmp;
}
}
public static void main(String[] args) {
Deck deckInst = new Deck();
Vector<Card> deck = null;
for (int i=0; i<6; i++) {
deck = deckInst.shuffle(deck);
System.out.println("\nout:");
for (Card card : deck) {
System.out.print(","+card.toString());
}
}
System.out.println("\nsorted:");
Collections.<Card>sort(deck);
for (Card card : deck) {
System.out.print(","+card.toString());
}
}
}
Sunday, March 13, 2011
Permutations
import java.util.*;
public class PermStr {
public static void main(String[] args) {
String inp = "0ab";
if (args.length>0) inp = args[0];
for (String str : permStr(inp)){
System.out.println(str);
}
}
static Vector<String> permStr(String str){
if (str.length() == 1){
Vector<String> ret = new Vector<String>();
ret.add(str);
System.out.println(" >ret:"+ret);
return ret;
}
char start = str.charAt(0);
Vector<String> endStrs = permStr(str.substring(1));
Vector<String> newEndStrs = new Vector<String>();
for (String endStr : endStrs){
System.out.println(" >next:"+endStr);
for (int j = 0; j <= endStr.length(); j++){
System.out.println(" >j:"+j);
if (endStr.substring(0, j).endsWith(String.valueOf(start)))
break;
System.out.println(" >endStr.substring(0, j)"+endStr.substring(0, j));
System.out.println(" >String.valueOf(start)"+String.valueOf(start));
System.out.println(" >endStr.substring(j);:"+endStr.substring(j));
newEndStrs.add(endStr.substring(0, j) + String.valueOf(start) + endStr.substring(j));
}
}
System.out.println(" >>return newEndStrs: "+newEndStrs);
return newEndStrs;
}
}
0ab
a0b
ab0
0ba
b0a
ba0
Saturday, March 12, 2011
f(a, b) returns string with only the characters found in both strings in the order of a
/* Write a function f(a, b) which takes two character string arguments and
* returns a string containing only the characters found in both strings in the
* order of a. Write a version which is order N-squared and one which is order N.
*/
public class StrOverlap {
public char[] overlapn2(char[] a, char[] b) {
char [] o = new char[a.length];
int k=0;
for(int i=0; i<a.length; i++) {
for(int j=0; j<b.length; j++) {
if (a[i] == b[j]) {
o[k++] = a[i];
break; // go to the next 'a'
}
}
}
for(; k<o.length; k++) {
o[k]= '\n';
}
return o;
}
public String overlapn(String b, String a, boolean showRepeats) {
StringBuffer result = new StringBuffer();
boolean[] asciiArr = new boolean[256]; // boolean ascii array (initially all false)
char[] aarr = a.toCharArray();
for (int i = 0; i < aarr.length; i++)
asciiArr[aarr[i]] = true;
char[] bbrr = b.toCharArray();
for (int i = 0; i < bbrr.length; i++)
if (asciiArr[bbrr[i]]) {
result.append(bbrr[i]);
if (!showRepeats) asciiArr[bbrr[i]] = false; // already printed
}
return result.toString();
}
public void init(String astr, String bstr) {
char []a = new char[astr.length()];
char []b = new char[bstr.length()];
astr.getChars(0, astr.length(), a, 0);
bstr.getChars(0, bstr.length(), b, 0);
char [] arr = overlapn2(a, b);
String stro = new String(arr);
System.out.println("o: \n"+stro);
String stron = overlapn(astr, bstr, true);
System.out.println("o: \n"+stron);
}
static public void main(String[] args) {
StrOverlap so = new StrOverlap();
if(args.length>1) {
so.init(args[0], args[1]);
} else {
System.out.println("usage: StrOverlap a b");
}
}
}
partisan voting applet
A fun applet which moves some of the buttons around when you try to click them so that they can't be depressed :)
import java.applet.Applet;
import java.awt.*;
import java.awt.event.*;
import java.util.Random;
/**
** Vote2006.java by Douglas A. Bauman
**/
public class Vote2006 extends Applet implements MouseMotionListener, MouseListener {
String title1a, title1b, title1c, title2a, title2b, title2c;
Button b1a, b1b, b1c, b2a, b2b, b2c;
int xpos, ypos, hits;
int rect1xco,rect1yco,rect1width,rect1height;
boolean rect1Active;
boolean rdB1;
Random r;
public void init() {
title1a = getParameter("title1a");
title1b = getParameter("title1b");
title1c = getParameter("title1c");
title2a = getParameter("title2a");
title2b = getParameter("title2b");
title2c = getParameter("title2c");
r = new Random();
b1a = new Button(title1a);
b1b = new Button(title1b);
b1c = new Button(title1c);
b2a = new Button(title2a);
b2b = new Button(title2b);
b2c = new Button(title2c);
setLayout(null);
add(b1a);
add(b1b);
add(b1c);
add(b2a);
add(b2b);
add(b2c);
hits = 0;
rect1xco = 100;
rect1yco = 50;
rect1width = 40;
rect1height= 26;
b1a.setBounds(rect1xco, rect1yco, rect1width, rect1height);
b1b.setBounds(rect1xco+rect1width+10, rect1yco, rect1width, rect1height);
b1c.setBounds(rect1xco+2*rect1width+20, rect1yco, rect1width, rect1height);
b2a.setBounds(rect1xco+10, rect1yco+rect1height, rect1width, rect1height);
b2b.setBounds(rect1xco+rect1width+10, rect1yco+rect1height, rect1width, rect1height);
b2c.setBounds(rect1xco+2*rect1width+10, rect1yco+rect1height, rect1width, rect1height);
//addMouseListener(this);
b1a.addMouseMotionListener(this);
b1b.addMouseMotionListener(this);
b1c.addMouseMotionListener(this);
}
public void destroy() {
//removeMouseListener(this);
//removeMouseMotionListener(this);
}
public void start() {
}
public void stop() {
}
public boolean handleEvent(Event e) {
if (title2a.equals(e.arg) ||
title2b.equals(e.arg) ||
title2c.equals(e.arg)) {
b1a.setBounds(rect1xco + r.nextInt()%rect1xco,
rect1yco + r.nextInt()%rect1yco,
rect1width, rect1height);
b1b.setBounds(rect1xco + r.nextInt()%rect1xco,
rect1yco + r.nextInt()%rect1yco,
rect1width, rect1height);
b1c.setBounds(rect1xco + r.nextInt()%rect1xco,
rect1yco + r.nextInt()%rect1yco,
rect1width, rect1height);
rect1Active = true;
showStatus("Thanks for your vote!");
repaint();
}
return true;
}
public void mouseReleased(MouseEvent e) {
}
public void mousePressed(MouseEvent e) {
}
public void mouseClicked(MouseEvent e) {
}
public void mouseEntered(MouseEvent e) {
}
public void mouseExited(MouseEvent e) {
}
public void mouseDragged(MouseEvent e) {
}
public void mouseMoved(MouseEvent e) {
xpos = e.getX();
ypos = e.getY();
b1a.setBounds(rect1xco + r.nextInt()%rect1xco,
rect1yco + r.nextInt()%rect1yco,
rect1width, rect1height);
b1b.setBounds(rect1xco + r.nextInt()%rect1xco,
rect1yco + r.nextInt()%rect1yco,
rect1width, rect1height);
b1c.setBounds(rect1xco + r.nextInt()%rect1xco,
rect1yco + r.nextInt()%rect1yco,
rect1width, rect1height);
rdB1 = true;
rect1Active = false;
b1a.repaint();
b1b.repaint();
b1c.repaint();
b1a.getParent().repaint();
b1b.getParent().repaint();
b1c.getParent().repaint();
repaint();
e.consume();
}
public void paint(Graphics g) {
if (rect1Active) g.setColor(Color.red);
else g.setColor(Color.blue);
g.fillRect(0,0, 600-1, 200-1);
g.setColor(Color.blue);
if (rdB1) {
rdB1 = false;
showStatus("Please place your vote!");
}
}
}
<html> <head> <title>U.S. election of 1800</title> </head>
<body>
<a href="http://americanhistory.about.com/od/elections/p/election1800.htm">
Alexander Hamilton backed Charles Pinckney and saw Thomas Jefferson
as a bitter rival because of his stance on states’ rights. However, when the election came down to
Aaron Burr versus Thomas Jefferson, Hamilton put his weight behind
Jefferson because he couldn’t stand Burr. They would eventually meet in
a duel in 1804 in which Hamilton would be killed.</a>
<hr>
<applet code="Vote2006.class" width=600 height=200>
<param name=title1a value="Jefferson">
<param name=title1b value="Jay">
<param name=title1c value="Burr">
<param name=title2a value="Adams">
<param name=title2b value="Pinckney">
<param name=title2c value="Hamilton">
Sorry, You can't vote, since you are registered Republican.
</applet>
<br>
<a href="Vote2006.java"> The source</a>
</body> </html>
Friday, March 11, 2011
shuffle
import java.util.*;
public class Deck {
public class Card {
private int value;
Card(int v) {
value = v;
}
public void print(){
System.out.print(value+";");
}
}
private final int num=52;
Vector<Card> deck = new Vector<Card>();
int[] arr = new int[num];
// implement this shuffle function. DO NOT USE Collections.shuffle() !!
public void shuffle(){
Random rand = new Random();
//given a[]
for (int i=0; i<arr.length; i++) {
arr[i] = i;
}
//for i <- 0..a.length-2
//for(Card c : deck) {
for (int i=0; i<arr.length-1; i++) {
//rnd_index <- random(i, a.length) #inclusive, exclusive
int rnd = i+ rand.nextInt(arr.length-i); //deck.size());
System.out.print(","+rnd);
//swap a[i] and a[rnd_index]
int tmp = arr[i];
arr[i] = arr[rnd];
arr[rnd] = tmp;
}
System.out.println("\nout:");
for (int i=0; i<arr.length; i++) {
System.out.print(","+arr[i]);
}
}
public static void main(String[] args) {
Deck deck = new Deck();
deck.shuffle();
}
}
Binary Tree implementation
Binary Tree implementation...
output:
In-Order Dump (Add node 9)
data: 3 (root)
data: 9 (right)
In-Order Dump (Add node 1)
data: 1 (left)
data: 3 (root)
data: 9 (right)
In-Order Dump (Add node 4)
data: 1 (left)
data: 3 (root)
data: 4 (left)
data: 9 (right)
In-Order Dump (Add node 8)
data: 1 (left)
data: 3 (root)
data: 4 (left)
data: 8 (right)
data: 9 (right)
In-Order Dump (Add node 2)
data: 1 (left)
data: 2 (right)
data: 3 (root)
data: 4 (left)
data: 8 (right)
data: 9 (right)
In-Order Dump (Add node 5)
data: 1 (left)
data: 2 (right)
data: 3 (root)
data: 4 (left)
data: 5 (left)
data: 8 (right)
data: 9 (right)
In-Order Dump (Add node 7)
data: 1 (left)
data: 2 (right)
data: 3 (root)
data: 4 (left)
data: 5 (left)
data: 7 (right)
data: 8 (right)
data: 9 (right)
In-Order Dump (Add node 0)
data: 0 (left)
data: 1 (left)
data: 2 (right)
data: 3 (root)
data: 4 (left)
data: 5 (left)
data: 7 (right)
data: 8 (right)
data: 9 (right)
In-Order Dump (Add node 6)
data: 0 (left)
data: 1 (left)
data: 2 (right)
data: 3 (root)
data: 4 (left)
data: 5 (left)
data: 6 (left)
data: 7 (right)
data: 8 (right)
data: 9 (right)
import java.util.*;
public class NodeT {
int data;
NodeT left;
NodeT right;
public NodeT(int data) {this.data = data;}
public NodeT insert(NodeT n, int data) {
if (n == null) {
// create new node
n = (NodeT) new NodeT(data);
} else if (data > n.data) {
n.right = insert(n.right, data);
} else {
n.left = insert(n.left, data);
}
return n;
}
public void dumptree(NodeT tree, String tag) {
if (tree == null) return;
NodeT node = tree;
if (node != null) {
dumptree(node.left, "left");
System.out.println("data: "+node.data+" ("+tag+")");
dumptree(node.right, "right");
}
}
public void dump(NodeT tree, String tag) {
System.out.println("In-Order Dump ("+tag+")");
dumptree(tree, "root");
}
public static void main(String[] args) {
int array[] = { 3, 9, 1, 4, 8, 2, 5, 7, 0, 6 };
int i;
NodeT base = new NodeT(array[0]);
for (i = 1; i < 10; i++) {
String buffer = "Add node " + array[i];
base = base.insert(base, array[i]);
base.dump(base, buffer);
}
}
}
output:
In-Order Dump (Add node 9)
data: 3 (root)
data: 9 (right)
In-Order Dump (Add node 1)
data: 1 (left)
data: 3 (root)
data: 9 (right)
In-Order Dump (Add node 4)
data: 1 (left)
data: 3 (root)
data: 4 (left)
data: 9 (right)
In-Order Dump (Add node 8)
data: 1 (left)
data: 3 (root)
data: 4 (left)
data: 8 (right)
data: 9 (right)
In-Order Dump (Add node 2)
data: 1 (left)
data: 2 (right)
data: 3 (root)
data: 4 (left)
data: 8 (right)
data: 9 (right)
In-Order Dump (Add node 5)
data: 1 (left)
data: 2 (right)
data: 3 (root)
data: 4 (left)
data: 5 (left)
data: 8 (right)
data: 9 (right)
In-Order Dump (Add node 7)
data: 1 (left)
data: 2 (right)
data: 3 (root)
data: 4 (left)
data: 5 (left)
data: 7 (right)
data: 8 (right)
data: 9 (right)
In-Order Dump (Add node 0)
data: 0 (left)
data: 1 (left)
data: 2 (right)
data: 3 (root)
data: 4 (left)
data: 5 (left)
data: 7 (right)
data: 8 (right)
data: 9 (right)
In-Order Dump (Add node 6)
data: 0 (left)
data: 1 (left)
data: 2 (right)
data: 3 (root)
data: 4 (left)
data: 5 (left)
data: 6 (left)
data: 7 (right)
data: 8 (right)
data: 9 (right)
Thursday, March 10, 2011
Quick sort and Merge sort
Quick sort and Merge sort - both use recursion.
import java.util.*;
public class qs {
int recursionCount = 0;
void quickSort(int arr[]) {
recursionCount = 0;
quickSort(arr, 0, arr.length-1);
}
void quickSort(int arr[], int left, int right) {
int i = left, j = right;
int tmp;
int pivot = arr[(left + right) / 2];
recursionCount++;
/* partition */
while (i <= j) {
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
}
/* recursion */
if (left < j)
quickSort(arr, left, j);
if (i < right)
quickSort(arr, i, right);
}
void mergeSort(int arr[]) {
recursionCount = 0;
mergeSortR(arr);
}
int [] mergeSortR(int arr[]) {
if (arr.length > 1) { // split into two halves
recursionCount++;
int sizeL = arr.length/2;
int sizeR = arr.length - sizeL;
int arrL[] = new int[sizeL];
int arrR[] = new int[sizeR];
for(int i=0; i<sizeL; i++) arrL[i] = arr[i];
for(int i=sizeL; i<sizeL+sizeR; i++) arrR[i-sizeL] = arr[i];
/* recursion */
arrL = mergeSortR(arrL);
arrR = mergeSortR(arrR);
int i = 0, j = 0, k = 0;
while(arrL.length != j && arrR.length != k) {
if(arrL[j] < arrR[k]) {
arr[i] = arrL[j];
i++;
j++;
} else {
arr[i] = arrR[k];
i++;
k++;
}
}
while(arrL.length != j) {
arr[i] = arrL[j];
i++;
j++;
}
while(arrR.length != k) {
arr[i] = arrR[k];
i++;
k++;
}
}
return arr;
}
public qs(){
}
int arr[];
int arrCopy[];
public void init() {
System.out.println(""+getAppletInfo());
System.out.println("quick sort before..., count:"+arr.length);
print();
quickSort(arr);
System.out.println("after...");
print();
System.out.println("recursionCount:"+recursionCount);
for(int i=0; i<arrCopy.length; i++) {
arr[i] = arrCopy[i];
}
System.out.println("merge sort, before..., count:"+arr.length);
print();
mergeSort(arr);
System.out.println("after...");
print();
System.out.println("recursionCount:"+recursionCount);
}
public void print() {
for(int i=0; i<arr.length; i++) {
System.out.print(","+arr[i]);
}
System.out.println("");
}
public String getAppletInfo() {
return "quicksort by Douglas A. Bauman";
}
static public void main(String[] args) {
qs qsi = new qs();
qsi.arr = new int[args.length];
qsi.arrCopy = new int[args.length];
boolean valid = args.length > 0;
for(int i=0; i<args.length; i++) {
try{
qsi.arr[i] = (new Integer(args[i])).intValue();
qsi.arrCopy[i] = qsi.arr[i];
}catch (NumberFormatException e) {
System.out.println("args["+i+"], not a number: "+args[i]);
valid = false;
}
}
if (valid)
qsi.init();
}
}
Wednesday, March 9, 2011
GIQ: depth-first graph traversal
Describe the algorithm for a depth-first graph traversal.
The use of a Stack and a Node with children...
The stack is used to traverse the tree of nodes.
The use of a Stack and a Node with children...
The stack is used to traverse the tree of nodes.
import java.util.*;
public class depthfirst {
public class Node {
Object o;
Collection children;
Node(Object o) {this.o=o; children=new ArrayList();}
}
Node tree = null;
Stack stack = new Stack();
/* Push input node into Stack
* Store input node in 'node'
* Loop until stack is not empty:
* Pop stack into 'node'
* Print Node Data
* Push all child nodes into Stack
*/
void depthFirstTraversal(Node node) {
if (node == null) return;
stack.push(node);
while(!stack.empty()) {
node = (Node) stack.pop();
System.out.println("Next: "+node.o);
for(Iterator i=node.children.iterator(); i.hasNext(); ) {
Node next = (Node) i.next();
stack.push(next);
}
}
}
void breadthFirstTraversal(Node node) {
if (node == null) return;
list.add(node);
while(!list.isEmpty()) {
node = (Node) list.remove();
System.out.println("Next: "+node.o);
for(Iterator i=node.children.iterator(); i.hasNext(); ) {
Node next = (Node) i.next();
list.add(next);
}
}
}
public depthfirst(){
}
public void init() {
System.out.println(""+getAppletInfo());
System.out.println("depthfirst:");
depthFirstTraversal(tree);
System.out.println("breadthfirst:");
breadthFirstTraversal(tree);
}
int c = 0;
/* java depthfirst a b c d e f g h i
* will result in: a i d g c f b e h
* breadthfrist : a b c d i e f g h
* tree: a
* b c d i
* e f g
*/
public void createTree(Object o) {
System.out.println("push:"+o);
Node n = new Node(o);
if (tree==null) {
System.out.println("tree:"+n); // a
tree = n;
} else {
if (c<=3) {
System.out.println("c<=3:"+n); // b c d
tree.children.add(n);
} else if (c<=6) {
Iterator j = tree.children.iterator();
Node m = null;
for(int i=4; i<=c; i++) {
System.out.println("i:"+i);
m = (Node) j.next();
}
System.out.println("n:"+n); // e f g
m.children.add(n);
} else if (c<=7) {
Iterator j = tree.children.iterator();
Node m4 = (Node) j.next(); // e
j = m4.children.iterator();
Node m = null;
for(int i=7; i<=c; i++) {
System.out.println("i:"+i);
m = (Node) j.next();
}
System.out.println("n:"+n); // h
m.children.add(n);
} else {
System.out.println("else:"+n); // i
tree.children.add(n);
}
}
c++;
}
public String getAppletInfo() {
return "depth first graph by Douglas A. Bauman";
}
static public void main(String[] args) {
depthfirst df = new depthfirst();
for(int i=0; i<args.length; i++) {
df.createTree(args[i]);
}
df.init();
}
}
GIQ: random number range
Given a function which produces a random integer in the range 1 to 5, write a function which produces a random integer in the range 1 to 7.
This is my solution, thrown together quickly, in java of course, bear in mind that the algorithm is simply to loop over the first function (1-5) 7 times, adding in the result to a running total, then do a modulo 7 for the grand result of the second function...
This is my solution, thrown together quickly, in java of course, bear in mind that the algorithm is simply to loop over the first function (1-5) 7 times, adding in the result to a running total, then do a modulo 7 for the grand result of the second function...
import java.util.Random;
public class rand {
int A = 5;
int B = 7;
int sample = 50;
public rand(){
}
public void init() {
System.out.println(""+getAppletInfo());
if (A<=0) throw new IllegalArgumentException("A must be >= 0");
if (B<=0) throw new IllegalArgumentException("B must be >= 0");
int[] dist = new int[B];
for(int j=0; j<B; j++) {
dist[j] = 0;
}
for(int i=0; i<sample; i++) {
int next = randB();
dist[next-1] += 1;
System.out.println(".."+next);
}
System.out.println("Distribution...");
for(int j=0; j<B; j++) {
System.out.println("j:"+j+",count:"+dist[j]);
}
}
Random random = new Random();
int randA () {
return random.nextInt(A) + 1;
}
int randB () {
int r = 0;
for(int i=0; i<B; i++) {
r += randA() - 1;
}
return r % B + 1;
}
public String getAppletInfo() {
return "randB from randA by Douglas A. Bauman";
}
static public void main(String[] args) {
rand rr = new rand();
try {
rr.A = Integer.parseInt(args[0]);
try {
rr.B = Integer.parseInt(args[1]);
} catch (NumberFormatException e) {
} catch (RuntimeException e) {
}
} catch (NumberFormatException e2) {
} catch (RuntimeException e2) {
}
rr.init();
}
}
Subscribe to:
Posts (Atom)