4Bilder1Wort C Programm

[student (Gast)]

Hallo zusammen,

da ich aktuell C lernen möchte habe ich versucht ein Programm zu 
schreiben das mich bei dem Spiel 4Bilder1Wort "unterstützt".

Zunächst werden alle vorgeschlagenen Zeichen eingelesen und in einem 
Array gespeichert. Anschließend wird die Länge des Lösungswortes 
abgefragt und gespeichert um die möglichen Lösungen einzugrenzen. Der 
eigentliche Algorithmus prüft zunächst ob, das aus einem Wörterbuch 
geholte Wort, der gewünschten länge entspricht. Ist dies der Fall wird 
geprüft ob das Wort mit den vorhandenen Zeichen dargestellt werden kann. 
Sind beide Bedingungen (Länge und mögliche Zeichen) erfüllt wird das 
Wort als möglicher Lösungsvorschalg ausgegben.

Mein Problem ist, das mein Wörterbuch mit knapp 30000 Worten zu 
umfangreich ist. So werden z.b bei einem Alphabet [snmnzenluyie] 59 
mögliche Lösungen bei einer Wortlänge von 5 Zeichen gefunden. Das ist 
zwar nicht sooo viel, aber ich würde das dennoch gerne optimieren, da 
bei größerer Wortlänge auch die Anzahl möglicher Lösungen steigt.

Eventuell findet sich jemand der das Projekt interessant findet und es 
weiter entwickeln möchte bzw. eine, für das Spiel optimierte Wortliste 
hat.

[Frank M. (ukw) (Moderator)]

Nettes Programm :-)

Hier ein kleiner Fehler:

for(i = 0; i <= strlen(string); i = i + 1){

Hat das Wort 5 Buchstaben, müssen die Stellen 0..4 getestet werden. Du 
testest aber auf 6 Zeichen, nämlich 0..5. Das geht hier nur 
zufälligerweise gut, da natürlich jeder C-String auch einen Terminator 
'\0' hat. Der Test darauf ist aber überflüssig und kann in einem anderen 
Kontext sogar problematisch werden.

Schreibe daher:

for(i = 0; i < strlen(string); i = i + 1){

Also < statt <=. Außerdem kannst Du i = i + 1 bei der Gelegenheit zu i++ 
vereinfachen.

Merke: Immer wenn Du einen Index von 0 an laufen lässt, musst Du 
anschließend zu 95% auf < und nicht <= testen. Wenn ich so eine Zeile 
sehe, geht da automatisch der Alarmknopf im Kopf an. Solche 
Programmstellen sind meist Kandidaten für Buffer-Overflows.

Ich habe da aber noch ein Verständnisproblem. Nehmen wir mal an, das 
eingegebene Wort wäre:

aeeef

Nach der Programmlogik würde das Programm auch das Wort

aaaef

im Wörterbuch finden. Ist das so richtig? Das Programm testet nämlich 
nicht die Anzahl gleicher Buchstaben.

EDIT:

Hier ist noch ein dicker Programmfehler in:

char* cleanString(char string[]){
  char temp [MAXLEN];
  ...
  return temp;
}

Das Array temp ist eine Autovariable und wird mit dem Verlassen der 
Funktion zerstört. Ein Pointer darauf zurückzugeben ist höchst 
fahrlässig, da er auf einen nicht definierten Speicherbereich zeigt. 
Spätestens dann, wenn anschließend weitere Funktionen mit Autovariablen 
aufgerufen werden, bekommst Du undefinierte Zeichen zurück.

Schreibe also:

  static char temp [MAXLEN];

Dann lebt die Variable über die ganze Programmlebenszeit. Beachte aber, 
dass nach einem weiteren Aufruf von cleanString() Du den vorherigen 
Inhalt verlierst.

Warum machst Du nicht den toupper-Call und das Abschneiden von CR und LF 
nicht direkt im übergebenen Array string[]? Das spart auch den 
anschließenden strcpy().

Also so:

void cleanString(char string[])
{
  int i;

  for(i = 0; string[i]; i++)
  {
    if(string[i] == '\n' || string[i] == '\r')
    {
       break;
    }
    string[i] = toupper(string[i]);
  }
  
  string[i] = '\0';
}

Aufruf ohne strcpy:

cleanString(string);

P.S. Die Variable i bei der Definition mit 0 zu initialisieren und 
anschließend in der for-Schleife nochmals auf 0 zu setzen ist 
überflüssig. Ebenso kann man den Vergleich string[i] != '\0' 
vereinfachen, siehe oben.

Die Funktion ist nun vom Typ void, da sie keinen Zeiger mehr 
zurückliefern muss. Der anschließende strcpy-Aufruf entfällt.

[NoName (Gast)]

Die gleiche Aufgabe habe ich auch schon einmal in Python umgesetzt. 
Dabei hatte sich bei mir bewährt das Wörterbuch aufzuteilen um die zu 
untersuchende Datenmenge zu reduzieren.
Konkret bedeutet dies alle Wörter mit der Länge n in der Datei WB-n.txt 
abzuspeichern. Da die Länge deines Lösungswortes bekannt ist, kannst du 
direkt die richtige Teilmenge durchsuchen.

[Frank M. (ukw) (Moderator)]

Noch eine Bemerkung zu cleanString(). Wenn man mit Pointern arbeitet 
statt der Array-Schreibweise, spart man auch noch die Variable i ein. 
Außerdem kann der mehrmalige Speicherzugriff schneller werden, wenn der 
Compiler das nicht ohnehin optimiert.

Daher Vorschlag:

void cleanString(char *string)
{
  while (*string)
  {
    if (*string == '\n' || *string == '\r')
    {
       break;
    }

    *string = toupper(*string);
    string++;
  }
  
  *string = '\0';
}

[student (Gast)]

Hallo und danke erstmal für die Verbesserungsvorschläge.

@Frank M.

 for(i = 0; i <= strlen(string); i = i + 1)

+-1 Fehler passieren mir immer mal wieder



>Außerdem kannst Du i = i + 1 bei der Gelegenheit zu i++ vereinfachen.

Ich persönlich finde es einfacher lesbar i = i + 1; zu schreiben. Klar 
muss man mehr tippen aber ich finds schöner ist halt geschmackssache. 
Oder bringt i++; noch andere Vorteile?



>Ich habe da aber noch ein Verständnisproblem. Nehmen wir mal an, das
>eingegebene Wort wäre:

>aeeef

>Nach der Programmlogik würde das Programm auch das Wort

>aaaef

>im Wörterbuch finden. Ist das so richtig? Das Programm testet nämlich
>nicht die Anzahl gleicher Buchstaben.

Ja das stimmt, ich habs behoben indem ich das Zeichen (wenn es gefunden 
wurde) durch eine '0' ersetzte. Die kann in keinem Wort vorkommen also 
kann auch kein Buchstabe mehr doppelt verwendet werden.

 char* cleanString(char string[]){
  char temp [MAXLEN];
  ...
  return temp;
}

für mich als Anfänger unmöglich selbst zu erkennen, danke für den 
Hinweis



>Warum machst Du nicht den toupper-Call und das Abschneiden von CR und LF
>nicht direkt im übergebenen Array string[]? Das spart auch den
>anschließenden strcpy().

Sehr guter Punkt, hab ich einfach nicht bedacht bzw. zu wenig drüber 
nachgedacht und zu viel gefreut das es einfach funktioniert hat ;-)



>P.S. Die Variable i bei der Definition mit 0 zu initialisieren und
>anschließend in der for-Schleife nochmals auf 0 zu setzen ist
>überflüssig.

ja das ist richtig, aber ich hab mir angewöhnt Variablen bereits bei der 
deklaration zu initialisieren und mal abgesehen von ein paar wenigen 
Prozessortakten die verloren gehen gibts ja keinen Nachteil oder?

 void cleanString(char *string)
{
  while (*string)
  {
    if (*string == '\n' || *string == '\r')
    {
       break;
    }

    *string = toupper(*string);
    string++;
  }
  
  *string = '\0';
}

Hab deine Funktion mal zusätzlich eingefügt. Als Anfänger drückt man 
sich halt gern um Pointer zumindest da wo mans selber erkennt ;-)



