macOS Another Java Homework Thread!

[stadidas]

Im working on Java homework and I've got myself a bit stuck.
I have a Class called Anagrams which has two pointers to a Node class to create a linked list. These Nodes hold String values, and a pointer to the next Node in the list.
The problem is that I need to write a method in the anagrams class called getAnagrams to go through the list and return an array of Strings. Each string must an angram in the list with it's anagrams.
For example if there was a list containing:
abc, bca, ret, etr, hyg

The method would return:
abc bca
ret etr

My Anagrams class looks like this:

//  Class used to find anagrams
//
public class Anagrams implements AnagramsInterface {
    // This class needs to be implemented
    private Node first; // the start of the list
    private Node last;  // last node in the list
    private int count;  // number of nodes in the list
    
    public Anagrams() {
        first = null;
        last = null;
        count = 0;
    }
    
    public void addWord(String s) {
        Node n = new Node(s);
        if (first == null) {
            first = n;
            count++;
            if (last == null) {
                last = first;
            }
        }
        else {
            last.setNext(n);
            last = n;
            count++;
        }
    }
    
    public String[] getAnagrams () {
        
    }

}

The Node class is:

//  Class used to store individual nodes in a linked list
//
class Node {
	private String value;
	private Node next;

	public Node(String s)
	{
		value = s;
		next = null;
	}

	public Node(String s, Node n)
	{
		value = s;
		next = n;
	}

	// Accessors and mutators for value and next
	public String getValue() { return value; }
	public void setValue(String s) { value = s; }
	public Node getNext() { return next; }
	public void setNext(Node n) { next = n; }
	
}

I can only use String and StringBuffer from the standard library. I'm not sure if any kind of sorting would help. I've been wracking my brains but can't think of a decent way to do it. If anyone has any ideas that may help then please let me know.

 

[lmalave]

Im working on Java homework and I've got myself a bit stuck.
I have a Class called Anagrams which has two pointers to a Node class to create a linked list. These Nodes hold String values, and a pointer to the next Node in the list.
The problem is that I need to write a method in the anagrams class called getAnagrams to go through the list and return an array of Strings. Each string must an angram in the list with it's anagrams.
For example if there was a list containing:
abc, bca, ret, etr, hyg
......
I can only use String and StringBuffer from the standard library. I'm not sure if any kind of sorting would help. I've been wracking my brains but can't think of a decent way to do it. If anyone has any ideas that may help then please let me know.

I'm confused as to what your assignment is. Is it nothing more than converting a linked list to a String array? Are you just saying that you need to convert this linked list:

abc->bca->ret->etr->hyg

to this array:

[abc,bca,ret,etr,hyg]

...if so, then the assignment is fairly straightforward and I can post the general approach.

 

[MarkCollette]

I'm confused as to what your assignment is. Is it nothing more than converting a linked list to a String array? Are you just saying that you need to convert this linked list:

abc->bca->ret->etr->hyg

to this array:

[abc,bca,ret,etr,hyg]

...if so, then the assignment is fairly straightforward and I can post the general approach.

It sounds to me, more like the result is either:

[abc,bca,ret,etr]

or

[ [abc,bca], [ret,etr] ]


stadidas, how is your linked list populated? Do you read input from a file, or is the linked list of objects passed in to your code? Do you have to store it as a linked list, or was that just something you wanted to do?

 

[lmalave]

If it's just a matter of returning a String array, here is a possible getAnagrams():

public String[] getAnagrams() {
  // string array will have same number of elements as linked list
  String[] anagrams = new String[this.count]; 
  // start iterating through linked list beginning with first element
  Node currentNode = first;
  for (int i == 0; i < this.count; i++)
  {
     // add current node of linked list to array
     anagrams[i] = currentNode.getValue();
     // get next element in linked list
     currentNode = currentNode.getNext();
  }
  return anagrams; 
}

That should do it. That's all you needed, right? Or do you somehow need to detect which elements in the list are anagrams? (which would mean that at least one other element in the list is an anagram of that element).

 

[stadidas]

Hi Guys, thanks for the replies.

I probably should have posted this too, it's the test class used to test my methods:

// Run using
//  java TestBed <input-file
//
import java.io.*;

class TestBed {

