Solved

Java help

Posted on 2006-10-20
53
364 Views
Last Modified: 2007-12-19
I have this problem posted in http://img97.imageshack.us/my.php?image=albsin9.jpg however i dont understand what the question is asking about and do not know how to solve it. Hope someone can help me on this problem and so i can start and ***i must say this is a homework *** so i dont want whole program to be posted.

Thannks



0
Comment
Question by:heyhey84
  • 23
  • 22
  • 6
  • +1
53 Comments
 
LVL 6

Expert Comment

by:valipotor
ID: 17779251
0
 
LVL 6

Expert Comment

by:valipotor
ID: 17779253
sorry, wrong post
0
 

Author Comment

by:heyhey84
ID: 17780134
Help needed...............!!!!!!!!
0
 

Author Comment

by:heyhey84
ID: 17780751
0
 
LVL 9

Expert Comment

by:shinobun
ID: 17781160
0
 
LVL 9

Expert Comment

by:shinobun
ID: 17781166
0
 
LVL 9

Expert Comment

by:shinobun
ID: 17781294
In your assignment, "Word Ladder" seems like you are only allowed to change one letter.  No adding, removing, or reordering as in the original definition.

(there are at most 25 * length of work neighbours)
0
 

Expert Comment

by:babypink
ID: 17782495
I'm not allow to  use HashMap, HashSet or Hashtable class and hashCode method of the String class.

i also donno what the step i should do?

What i have in mind is that given a string, convert it to an integer and put this string into an array using a hash function.

can guide me what the data structure n algo to use?



0
 

Author Comment

by:heyhey84
ID: 17782524
Firstly how to convert the string to a integer value without using the hashCode()?

secondly -> (there are at most 25 * length of work neighbours) i have already done that, but i what i am suppose to do with this?
0
 
LVL 9

Expert Comment

by:shinobun
ID: 17782736
>> babypink

You guys go to the same school or something?  :)
Anyways, it's heyhey84's question, so I'll put your questions aside for now.  If you read all the articles I posted, and follow this thread, you should be able to figure it out.

>> Firstly how to convert the string to a integer value without using the hashCode()?

Read the following articles, and tell us which part you can't figure out:

http://en.wikipedia.org/wiki/Hash_function
http://en.wikipedia.org/wiki/Hash_table

>> (there are at most 25 * length of work neighbours) i have already done that, but i what i am suppose to do with this?

If I read the assignment correctly, this method is already provided as a method called "generateNeighbours".  And as what to do with that, quoting your assignment:

"A better strategy is to first construct a hash table from the dictionary, so that given any word you can generate all possible neighbouring words and for each one you only need to check whether it is in the hash table."
0
 

Author Comment

by:heyhey84
ID: 17782779
so what is the step i should do?

becoz i really dont know why need to use hashing and BFS

Too bad it is hard to explain in words instead of drawing........


shinobun  are u able to explain in drawing for my assignment?
0
 
LVL 9

Expert Comment

by:shinobun
ID: 17782899
I'm not good at drawing, but some easy answers to your questions:

You need BFS because that is what this assignment is about.  It is also a good algorithm to use to find paths from one place to another, which is what this word ladder is all about.  The picture in the article about the German cities might help you visualize what you are trying to accomplish.  (The BFS part, at least.)

http://en.wikipedia.org/wiki/Breadth-first_search

You need hashing because otherwise, you will not be able to implement a hash table.  In the pictures in the article, the conversion from Keys to Indexes is where you need the hashing.

http://en.wikipedia.org/wiki/Hash_table
0
 

Author Comment

by:heyhey84
ID: 17782926
so given a string "abc" i will hash it to a integer.

then with this integer(indexs) i store all the neighbour "abc" in an array of object?

what is the correct step to solve this problem?

0
 

Author Comment

by:heyhey84
ID: 17783444
Any experts can help?

Thanks in advance
0
 
LVL 9

Expert Comment

by:shinobun
ID: 17783610
>> so given a string "abc" i will hash it to a integer.

