Tuesday, June 19, 2012

Topcoder: Always run system tests in practice.

This post is just to note something that I missed all along.

When practicing in Topcoder practice rooms, just submitting the solution and getting a "submitted for X points" is not enough. There is also a run system test option that should always be tried to ensure that the code really was correct. I wonder why running system tests is not the default in the practice rooms?
Maybe it is because in the real environment, system tests are run after the coding phase had ended, and they expect the coder to think about other cases that have not been mentioned in the problem statement.

I learnt this the hard way, since one of my solutions for the div 2 500 points was successfully challenged, and this prompted me to look for ways to develop more confidence in the code I write.


Monday, May 28, 2012

USACO : Prime cryptarithm


Easier problem overall.

Lost 1 hour in the binary search step, where condition was stated incorrectly by me as >0 when it should have been >=0.

Found a concise way to count number of digits in a number, using Math log to base 10, with special condition for the number 0. I think there might be some better bit twiddling hacks for this, but for now this will do.

/*
ID: abhi
LANG: JAVA
TASK: crypt1
 */

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;


public class crypt1
{
/*
 
   A B C
    D E
 
   2 1 0
     4 3
 
      * * *
   x    * *
    -------
      * * *         <-- partial product 1
    * * *           <-- partial product 2
    -------
    * * * *

 */

private static int[] assigned  = new int[5];
private static int[] possibleNumbers;
private static int solutionCount=0;
// private static int optionCount=0;

public static void main(String[] args) throws NumberFormatException, IOException
{
BufferedReader reader = new BufferedReader(new FileReader(new File("crypt1.in")));
int possibleNumbersCount = Integer.parseInt(reader.readLine());
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());

possibleNumbers = new int[possibleNumbersCount];
for(int i=0;i<possibleNumbersCount;i++) {
possibleNumbers[i]=Integer.parseInt(tokenizer.nextToken());
}
Arrays.sort(possibleNumbers);

assignAndSolve(0);
PrintWriter out = new PrintWriter("crypt1.out");
out.println(solutionCount);
out.close();
// System.out.println(optionCount);
System.exit(0);
}

private static void assignAndSolve(int assignedCount) {
if(assignedCount == 5) {
// optionCount++;
int upper = assigned[0] + (assigned[1]*10) + (assigned[2]*100);
int partialProduct1= upper* assigned[3];
if(!isValid(partialProduct1,3)) {
return;
}
int partialProduct2= upper*assigned[4];
if(!isValid(partialProduct2, 3)) {
return;
}
int sumOfPartialProducts = partialProduct1 + (10*partialProduct2);
if(!isValid(sumOfPartialProducts,4)) {
return;
}
// System.out.println(assigned[2] + " " + assigned[1] + " " + assigned[0] + "\n  " + assigned[3] + " " + assigned[4]);
solutionCount++;
}
else {
for(int i=0;i<possibleNumbers.length;i++) {
assigned[assignedCount]= possibleNumbers[i];
assignAndSolve(assignedCount+1);
}
}
}

private static boolean isValid(int number, int digitCount)
{
int count = (number ==0) ? 1 : (int)Math.log10(number) + 1;
if(count!=digitCount) {
return false;
}
while(number>0) {
int thisDigit=number%10;
if(!(Arrays.binarySearch(possibleNumbers, thisDigit)>=0)) {
return false;
}
number= number/10;
}
return true;
}
}

Monday, May 21, 2012

USACO : calfflac

Just to remind myself later how chaotic my code can be and see my progress as time goes by, this time I want to paste two of my solutions, the first one where I tried to extract common functions and made things too complicated, and the second where I kept things simple. Abstraction and its object oriented cousins are not so helpful when you just want to implement an algorithm,

It seems that if the logic is too convoluted, it gets way out of hand and out of control. Its symptoms are thinking that one more if condition here or there will fix the problem. This only makes the code inordinately long, and then it is just downhill from there.