    // Test the Anagrams class interactively.
    public static void interactiveTest()
    {
        for (;;) {
            System.out.println("type words, one per line, terminated by a blank line");
            try {
                BufferedReader br = new BufferedReader(new FileReader(FileDescriptor.in));
                runTest(br);
            }
            catch (IOException e) {
                System.out.println("Exception: " + e + "\n");
            }
        }
    }
    
    // Test the Anagrams class using words loaded from a file
    public static void fileTest(String filename)
    {
        try {
            BufferedReader br = new BufferedReader(new FileReader(filename));
            long tstart = System.currentTimeMillis();
            runTest(br);
            System.out.println(System.currentTimeMillis() - tstart);
        }
        catch (IOException e) {
            System.out.println("Exception: " + e + "\n");
        }
    }
    
    // Run the test by loading words from br
    private static void runTest(BufferedReader br) throws IOException
    {
        Anagrams anagrams = new Anagrams();
        String s = br.readLine();
        while (s != null && s.length() > 0) {
            anagrams.addWord(s);
            s = br.readLine();
        }
        String[] results = anagrams.getAnagrams();
        for (int i = 0; i < results.length; i++)
            System.out.println(results[i]);
    }
}

The input is from a file of words all on separate lines. The getAnagrams class needs to return an array, and each element of that array must contain a string concatination of the anagrams found. I hope that makes it a bit clearer, thanks for any advice you can give because I am stumped.

 

[stadidas]

Or do you somehow need to detect which elements in the list are anagrams? (which would mean that at least one other element in the list is an anagram of that element).

That's exactly it yes. Thanks for helping me!
I presume that a linked list is the best way to do this. However, any other data structure may be implemented, so if you think a binary tree for example may be better then that may be used instead.

 

[lmalave]

It sounds to me, more like the result is either:

[abc,bca,ret,etr]

or

[ [abc,bca], [ret,etr] ]

Definitely not the second option, since getAnagrams() returns an array of Strings, not an array of arrays. Hmm...sounds like I just need to add an containsAnagramOf(String) method to the code I already posted above...

// returns true if input Strings A and B are anagrams
private boolean areAnagrams(String stringA, String stringB)
{
... need to define "anagram" algorithm here...
... note: if input strings A and B are the same, that does NOT count as an anagram!!
}
// returns true if the linked list contains at least 1 value that is an anagram of the input String
public boolean containsAnagramOf(String inputString)
{
  Node currentNode = this.first;
  for (int i = 0; i < this.count; i++)
  {
    // use hypothetical "areAnagrams" method to check if 
    if (areAnagrams(inputString, currentNode.getValue())
    {
      // if found an anagram, no need to continue looping, so return true immediately
      return true;
    }
    // still haven't found anagram, so get next node and continue looping
    currentNode = currentNode.getNext();
  }
  // no anagrams found, return false; 
  return false;
}

 

[stadidas]

Definitely not the second option, since getAnagrams() returns an array of Strings, not an array of arrays. Hmm...sounds like I just need to add an containsAnagramOf(String) method to the code I already posted above...

// returns true if input Strings A and B are anagrams
private boolean areAnagrams(String stringA, String stringB)
{
... need to define "anagram" algorithm here...
... note: if input strings A and B are the same, that does NOT count as an anagram!!
}
// returns true if the linked list contains at least 1 value that is an anagram of the input String
public boolean containsAnagramOf(String inputString)
{
  Node currentNode = this.first;
  for (int i = 0; i < this.count; i++)
  {
    // use hypothetical "areAnagrams" method to check if 
    if (areAnagrams(inputString, currentNode.getValue())
    {
      // if found an anagram, no need to continue looping, so return true immediately
      return true;
    }
    // still haven't found anagram, so get next node and continue looping
    currentNode = currentNode.getNext();
  }
  // no anagrams found, return false; 
  return false;
}

Excellent! That's very handy.
To see if they are anagrams I think it would be possible to sort the string's array of chars into alphabetical order and then see if the strings are equal. If this is the case then return true. Would that work?

 

[lmalave]

Excellent! That's very handy.
To see if they are anagrams I think it would be possible to sort the string's array of chars into alphabetical order and then see if the strings are equal. If this is the case then return true. Would that work?

Yes! Exactly the approach I was thinking of. Luckily the (newly open-source) Java API has all the utility methods you could want, like:

myString.toCharArray()
Arrays.sort(char[])
new String(char[])
and of course... myString.equals(String)

So now you should have all the elmements you need:

1) a method to determine if two strings are anagrams
2) a method do determine if an input string has an anagram in the Anagrams linked list
3) a getAnagrams() method that returns all the strings in the list that have at least one anagram