@NoName
Auch eine gute Idee, das Problem ist aber nicht die Laufzeit, sondern 
das die Wortliste nicht auf 4Bilder1Wort optimiert ist und man so sehr 
viele Lösungsmöglichkeiten bekommt.

[Dirk B. (dirkb2)]

student schrieb:
>>Außerdem kannst Du i = i + 1 bei der Gelegenheit zu i++ vereinfachen.
>
> Ich persönlich finde es einfacher lesbar i = i + 1; zu schreiben. Klar
> muss man mehr tippen aber ich finds schöner ist halt geschmackssache.
> Oder bringt i++; noch andere Vorteile?

Ja, es ist lesbarer, da du nicht schauen must, ob da noch ein j oder l 
(kleines L) oder Fliegendreck im Spiel ist.

Den Rest macht der Compiler.

student schrieb:
> ja das ist richtig, aber ich hab mir angewöhnt Variablen bereits bei der
> deklaration zu initialisieren und mal abgesehen von ein paar wenigen
> Prozessortakten die verloren gehen gibts ja keinen Nachteil oder?

Das ist zum einen eine Definition und Prozessortakte gehen auch nicht 
verloren, wenn der Compiler optimieren darf.

[Der Andere (Gast)]

student schrieb:
> Ich persönlich finde es einfacher lesbar i = i + 1; zu schreiben. Klar
> muss man mehr tippen aber ich finds schöner ist halt geschmackssache.
> Oder bringt i++; noch andere Vorteile?

Ja, du machst es nicht anders wie 99% aller erfahrener Programmierer.

Der resultierende Code dürfte bei modernen Compilern ziemlich der 
gleiche werden.

'++' ist ein unärer Operator, ein '+' und das '=' ist ein binärer 
Operator und eine Zuweisung und damit ein deutlich komplexerer Ausdruck.

Benutze die Operatoren die die Programmiersprache dir bietet.

[Frank M. (ukw) (Moderator)]

student schrieb:
> +-1 Fehler passieren mir immer mal wieder

Die Fehler, die Du gemacht hast, sind eigentlich typische 
Anfängerfehler. Da sind die meisten schon reingetappt. Trotzdem ist eine 
gewisse Selbstdisziplin bei C unumgänglich, denn durch die vielen 
"Freiheiten", die C bietet, kann man auch schnell Murks programmieren. 
Das rächt sich dann irgendwann.

> Ich persönlich finde es einfacher lesbar i = i + 1; zu schreiben. Klar
> muss man mehr tippen aber ich finds schöner ist halt geschmackssache.

Heutzutage ist das wirklich Geschmackssache. Vor 30 Jahren war das noch 
anders. Da optimierten die Compiler nicht so gut und ein i++ verstand 
man damals als Tipp an den Compiler: "Benutze das Increment des 
Prozessors!". Mittlerweile macht das keinen Unterschied. Beide Varianten 
ergeben denselben Maschinencode.

> Ja das stimmt, ich habs behoben indem ich das Zeichen (wenn es gefunden
> wurde) durch eine '0' ersetzte.

Gute Lösung!

> für mich als Anfänger unmöglich selbst zu erkennen, danke für den
> Hinweis

Auch das ist ein typischer Anfängerfehler. Erst bemerkt man den Fehler 
nicht (es läuft ja!), aber wenn das Programm dann größer ist, bekommt 
man Murks aus dem Speicher geliefert. Das Problem: Man sucht dann den 
Fehler in den letzten Änderungen... und sucht sich dann einen Wolf, weil 
der Fehler eigentlich schon immer im Programm war. Bei Dir trat das 
Problem nicht auf, weil Du den strcpy() jedesmal unmittelbar nach dem 
cleanString-Call aufgerufen hast. Sobald da nur eine Funktion mit 
Autovariablen durch eine spätere Änderung dazwischen aufgerufen worden 
wäre, wäre der Speicherbereich, auf den der Pointer zeigte, vollkommen 
undefiniert.