On the other hand, keeping things simple, having code that runs for the simple cases first, makes it easier to predict where the rest of the test cases are failing.

I also seem to write 90 % of the solution quickly and get stuck trying to pass one or the other test case. That last 10% seems to be taking at least half of the time. Its not the difficulty of the problem, but probably my inexperience. Maybe I should start thinking much more carefully about the corner cases.

I have also noticed that there is a bit of something that I take along from one solution that helps me in the next, cutting those few seconds off my personal time. I am getting faster, from idea to implementation.


Failed Solution:


import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;


public class calfflac2
{
private static String data = null;
private static int maxLength=0, pointer=0;

public static void main(String[] args) throws NumberFormatException, IOException
{
// BufferedReader reader = new BufferedReader(new FileReader(new File("calfflac.in")));
// data = reader.readLine();
// PrintWriter out = new PrintWriter(new File("calfflac.out"));
data="Confucius say: Madam, I'm Adam.";

longestPalindrome();

// out.print(data.substring(pointer, pointer+maxLength));
// out.close();
System.out.println(data.substring(pointer, pointer+maxLength));
System.exit(0);
}

private static boolean isSpecial(char myChar)
{
return myChar=='\n' || myChar==',' || myChar=='\'' || myChar==' ' || myChar==':';
}

private static void longestPalindrome()
{
int upper=0, lower=0, thisLength=0;
// for(int k=0;k<2;k++) {
upper=0;
lower=0;
thisLength=0;
for(int i=0;i<data.length();i++) {
if(isSpecial(data.charAt(i))) // dont' make starting character as special
continue;
// if(k==0) {
// lower=upper=i;
// }
// else {
lower=i;
upper=i+1;
// }

// Just increment and decrement pointers while matching continues, and ignore special characters.
while(true) {
if(lower<0 || upper>data.length()-1) {
break;
}
// ensure that characters are valid.
if(isSpecial(data.charAt(lower))) {
lower--;
continue;
}
if(isSpecial(data.charAt(upper))) {
upper++;
continue;
}

if(Character.toLowerCase(data.charAt(lower))==Character.toLowerCase(data.charAt(upper))) {
thisLength=upper-lower+1;
if(thisLength>maxLength) {
maxLength=thisLength+2;
pointer=lower-1;
}
}

lower--;
upper++;
}
}
}
// }
}

Working solution:

/*
ID: abhi
LANG: JAVA
TASK: calfflac
 */

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;


public class calfflac
{
private static String data="";
public static void main(String[] args) throws IOException
{
BufferedReader reader = new BufferedReader(new FileReader(new File("calfflac.in")));
String line="";
while ((line = reader.readLine()) != null) {
data += line + "\n";
}
longestPalindrome();
System.exit(0);
}

private static void longestPalindrome() throws FileNotFoundException
{
int upper=0, lower=0, thisLength=0, maxLength=0, pointer=-1;
// int countSpecial=0, storeSpecial=0;
PrintWriter writer = new PrintWriter(new File("calfflac.out"));
for(int k=0;k<2;k++) {
for(int i=0;i<data.length();i++) {
upper=i+k; lower=i;
thisLength=0;
// countSpecial=0;
while(lower>=0 && upper<data.length() 
&& (Character.toLowerCase(data.charAt(lower))==Character.toLowerCase(data.charAt(upper)))) {
thisLength=upper-lower +1 ;
if(thisLength>maxLength) {
maxLength=thisLength;
pointer=lower;
// storeSpecial= countSpecial;
}
lower--;
while(lower>0 && isSpecial(data.charAt(lower))) {
lower--;
// countSpecial++;
}
upper++;
while(upper<data.length() && isSpecial(data.charAt(upper))) {
upper++;
// countSpecial++;
}
}
}
}
// writer.println(maxLength-storeSpecial);
int count=0;
for(int i=0;i<maxLength;i++) {
if(isSpecial(data.charAt(pointer+ i))) {
count++;
}
}
writer.println(maxLength-count);
writer.println(data.substring(pointer, pointer+maxLength));
writer.close();
}
private static boolean isSpecial(char myChar)
{
return !( (myChar>=65 && myChar<=90) || (myChar>=97 && myChar<=122));
}
}