Good luck!

 

[stadidas]

Awesome. Would that work within this part of the assignment :
"It should not make use of any Java API classes except String and StringBuffer." ?

 

[lmalave]

Awesome. Would that work within this part of the assignment :
"It should not make use of any Java API classes except String and StringBuffer." ?

Doh!!! No, I guess not. The approach I was thinking of would use the Arrays.sort() method to do the sorting. So I guess what you'll have to do is do the sorting of the char[] array yourself :-(

It *is* homework after all, I guess - so the point of it is not to be easy

EDIT: Since implementing the sorting yourself is kind of a pain, there is another "brute force" method that I thought of to determine if 2 string are anagrams:

Basically, let's say you have stringA and stringB. What you can do is:

1) loop through the characters in stringA
2) for each character, see if it exists in stringB ( can use stringB.indexOf(ch); )
3) if stringB does *not* have the character, then immediately return false since you know the two strings cannot be anagrams
4) if stringB *does* have the character, then remove that character from the stringB ( can use stringB.replaceFirst(String.valueOf(ch), ""); ), and continue loop
5) if the loop finishes without returning false on any of the characters, then after the loop you can return true, since you have determined that the two strings are indeed anagrams!!

I'm about 10 years removed from school, so I have to admit that in my own work (if I had to implement something like this for some reason), I would implement it with the above "brute force" method rather than by implementing a proper sorting algorithm.

 

[stadidas]

That's ok, we've been taught how to do a quicksort method, so I'll have to write that.

However, today a major spanner got thrown in the works. I found out the class must be able to find anagrams in a list of 10000 words in less than half a second. This is only possible using a binary tree, not a linked list. So I'm going to have to change the data structure to a binary tree which means re-writing a lot of code. I've uploaded the current project here so you can have a look at what I've done. The code was mainly written between midnight and three in the morning last night (I live in England) so forgive me if it's a bit rubbish. It still doesn't quite work correctly. If you run the interactive test from the test bed class you can check it yourself. Only the anagrams class and the node class are ones I wrote.
Once again, any help appreciated! There are some test files in the package with the file extension .wds. The answers for those lists have the same file name with the extension ana. The whole lot is done in BlueJ because the guy that developed it is one of my lecturers and that's what we use.

 

[mufflon]

That's ok, we've been taught how to do a quicksort method, so I'll have to write that.

However, today a major spanner got thrown in the works. I found out the class must be able to find anagrams in a list of 10000 words in less than half a second. This is only possible using a binary tree, not a linked list. So I'm going to have to change the data structure to a binary tree which means re-writing a lot of code. I've uploaded the current project here so you can have a look at what I've done. The code was mainly written between midnight and three in the morning last night (I live in England) so forgive me if it's a bit rubbish. It still doesn't quite work correctly. If you run the interactive test from the test bed class you can check it yourself. Only the anagrams class and the node class are ones I wrote.
Once again, any help appreciated! There are some test files in the package with the file extension .wds. The answers for those lists have the same file name with the extension ana. The whole lot is done in BlueJ because the guy that developed it is one of my lecturers and that's what we use.

