Wortleiter gesamter Programmcode



  • Hallo,

    jeder kennt doch bestimmt das Wortleiterspiel. Man hat ein Startwort und ein Endwort und soll eine Wortleiter bilden.

    Hier der Code dazu. Viel Freude damit 🙂

    //main.java
    
    public class main {
    
    	public static void main(String[] args) {
    		Wordladder wordladder = new Wordladder();
    	}
    }
    
    //Wordladder.java
    
    import java.util.ArrayList;
    import java.util.Queue;
    import java.util.LinkedList;
    
    public class Wordladder {
    
    	String [] dictionary = new String[]{"tears","spile","spars","spare","sears","spire","smile"};
    	String startWord = "tears";
    	String endWord = "smile";
    
    	Queue<ArrayList<String>> queue = new LinkedList<ArrayList<String>>();
    
    	public Wordladder()
    	{
    		ArrayList<String> root = new ArrayList<String>();
    		root.add(startWord);
    		queue.add(root);
    
    		while(!queue.isEmpty())
    		{
    			ArrayList<String> current = queue.remove();
    
    			for(int i = 0 ; i < current.size();i++)
    			{
    				for(int j = 0 ; j < dictionary.length;j++)
    				{
    					if(  isNeighbor(current.get(i),dictionary[j]) )
    					{
    						if(current.get(i).equals(endWord))
    						{
    							String ausgabe = "";
    							for(int k = 0 ; k< current.size();k++)
    							{
    								if(k < current.size()-1)
    									ausgabe +=current.get(k)+" - ";
    								else
    									ausgabe +=current.get(k);
    							}
    							System.out.println("Wordladder");
    							System.out.println(ausgabe);
    							return;
    						}
    
    						if(!current.contains(dictionary[j]))
    						{
    							ArrayList<String> partialLadder = new ArrayList<String>(current.size()+1);
    							copyArrayList(current, partialLadder);
    							partialLadder.add(dictionary[j]);
    							queue.add(partialLadder);
    						}
    					}
    				}
    			}
    
    		}
    	}
    
    	public boolean isNeighbor(String str1, String str2)
    	{
    		int count = 0;
    		for(int i =0;i < str1.length();i++)
    		{
    			if(str1.charAt(i) != str2.charAt(i) )
    			{
    				count++;
    			}
    			if(count >1 || (str1.length() != str2.length()))
    			{
    				return false;
    			}
    		}
    		return true;
    	}
    
    	private void copyArrayList(ArrayList<String> src, ArrayList<String> dst)
    	{
    		for(int i = 0;i < src.size();i++ )
    		{
    			dst.add(src.get(i));
    		}
    	}	
    
    }
    


  • Für die copyArrayList-Funktion kannst du Collections.copy nehmen.
    --> https://www.tutorialspoint.com/java/util/collections_copy.htm

    Und ein Bug ist auch drin: Zeile 33 -> das == muss .equals heißen. Dass es bei dir auch mit == funktioniert, liegt daran, dass der Compiler den Code optimiert (Mehrfachverwendung von immutable Objekten). Aber mit == checkst du nur die Referenzen auf Gleichheit. Bei zwei verschiedenen Strings mit gleichem Inhalt geht das schief. 🙂



  • ok. Danke Zeile 33 schon korrigiert 🙂

    Bin für jeden Review dankbar 🙂



  • Here is wordladder with Depth First - Search Algorithm

    import java.util.ArrayList;
    
    public class Wordladder {
    
        String [] dictionary = new String[]{"tears","spile","spars","teari","lears","sears","spire","spare","smile"}; 
        String startWord = "tears"; 
        String endWord = "smile"; 
    
        public Wordladder()
        {
        	ArrayList<String> list = new ArrayList<String>();
        	list.add(startWord);
        	dfs(list);
        }
    
        public void dfs(ArrayList list)
        {	
        	int lastElement = list.size()-1;
    
        	for(int i=0;i<dictionary.length;i++)
        	{
        		if(isNeighbor(dictionary[i],list.get(lastElement).toString()) && !list.contains(dictionary[i]))
        		{
        	    	ArrayList<String> list2 = new ArrayList<String>();
        			copyArrayList(list, list2) ;
        			list2.add(dictionary[i]);
    
            		if(dictionary[i].equals(endWord))
            		{
                        String ausgabe = ""; 
                        for(int k = 0 ; k< list2.size();k++) 
                        { 
                            if(k < list2.size()-1) 
                                ausgabe +=list2.get(k)+" - "; 
                            else 
                                ausgabe +=list2.get(k); 
                        } 
                        System.out.println("Wordladder"); 
                        System.out.println(ausgabe); 
                        return;    		
                    }
    
            		dfs(list2);
        		}
    
        	}
        }
    
        public boolean isNeighbor(String str1, String str2) 
        { 
            int count = 0; 
            for(int i =0;i < str1.length();i++) 
            { 
                if(str1.charAt(i) != str2.charAt(i) ) 
                { 
                    count++; 
                } 
                if(count >1 || (str1.length() != str2.length())) 
                { 
                    return false; 
                } 
            } 
            return true; 
        } 
    
        private void copyArrayList(ArrayList<String> src, ArrayList<String> dst) 
        { 
            for(int i = 0;i < src.size();i++ ) 
            { 
                dst.add(src.get(i)); 
            } 
        } 
    }
    


  • Welcher Algorithmus findet die kuerzeste Loesung. Welcher Algorithmus findet die Loesung am schnellsten.

    Breadth First Search findet die kuerzeste Loesung allgemeinhin zuerst.
    Depth First Search findet die Loesung am schnellsten.



  • Hier noch die Depth First Search Iterative Loesung 🙂

    import java.util.ArrayList;
    import java.util.Stack;
    
    public class Wordladder {
    
        //String [] dictionary = new String[]{"tears","spile","spars","lears","sears","teari","spire","spare","smile"}; 
        String [] dictionary = new String[]{"tears","sears","bears","seare"}; 
        String startWord = "tears"; 
        String endWord = "seare";   
    
    	ArrayList<String> list = new ArrayList<String>();
    
        public Wordladder()
        {
        	list.add(startWord);
        	dfsIterativ(list);
        }
    
        public void dfsIterativ(ArrayList<String> list1)
        { 	   	
        	Stack<Object> stack = new Stack();
        	stack.push(0);
        	stack.push(list.size()-1);
        	stack.push(list1);
    
        	while(!stack.empty())
        	{    	   	
        		ArrayList<String> list = (ArrayList)stack.pop();
            	int lastElement = (int)stack.pop();
            	int indexDictionary = (int)stack.pop();
    
    	    	for(int i=indexDictionary;i<dictionary.length;i++)
    	    	{
    	    		if(isNeighbor(dictionary[i],list.get(lastElement).toString()) && !list.contains(dictionary[i]))
    	    		{			    			
    	        		if(dictionary[i].equals(endWord))
    	        		{
    		    			list.add(dictionary[i]);
    	                    String ausgabe = ""; 
    	                    for(int k = 0 ; k< list.size();k++) 
    	                    { 
    	                        if(k < list.size()-1) 
    	                            ausgabe +=list.get(k)+" - "; 
    	                        else 
    	                            ausgabe +=list.get(k); 
    	                    } 
    	                    System.out.println("Wordladder"); 
    	                    System.out.println(ausgabe); 
    	                    break;
    	                }
    
    	    			ArrayList<String> list3 = new ArrayList<String>();
    	    			copyArrayList(list, list3);
    	    			stack.push(i+1);
    	    			stack.push(list3.size()-1);
    	        		stack.push(list3);
    
    	    			list.add(dictionary[i]);
    
    	        		stack.push(0);
    	        		stack.push(list.size()-1);
    	        		stack.push(list);
    	        		break;
    
    	    		}  		
    	    	}
        	} 	
        }
    
        public void dfs(ArrayList list)
        {	
        	int lastElement = list.size()-1;
    
        	for(int i=0;i<dictionary.length;i++)
        	{
        		if(isNeighbor(dictionary[i],list.get(lastElement).toString()) && !list.contains(dictionary[i]))
        		{
        			list.add(dictionary[i]);
    
            		if(dictionary[i].equals(endWord))
            		{
                        String ausgabe = ""; 
                        for(int k = 0 ; k< list.size();k++) 
                        { 
                            if(k < list.size()-1) 
                                ausgabe +=list.get(k)+" - "; 
                            else 
                                ausgabe +=list.get(k); 
                        } 
                        System.out.println("Wordladder"); 
                        System.out.println(ausgabe); 
                        return;    		
                    }
    
            		dfs(list);
        		}
    
        	}
        }
    
        public boolean isNeighbor(String str1, String str2) 
        { 
            int count = 0; 
            for(int i =0;i < str1.length();i++) 
            { 
                if(str1.charAt(i) != str2.charAt(i) ) 
                { 
                    count++; 
                } 
                if(count >1 || (str1.length() != str2.length())) 
                { 
                    return false; 
                } 
            } 
            return true; 
        } 
    
        private void copyArrayList(ArrayList<String> src, ArrayList<String> dst) 
        { 
            for(int i = 0;i < src.size();i++ ) 
            { 
                dst.add(src.get(i)); 
            } 
        } 
    }
    


  • Hier der korriegierte Code fuer den breadth first Search. Hatte nee for schleife zuviel drin

    //Wordladder.java 
    
    import java.util.ArrayList; 
    import java.util.Queue; 
    import java.util.LinkedList; 
    
    public class Wordladder { 
    
        String [] dictionary = new String[]{"tears","spile","spars","teari","lears","sears","spire","spare","smile"};    
        String startWord = "tears"; 
        String endWord = "smile"; 
    
        Queue<ArrayList<String>> queue = new LinkedList<ArrayList<String>>(); 
    
        public Wordladder() 
        { 
        		bfs();
        } 
    
        public void bfs()
        {
            ArrayList<String> root = new ArrayList<String>(); 
            root.add(startWord); 
            queue.add(root); 
    
            while(!queue.isEmpty()) 
            { 
                ArrayList<String> current = queue.remove(); 
    
                    for(int j = 0 ; j < dictionary.length;j++) // process dictionary for each queue
                    { 
                        if(  isNeighbor(current.get(current.size()-1),dictionary[j]) ) 
                        { 
                            if(current.get(current.size()-1).equals(endWord)) 
                            { 
                                String ausgabe = ""; 
                                for(int k = 0 ; k< current.size();k++) 
                                { 
                                    if(k < current.size()-1) 
                                        ausgabe +=current.get(k)+" - "; 
                                    else 
                                        ausgabe +=current.get(k); 
                                } 
                                System.out.println("Wordladder"); 
                                System.out.println(ausgabe); 
                                break;
                            } 
    
                            if(!current.contains(dictionary[j])) 
                            { 
                                ArrayList<String> partialLadder = new ArrayList<String>(current.size()+1); 
                                copyArrayList(current, partialLadder); 
                                partialLadder.add(dictionary[j]); 
                                queue.add(partialLadder); 
                            } 
                        } 
                    }            
            } 
        }
    
        public boolean isNeighbor(String str1, String str2) 
        { 
            int count = 0; 
            for(int i =0;i < str1.length();i++) 
            { 
                if(str1.charAt(i) != str2.charAt(i) ) 
                { 
                    count++; 
                } 
                if(count >1 || (str1.length() != str2.length())) 
                { 
                    return false; 
                } 
            } 
            return true; 
        } 
    
        private void copyArrayList(ArrayList<String> src, ArrayList<String> dst) 
        { 
            for(int i = 0;i < src.size();i++ ) 
            { 
                dst.add(src.get(i)); 
            } 
        }   
    
    }