Vorstellung Buchstabensalat KNACKER! ;-)

patrick210778 · Newbie Anmeldungsdatum: 06.07.2007 Beiträge: 8

Hallo,

am besten stelle ich mal ganz kurz vor.
Ich heiße Patrick bin 29 Jahre alt und komme aus Wolfsburg

Irgendwann habe ich mal 9Live geschaut und wollte unbedingt die Lösung eines Buchstabensalates Wissen, allerdings wollte ich mir den „Quatsch“ vom Moderator auch nicht mehr länger antun. Also habe ich ein Programm geschrieben welches Buchstabensalat knackt. Ich denke, dass das Forum hier der Richtige Ort ist um mein Projekt mal der Öffentlichkeit zur Verfügung zu stellen.

Ich bin zwar selber kein Mathe Krack, allerdings habe ich einen „Genialen“ Algorithmus entwickelt um einen Buchstaben Salat zu knacken.

Fangen wir ganz einfach an, wir haben drei Buchstaben und möchten Wissen wie viel verschiede Konstellationen wir aus diesen Buchstaben Anordnen können?

Nehmen wir die drei Buchstaben A B und C
Daraus ergeben sich genau sechs Möglichkeiten

A B C
A C B
B A C
B C A
C A B
C B A

Das sind genau sechs Möglichkeiten! Bei „nur“ wenigen Buchstaben ist die Variation noch relativ Übersichtlich.

Um Mathematisch auf die Lösung zu kommen wie viel Möglichkeiten es gibt. Bedienen wir uns der Fakultät. Also (n!)
Um auf das obige Beisp. zurück kommen 3! < --- > 1 x 2 x 3 = 6

Allerdings gibt es wenige Wörter mit drei Buchstaben!

Schaffen wir uns mal einen kleinen realistischen Überblick.

4! 1 x 2 x 3 x 4 = 24
5! 1 x 2 x 3 x 4 x 5 = 120
6! … 720
7! … 5.040
8! … 40.320
9! … 362.880
10! 1 x 2 x 3 … usw x 10 = 362.8800
…
13! Das Wort „Kraftfahrzeug“ kann man also in seinen Buchstaben auf 6.227.020.800 verschiedene Möglichkeiten zerstückeln!

Mein Buchstabensalat Knacker kann nahezu jeden deutschen Begriff entschlüsseln und das in einem sehr akzeptablen Zeitfenster. Sicherlich kommen bei einigen Buchstabenkonstellationen „komische“ Wörter heraus. Allerdings befindet sich das Programm noch in der Testphase und ich habe zu beginn des Projektes nie gedacht das ich soviel Energie und Elan in das Projekt stecke. Allerdings arbeite ich schon seid geraumer Zeit daran die Antwortzeiten immer weiter zu optimieren.

Buchstabensalat Knacken http://salat.htm24.de/

Schönen Gruß

Patrick

someDay · Senior Member Anmeldungsdatum: 04.09.2005 Beiträge: 3889

Alles was man dazu braucht ist eine Datenbank der meisten deutschen Woerter - das allerdings duerfte aufwaendig werden - und eine simple Idee, naemlich das man die Buchstaben im Wort eindeutig ordnen kann (z.b. a zuerst und z zuletzt) und dies problemlos mit einer Datenbank vergleichen kann. Schlimmer ist der Fake 'Berechnete Woerter Zaehler'...

Edit: Weil ich mir an einem Freitagabend nichts interessanteres vorstellen kann, ich wette mit dir das ich binnen 2h ein Programm schreibe das die gleiche Aufgabe erfuellt... Wink

Edit2: Wenngleich ich den Sinn des "Berechnete Woerter zaehlen" nicht sehe, er zaehlte die in der Datenbank aufgenommenen Woerter und nicht die bisher berechneten - insofern kein Fake.

sD.

patrick210778 · Newbie Anmeldungsdatum: 06.07.2007 Beiträge: 8

someDay · Senior Member Anmeldungsdatum: 04.09.2005 Beiträge: 3889

Ironiker · Senior Member Anmeldungsdatum: 27.11.2005 Beiträge: 879

http://www.sibiller.de/anagramme/
_________________
Auf der Suche nach Identität und Südfrüchten

patrick210778 · Newbie Anmeldungsdatum: 06.07.2007 Beiträge: 8

nico123 · Full Member Anmeldungsdatum: 30.10.2005 Beiträge: 224

dein beispiel mit dem kraftfahrzeug ist irgendwie komisch. da gibts doch doppelte buchstaben, ist also gar nicht 13! .

patrick210778 · Newbie Anmeldungsdatum: 06.07.2007 Beiträge: 8

Da hast Du allerdings vollkommen Recht! Das Beispiel sollte auch mehr einen Symbolischen Charakter haben um zu erahnen was für eine Dimension sich dahinter verbirgt.

Allerdings vielen Dank für Deinen Hinweis!

Viele Grüße aus Wolfsburg

Patrick

someDay · Senior Member Anmeldungsdatum: 04.09.2005 Beiträge: 3889

Ist fertig und funktioniert. Allerdings sind erst 10000 Woerter bisher in der Datenbank - ich werde es veroeffentlichen sobald es ~ 50000 sind.

Siehe: http://brightlight.ch/results.php

sD.

Ironiker · Senior Member Anmeldungsdatum: 27.11.2005 Beiträge: 879

patrick210778 · Newbie Anmeldungsdatum: 06.07.2007 Beiträge: 8