Thursday, May 17, 2012

Barn Repair : USACO, Greedy algorithms


It is beginning to take huge amounts of time to solve these problems, simply because I refuse to read the writeup/tutorials from USACO and also the problem statement properly, and am not as disciplined as I need to be to cover the corner cases in the first cut itself.

Must approach the problem step by step, it is almost always easier than it seems once I start writing the conditions in code.
Must consider what happens if the input is not in sorted order and if the loop breaking conditions are comprehensive.

I was very sloppy when it came to implementation, and refused to observe carefully the boundary conditions. Maybe it is because I write this in the middle of the night.

Another factor that concerns me is the length of this code. Time taken to write code is related to its length, and it needs to get much shorter to be useful.

I think writing the complete logic in detail on paper might be a good exercise, just to see if the IDE is making me too lazy.

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;


public class barn1
{
static boolean[] stallStatus ;
static int[] occupiedPositions;
static boolean[] answer;
static int maxBoards=0, stalls=0, countCows=0;

public static void main(String[] args) throws NumberFormatException, IOException
{
// READ INPUTS
BufferedReader reader = new BufferedReader(new FileReader(new File("barn1.in")));
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());

// INITIALIZE VARIABLES
maxBoards = Integer.parseInt(tokenizer.nextToken());
stalls = Integer.parseInt(tokenizer.nextToken());
countCows = Integer.parseInt(tokenizer.nextToken());


answer= new boolean[stalls+1];
Arrays.fill(answer, false);

occupiedPositions = new int[countCows];
// STORE POSITIONS OCCUPIED BY COWS
for(int i=0;i<countCows;i++) {
int position=Integer.parseInt(reader.readLine());
occupiedPositions[i]=position;
answer[position]=true;
}

Arrays.sort(occupiedPositions);

// Select the board which has longest section that does not need to be covered.
// First, assume that the complete space is one board.
// Guess, we need to keep track of all boards, and search only within all boards.

// ith position is for ith board
int[] boardBegin = new int[maxBoards+1];
int[] boardEnd = new int[maxBoards+1];

int boardCreated=0;
boardBegin[boardCreated]=occupiedPositions[0];
boardEnd[boardCreated]=occupiedPositions[countCows-1];
// iterate over space between each board, using answer array.
// this should be run length encoding type code to find the longest unoccupied length.
boardCreated++;
int selectedBoardIndex=0;
while(boardCreated<maxBoards) { // DO THIS UNTIL WE HAVE BROKEN TO DESIRED COUNT

// Finding the longest run in all boards.
int longestRun=0, thisRun=0, startPosition=0;
for(int boardIndex=0;boardIndex<=boardCreated;boardIndex++) { // IN RANGE MENTIONED
for(int k=boardBegin[boardIndex]; k<boardEnd[boardIndex];) {
if(!answer[k]) {
thisRun++;
if(thisRun>longestRun) {
longestRun=thisRun;
selectedBoardIndex=boardIndex;
startPosition=k-thisRun+1;
}
}
else {
thisRun=0;
}
k=k+1;
}
}

// System.out.println("Longest run is : " + longestRun  + " from,to :" + (startPosition-1) + " " + (startPosition + longestRun));
// Breaking the board.
boardEnd[boardCreated] = boardEnd[selectedBoardIndex];
boardEnd[selectedBoardIndex]=startPosition-1;
boardBegin[boardCreated]=startPosition + longestRun;

sort(boardBegin, boardEnd, boardCreated);
printBoards(boardBegin, boardEnd, boardCreated);
boardCreated++;

int counter=0;
for(int boardIndex=0;boardIndex<boardCreated;boardIndex++) {
for(int k=boardBegin[boardIndex]; k<=boardEnd[boardIndex]; k++) {
// if(answer[k]) {
counter++;
// }
}
}
if(counter==countCows) {
break;
}
}

// CALCULATING STALLS BLOCKED
int counter=0;
for(int boardIndex=0;boardIndex<boardCreated;boardIndex++) {
for(int k=boardBegin[boardIndex]; k<=boardEnd[boardIndex]; k++) {
// if(answer[k]) {
counter++;
// }
}
}
// System.out.println(counter);
PrintWriter out = new PrintWriter(new File("barn1.out"));
out.println(counter);
out.close();
System.exit(0);
}

