This blog is accompanied site of http://j2megamer.blogspot.com. Here I will post various source codes. Related to software and computer science. Its exclusively for code posting.
Site Menu
Previous Posts
- Nice Cryptography Article
- Topcoder Open 2004 - Qualification Round
- Swapping Without a Temporary Location
- Laws of Cryptography Book
- DevX September 2004 Challenge Level 2, Difficult
- Google Code Jam 2004 Practice Room 500 Point
- Google Code Jam 2004 Practice Room 250 Point
- SRM 209 DIV 2 - 500 pts
- First Post
Archives
Gaming Links
Powered By
Java Codes by Gamer
Tuesday, September 27, 2005
Nice Cryptography Article
Really kool article on cryptography. Easy to follow and presents nice ideas.
http://www.mapplot.com/my/articles/crypt/index.htm
- posted by Max @ 7:59 AM 0 comments
Tuesday, September 07, 2004
Topcoder Open 2004 - Qualification Round
Ah, I sucked completely in the arena. I couldn't even submit easiest problem on time. Reason, I panicked. In the situations like these one can really know his/her true nature. After the time-out it took me just few minutes to solve the entire riddle. It is damn easy. But then they say "If you lose confidence you lose everything". A learning at least.
Problem Statement
At a recent competition, each competitor received an integer score between 0 and 100, inclusive. Now, you need to rank the competitors from first to last. First place (the highest score) is ranked 1, second is ranked 2, and so on. In the event of a tie, all of the tied competitors should receive the average of the ranks they would have received if there were put in some order (it doesn't matter what order, the average is always the same). For example, if there is a tie between two people for first place, then ordering them would give one competitor rank 1, and the other rank 2. The average of these is 1.5, so both competitors receive a rank of 1.5. You should return a double[] containing the ranks of the competitors, each of whose elements corresponds to the element of score with the same index.
import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;
class Value
{
double rank;
int score;
}
public class Rank
{
public double[] rank(int[] scores)
{
int bscores[] = new int[ scores.length ];
for( int count = 0; count < bscores.length; count++ )
{
bscores[count] = scores[count];
}
Value ranks[] = new Value[ scores.length ];
Arrays.sort( scores );
int k = 1;
for( int i = scores.length - 1; i >= 0; i-- )
{
ranks[ k - 1 ] = new Value();
ranks[ k - 1 ].rank = k;
ranks[ k - 1 ].score = scores[ i ];
k++;
}
for( int i = 0; i < scores.length; i++ )
{
int count = 0;
int jth = 0;
for( int j = 0; j < scores.length; j++ )
{
if( ranks[ i ].score == ranks[ j ].score && i != j )
{
count++;
jth = j;
}
}
if( count >= 1 )
{
int start = jth - count;
int end = start + count;
double sum = 0;
for( ;start <= end; start++ )
{
sum += ranks[ start ].rank;
}
sum /= (count+1);
start = jth - count;
for( ;start <= end; start++ )
{
ranks[ start ].rank = sum;
}
i += count;
}
}
double res[] = new double[ scores.length ];
for( int i = 0; i < res.length; i++ )
{
res[ i ] = ranks[ i ].rank;
}
for( int i = 0; i < scores.length; i++ )
{
int score = bscores[i];
int count = 0;
int index = 0;
for( int j = 0; j < scores.length; j++ )
{
if( ranks[j].score == score )
{
res[ i ] = ranks[ j ].rank;
break;
}
}
}
return res;
}
}
- posted by Max @ 11:28 AM 3 comments
Monday, September 06, 2004
Swapping Without a Temporary Location
We all know how to swap to numbers using a temporary location. Say two numbers are A, B
then to swap
C = new type;
C = A
A = B
B = C
Also this can be done in following way. It requires butwise XOR (^) operator to be working. For object and struct types one can apply ^ directly on bit level.
A = A ^ B
B = A ^ B
A = A ^ B
Swap without a temporary location!
- posted by Max @ 8:25 AM 0 comments
Laws of Cryptography Book
Its one of the most complete books and a must for any newbie who wants to plunge into this domain. Book contains very detailed algorithms and source code in Java. Mathematics is also explained nicely.
www.cs.utsa.edu/~wagner/lawsbookcolor/laws.pdf
- posted by Max @ 8:22 AM 0 comments
Sunday, September 05, 2004
DevX September 2004 Challenge Level 2, Difficult
Problem Statement
There are several software packages that typeset mathematical expressions. For example,
the expression "(31+24/12)/(5+6) + 16" might be typeset like this:
" 24 "
" 31 + ---- "
" 12 + 16"
"----------- "
" 5 + 6 "
Write a method that takes such a typeset mathematical expression and evaluates it,
returning the numerical value of the expression. If given the expression above, your
method should return 19.
The input expression will be a two-dimensional array of characters, given as a String
[]. Expressions will be built out of other expressions, rectangular portions of the
given array. Every expression will be in one of three forms:
integer constant: The expression will be exactly one character high, will consist
solely of digits, and will not contain any leading zeros.
addition: The expression will be constructed out of left and right subexpressions.
Zero or more rows of spaces will be added above and below each subexpression and
will give them the same height. Three columns of that height will be placed between
them, containing all spaces, except for a single '+' character anywhere in the
middle column.
division: The expression will be constructed out of top and bottom subexpressions.
One or more columns of spaces will be added to the left and right of each
subexpression to give them the same width. One row consisting entirely of '-'
characters will be placed between them.
Example:
The expression above has one column (column 12) with all spaces except for a
single '+' character. Therefore, this expression is built by adding two
subexpressions together. If we take the regions to the left and right of column 12,
and remove all rows and columns on the edges containing only spaces, we get the
following two subexpressions:
" 24 "
" 31 + ---- "
" 12 " and "16"
"-----------"
" 5 + 6 "
The right subexpression contains only digits, so it evaluates to the value 16. The
left subexpression has one row (row 3) with all '-' characters. Therefore, this
expression is built by dividing two subexpressions. If we take the regions above and
below row 3, and remove all rows and columns on the edges containing only spaces, we
get the following two subexpressions:
" 24 "
"31 + ----" and "5 + 6"
" 12 "
Here, both subexpressions are addition. The right subexpression adds "5" and "6",
resulting in the value 11. The left subexpression is built by adding two more
subexpressions:
" 24 "
"31" and "----"
" 12 "
The left side evaluates to the value 31, and the right side evaluates to the
division of the subexpressions "24" and "12". Working back up, 24 divided by 12 is
2, added to 31 is 33, divided by 11 is 3, plus 16 is 19.
import java.util.*;
public class Untypeset
{
public static void main( String s[] )
{
String []input =
{ " 625 + 0 ",
"-----------------",
" 5 " };
int result = evaluate( input );
System.out.println( "Result is:" + result );
}
public static int evaluate(String[] expression)
{
Stack myStack = new Stack();
myStack.push( expression );
String key = "0123456789 ";
String plus[] = {"P"
};
String div[] = {"D"
};
Stack finalStack = new Stack();
_L1:
while( myStack.size() != 0 )
{
String expr[] = (String[])myStack.pop();
int test1 = 0;
int validindex = 0;
for( int count = 0; count < expr.length; count++ )
{
if( expr[ count ].trim().length() == 0 )
{
test1++;
}
else
{
validindex = count;
}
}
if( expr.length == 1 )
{
boolean insert = true;
for( int t = 0; t < expr[0].length(); t++ )
{
if( expr[0].charAt( t ) == '+' || expr[0].charAt( t ) == '-' )
{
insert = false;
break;
}
}
if( insert )
{
finalStack.push( expr[ 0 ] );
}
}
else if( (expr.length - test1) == 1 )
{
if( !expr[ validindex ].equals( "P" ) && !expr[ validindex ].equals( "D" ) )
{
boolean insert = true;
for( int t = 0; t < expr[validindex].length(); t++ )
{
if( expr[validindex].charAt( t ) == '+' || expr[validindex].charAt( t ) == '-' )
{
insert = false;
break;
}
}
if( insert )
{
finalStack.push( expr[ validindex ] );
}
}
}
int vlen = expr.length;
int hlen = expr[0].length();
StringTokenizer st;
for( int i = 0; i < hlen; i++ )
{
String temp = "";
for( int j = 0; j < vlen; j++ )
{
temp += expr[ j ].charAt(i);
}
st = new StringTokenizer( temp, key );
if( st.countTokens() == 1 && st.nextToken().equals("+") ) //theres a +
{
//seperate into two and push on the stack
String one[] = new String[ expr.length ];
String two[] = new String[ expr.length ];
for( int k = 0; k < vlen; k++ )
{
one[ k ] = two[ k ] = "";
one[ k ] = expr[ k ].substring( 0, i );
two[ k ] = expr[ k ].substring( i + 1, hlen );
}
boolean stest = true;
if( one.length == 1 && two.length == 1 )
{
for( int ione = 0; ione < one[0].length();ione++ )
{
if( one[0].charAt( ione ) == '+' || one[0].charAt( ione ) == '-' )
{
stest = false;
break;
}
}
for( int itwo = 0; itwo < two[0].length();itwo++ )
{
if( two[0].charAt( itwo ) == '+' || two[0].charAt( itwo ) == '-' )
{
stest = false;
break;
}
}
}
if( one.length == 1 && two.length == 1 && stest )
{
String sone = one[ 0 ].trim();
String stwo = two[ 0 ].trim();
int ione = Integer.parseInt( sone );
int itwo = Integer.parseInt( stwo );
String ans = "" + (ione + itwo);
String aans[] = { ans
};
myStack.push( aans );
}
else
{
myStack.push( one );
myStack.push( plus );
myStack.push( two );
}
continue _L1;
}
} //+ are done
//now horizontal split for /
for( int i = 0; i < vlen; i++ )
{
String temp = "";
for( int j = 0; j < hlen; j++ )
{
temp += expr[ i ].charAt(j);
}
boolean test = true;
temp = temp.trim();
for( int count = 0; count < temp.length(); count++ )
{
if( temp.charAt( count ) != '-' )
{
test = false;
break;
}
}
if( temp.length() == 0 )
{
test = false;
}
if( test ) //theres a +
{
String one[] = new String[ i ];
String two[] = new String[ vlen - i - 1 ];
for( int k = 0; k < i; k++ )
{
one[ k ] = "";
one[ k ] = expr[ k ];
}
for( int k = i + 1; k < vlen; k++ )
{
two[ k - i - 1 ] = "";
two[ k - i - 1 ] = expr[ k ];
}
boolean stest = true;
if( one.length == 1 && two.length == 1 )
{
for( int ione = 0; ione < one[0].length();ione++ )
{
if( one[0].charAt( ione ) == '+' || one[0].charAt( ione ) == '-' )
{
stest = false;
break;
}
}
for( int itwo = 0; itwo < two[0].length();itwo++ )
{
if( two[0].charAt( itwo ) == '+' || two[0].charAt( itwo ) == '-' )
{
stest = false;
break;
}
}
}
if( one.length == 1 && two.length == 1 && stest )
{
String sone = one[ 0 ].trim();
String stwo = two[ 0 ].trim();
int ione = Integer.parseInt( sone );
int itwo = Integer.parseInt( stwo );
String ans = "" + ione/itwo;
String aans[] = { ans
};
myStack.push( aans );
}
else
{
myStack.push( one );
myStack.push( div );
myStack.push( two );
}
continue _L1;
}
}
}
while( finalStack.size() > 1 )
{
while( finalStack.size() >= 3 )
{
String one = (String)finalStack.pop();
String two = (String)finalStack.pop();
String three = (String)finalStack.pop();
if( two.trim().equals("P") )
{
int ione = Integer.parseInt( one.trim() );
int itwo = Integer.parseInt( three.trim() );
finalStack.push( "" + (ione + itwo ) );
}
else if( two.trim().equals("D") )
{
int ione = Integer.parseInt( one.trim() );
int itwo = Integer.parseInt( three.trim() );
finalStack.push( "" + (ione / itwo ) );
}
}
}
return Integer.parseInt( (String)finalStack.pop() );
}
}
- posted by Max @ 11:06 AM 0 comments
Google Code Jam 2004 Practice Room 500 Point
Problem Statement
A simple network of resistors can be defined recursively as:simple network ::= a simple network in parallel with another simple networksimple network ::= a simple network in series with another simple networksimple network ::= a single resistorIf two networks are in parallel with each other and have resistances r1 and r2, then the total resistance is 1/(1/r1+1/r2). If two networks are in series with each other and have resistances r1 and r2, then the total resistance is r1+r2. If a network is a single resistor, then its resistance is defined as the resistance of that single resistor.You will be given a simple network of resistors represented as a String[], resistors. Each element of resistors will be either "P", "S", or a decimal number. If an element is a number, then it represents a single resistor with resistance defined by that number. If an element is "P", it defines a simple network whose two component simple networks consist of the next two simple networks in resistors. Similarly, if an element is "S", then the next two simple networks in resistors are in series. Thus, the total number of elements that are numbers will be equal to the total number of elements that are "S" or "P" plus 1. For example, {"S","5.3","P","40","60"} represents a simple network where a single resistor with resistance 5.3 is in series with two resistors in parallel with resistances 40 and 60:
+----- 40 ----+
| |
---- 5.3 ---+ +----
| |
+----- 60 ----+
Your task is to compute the total resistance of the network, and return the result as a double. Small rounding errors
will be ignored when examining your result for correctness. As long as your result has a relative or absolute error
of less than 1e-9, it will be judged correct.
import java.util.*;
public class Resistors
{
public static void main(String args[])
{
double result;
String[][] param0 = {{"S","5.3","P","40","60"},
{"S","P","P","1.65","7.59","S","75","1.2","10"}, {"032.350"}};
double[] result_expected = {29.3,11.331670926296885, 32.35};
for(int count = 0; count < result_expected.length; count++)
{
result = getResistance(param0[count]);
if(result != result_expected[count])
System.out.println("Failure:" + result);
else
System.out.println("Success:" + result);
}
}
public static double getResistance(String[] resisters)
{
double ans = 0.0;
Stack myStack = new Stack();
if(resisters.length > 1 )
{
myStack.push( resisters[0] );
myStack.push( resisters[1] );
myStack.push( resisters[2] );
}
else
{
myStack.push( resisters[0] );
}
int j = 3;
while( myStack.size() != 1 )
{
boolean flag = true;
while( myStack.size() >= 3 && flag )
{
String one = (String)myStack.pop();
String two = (String)myStack.pop();
String op = (String)myStack.pop();
if( one.equals("P") || one.equals("S") || two.equals("P")
|| two.equals("S") || !( op.equals("P") || op.equals("S")) )
{
myStack.push(op);
myStack.push(two);
myStack.push(one);
flag = false;
}
else
{
double done = Double.parseDouble( one );
double dtwo = Double.parseDouble( two );
double res = 0.0;
if( op.equals("P") )
{
res = 1/( 1/done + 1/dtwo );
}
else
{
res = done + dtwo;
}
myStack.push("" + res);
flag = true; //check again
}
}
//if still top three elements are solvable revert
if( j != resisters.length )
{
myStack.push( resisters[j] );
j++;
}
}
return Double.parseDouble( (String)myStack.pop() );
}
}
- posted by Max @ 10:48 AM 1 comments
Google Code Jam 2004 Practice Room 250 Point
Problem Statement
There are often a number of cell towers that are within range of a cell phone. Your task is to find the best cell tower for a cell phone at a particular location. You will be given a String[], towers, each of whose elements is formatted as (quotes for clarity) "(
import java.util.*;
public class CellTower
{
public static void main(String args[])
{
String[] param0 = {"(-43.54,632.5331)","(43.53,632.5332)","(-652.23000,00.000)"};
int param1 = 30;
int param2 = 532;
int result;
result = best(param0,param1,param2);
System.out.println( result );
}
public static int best(String[] towers, int x, int y)
{
Point []points = new Point[ towers.length ];
StringTokenizer st;
for( int i = 0; i < towers.length; i++ )
{
points[i] = new Point();
st = new StringTokenizer( towers[i], "(),");
points[i].x = Float.parseFloat( st.nextToken() );
points[i].y = Float.parseFloat( st.nextToken() );
}
Point myp = new Point();
myp.x = x;
myp.y = y;
//now distance from every point
float dis[] = new float[ towers.length ];
for( int i = 0; i < towers.length; i++ )
{
dis[i] = (float)Math.sqrt( (( points[i].x - myp.x ) * (
points[i].x - myp.x )) + (( points[i].y - myp.y ) *
( points[i].y - myp.y )) );
}
float dis2[] = new float[ towers.length ];
for( int i = 0; i < dis.length; i++ )
{
dis2[i] = dis[i];
}
Arrays.sort( dis2 );
int ans = 0;
for( int i = 0; i < dis.length; i++ )
{
if( dis2[0] == dis[i] )
{
ans = i;
break;
}
}
for( int i = 0; i < dis.length; i++ )
{
if( dis[i] <= dis[ans] + 2 )
{
ans = i;
break;
}
}
return ans;
}
}
class Point
{
float x;
float y;
}
- posted by Max @ 10:35 AM 1 comments
SRM 209 DIV 2 - 500 pts
I dint saved the solution for 250 point. But 500 point was also good. Heres the problem statement. I could not complete 900 point problem.
The Olympic Games in Athens end tomorrow. Given the results of the olympic disciplines, generate and return the medal table. The results of the disciplines are given as a String[] results, where each element is in the format "GGG SSS BBB". GGG, SSS and BBB are the 3-letter country codes (three capital letters from 'A' to 'Z') of the countries winning the gold, silver and bronze medal, respectively. The medal table is a String[] with an element for each country appearing in results. Each element has to be in the format "CCO G S B" (quotes for clarity), where G, S and B are the number of gold, silver and bronze medals won by country CCO, e.g. "AUT 1 4 1". The numbers should not have any extra leading zeros. Sort the elements by the number of gold medals won in decreasing order. If several countries are tied, sort the tied countries by the number of silver medals won in decreasing order. If some countries are still tied, sort the tied countries by the number of bronze medals won in decreasing order. If a tie still remains, sort the tied countries by their 3-letter code in ascending alphabetical order.Definition
Heres my solution
import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;
class Country
{
String name;
int gold;
int silver;
int bronze;
Country()
{
name = "";
gold = silver = bronze = 0;
}
public String toString()
{
return (name + " " + gold + " " + silver + " " + bronze);
}
public int compareTo( Country other )
{
if( gold > other.gold )
{
return 1; //this come first
}
else if( gold < other.gold )
{
return -1;
}
if( silver > other.silver)
{
return 1; //this come first
}
else if( silver < other.silver )
{
return -1;
}
if( bronze > other.bronze )
{
return 1; //this come first
}
else if( bronze < other.bronze )
{
return -1;
}
return -1*name.compareTo(other.name);
}
}
public class MedalTable
{
public String[] generate(String[] results)
{
Hashtable cnames = new Hashtable();
for(int i = 0; i < results.length; i++)
{
StringTokenizer st = new StringTokenizer( results[i], " " );
while( st.hasMoreTokens() )
{
cnames.put( st.nextToken(), "" );
}
}
Country cns[] = new Country[ cnames.size() ];
Enumeration en = cnames.keys();
int i = 0;
for(; en.hasMoreElements(); )
{
cns[i] = new Country();
cns[i].name = "" + en.nextElement();
System.out.println(cns[i].name);
i++;
}
for(int k = 0; k < results.length; k++)
{
StringTokenizer st = new StringTokenizer( results[k], " " );
while( st.hasMoreTokens() )
{
String coun = "" + st.nextElement();
for( int j = 0; j < cns.length; j++ )//for gold
{
if( cns[j].name.equals(coun) )
{
cns[j].gold++;
}
}
coun = "" + st.nextElement();
for( int j = 0; j < cns.length; j++ )//for silver
{
if( cns[j].name.equals(coun) )
{
cns[j].silver++;
}
}
coun = "" + st.nextElement();
for( int j = 0; j < cns.length; j++ )//for bronze
{
if( cns[j].name.equals(coun) )
{
cns[j].bronze++;
}
}
}
}
sortCountry( cns );
String out[] = new String[ cns.length ];
for( int k = 0; k < out.length;k++ )
{
out[k ] = cns[k].toString();
}
return out;
}
private void sortCountry( Country cns[] )
{
for( int i = 0; i < cns.length; i++ )
{
for( int j = i + 1; j < cns.length; j++ )
{
if( cns[i].compareTo( cns[j] ) < 0 )
{
Country temp = new Country();
temp = cns[i];
cns[i] = cns[j];
cns[j] = temp;
}
}
}
}
}
- posted by Max @ 7:11 AM 1 comments
First Post
My other blog http://j2megamer.blogspot.com is getting deviated from its original theme. Reason, I am posting lots of codes there. Therefore I decided to create another blog exclusively for code.
- posted by Max @ 5:19 AM 9 comments
