Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > Data Structures help

Reply
Thread Tools

Data Structures help

 
 
MIke Beam
Guest
Posts: n/a
 
      10-10-2003
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
 
Reply With Quote
 
 
 
 
Joe
Guest
Posts: n/a
 
      10-10-2003
On Fri, 10 Oct 2003 09:46:44 -0700, MIke Beam wrote:

> 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.
 
Reply With Quote
 
 
 
 
Roedy Green
Guest
Posts: n/a
 
      10-10-2003
On 10 Oct 2003 09:46:44 -0700, http://www.velocityreviews.com/forums/(E-Mail Removed) (MIke Beam) wrote or
quoted :

>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.


--
Canadian Mind Products, Roedy Green.
Coaching, problem solving, economical contract programming.
See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.
 
Reply With Quote
 
Larry Coon
Guest
Posts: n/a
 
      10-13-2003
MIke Beam wrote:

> 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
 
Reply With Quote
 
Roedy Green
Guest
Posts: n/a
 
      10-13-2003
On Mon, 13 Oct 2003 09:25:44 -0700, Larry Coon <(E-Mail Removed)>
wrote or quoted :

>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.


--
Canadian Mind Products, Roedy Green.
Coaching, problem solving, economical contract programming.
See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.
 
Reply With Quote
 
antroy
Guest
Posts: n/a
 
      10-14-2003
MIke Beam wrote:
> 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[i] != null; i++){
out.addAll(destinations[i].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.

--
Ant...


 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Help with tied/nested data structures Clint Olsen Perl Misc 12 07-20-2006 11:23 AM
data structures please help which book ? osp C++ 3 05-25-2006 03:08 PM
structures, structures and more structures (questions about nestedstructures) Alfonso Morra C Programming 11 09-24-2005 07:42 PM
Type Casting IPv4 and IPv6 structures to Generic Structures tweak C Programming 14 06-11-2004 02:43 PM
sharing complex data structures between threads in mod_perl2 Dennis Gavrilov Perl 1 07-24-2003 07:22 AM



Advertisments