This part is your homework.  Requirement #2:  "You are required to implement your own hash function for Strings,"

The simplest hash function is to return a constant.  However, this implementation is far from practical.  (But it fulfills all requirements for a hash function.)

The most intuitive hash function for words would be to convert it to the page the word is listed in a dictionary.  That's not possible with programming, but you can simulate it by passing the ASCII value of the first letter.  (A 26 page dictionary!)  However, this is also far from practical.

Here's something to chew on:

private int yourOwnHashFunction(String word) {
  int hash = 0;
  // implement me!
  return hash;
}

>> then with this integer(indexs) i store all the neighbour "abc" in an array of object?

That would be Requirement #1:  "Implement your own hash table class,"

You should read the hash table article for the details of implementation:

http://en.wikipedia.org/wiki/Hash_table

But here's something to chew on:

public class YourOwnHashTable {
  // an array of object
  public void put(String word, String[] neighbours);
  public String[] get(String word);
}

In your code, you would do this to register:

YourOwnHashTable hashTable = new YourOwnHashTable();
hashTable.put(word, generateNeighbours(word));

And to get the neighbours:

String[] neighbours = hashTable.get(word);

I'm not saying this is the only way to do it, but it is definitely one way you can do it.  :)
0
 

Expert Comment

by:babypink
ID: 17783656
After implemting my own hash method and hashtable, how can i use them to solve my problem?
0
 

Expert Comment

by:babypink
ID: 17783657
can u explain step by step....

Thanks in advance
0
 
LVL 9

Expert Comment

by:shinobun
ID: 17783699
>> babypink

This is heyhey84's question.  Please read through all the articles I posted.  They all have some pseudo-code, and it's just a combination.
0
 

Author Comment

by:heyhey84
ID: 17783735
Hi shinobun ,

Really it would be good that u can explain step by step though.

Example

Step 1 - convert string to integer using implmented hash function
Step 2 .... etc.......
0
 
LVL 9

Expert Comment

by:shinobun
ID: 17783758
OK.  First, let's implement each piece separately.  We'll pull them together after that.

Step 1.  Implement your hash function.
Step 2.  Implement your hash table.
Step 3.  Implement your BFS.
Step 4.  We'll talk about combining these when we get here.
0
 

Expert Comment

by:babypink
ID: 17783919
Haha :)

Those are the step in heyhey84 assignment.
whats the point saying it again.

I think heyhey84 is having problem implementing them.
0
 

Author Comment

by:heyhey84
ID: 17783970
Step 1 done
private static int hashFunction(String s) {
              
        int result = 0;
        int B = 3;
          for (int i = 0; i < s.length (); ++i)
            result = result * B + s.charAt (i);
          return result;
              
      }
Need help in step 2....
Need more specific detail like what method (add and get) etc
add into what data structure? what data structure to use? and what to add?
get what?

0
 
LVL 9

Expert Comment

by:shinobun
ID: 17784251
>> whats the point saying it again.

It's incremental learning.  Even if you don't see the entire picture at the beginning, if you do it step by step, your questions are answered on the way.  The professor is good at giving the assignment.  :)

>> Need more specific detail like what method (add and get) etc

You basically only need a put and get as public methods.

>> add into what data structure? what data structure to use?

Read the hash table article for how a hash table is structured.  It even has some pseudo-code!

http://en.wikipedia.org/wiki/Hash_table

>> and what to add?
>> get what?

Read your assignment.  What does it say about using the hash table?

Hint: "A better strategy is to..."
0
 

Author Comment

by:heyhey84
ID: 17786214
Given this is the generateNeighbours(String word) method

private static List<String> generateNeighbours(String word){

}

Am i correct for my class myhashTable?

class myhashTable {
 
   // an array of object
   Object[] container = null;
   
  // contructor
  public myhashTable (int n){
        
        container = new Object[n];
        
        }
        
  public void add(String word, List<String> neighbours){
        
        
        }
        
