Hypercell ein ] Hypercell aus ] Zeige Navigation ] Verstecke Navigation ]
c++.net  
   

Die mobilen Seiten von c++.net:
https://m.c-plusplus.net

  
C++ Forum :: Java ::  Wortleiter gesamter Programmcode     Zeige alle Beiträge auf einer Seite Auf Beitrag antworten
Autor Nachricht
Peter_Mueller
Mitglied

Benutzerprofil
Anmeldungsdatum: 28.01.2016
Beiträge: 188
Beitrag Peter_Mueller Mitglied 18:14:35 18.03.2017   Titel:   Wortleiter gesamter Programmcode            Zitieren

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 :)

Java:
1
2
3
4
5
6
7
8
//main.java
 
public class main {
 
    public static void main(String[] args) {
        Wordladder wordladder = new Wordladder();
    }
}


Java:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
//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));
        }
    }  
   
}


Zuletzt bearbeitet von Peter_Mueller am 23:53:50 18.03.2017, insgesamt 4-mal bearbeitet
Andromeda
Mitglied

Benutzerprofil
Anmeldungsdatum: 09.12.2006
Beiträge: 2021
Beitrag Andromeda Mitglied 19:01:24 18.03.2017   Titel:              Zitieren

Für die copyArrayList-Funktion kannst du Collections.copy nehmen.
--> https://www.tutorialspoin ....... 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. :)

_________________
My Browser User Agent String is Mozilla/5.0 (X11; SunOS i86pc; rv:10.0.6) Gecko/20100101 Firefox/10.0.6
Peter_Mueller
Mitglied

Benutzerprofil
Anmeldungsdatum: 28.01.2016
Beiträge: 188
Beitrag Peter_Mueller Mitglied 23:45:28 18.03.2017   Titel:              Zitieren

ok. Danke Zeile 33 schon korrigiert :)

Bin für jeden Review dankbar :)
computernerds
Mitglied

Benutzerprofil
Anmeldungsdatum: 28.06.2017
Beiträge: 165
Beitrag computernerds Mitglied 21:41:48 21.07.2017   Titel:              Zitieren

Here is wordladder with Depth First - Search Algorithm

Java:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
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));
        }
    }
}


Zuletzt bearbeitet von computernerds am 12:51:17 25.07.2017, insgesamt 3-mal bearbeitet
computernerds
Mitglied

Benutzerprofil
Anmeldungsdatum: 28.06.2017
Beiträge: 165
Beitrag computernerds Mitglied 21:44:14 21.07.2017   Titel:              Zitieren

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.


Zuletzt bearbeitet von computernerds am 13:07:40 25.07.2017, insgesamt 3-mal bearbeitet
computernerds
Mitglied

Benutzerprofil
Anmeldungsdatum: 28.06.2017
Beiträge: 165
Beitrag computernerds Mitglied 11:28:28 25.07.2017   Titel:              Zitieren

Hier noch die Depth First Search Iterative Loesung :)

Java:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
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));
        }
    }
}


Zuletzt bearbeitet von computernerds am 18:10:57 26.07.2017, insgesamt 4-mal bearbeitet
computernerds
Mitglied

Benutzerprofil
Anmeldungsdatum: 28.06.2017
Beiträge: 165
Beitrag computernerds Mitglied 00:43:58 26.07.2017   Titel:              Zitieren

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

Java:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
//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));
        }
    }  
   
}


Zuletzt bearbeitet von computernerds am 00:47:50 26.07.2017, insgesamt 2-mal bearbeitet
C++ Forum :: Java ::  Wortleiter gesamter Programmcode   Auf Beitrag antworten

Zeige alle Beiträge auf einer Seite




Nächstes Thema anzeigen
Vorheriges Thema anzeigen
Sie können Beiträge in dieses Forum schreiben.
Sie können auf Beiträge in diesem Forum antworten.
Sie können Ihre Beiträge in diesem Forum nicht bearbeiten.
Sie können Ihre Beiträge in diesem Forum nicht löschen.
Sie können an Umfragen in diesem Forum nicht mitmachen.

Powered by phpBB © 2001, 2002 phpBB Group :: FI Theme

c++.net ist Teilnehmer des Partnerprogramms von Amazon Europe S.à.r.l. und Partner des Werbeprogramms, das zur Bereitstellung eines Mediums für Websites konzipiert wurde, mittels dessen durch die Platzierung von Werbeanzeigen und Links zu amazon.de Werbekostenerstattung verdient werden kann.

Die Vervielfältigung der auf den Seiten www.c-plusplus.de, www.c-plusplus.info und www.c-plusplus.net enthaltenen Informationen ohne eine schriftliche Genehmigung des Seitenbetreibers ist untersagt (vgl. §4 Urheberrechtsgesetz). Die Nutzung und Änderung der vorgestellten Strukturen und Verfahren in privaten und kommerziellen Softwareanwendungen ist ausdrücklich erlaubt, soweit keine Rechte Dritter verletzt werden. Der Seitenbetreiber übernimmt keine Gewähr für die Funktion einzelner Beiträge oder Programmfragmente, insbesondere übernimmt er keine Haftung für eventuelle aus dem Gebrauch entstehenden Folgeschäden.