Worträtsel

stefan.h

Mitglied
Hey!

Ich soll eine Methode schreiben die aus einer Buchstabentabelle, vordefinierte Wörter suchen soll!
Ausgabe soll sein: Wort gefunden oder Wort nicht gefunden!

Die Methode soll vertikal, horizontal und diagonal suchen (diagonal hab ich noch nicht aber egal)
Witzig ist, dass meine Methode zwar funktioniert aber nicht jedes Wort findet :/
(nicht alle Wörter nach den gesucht wird sind auch wirklich drin enthalten)
Vielleich kann mal jemand über meinen Code drüberschaun', find den Fehler einfach nicht!

Java:
//
public class Wörterraetsel {

   public static void main(String[] args){
    
     char[][] m=
       {
         {'O','E','S','T','E','R','R','E','I','C','H','P'},
         {'E','R','M','I','T','T','E','L','N','Y','F','A'},
         {'M','O','S','E','N','D','E','N','E','P','A','L'},
         {'P','A','O','I','L','O','O','A','E','O','B','I'},
         {'F','O','F','P','C','K','S','P','S','K','F','N'},
         {'A','W','T','R','E','H','T','T','E','E','H','Z'},
         {'N','L','W','E','D','R','E','I','A','R','I','E'},
         {'G','P','A','F','O','D','R','R','N','G','N','R'},
         {'E','U','R','O','P','A','T','N','P','H','W','I'},
         {'N','M','E','X','P','R','E','S','S','E','E','N'},
         {'P','I','N','F','A','N','T','A','S','T','I','C'},
         {'W','A','H','N','S','I','N','N','O','K','S','T'}
        
     };
     char[][] words=
       {{'S','O','F','T','W','A','R','E'},
       {'H','I','N','W','E','I','S'},
     {'S','E','N','D','E','N'},
     {'E','M','P','F','A','N','G','E','N'},
     {'E','R','M','I','T','T','E','L','N'},
     {'W','A','H','N','S','I','N','N'},
     {'E','X','P','R','E','S','S'},
     {'S','I','C','H','E','R','H','E','I','T'},
     {'N','E','P','A','L'} ,
     {'O','S','T','E','R','N'},
     {'F','A','N','T','A','S','T','I','C'},
     {'L','I','N','Z','E','R','I','N'},
     {'K','A','T','A','S','T','R','O','P','H','E'},
     {'E','U','R','O','P','A'} ,
     {'M','A','T','R','I','X'},
     {'P','O','K','E','R'},
     {'O','E','S','T','E','R','R','E','I','C','H'},
     {'O','P','E','R','N'},
     {'F','U','N','N','Y'},
     {'M','E','L','K'},
     {'T','I','N','T','E'},
     {'R','A','E','T','S','E','L'}};
    
     for(int r=0; r<words.length; r++){
      
     char word[];
     word= words[r];
    
     boolean z=find(m,word);
     if(z==true){
       IO.print("\n");
       for(int s=0; s<word.length; s++){
         IO.print(word[s]);
       }
       IO.print(":  ");
       IO.print("Wort gefunden");
     }else{
       IO.print("\n");
       for(int s=0; s<word.length; s++){
         IO.print(word[s]);
       }
       IO.print(":  ");
       IO.print("Wort nicht gefunden");
     }
     }
     IO.print("\n");
   }//end main
  
   public static boolean find(char[][] m, char[] word){
    
    
     int a=0, b=0, c=0, d=0;
     boolean find= false;
     if(m != null&& word != null){
      
       //Array 1 durchgehen
      
       for(c=0; c<m.length; c++){
      
       int word_l= word.length;
       int word_diff= m[c].length-(a+1);
       //ist das Array lange genug für das Wort
       if(word_diff >= word_l){
        
         for(b=0; b<word.length; b++){
           while(b<word.length){
           if(word[b] == m[c][a]){
             find= true;
             b++;
             a++;
           }else{
             find= false;
             b=word.length;
           }//end if
           }//end while
         }//end for
       }//end if
       }//end for
      
       a=0;
        
         for(a=0; a<m[0].length;a++){
          
          
          
            
             for(d=0; d<m.length; d++){
               int word_l= word.length;
               int word_diff= (m.length -d)+1;
              
               if(word_diff>=word_l){
               b=0;
               if(word[0]==m[d][a]){
              
                 while(b<word.length){
                
                
                   if(m[d][a]==word[b]){
                   find= true;
                   d++;
                   b++;
                 }else{
                   find=false;
                   b=word.length;
                  
                 }
                  
               }//end while
               }//end if
             }//end for
           }//end if
          
         }//end while a
      
     }//end if null
    
     return find;
   }//end find
}//end class

Schönen Sonntag euch allen ;)
 

mariane