  public void get(String word){
        
        
        }
}
0
 

Author Comment

by:heyhey84
ID: 17786260
This is in my main statement.......

hTable.put(hashFunction(word),generateNeighbours(word));


This is my hashTable class . Am i on the right track?

public myhashTable (int n){
        
         Object container = new Object[n];
        
        }

public void put(int key, List<String> neighbours){
        
        container[key] = neighbours;
        }
0
 

Author Comment

by:heyhey84
ID: 17786300
Hi shinobun,

Below is the where i have done. Can u help me see am i correct?
Did i implemented the hashFunction and hashTable correctly?
Am i on the right Track for my assignment?
Because i do not have a clear picture in mind how to do a BFS
I just follow the step u mention
Below is implemention of Step 1 and Step 2 :)


import java.io.*;
import java.util.*;

public class WordLadder {      
      
      
    public static void main(String[] args) throws IOException {      
            
    Scanner input = new Scanner(System.in);
   
    int m = input.nextInt();
   
    myhashTable hTable = new myhashTable(m);
   
    for (int i=0; i<m;i++)
    {
          String word = input.next();
          
          hTable.put(hashFunction(word),generateNeighbours(word));
                    
    }
   
    int start = hashFunction(input.next());
    int end = hashFunction(input.next());
   
   
   
  }// end of main      
      
    // start of generateNeighbours method
    private static List<String> generateNeighbours(String word) {
        //precondition: word != null
        assert word != null : "null input in generateNeighbours";
        //postcondition: returns a list of neighbours of word
 
        //generate neighbours in lexicographical order
      List<String> result = new LinkedList<String>();
      char [] letters = word.toCharArray();
      for (int i = 0; i < letters.length; i++) {
          for (char c = 'a'; c <= 'z'; c++) {
            if (c != word.charAt(i)) {
                letters[i] = c;
                String w = new String(letters);
                result.add(w);                              
            }                  
          }
          letters[i] = word.charAt(i);
      }
      Collections.sort(result);            
      return result;
    }// end of generateNeighbours method
   
    // start of hashFunction
    private static int hashFunction(String s) {
              
              int result = 0;
              int B = 7;
          for (int i = 0; i < s.length (); ++i)
          {
                result = result * B  + s.charAt (i);
          }
            
          return result;
              
      }// end of hashfunction methold
}// end of WordLadder



class myhashTable {
 
   // an array of object
   Object[] container = null;
   
  // contructor
  public myhashTable (int n){
        
        container = new Object[100000];
        
        }
 
  // put method      
  public void put(int key, List<String> neighbours){
        
        container[key] = neighbours;
        
        }
        
  // get method
  public Object get(int key){
                
        return container[key];
        
        }
}// end of class myhashTable
0
Do You Know the 4 Main Threat Actor Types?

Do you know the main threat actor types? Most attackers fall into one of four categories, each with their own favored tactics, techniques, and procedures.

 
LVL 9

Expert Comment

by:shinobun
ID: 17786473
Some quick comments (I haven't actually tried out your code, though):

So the generateNeighbours method you need to implement by yourself.  :)
Looks OK.

hashFunction : looks OK.

myhashTable : You will need to be able to convert the word to a List<String>.  So, instead of taking in the key, you will need to take in the word.  This is because two different words might have the same hash result, in which case you will not be able to retrieve the correct neighbours.

public void put(String word, List<String> neighbours)
public List<String> get(String word)
0
 
LVL 9

Expert Comment

by:shinobun
ID: 17786489
>> myhashTable

So your first attempt on the class was very close.  :)
0
 

Expert Comment

by:babypink
ID: 17786529
-->This is because two different words might have the same hash result, in which case you will not be able to retrieve the correct neighbours.

Then how i going to use array[index] to store the neighbour without a key?

Maybe u can try out my program..... :)
0
 
LVL 9

Expert Comment

