Data Structures help

[MIke Beam]

I am trying to solve a problem in Java and need some help. I basically
need to figure out how many possible 7 digit numbers can be mapped out
of a number keypad, while moving like any chess peice.

123
456
789
#0*

For example, starting in the upper-right corner (the "3" key) using a
rook (which moves any number of spaces horizontally or vertically),
one valid number is: 314-5289.

I figured out how to get every possible move, I now need a good way to
represent the data, so I can traverse it to find my solutions.

any ideas?

thanx
mike

 

[Joe]

I figured out how to get every possible move, I now need a good way to
represent the data, so I can traverse it to find my solutions.

any ideas?

The teacher who gave you this assignment is mentally ill. Alert the
authorities and do not try to apprehend them yourself.

 

[Roedy Green]

I am trying to solve a problem in Java and need some help. I basically
need to figure out how many possible 7 digit numbers can be mapped out
of a number keypad, while moving like any chess peice.

for each chess piece you need to invent a function that provides a
list of relative x,y jumps it can make.

e.g. rook is 0,1 1,0 0,2 2,0 0,3 3,0

Now for each piece for each starting point, you enumerate all moves
continuing till you either get a 7 digit number or jump off the
chessboard. You probably have to dedup your list of 7 digit numbers
since there will be many ways of getting a number. Try a
java.util.BitSet to track your successes.

See http://mindprod.com/jgloss/combination.html

This is not a good student problem. You as student have no way of
knowing if you did it correctly. The teacher has an easy job -- just
check the number to prove correctness. You can though exercise your
code with one simplified chess piece, on a smaller square to test your
logic.

Some might be tempted to take revenge on this prof by asking a bright
student the magic final answer, then writing gibberish code that gives
that result and let the prof baffle over why it does.

 

[Larry Coon]

I figured out how to get every possible move, I now need a good way to
represent the data, so I can traverse it to find my solutions.

Yuck. Use a recursive solution. You are building a
string of length seven. At any position i in the string,
if you are adding the seventh "move," then you increment
your counter. Otherwise, you generate all the moves for
the current piece, and iterate over them, calling yourself
recursively to solve for positions i + 1 to 7.

If you don't have to worry about dupiicates (is a queen
moving 1-2-1-2-1-2-1 the same as a rook making the same
moves?) then this should be effective enough.


Larry Coon
University of California

 

[Roedy Green]

If you don't have to worry about dupiicates (is a queen
moving 1-2-1-2-1-2-1 the same as a rook making the same
moves?) then this should be effective enough.

You can ignore pawn, bishop and rook and king. Queen and knight
suffice since combined they can do anything any of the others can.

 

[antroy]

I am trying to solve a problem in Java and need some help. I basically
need to figure out how many possible 7 digit numbers can be mapped out
of a number keypad, while moving like any chess peice.

123
456
789
#0*

For example, starting in the upper-right corner (the "3" key) using a
rook (which moves any number of spaces horizontally or vertically),
one valid number is: 314-5289.

I figured out how to get every possible move, I now need a good way to
represent the data, so I can traverse it to find my solutions.

any ideas?

Assuming each number must be generated by a single piece, then you could
do it the following way:

For each of the two relevant pieces, Queen and Knight, set up a graph
structure to represent the possible moves available from each square.
You could do this by having a node object for each digit, which holds
that digit, and a reference to each node it can reach (in a nine element
array since this is the largest number of other nodes).

Then, set up a method say public Set getDigits(String numb) which sets
up a String containing numb + (the current digit), and if

class DigitNode{
private int keypadDigit;
private DigitNode[] destinations = new DigitNode[9];

public Set getDigits(String num, int count){
count++;
String number = num + keypadDigit;
Set out = new HashSet();
if (count == 7) {
out.add(number);
} else{
for (int i = 0; destinations != null; i++){
out.addAll(destinations.getDigits(number, count));
}
return out;
}
}

Or something along those lines. You'll then need another method to call
getDigits(...) on each Node, and for each Graph, so you'll have 20 sets
generated. Add up set.size() for each result.


HTH.