Mitglied
Geh mal die Sache anders an, vorallem arbeite erstmal mit einem kleinerem Array; und wichtig kein quadratisches, nur so vermeidest du beim erstellen einer allg. Methode Fehler bei den Indizes - passiert dies nämlich schnell. Ich poste mal nicht gleich Code.

Schreibe mal Wörter in eine 5x6 Array und untersuche dieses Array unter den untenstehen Gesichtspunkten. Wie sehe es aus, wenn das Array wie auch die Matritzen Eindimensional wären? Die Matritzen also z.B. int[] wären und das Array einfach nur ein String ist.

waagerecht
11111
22222
33333
44444
55555
66666

senkrecht
12345
12345
12345
12345
12345
12345

diagonal
12345
23456
34567
45678
56789
67890

Frage 1: wie kannst du die andere Diagonale beqeum ermitteln, ist dafür eine ander Matrix notwendig oder gehts auch geschickter
Frage 2: wie kannst du bequem rückwärts stehende Worte finden

Deine Aufgabe wäre:
- Wörter in eine Liste einlesen
- das Array in einen einzigen String umwandeln
- diese Umwandlung für einen zweiten String anpassen, so dass er für die andere diagonale lesform geeignet ist (kann in einem Rutsch gemacht werden)
- die Matritzen passend zu deinem Array generieren
- mit Hilfe der Matritzen die Charsequenzen aus dem String extrahieren
- prüfen, ob die Wörter in diesen Charsequenzen vorkommen
- prüfen, ob die Wörter rückwärts in diesen Charsequenzen vorkommen

Ich habe mir eine Hilfsmethode geschrieben, diese wird viermal aufgerufen:
findWords(dia, text);
findWords(dia, revText);
findWords(row, text);
findWords(col, text);
wobei dia, row und col die Matritzen, eindimensional als int[] sind. Diese Methode generiert mir alle möglichen Charsequenzen inkl. der gespiegelten Leserichtung und vergleicht diese anschließend mit der globale Liste mit den gesuchten Wörtern und gibt ein Wort aus, sofern vorhanden.

Es gibt sicher auch Wege nach Rom, aber mein Latein ist schlecht. :)
 

stefan.h

Mitglied
Hallo und danke für deine ausführliche Antwort!
Das Problem ist nicht, dass das ganze bei einem rechteckigen Array nicht funktioniert!
Mein Problem ist ich finde das eine oder andere Wort, aber einfach nicht alle!
An was kann das liegen? :/

Strings sind nicht erlaubt!
 

Joose

Top Contributor
Zuerst kurz zum Code im Allgemeinen:
Achte auf eine korrekte Einrückung des Codes dann ersparst du dir diese ganzen "//end" Kommentare
Java:
               }//end while
             }//end if
           }//end for
         }//end if
       }//end while a
     }//end if null
     return find;
   }//end find
}//end class
Schlecht zu lesen und wenn man kein Syntaxhighlighting hat von der IDE dann geht das return find; darin unter.
Bei einer korrekten Einrückung sollte gut erkennbar sein welche Klammern zu welchen Block gehört. Abgesehen davon ist die Beschriftung teilweise falsch ;)

Folgenden verschachtelte Schleifen haben keinen Sinn:
Java:
for(b = 0; b < word.length; b++) {
   while(b < word.length) {
     if(word[b] == m[c][a]) {
       find = true;
       b++;
       a++;
     } else {
       find = false;
       b = word.length;
     }
   }
}
Wozu brauchst du hier noch die while-Schleife? Du hast doch die for-Schleife welche genau den gleichen Zweck erfüllt.

Und ein Tipp: deklariere die Variablen erst dann wenn du sie benötigst, und nicht alle am Anfang der Methode.
"c" und "d" werden nur als Zählervariable für eine Schleife verwendet, deklariere sie daher direkt im Schleifenkopf bzw. direkt davor.
So kommst du nicht in Versuchung sie woanders zu benutzen mit einen völlig falschen Wert.
Und gib den Variablen sprechende Namen wie "zeile" oder "spalte" damit du in mehreren Wochen noch ohne Probleme nachvollziehen kannst wofür die Variablen gedacht sind/waren.

Nun zu deinem Problem:
Dein Problem ist das du bei der waagrechten Suche, zwar brav Zeile für Zeile durchgehst, aber den Index "a" nie zurücksetzt.
Jetzt findest du in Zeile 1 und Spalte 1 den Buchstaben vom 1.gesuchten Wort, in Spalte 2 den 2.Buchstaben, in Spalte 3 einen falschen.
Einerseits bleibt jetzt "a" am Wert für die 3.Spalte, andererseits wird diese Zeile nicht weiterdurchsucht (hier fehlt eine Schleife welche die Zeile solange durchgeht bis sich das Wort nicht mehr ausgeht bzw. nicht gefunden wurde).
Danach wird die nächste Zeile untersucht, da "a" aber nicht zurückgesetzt wurde wird ab der 3.Spalte gesucht und nicht wie gewünscht ab der 1.Spalte