hmm the alternative would be to use a hashmap with 0.75% load - will be huge, but so will the binary tree implementation (which would have to be self sorting which is often a pain - or the tree won't be idea)

I have some memory of hashmap-searching is close to the ordo notation of a binary tree - so might be worth it...

edit: doh, only string and stringbuffer... ... this kinda sucks

 

[aLoC]

Here is one way to do it. Handles 10,000 words in 143ms on my iMac.

Add to Anagrams.java:

    public String[] getAnagrams ()
    {
        String[] results = null;
        int numResults = 0;
        
        MyHashMap map = new MyHashMap(count * 2);
        
        Node n = first;
        while ( n != null ) {
            String val = n.getValue();
            String norm = n.getNormalizedValue();    
                        
            String existingVal = map.get(norm);
            if ( existingVal != null ) {
                String newVal = existingVal + " " + val;
                map.put(norm, newVal);
                if ( existingVal.indexOf(" ") == -1 ) {
                    numResults++;
                }
            } else {
                map.put(norm, val);
            }
            
            n = n.getNext();
        }
        //System.err.println("numResults:" + numResults);
        
        // Compact the results in to an array to return
        results = new String[numResults];
        int resultsIndex = 0;
        Node n2 = first;
        while ( n2 != null ) {
            String norm = n2.getNormalizedValue();
            String mapVal = map.get(norm);
            if ( !mapVal.equals("!") && mapVal.indexOf(" ") != -1 ) {
                results[resultsIndex] = mapVal;
                resultsIndex++;
                map.put(norm, "!"); // "deleted"
            }
            n2 = n2.getNext();
        }
        
        return results;
    }

Add to Node.java:

    public String getNormalizedValue()
    {
        if ( value == null ) return null;
        
        StringBuffer norm = new StringBuffer("");
        char[] cs = value.toCharArray();
        while ( norm.length() < value.length() ) {           
            char lowest = 255;
            int lowestIndex = 0;
            for ( int i = 0; i < cs.length; i++) {
                if ( cs[i] < lowest ) {
                    lowestIndex = i;
                    lowest = cs[i];
                }
            }
            norm.append(lowest);
            cs[lowestIndex] = 255;
        }
        
        return norm.toString();
    }

New class MyHashMap.java:

/** Simple fixed capacity hash map. Not allowed to use the standard library one. */
public class MyHashMap
{
    Node[] _data;
    int _capacity;
    
    public MyHashMap(int capacity)
    {
        _data = new Node[capacity];
        _capacity = capacity;
    }
    
    public void put(String key, String val)
    {
        int idx = key.hashCode(); 
        if ( idx < 0 ) idx = idx * -1;
        idx = idx % _capacity;

        Node n = _data[idx];
        while ( n != null ) {
            String nodeVal = n.getValue();
            if ( nodeVal.startsWith(key + "=") ) {
                break;
            }    
            n = n.getNext();
        }
                
        if ( n == null ) {
            // New node in bucket
            n = new Node(key + "=" + val);
            n.setNext(_data[idx]);
            _data[idx] = n;
        } else {
            // Add to existing
            n.setValue(key + "=" + val);
        }
    }
    
    public String get(String key) 
    {
        int idx = key.hashCode();
        if ( idx < 0 ) idx = idx * -1;
        idx = idx % _capacity;
         
        Node n = _data[idx];
        while ( n != null ) {
            String nodeVal = n.getValue();
            if ( nodeVal.startsWith(key + "=") ) {
                break;
            }    
            n = n.getNext();
        }
            
        String result;            
        if ( n == null ) {
            result = null;
        } else {
            String val = n.getValue();
            result = val.substring(key.length() + 1);
        }
        
        return result;
    }
}

Add to TestBed.java:

    public static void main(String[] argv)
    {
        fileTest(argv[0]);
    }

Run like so:
java TestBed w10000.wds

 

[MarkCollette]

That's exactly it yes. Thanks for helping me!
I presume that a linked list is the best way to do this. However, any other data structure may be implemented, so if you think a binary tree for example may be better then that may be used instead.

Here is one way to do it. Handles 10,000 words in 143ms on my iMac.

Damn, aLoC beat me to it. Basically, the idea is that instead of trying to find the anagrams, just properly insert them in the first place. A lot of the time, if you properly store your data in the first place, that really helps retrieval.

All anagrams would share a similar sorted version of themselves. So, if you just use some kind of hash table (Hashtable, HashMap) where the sorted string is the key, and the value is some container (Vector, ArrayList) of the various anagram strings, then you can just iterate over all entries in the hash table, and pick out the containers with more than one entry in them.

Personally, I wouldn't store the concatenated string, since that's a kind of lossy storage mechanism. Instead I'd use an ArrayList<String>, and concatenate them at reporting time.

Oh, and linked lists are nearly useless, so don't bother using them. If you're inserting at the end of a list, then a vector is always better. They're only useful for rapid insertions and removals in the middle of really long lists, like a million entries long.

 

[MarkCollette]

public class Anagrams {
    private HashMap entries = new HashMap( 10000 ); // HashMap<String sorted, ArrayList<String> anagrams>

    public void addWord(String word) {
        char[] wordChars = word.toCharArray();
        Arrays.sort( wordChars );
        String sorted = new String( wordChars );
        ArrayList anagrams = (ArrayList) entries.get( sorted );
        if( anagrams == null ) {
            anagrams = new ArrayList();
            entries.put( sorted, anagrams );
            anagrams.add( word );
        }
        else {
            if( anagrams.contains(word) )
                System.out.println("Word was already given: " + word);
            else
                anagrams.add( word );
        }
    }
    
    public String[] getAnagrams() {
        Collection anagramsCollection = entries.values();
        if( anagramsCollection.size() == 0 )
            return new String[0]; // Or null, whichever you're supposed to
        Iterator anagramsIterator = anagramsCollection.iterator();
        ArrayList resultsList = new ArrayList( anagramsCollection.size() );
        while( anagramsIterator.hasNext() ) {
            ArrayList anagrams = (ArrayList) anagramsIterator.next();
            if( anagrams.size() > 1 ) {
                StringBuffer sb = new StringBuffer();
                for(int i = 0; i < anagrams.size(); i++) 
                    sb.append( anagrams.get(i) );
                    sb.append("  "); // Or however you're supposed to delimit them
                }
                resultsList.add( sb.toString() );
            }
        }
        if( resultsList.size() == 0 )
            return new String[0]; // Or null, whichever you're supposed to
        String[] resultsArray = new String[ resultsList.size() ];
        for(int i = 0; i < resultsList.size(); i++)
            resultsArray[i] = resultsList.get(i).toString();
        return resultsArray;
    }
}

 