someDay · Senior Member Anmeldungsdatum: 04.09.2005 Beiträge: 3889

Keine Schande, du bist ja auch noch jung - erst 5 Beitraege!

Anspruchsvollere Varianten des Problems:

(i) Keine Datenbank erlaubt, maximal 2.5kb Code (im Code darf eine Mini Datenbank enthalten sein), externe Bibliotheken duerfen genutzt werden, solange sie keine Datenbanken (oder aehnliches) sind. Oder, als Variante B, mit einer Datenbank die (Komprimierung erlaubt) maximal 50kb gross ist.

(ii) Teile von Woertern erkennen - internet enthaelt beispielsweise u.a. intern, nett und rennt - einmal mit und einmal ohne Datenbank.

(iii) Verwandt mit (ii), zusammengesetzte Woerter erkennen (ohne Datenbank von zusammengesetzten Woertern).

Das Problem bei der Datenbank ist sowieso, das ab einer bestimmten Groesse die Prozentzahl der aufgenommen Rechtschreibfehler und "redundanten" Woerter (zusammengesetzte, sinnlose, ...) stark zunimmt. Muesste man mal mit dem Duden oder so etwas abgleichen.

sD.

patrick210778 · Newbie Anmeldungsdatum: 06.07.2007 Beiträge: 8

@SomeDay
Ja das stimmt die Anzahl der sinnfreien Begriffe nimmt bei einem hohem Datenbestand schneller zu. Aus meiner Erfahrung heraus kommt man relativ Fix auf round about 700.00 Begriffe, alles darüber benötigt man fast Exponential soviel „Rohmaterial“ um noch neue Sinnvolle Wörter hinzufügen. Bis jetzt habe ich ganz locker über 2-3 GB Digitale Dokumente ausgewertet und diese auf neue Begriffe abgeklopft.

Variante 1 wäre nichts für mich, da man ohne einen gescheiten Bestand nicht wirklich effizient Buchstabensalat lösen kann.

Variante 3 wäre auch nichts für mich, aus dem gleichen Grund wie Variante 1.

Variante 2 ist schön besser allerdings nur mit Datenbank evtl. sogar mit zwei Datenbanken auf zwei unterschiedlichen Physischen Systemen um keine Performance Verluste zu haben. Ich besitze momentan einen Datenbestand von mehr als 1.5 Millionen Begriffen. Und bei dieser Dimension spürt man es sofort Signifikant was die Performance angeht. Ich hätte da schon einen ganz konkreten Ansatz wie ich das Umsetzen könnte mit der Idee alle möglichen Wörter aus den Gegebenen zu berechnen. Allerdings würde jede Abfrage einige Sekunden dauern, da jeder Datensatz Untersucht werden würde. Die meisten Datensätze würden schon bei der ersten „grob“ Analyse aus dem Raster fallen. Allerdings ist wie gesagt die Menge der Faktor Zeit bei 1.5 Millionen Datensätzen. Wenn bei 10.000 Begriffen die Abfrage 1 Sekunde dauert ist es kaum spürbar, beim 150 Fachen allerdings deutlich spürbar.

An Aufgabe zwei werde ich mich mal ransetzen ich denke das dies für mich Realisierbar ist. Allerdings ist der Begriff Zeit für mich gerade ein Luxus, da ich dieses Projekt immer wenn ich Lust und vor allem Zeit habe etwas vorantreibe. Sobald ich die zweite Funktion um es mal zu bezeichnen implementiert habe melde ich bei Dir.

Schönen Gruß

Patrick

someDay · Senior Member Anmeldungsdatum: 04.09.2005 Beiträge: 3889

Primaer geht es bei allen Varianten darum das Problem von "Datenbank anlegen" zu "Intelligenten Algorithmus entwickeln" zu verlagern.

Variante (i) ist meines Ermessens nach durchaus machbar - die mit 50kb Datenbank definitiv, die Variante mit 2.5kb Code ist natuerlich sehr anspruchsvoll, aber ebenfalls machbar. Natuerlich nicht mehr zu 100% korrekt (was im Moment ja angesichts der fehlerhaften Datenbankeintraege sowieso nicht der Fall ist), aber naeherungsweise.

Variante (iii) ist weniger kompliziert als Variante (ii) - wenn du bereits Teile von Woertern erkennen kannst, sollte man die problemlos zusammen fuegen koennen. Problematischer wird es eher sein, die Datenbank von zusammengesetzten Woertern zu sauebern.

Variante (ii) ist nicht mit Bruteforce in absehbarer Zeit loesbar, Backtracking eventuell. Man koennte das alles im Voraus berechnen (nicht in PHP Wink

und in einer Datenbank speichern, aber das ist eine sehr unelegante, haessliche Loesung.

sD.

derBucklige · Verfasst am: 07 Jul 2007 - 22:52:32 Titel:

heyho
erstmal glückwunsch euch beiden .. beide progs funktionieren sehr gut
@ sD .. warum steht bei http://brightlight.ch/results.php "©brightlight" ist das deine schweizer firma oder wie? kannste beweisen das es echt von dir ist? oder gar nicht schon irgendwie existiert hat?

MfG
Hunchback aka Nino Hinte

someDay · Senior Member Anmeldungsdatum: 04.09.2005 Beiträge: 3889

Das ist mein Arbeitgeber. Solltest du Zweifel haben, schau dir den Quelltext an Wink

sD.