private static void sort(int[] boardBegin, int[] boardEnd, int boardCreated)
{
for(int i=0;i<=boardCreated;i++) {
for(int j=i+1;j<=boardCreated;j++) {
if(boardBegin[j]<boardBegin[i]) {
int temp = boardBegin[i];
boardBegin[i]=boardBegin[j];
boardBegin[j]=temp;

temp = boardEnd[i];
boardEnd[i]=boardEnd[j];
boardEnd[j]=temp;
}
}
}
}

private static void printBoards(int[] boardBegin, int[] boardEnd, int boardCreated)
{
for(int i=0;i<=boardCreated;i++) {
System.out.print("(" + boardBegin[i] + "," + boardEnd[i] + ")");
}
System.out.println();
}
}

Monday, May 14, 2012

Topcoder: GogoxCake (Single Round Match 530 Round 1 - Division II, Level Two)


For too long I have been focused on dynamic programming, which I must admit is slightly on the harder side when it comes to recognizing and applying quickly. Its evil twin, greedy, is much more implementation friendly.

There is mention of matroid theory, an approach that can be used for theoretically proving if greedy approach is valid to a particular problem or not. But haven't come around to actually reading it.

For now, my personal rules for greedy: if it is an optimization problem, which seems like Dynamic programming, and if bigger problems seem to be a copy of smaller problems and optimal solution to a smaller problem is sure to be part of optimal solution to the bigger problem, then greed is good.

Here is a practice problem from a recent Topcoder SRM(530), solved of course in a leisurely non contest environment. Once it is clear that a greedy solution is possible, it's just implementation.

Notes to myself: Wasted some time when trying to position the cutter over the cake. Made a mistake when evaluating boundary conditions, using the sizes along x and y for both cutter and cake.

Another observation is that one should work with the data structure provided by the problem statement. Trying to convert the input data into a more understandable array of something, or some other custom data structure, is also a waste of time. Exception is when the original data needs to be preserved, in which case a copy may be made using arrayCopy.

public class GogoXCake
{
public String solve(String[] cake, String[] cutter) {
int cutterSizeX = cutter[0].length();
int cutterSizeY = cutter.length;
int cakeSizeX= cake[0].length();
int cakeSizeY=cake.length;
for(int i=0; i<cake.length;i++) {
for(int j=0;j<cake[i].length();j++) {
if(cutterSizeX<=cakeSizeX-j && cutterSizeY<=cakeSizeY-i && cake[i].charAt(j)=='.' ) { // if cake is empty, position cutter at this location.
for(int p=0;p<cutter.length;p++) {
for(int q=0;q<cutter[p].length();q++) {
if(cutter[p].charAt(q)=='.' && cake[i+p].charAt(j+q)=='.') {
cake[i+p]=cake[i+p].substring(0, j+q)+ 'X' + cake[i+p].substring(j+q+1);
}
}
}
}
}
}
// for(int i=0; i<cake.length;i++) {
// for(int j=0;j<cake[i].length();j++) {
// System.out.print(cake[i].charAt(j) + " ");
// }
// System.out.println();
// }

for(int i=0; i<cake.length;i++) {
for(int j=0;j<cake[i].length();j++) {
if(cake[i].charAt(j)=='.') { // if cake is empty, position cutter at this location.
return "NO";
}
}
}
return "YES";
}
}