[Grover]

If you have access to a copy of Programming Pearls by Jon Bentley there's a discussion of this sort of exercise that you might find helpful. The code files from the book can be found at http://www.cs.bell-labs.com/cm/cs/pearls/code.html.

 

[stadidas]

public class Anagrams {
    private HashMap entries = new HashMap( 10000 ); // HashMap<String sorted, ArrayList<String> anagrams>

    public void addWord(String word) {
        char[] wordChars = word.toCharArray();
        Arrays.sort( wordChars );
        String sorted = new String( wordChars );
        ArrayList anagrams = (ArrayList) entries.get( sorted );
        if( anagrams == null ) {
            anagrams = new ArrayList();
            entries.put( sorted, anagrams );
            anagrams.add( word );
        }
        else {
            if( anagrams.contains(word) )
                System.out.println("Word was already given: " + word);
            else
                anagrams.add( word );
        }
    }
    
    public String[] getAnagrams() {
        Collection anagramsCollection = entries.values();
        if( anagramsCollection.size() == 0 )
            return new String[0]; // Or null, whichever you're supposed to
        Iterator anagramsIterator = anagramsCollection.iterator();
        ArrayList resultsList = new ArrayList( anagramsCollection.size() );
        while( anagramsIterator.hasNext() ) {
            ArrayList anagrams = (ArrayList) anagramsIterator.next();
            if( anagrams.size() > 1 ) {
                StringBuffer sb = new StringBuffer();
                for(int i = 0; i < anagrams.size(); i++) 
                    sb.append( anagrams.get(i) );
                    sb.append("  "); // Or however you're supposed to delimit them
                }
                resultsList.add( sb.toString() );
            }
        }
        if( resultsList.size() == 0 )
            return new String[0]; // Or null, whichever you're supposed to
        String[] resultsArray = new String[ resultsList.size() ];
        for(int i = 0; i < resultsList.size(); i++)
            resultsArray[i] = resultsList.get(i).toString();
        return resultsArray;
    }
}

That's really cool code, but I can't use ArrayLists or actual HashMaps. aLoc's implementation fits the spec perfectly which is cool, I really should have thought of it myself. I'm going through it now so that I fully understand how it works.
Thanks again everyone for all your help. This seems to be the only programming forum where people don't flame you for asking for help. You guys are great, hopefully one day I'll be good enough to help other people out!

 

[MarkCollette]

That's really cool code, but I can't use ArrayLists or actual HashMaps. aLoc's implementation fits the spec perfectly which is cool, I really should have thought of it myself. I'm going through it now so that I fully understand how it works.
Thanks again everyone for all your help. This seems to be the only programming forum where people don't flame you for asking for help. You guys are great, hopefully one day I'll be good enough to help other people out!

Sorry, I wasn't trying to do the exact assignment, just express the gist of my algorithm suggestion. I was going to use pseudo-code, but realised it wouldn't save me much typing.