Thursday, August 25, 2011

101 The Blocks Problem - Choosing data structures

The next step is choosing good data structures to deal with the problem.

  • When talking about putting blocks one on top of the other, comes natural to think in terms of stacks.


These stacks should be able to quickly tell whether a particular block is contained inside, for it is an illegal operation to make a movement of any kind if both a and b are piled within the same stack.

One advantage to this problem is having an upper bound of  n<= 25 blocks, so sequential searching is not an issue. I'm even tempted to use a n x n matrix of some sort.

It's late and I'm kind of tired, lets have some rest.

[sourcecode language="java"]

package blocks_problem;
import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
String line;
char a,b;
int numBlocks;
line = cin.nextLine();
numBlocks = Integer.parseInt(line);
while(cin.hasNextLine()) {
line = cin.nextLine();
if(line.contentEquals("quit"))break;
String tokens[]  = line.split("\\s+");
a = tokens[1].charAt(0);
b = tokens[3].charAt(0);
if(tokens[0].contentEquals("move")){
if(tokens[2].contentEquals("onto")){

}
else //tokens[2] == "over"
{

}
}
else // tokens[0] == "pile"
{
if(tokens[2].contentEquals("onto")){

}
else //tokens[2] == "over"
{

}
}
}
}
}

[/sourcecode]

No comments:

Post a Comment