by:shinobun
ID: 17786530
As for the BFS, you might want to go through the article again, especially the "How it works" section.  I find the two diagram of finding the path from Frankfurt to Munchen quite helpful.  You can ignore the distance part, as that is irrelevant in your case (the distance is always 1).

http://en.wikipedia.org/wiki/Breadth-first_search
0
 
LVL 9

Expert Comment

by:shinobun
ID: 17786540
You can read the "Collision resolution" section of the hash table article for some hints for your implementation.

http://en.wikipedia.org/wiki/Hash_table
0
 

Author Comment

by:heyhey84
ID: 17786600
Let ignore the Collision part at the moment.

I want to foucs on the BFS so as i can somehow complete my program and tune it when everything is done. So i presume that my program above is ready to go for BFS :)

Given Dictionary
dot
cat
cot
dog
start -> cat  end ->dog

BFS
Step 1 - hashFunction start-->"cat" and look for all neighbour
Step 2 - in Lexicographical order look into the neighbour 1 by 1 until there is one contain in Given Dictionary -> set it to current
step 3 - recursively search until current == end then return the step

Is this algo correct? and what thw assignment is looking for? thanks
0
 
LVL 9

Expert Comment

by:shinobun
ID: 17786627
>> Let ignore the Collision part at the moment.

OK.

>> Is this algo correct? and what thw assignment is looking for?

That would be one way to search for a Word Ladder, but that does not use the BFS algorithm.  Read the "How it works" and "Algorithm (informal)" section to understand what the concept of BFS is.  And you can try converting the "Pseudocode" section to java to give it a try.

http://en.wikipedia.org/wiki/Breadth-first_search
0
 
LVL 9

Expert Comment

by:shinobun
ID: 17786631
And remember the Hints on your assignment.
0
 

Author Comment

by:heyhey84
ID: 17786642
i really dont understand the hint

#
Instead of storing the distance from the start, you should store a value which indicates the “parent” of a word. The parent of a word w is the word which caused w to be added to the queue.
#
After completing the breadth first search starting from the start word, we simply start from the end word and trace the parent links to retrieve the actual word ladder.


0
 

Author Comment

by:heyhey84
ID: 17786647
Really hope u can help to code a little for the BFS.............

0
 

Author Comment

by:heyhey84
ID: 17786664
For my case

Given Dictionary, start and end

What is my parent node?
what is my child node?
0
 
LVL 9

Expert Comment

by:shinobun
ID: 17788347
Which part of the article don't you understand?  If you don't understand BFS, you won't be able to go further.  Actually, you can by blindly implementing it from the "Pseudocode" section, if coding it lets you understand the algorithm better.

http://en.wikipedia.org/wiki/Breadth-first_search
0
 
LVL 9

Expert Comment

by:shinobun
ID: 17788391
In the article's diagram,

Given Dictionary = cities of Germany
start = Frankfurt
end = Munchen

Frankfurt is the parent of Mannheim, Wurzberg, Kassel.
Munchen is the child node of Kassel.  However, it will not be a child node of Augsburg or Numberg because Munchen would already be a visited node.
0
 

Author Comment

by:heyhey84
ID: 17788858
i dont really understand BFS.......

Anymore good website then wikipedia.....

Wikipedia seem like very general........
0
 
LVL 9

Expert Comment

by:shinobun
ID: 17788943
http://www.google.com/search?q=breadth+first+search

If you don't understand the general idea, how are you going to apply it to java?
0
 

Author Comment

by:heyhey84
ID: 17789025
Looiking at cities of Germany

haha look quite simple

From Parent node Frankfurt
enqueue all the child node
visit the child node and enqueue the grandchild node and so on................

if nodes are visited ignore it.........

Correct? How to apply to my problem?
0
 
LVL 9

Expert Comment

by:shinobun
ID: 17789484
>> enqueue all the child node

Not all, only the child nodes that are not yet visited.

>> How to apply to my problem?

Replace the cities with "dot","cat","cot","dog"
Replace the left diagram with your hash table from words to neighbours.
Replace "Frankfurt" with "cat".
Replace "Munchen" with "dog".

