Perlprogramm das für scrabble verwendet werden soll

byron1778 · 4 März 2005

Hallo,
ich habe eine etwas unübliche Frage wahrscheinlich - kam im Zuge des Scrabbeln darauf. Ich möchte aus einer Textdatei, in welcher Wörter stehen (Wörter kamen wiederum von Internetseiten)Wörter auslesen. Der Benutzer gibt 8 Buchstaben ein (zB: hadnumfz) und in der Datei befinden sich jetzt zufällig die Wörter Hund und Hand.

Das Programm soll nun eigenständig aus den 8 Buchstaben, die der Benutzer eingegeben hat, alle Wörter finden, die sich mit den 8 Buchstaben zusammensetzen lassen.

Dabei ist zu beachten, dass die 8 Buchstaben natürlich nicht so eingegeben wurden. hund bzw hand, weil es schwierigere Wörter gibt, die man nicht kennt (zB: Zythotoxin - sollte sich dieses Wort in der Datei befinden und man gibt die Buchstaben ein, aber in einer anderen Reihenfolge ((nur kennt man das Wort natürlich nicht) so soll er selbst rausfinden, dass mit der willkürlichen Buchstabensuppe so ein Wort zu bilden möglich ist!

Kann mir jemand sagen, ob es überhaupt möglich ist unter Perl soetwas zu schreiben und wenn ja, wie kann ich das realisieren?
Mit regulären Ausdrücken dürfte es nicht funktionieren, was ich so gesehen habe!

Vielen Dank für jede Hilfe!

Mfg
Bernd

TeXpert · 4 März 2005

jein, mit einem grep und einer _sehr_ simplen RegEx geht das schon

das Problem ist, aus den Worten die entsprechenden Kombinationen zu machen.

brute-force-Variante: Du musst aus den Buchstaben alle Teilmengen bilden und daraus jeweils alle Permutationen und dann mit diesen so gewonnenen Worten auf Übereinstimmung testen. -> Aufwändig

Hier ist viel Raum für Optimierungen, spontan würde mir einfallen, dass alle Worte in willkürliche Buchstabenfolgen umkodiert werden und zwar in lexikalisch geordnete, also aus HUND macht man ein DHNU aus HAND ein ADHN etc. dann müssen die Inputworte auch lexikalisch geordnet sein und man muss nur noch alle möglichen Teilworte auf Übereinstimmung matchen.

Aber da gibts bestimmt noch andere intelligentere Optimierungen

byron1778 · 4 März 2005

Ok,

der 2te Teil mit dem lexikalischen Verfahren, das überschnalle ich noch

Bei der Permutation steige ich dann aber sofort aus

Ich weiss zwar was es ist, aber so ein Script schreiben liegt doch eher in höheren Bereichen schätze ich einmal!

Eine andere Möglichkeit die mir noch einfällt wäre, dass man bestimmte Buchstaben vorgibt aus den 8, also nehmen wir schwierige Buchstaben (Q, Ö, Ä, Y) und suche durch alle Worte, die im Text stehen und gib Wörter aus, die alle diese 4 enthalten, aber so das wahre ist es auch nicht, zudem ist es ja ein einfacheres regulär expression!

Danke jedenfalls!

TeXpert · 4 März 2005

hehe, Permutation war auch das flashce Stichwort, der Schlüssel ist Potenzmenge

aber ich fand die Idee witzig, ich hab gerade mal ein entsprechendes Programm in Python runtergehackt:

Code:

#!/usr/bin/python

# import
import sys

# lookup-dict
dictionary={}

# sort letters lexically
def sortletters(word):
    letters=[]
    for i in word:
         letters.append(i)	 
    letters.sort()
    ret="".join(letters)
    return ret
        
# build dictionary on the fly
def makedict(infile):
    global dictionary
    dictionary = {}
    words = open(infile, 'r')
    for word in words.readlines():
        word=word[:-1]
        if word != "":	   
	   dictionary[sortletters(word.upper())] = word.upper()	      
    words.close()

# read chars from user, sort them
def readletters():
    print "enter letters: ",
    # read and strip '\n'
    letters = sys.__stdin__.readline()
    return letters[:-1]
    
# check if letters match dictionary-key
def checkdict(word):
    global dictionary
#    print "check " + word
    if dictionary.has_key(word):
       print "wordmatch: " + word + " --> " + dictionary[word]

# build power set and check each subset
def powersetcheck(subset, reminder):
  if len(reminder) == 0:
     checkdict(subset)
  else:
     powersetcheck(subset, reminder[1:])
     powersetcheck(subset + reminder[0:1], reminder[1:])
     
	   
## Programm, first read wortlist, then interactive checking :)  
makedict("wortliste.txt")
print "enter your letters, a '-' terminates the program"
# input-loop
while 1: 
    letters = readletters()
    if letters == "-": sys.exit()
    letters = letters.upper();
    print "sorted:    " + sortletters(letters)
    powersetcheck("", sortletters(letters))

Vorraussetzung eine Wortliste (z.zt. hardcodes wortliste.txt) mit einem Wort pro Zeile also z.B. so:

Code:

HUND
KATZE
MAUS
HAND
BEIN
fisch
FLEISCH
SUSHI
Auge

gross/klein ist egal, ich konvertiere eh alles in Capitals.

Probleme: Worte werden durch diese Potenzmengen konstruktion mehrfach gefunden

etwas unschön, hier müsste man erst sammeln

weitere potentielle Probleme: ich halte das gesamte Wörterbuch im Speicher, das könnte latürnich irgendwann eng werden, dann müsste man das Dictionary z.B. in die db oder eine Datei auslagern

Beispielausgabe mit der angegebenen Wortliste

> ./scrabble.py
enter your letters, a '-' terminates the program
enter letters: fischauge
sorted: ACEFGHISU
wordmatch: CFHIS --> FISCH
wordmatch: AEGU --> AUGE
enter letters: -

TeXpert · 4 März 2005

ich antworte mir mal

eine kleine Änderung und jetzt gibts auch keine Duplikate mehr:

Code:

#!/usr/bin/python

# import
import sys

# lookup-dict
dictionary={}
# collect matches
wordmatches=[]

# sort letters lexically
def sortletters(word):
    letters=[]
    for i in word:
         letters.append(i)	 
    letters.sort()
    ret="".join(letters)
    return ret
        
# build dictionary on the fly
def makedict(infile):
    global dictionary
    dictionary = {}
    words = open(infile, 'r')
    for word in words.readlines():
        word=word[:-1]
        if word != "":	   
	   dictionary[sortletters(word.upper())] = word.upper()	      
    words.close()

# read chars from user, sort them
def readletters():
    print "enter letters: ",
    # read and strip '\n'
    letters = sys.__stdin__.readline()
    return letters[:-1]
    
# check if letters match dictionary-key
def checkdict(word):
    global dictionary
    global wordmatches
    if dictionary.has_key(word):
       wordmatches.append(word + " --> " + dictionary[word])

# build power set and check each subset
def powersetcheck(subset, reminder):
  if len(reminder) == 0:
     checkdict(subset)
  else:
     powersetcheck(subset, reminder[1:])
     powersetcheck(subset + reminder[0:1], reminder[1:])
     
    	   
#################################################    
makedict("wortliste.txt")
print "enter your letters, a '-' terminates the program"
while 1: 
    letters = readletters()
    if letters == "-": sys.exit()
    letters = letters.upper();
    print "sorted:    " + sortletters(letters)
    wordmatches=[]
    powersetcheck("", sortletters(letters))
    if len(wordmatches) == 0:
        print "no match"
    else:	
        wordmatches=reduce(lambda l, x: x not in l and l.append(x) or l, wordmatches, [])
    	print "found", len(wordmatches), "matches:"
        for i in range(len(wordmatches)):
            print wordmatches[i]

byron1778 · 5 März 2005

Danke Dir vielmals!

Ich werde es gleich ausprobieren. Habe leider keine Ahnung in Python, werde mir daher ein Wörterbuch zusammenstellen aus HTML - Links. Folgendes habe ich mir dabei nämlich noch gedacht.

Im Programm weden beliebig viele HTML - Links eingetragen und aus denen heraus extrahiert das Programm dann alle Wörter (unabhängig der Sprache), dadurch ergibt sich dann das Wörterbuch, welches man perfekt für Scrabble verwenden kann und somit die Gewinnchancen um ein vielfaches erhöhen sollte

Jedenfalls danke schon für das PRogramm!

Man wird ja wahrscheinlich auch in Python HTML - Links angeben können, aus denen das Programm dann sich die Wörter extrahiert.

Weisst Du wie die Syntax dafür auch geht?

Mfg
Bernd

byron1778 · 5 März 2005

Hallo,

beim Ausführen des Programms ergibt sich folgender Fehler bei mir (Suse Linux 9.0 Maschine mit Python Interpreter)

mail1:~/Desktop # ./test.py
File "./test.py", line 4
import sys
^
SyntaxError: invalid syntax

Muss ich vielleicht etwas ändern beim Ausführen der Datei od irgendwelche bestimmten Pakete dazuinstallieren?

TeXpert · 6 März 2005

das sieht so aus, als wäre da bei C&P einiges kaputt

Das problem bei Python ist, dass die Block-Syntax genau den Leerzeichen entspricht, d.h. vor allen Zeilen des 1. Blocks (z.B. dieses import) darf kein Tab oder Leerzeichen stehen, der nächste Block muss dann komplett jeweils mit der gleichen Anzahl Zeichen eingerückt sein, z.B. (alle Leerzeichen durch ~ ersetzt)

Code:

# das geht:
import~sys
# das geht nicht (syntax-fehler)
~import~sys

# das geht
if~a==b:
~~print~"hallo"
~~print~a
~~print~b

# das geht nicht (syntax-fehler
if~a==b:
~~print~"hallo"
~~~print~a
~~print~b

byron1778 · 7 März 2005

Ok, danke!

Jetzt zeigt er einen Fehler in Line 28 an, (auch dort habe ich versucht die Leerzeichen zu entfernen bzw aufzufüllen, mag er aber nicht!)

Folgende Fehlermeldung erhalten ich dieses Mal!

File "C:\Dokumente und Einstellungen\Bernd\Desktop\t.py", line 28
dictionary[sortletters(word.upper())] = word.upper()
^
IndentationError: unindent does not match any outer indentation level

Leider habe ich noch nie mit Python gearbeitet!

byron1778 · 7 März 2005

Hoppla, da hat sich doch das "Dach" verschoben, es gehört zur letzten Klammer von word.upper!

File "C:\Dokumente und Einstellungen\Bernd\Desktop\t.py", line 28
dictionary[sortletters(word.upper())] = word.upper()
^
IndentationError: unindent does not match any outer indentation level

TeXpert · 7 März 2005

IndentationError: sagt doch schon alles, hier stimmen auch die Leerzeichen nicht, die müssen pro Block alle gleich sein

Code:

# das geht nicht
if~a==b:
~~print~"hallo"
~~print~a
~~if~a!=b:
~~print hallo
~~print~b 

# das geht:
if~a==b:
~~print~"hallo"
~~print~a
~~if~a!=b:
~~~print hallo
~~print~b

also noch mal anders:

Code:

#!/usr/bin/python

#~import
import~sys

#~lookup-dict
dictionary={}
#~collect~matches
wordmatches=[]

#~filter~duplicates~out~of~list
def~filterdups(iterable):
~~~~seen~=~set()
~~~~for~item~in~iterable:
~~~~~~~~if~item~not~in~seen:
~~~~~~~~~~~~seen.add(item)
~~~~~~~~~~~~yield~item

#~sort~letters~lexically
def~sortletters(word):
~~~~letters=[]
~~~~for~i~in~word:
~~~~~~~~~letters.append(i)
~~~~letters.sort()
~~~~ret="".join(letters)
~~~~return~ret

#~build~dictionary~on~the~fly
def~makedict(infile):
~~~~global~dictionary
~~~~dictionary~=~{}
~~~~words~=~open(infile,~'r')
~~~~for~word~in~words.readlines():
~~~~~~~~word=word[:-1]
~~~~~~~~if~word~!=~"":	~~~
~~~~~~~~~~~dictionary[sortletters(word.upper())]~=~word.upper()
~~~~words.close()

#~read~chars~from~user,~sort~them
def~readletters():
~~~~print~"enter~letters:~",
~~~~#~read~and~strip~'\n'
~~~~letters~=~sys.__stdin__.readline()
~~~~return~letters[:-1]

#~check~if~letters~match~dictionary-key
def~checkdict(word):
~~~~global~dictionary
~~~~global~wordmatches
~~~~if~dictionary.has_key(word):
~~~~~~~wordmatches.append(word~+~"~-->~"~+~dictionary[word])

#~build~power~set~and~check~each~subset
def~powersetcheck(subset,~reminder):
~~if~len(reminder)~==~0:
~~~~~checkdict(subset)
~~else:
~~~~~powersetcheck(subset,~reminder[1:])
~~~~~powersetcheck(subset~+~reminder[0:1],~reminder[1:])

#################################################~~~~
makedict("wortliste.txt")
print~"enter~your~letters,~a~'-'~terminates~the~program"
while~1:
~~~~letters~=~readletters()
~~~~if~letters~==~"-":~sys.exit()
~~~~letters~=~letters.upper();
~~~~print~"sorted:~~~~"~+~sortletters(letters)
~~~~wordmatches=[]
~~~~powersetcheck("",~sortletters(letters))
~~~~if~len(wordmatches)~==~0:
~~~~~~~~print~"no~match"
~~~~else:	
~~~~~~~~wordmatches=reduce(lambda~l,~x:~x~not~in~l~and~l.append(x)~or~l,~wordmatches,~[])
~~~~~~~~print~"found",~len(wordmatches),~"matches:"
~~~~~~~~for~i~in~range(len(wordmatches)):
~~~~~~~~~~~~print~wordmatches[i]

hier sind jetzt alle Leerzeichen durch '~' ersetzt, speichern als s.py und dann:

Code:

sed -e 's/~/ /g' s.py > scrabble.py

in der Shell

byron1778 · 7 März 2005

Ok, danke vielmals!

Es funktioniert jetzt!

Probiere das Ganze gerade auf einer Windows-Maschine eben aus!

Muss es dann noch auf Linux portieren, da läuft es ja sicher schneller!

Mfg

Perlprogramm das für scrabble verwendet werden soll

byron1778

Hacker

TeXpert

Guru

byron1778

Hacker

TeXpert

Guru

TeXpert

Guru

byron1778

Hacker

byron1778

Hacker

TeXpert

Guru

byron1778

Hacker

byron1778

Hacker

TeXpert

Guru

byron1778

Hacker