Lösung: Du brauchst 3 verschachtelte Schleifen für die waagrechte Suche
1.Schleife geht alle Zeilen durch (for-Schleife)
2.Schleife wiederholt die Wortsuche solange bis das Wort gefunden oder in der Zeile nicht mehr genug Platz ist um es zu finden (while-Schleife)
3.Schleife vergleicht die einzelnen Zeichen des Wortes mit dem des Spielfeldes (for-Schleife)

Java:
public static boolean find(char[][] m, char[] word) {
   boolean find = false;
   if(m != null && word != null) {
     if(findHorizontal(m, word)){
       return true;
     }
     if(findVertical(m, word)) {
       return true;
     }
     if(findDiagonal(m, word)) {
       return true;
     }
   }
   return false;
}

private static boolean findHorizontal(char[][] m, char[] word) {
   // Zeile für Zeile durchgehen
   for(int zeile = 0; zeile < m.length; zeile++) {
     // beginne immer ab spalte 0 zu suchen
     int sucheAbSpalte = 0;
     // solange das wort noch in der zeile gefunden werden kann - abhängig von der länge
     while(word.length < m[zeile].length - sucheAbSpalte) {
       for(int b = 0; b < word.length; b++) {
         if(word[b] == m[zeile][sucheAbSpalte++]) {
           find = true;
         } else {
           find = false;
           break; // bricht die umgebende Schleife ab
         }
       }
       // wenn hier find noch true ist dann wurde das wort gefunden, die Methode kann verlassen werden
       if(find) {
         return true;
       }
     }
   }
   return false;
}
 

stefan.h

Mitglied
Hey!
Wow danke für deine Hilfe, son' blöder Fehler!
Findest du auch hier meinen Fehler?
Da such ich in der Diagonale, aber nur von links oben bis rechts unten, also die Hälfte nur!

Java:
private static boolean findDiagonal(char[][] m, char[] word) {
            boolean find= false;
            int zeile= 0;
            for(int spalte= 0; spalte<m[zeile].length; spalte++){
                while(word.length< m[zeile].length-spalte){
                for(int i= spalte; i<m.length; i++, zeile++){
                   
                        for(int b=0; b<word.length; b++){
                           
                            if(word[b] == m[zeile][spalte]) {
                                   find = true;
                                 } else {
                                   find = false;
                                   break;
                                 }
                               }
                              
                               if(find) {
                                 return true;
                               }
                           
                        }
                    }
                   
            }
           
            return false;
        }
 

Joose

Top Contributor
Findest du auch hier meinen Fehler?
Da such ich in der Diagonale, aber nur von links oben bis rechts unten, also die Hälfte nur!

Bei der Diagonale ist das ganze natürlich etwas komplizierter.
Hier ist es ratsam sich das mal so ein kleines Spielfeld aufzuzeichen und zu überlegen wo kann ich überall Wörter finden und gibt es Einschränkungen.

Beispiel ein 4x5 Raster:
Java:
+-+-+-+-+-+
| | | | | |
+-+-+-+-+-+
| | | | | |
+-+-+-+-+-+
| | | | | |
+-+-+-+-+-+
| | | | | |
+-+-+-+-+-+
Die längste Diagonale die du in diesem Feld finden kannst ist 4 Zeichen lang. Sprich bei Wörtern die länger sind musst du nicht mal anfangen zu suchen.
Wenn man sich nun anschaut wo man überall Diagonalen mit 4 Zeichen findet, fällt einem vielleicht auf wie man die Suche eingrenzen könnte.
Java:
+-+-+-+-+-+ // Die '\' und '/' sollen die Linien der Diagonalen darstellen, 'X' die Schnittpunkte ;)
|\|\| |/|/|
+-+-+-+-+-+
| |\|X|/| |
+-+-+-+-+-+
| |/|X|\| |
+-+-+-+-+-+
|/|/| |\|\|
+-+-+-+-+-+

Ich würde dir raten eben ein kleines Spielfeld zum Testen zu nehmen und dich auf den Algorithmus für die längste Diagonale zu konzentrieren (und hier auch erstmal auf die von links oben nach rechts unten ;))
Hast du diesen, dann kannst du dir überlegen wie es mit der um 1 Zeichen kürzeren Diagonale ausschaut.
Dabei sollten dir dann Gemeinsamkeiten im Algorithmus auffallen bzw. nur Unterschiede in den Begrenzungen. Diese können dann eben über Parameter festgelegt werden zum Beispiel.
 

Neue Themen


Oben