You problem is to create the right diagram using the same algorithm.
0
 

Author Comment

by:heyhey84
ID: 17793220
-->Replace the left diagram with your hash table from words to neighbours.

What u mean?
0
 
LVL 9

Expert Comment

by:shinobun
ID: 17793284
How would "dot","cat","cot","dog" connect to each other?  Which words are considered connected?
0
 

Author Comment

by:heyhey84
ID: 17793439
-->How would "dot","cat","cot","dog" connect to each other?

changing 1 letter at a time?

-->Which words are considered connected?

????
0
 
LVL 9

Expert Comment

by:shinobun
ID: 17793539
>> changing 1 letter at a time?

Exactly.  And you already have a way to check if one word is connected to another.

>> ????

I'm just trying to let you have an image of what needs to happen here.  Which words are just 1 letter apart?
0
 

Author Comment

by:heyhey84
ID: 17793569
:(

Still cant figure the algo for BFS in my problem
0
 
LVL 9

Expert Comment

by:shinobun
ID: 17793617
Are "dot" and "cat" 1 letter apart?
Are "dot" and "cot" 1 letter apart?
Are "dot" and "dog" 1 letter apart?
Are "cat" and "cot" 1 letter apart?
Are "cat" and "dog" 1 letter apart?
Are "cot" and "dog" 1 letter apart?

Connect all the ones you answered "yes" to with lines, and you have your left diagram.

Now take a look at "cat".  This would become the "Frankfurt" in the right diagram.
Which words is it connected to?  Those would become the "Mannheim", "Wurzberg", "Kassel" in the right diagram.  And so forth.

Now where is "dog"?  With BFS, you will start with "cat", go to the next row from left to right, then to the next from left to right, an so on until you reach "dog".
0
 

Author Comment

by:heyhey84
ID: 17793796
Are "dot" and "cat" 1 letter apart? NO
Are "dot" and "cot" 1 letter apart? YES
Are "dot" and "dog" 1 letter apart? YES
Are "cat" and "cot" 1 letter apart? YES
Are "cat" and "dog" 1 letter apart? NO
Are "cot" and "dog" 1 letter apart? NO
-->
Ans in this way is pretty easy

How to write in java program? The input is in random order.....
0
 

Author Comment

by:heyhey84
ID: 17793855
There are so many combination if there is 100 given word.....

now this example we have only 4 word.

0
 
LVL 9

Expert Comment

by:shinobun
ID: 17798730
>> Ans in this way is pretty easy

So this is what your left diagrams look like.

>> How to write in java program? The input is in random order.....

This lines in the diagram is actually your hash table from a certain word to all of its neighbours.

>> There are so many combination if there is 100 given word.....

That would be a pain for humans, but no difference for computers.  :)
You only need to simulate the right diagram, which would be the BFS algorithm.
0
 

Accepted Solution

by:
babypink earned 100 total points
ID: 17888566
This will solve your problem