Wednesday, May 9, 2012

Palindromic Squares : USACO


Slightly easier problem this time.
Simple solution, 
Missed the second condition in :
       if(remainder>base || remainder>=10)
and it took the failing test cases to remind of this mistake.

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;

public class palsquare
{
public static void main(String[] args) throws NumberFormatException, IOException
{
// System.out.println(decimalToBaseB(120, 11));
BufferedReader reader = new BufferedReader(new FileReader(new File("palsquare.in")));
int base = Integer.parseInt(reader.readLine());

PrintWriter out = new PrintWriter(new FileWriter(new File("palsquare.out")));

String result;
for(int i=1;i<=300;i++) {
result = decimalToBaseB(i*i, base);
if (isPalindrome(result)) {
// System.out.println(i + " " + decimalToBaseB(i, base) + " " + result);
out.println(decimalToBaseB(i, base) + " " + result);
}
}
out.close();
System.exit(0);
}

private static boolean isPalindrome(String result) {
int middle=result.length()/2;
for(int i=0;i<middle;i++)
if(result.charAt(i)!=result.charAt(result.length()-i-1))
return false;
return true;
}

private static final String symbols = "0123456789ABCDEFGHIJ"; // we support till base 20

private static String decimalToBaseB(int number, int base) {
int quotient=0, remainder=0;
String result="";
while(number!=0) {
quotient = number/base;
remainder = number%base;
if(remainder>base || remainder>=10) {
result= symbols.charAt(remainder) + result;
}
else {
result= remainder + result;
}
number= quotient;
}
return result;
}
}

"Name that Number" from USACO


Here is my solution to "Name that Number", from USACO.

Lessons learnt:

Two iterations over data might still be O(2N) which is same as O(N), but it will cross the 1 second time limit. Minimize operations, including iteration.
Also, reduce reliance on String, and prefer char arrays, specially when using recursion. Even StringBuffer/StringBuilder isn't good enough when compared to arrays.
Also, avoid writing custom binary search, as it'll take too much time, use java's inbuilt support instead.
Keep constant data/ result data structure at class level, recursive calls should use only the bare necessary arguments which are used to generate the output.

I wasted time on the Time limit exceeded. I first tried to optimize away the I/O. Again, to optimize algorithm, it is better to look at the loops first rather than constant operations.

BTW, validNames() should get the dictionary. I hardcoded it to squeeze some performance, didn't help much though.

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

public class namenum
{
private static String[] validNames = null;
private static char[][] map = createMap();
private static char[] numberc = null;
private static int[] number = null;
private static PrintWriter out=null;
private static boolean dataPresent = false;

public static void main(String[] args) throws IOException
{
validNames = getValidNames();

BufferedReader reader2 = new BufferedReader(new FileReader(new File("namenum.in")));
numberc = reader2.readLine().toCharArray();
number = new int[numberc.length];
int i=0;
for(char c : numberc) {
number[i++]=c-48;
}

out = new PrintWriter(new FileWriter(new File("namenum.out")));
createNames(0, "");

if(!dataPresent) {
out.println("NONE");
}
out.close();
System.exit(0);
}

private static void createNames(int numberIndex, String name)
{
if (numberIndex == number.length)
{
if (Arrays.binarySearch(validNames, name) >= 0)
{
dataPresent=true;
out.println(name);
}
}
else
{
for (char letter : map[number[numberIndex]])
{
createNames(numberIndex + 1, name + letter);
}
}
}

private static char[][] createMap()
{
char[][] map = new char[][] { {}, {}, { 'A', 'B', 'C' },
{ 'D', 'E', 'F' }, { 'G', 'H', 'I' }, {'J', 'K', 'L'} , { 'M', 'N', 'O' },
{ 'P', 'R', 'S' }, { 'T', 'U', 'V' }, { 'W', 'X', 'Y' }, };
return map;
}

private static String[] getValidNames()
{
               validNames = new String[] {"AARON" };
        }
}