> Sehr guter Punkt, hab ich einfach nicht bedacht bzw. zu wenig drüber
> nachgedacht und zu viel gefreut das es einfach funktioniert hat ;-)

Es gibt sehr oft einen kürzeren Weg ;-)

Aber Kompliment: Als Anfänger schlägst Du Dich schon ganz gut.

> ja das ist richtig, aber ich hab mir angewöhnt Variablen bereits bei der
> deklaration zu initialisieren und mal abgesehen von ein paar wenigen
> Prozessortakten die verloren gehen gibts ja keinen Nachteil oder?

Es ist sicher nicht verkehrt, Autovariablen auch direkt mit einem 
vernünftigen Wert zu initialisieren.

Solche Doppelzuweisungen:

    int i = 0;
    for (i = 0; ...)

optimieren moderne Compiler auch locker weg. Daher ist es nicht falsch, 
so vorzugehen. Denn damit stehst Du auf der sicheren Seite.

Ich sehe das mittlerweile nach über 30 Jahren C-Programmierung aber 
anders: Ich initialisiere nur Variablen, die auch initialisiert werden 
müssen. Ich will damit nicht Prozessortakte einsparen, sondern klar 
zum Ausdruck bringen, dass diese Variable erst später im Verlauf auf 
einen definierten Wert gesetzt wird, wobei dieser u.U. erst später durch 
den Kontext bekannt wird. Dasselbe mache ich mit solchen 
Scratch-Variablen wie z.B. dieses i. Das erscheint auf den ersten Blick 
fehleranfälliger, ist bei diszipliniertem Programmieren aber kein 
Problem.

Bei der Gelegenheit: Benutze besser Variablennamen, die mindestens 3 
Buchstaben lang sind. Bekommt eine Variable wie "i" mal später eine 
andere Bedeutung und möchtest Du sie umbenennen, ist es so gut wie 
unmöglich, diese Variable durch Replace-Global-Befehl im Editor 
umzubenennen. Hieße die Variable eher "idx", wäre das weniger ein 
Problem.

> Hab deine Funktion mal zusätzlich eingefügt. Als Anfänger drückt man
> sich halt gern um Pointer zumindest da wo mans selber erkennt ;-)

Ja, kann ich verstehen. Man sollte sich trotzdem möglichst früh an 
Pointer gewöhnen - auch wenn diese eher nur früher, als die Compiler 
noch nicht so gut optimierten, einen Geschwindigkeitsgewinn brachten. 
Das ganze erscheint einem (nach Gewöhnung an die vielen Sternchen) doch 
irgendwann lesbarer. Ausserdem läuft man so weniger Gefahr, zwei 
Indexvariablen innerhalb einer Funktion mal zu velwechsern.

Weiterhin viel Spaß mit C!

[Klopsomat (Gast)]

student schrieb:
> Ich persönlich finde es einfacher lesbar i = i + 1; zu schreiben. Klar
> muss man mehr tippen aber ich finds schöner ist halt geschmackssache.
> Oder bringt i++; noch andere Vorteile?

Es ist, insbesondere in Schleifen, einfach ein "C(C++, Java, C#, 
...)-Idiom". D.h., fast jeder, der sich seit zumindest ein paar Tagen 
mit einer dieser Programmiersprachen beschäftigt hat, wird i++ oder ++i 
schreiben und bei "i = i + 1" u.U. zweimal hinsehen. Ich persönlich 
benutze in solchen Fällen die "übliche" Variante, falls es keinen 
triftigen Grund dagegen gibt.
Außerdem muss man sich bei ++i nicht umgewöhnen, wenn man eine der 
Sprachen verwendet, in denen es tatsächlich einen Unterschied machen 
kann, ob man "x = x + 1" bzw. x++ oder ++x schreibt (wenn auch nicht bei 
ints und anderen primitiven Typen).