public class WordLadder {
 
 
    public static void main(String[] args) throws IOException {
       
        Scanner input = new Scanner(System.in);
        int numWords = input.nextInt();
        String[] storeWord = new String[5000000];        
        String givenWord;
        int index;
        int cannotStart=0;      
       
        for ( int i = 0 ; i < numWords ; i++ )
        {
              givenWord = input.next();
            index = findIndex( storeWord, givenWord );
            storeWord[ index ] = givenWord;
        }
       
        String startWord = input.next();
        String endWord = input.next();
        int startIndex = findIndex( storeWord, startWord );
        int endIndex = findIndex( storeWord, endWord );
           
        if (storeWord[ startIndex ] == null || storeWord[ endIndex ] == null )
                  {
                        cannotStart = 1;                       
                               
                  }             

        if (cannotStart == 1)
        {
              System.out.println("Impossible");
        }
       
        else
        {
        int[] parentWordIndex = new int[5000000];
        int pIndex;
        index = findIndex( storeWord, startWord );
        Queue<String> queue = new LinkedList<String>();
        List<String> neighbours = new LinkedList<String>();
        queue.offer(startWord);  

        while ( queue.size() > 0) {
           
            givenWord = queue.remove();
            pIndex = findIndex( storeWord, givenWord );
            neighbours = generateNeighbours(givenWord);
           
            while ( neighbours.size() > 0)
            {
               
                givenWord = neighbours.get(0);
                neighbours.remove(0);                
                index = findIndex( storeWord, givenWord );
               
                if ( storeWord[index] == null) {}
                else if ( storeWord[ index ].equals(givenWord) && parentWordIndex[ index ] == 0 )
                {
                   
                    if ( storeWord[index].equals(endWord) )
                    {                    
                        parentWordIndex[ index ] = pIndex;
                    }// close    
                   
                    else
                    {
                        parentWordIndex[index] = pIndex;
                        queue.offer(givenWord);
                    }// close
                   
                }// close
               
            }// close  
        }// close        
              index = findIndex( storeWord, endWord );
            Stack printStack = new Stack();
            givenWord = endWord;
           
            while ( !storeWord[index].equals(startWord) )
            {                
                printStack.push(givenWord);
                givenWord = storeWord[ parentWordIndex[index] ];
                index = findIndex( storeWord, givenWord );
                                                                   
            }// close
           
            printStack.push(startWord);
           
            while ( printStack.size() > 0 )
            {
                  System.out.println(printStack.pop());
            }// close
           
              
              }// close
   }// close main
 
     
    private static List<String> generateNeighbours(String word) {
       
        //precondition: word != null
        assert word != null : "null input in generateNeighbours";
        //postcondition: returns a list of neighbours of word
 
        //generate neighbours in lexicographical order
        List<String> result = new LinkedList<String>();
        char [] letters = word.toCharArray();
        for (int i = 0; i < letters.length; i++) {
            for (char c = 'a'; c <= 'z'; c++) {
                if (c != word.charAt(i)) {
                    letters[i] = c;
                    String w = new String(letters);
                    result.add(w);    
                }  
            }
            //arrange them in lexicographical order
            letters[i] = word.charAt(i);
        }  
        Collections.sort(result);
        return result;
    }
   
    private static int hashFunction(String word) {    
       
        int sum = 0;        
        for ( int i = 0; i < word.length(); i++ )
        {
              sum += (i + 1)*( word.charAt(i) - 96 );
        }          
        int m = sum % 991;
       
        return m;        
    }// close method
   
   private static int hashFunction2(String word) {    
       
        int m = 0;
              int b = 7;
          for (int i = 0; i < word.length (); ++i)
          {
                m = m * b  + word.charAt (i);
          }            
          return m;
    }// close method
   
    private static int findIndex( String[] storeWord, String word ) {
       
        int secondaryhashFunction = hashFunction2(word);
        int index = hashFunction(word) % (storeWord.length);
        if ( index == 0 )
        {
              index++;
        }

        while ( storeWord[index] != null && !storeWord[index].equals(word) )
        {  
            index += secondaryhashFunction;
            index = index % (storeWord.length);
            if ( index == 0 )
            {
                  index++;
            }                                          
        }    

        return index;
       
    }// close method  
     
}// close class
0

Featured Post

IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

Join & Write a Comment

Suggested Solutions

For customizing the look of your lightweight component and making it look lucid like it was made of glass. Or: how to make your component more Apple-ish ;) This tip assumes your component to be of rectangular shape and completely opaque. (COD…
Introduction This article is the last of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article covers our test design approach and then goes through a simple test case example, how …
Viewers will learn about the different types of variables in Java and how to declare them. Decide the type of variable desired: Put the keyword corresponding to the type of variable in front of the variable name: Use the equal sign to assign a v…
This tutorial explains how to use the VisualVM tool for the Java platform application. This video goes into detail on the Threads, Sampler, and Profiler tabs.

743 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

12 Experts available now in Live!

Get 1:1 Help Now