Data Structures help

Discussion in 'Java' started by MIke Beam, Oct 10, 2003.

  1. MIke Beam

    MIke Beam Guest

    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
     
    MIke Beam, Oct 10, 2003
    #1
    1. Advertising

  2. MIke Beam

    Joe Guest

    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.
     
    Joe, Oct 10, 2003
    #2
    1. Advertising

  3. MIke Beam

    Roedy Green Guest

    On 10 Oct 2003 09:46:44 -0700, (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.
     
    Roedy Green, Oct 10, 2003
    #3
  4. MIke Beam

    Larry Coon Guest

    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
     
    Larry Coon, Oct 13, 2003
    #4
  5. MIke Beam

    Roedy Green Guest

    On Mon, 13 Oct 2003 09:25:44 -0700, Larry Coon <>
    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.
     
    Roedy Green, Oct 13, 2003
    #5
  6. MIke Beam

    antroy Guest

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

    --
    Ant...
     
    antroy, Oct 14, 2003
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Dennis Gavrilov
    Replies:
    1
    Views:
    1,458
    Dennis Gavrilov
    Jul 24, 2003
  2. tweak
    Replies:
    14
    Views:
    2,796
    Eric Sosman
    Jun 11, 2004
  3. Alfonso Morra
    Replies:
    11
    Views:
    728
    Emmanuel Delahaye
    Sep 24, 2005
  4. osp
    Replies:
    3
    Views:
    298
    mlimber
    May 25, 2006
  5. Clint Olsen

    Help with tied/nested data structures

    Clint Olsen, Jul 19, 2006, in forum: Perl Misc
    Replies:
    12
    Views:
    152
    Mumia W.
    Jul 20, 2006
Loading...

Share This Page