Diese Website existiert nur weil wir Werbung mit AdSense ausliefern.
Bitte den AdBlocker daher auf dieser Website ausschalten! Danke.

Perlprogramm das für scrabble verwendet werden soll

Alles rund um die verschiedenen Konsolen und shells sowie die Programmierung unter Linux

Moderator: Moderatoren

Antworten
byron1778
Hacker
Hacker
Beiträge: 443
Registriert: 25. Nov 2004, 13:19

Perlprogramm das für scrabble verwendet werden soll

Beitrag von byron1778 »

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
Benutzeravatar
TeXpert
Guru
Guru
Beiträge: 2166
Registriert: 17. Jan 2005, 11:22

Beitrag von TeXpert »

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

Code: Alles auswählen

# to resolve all your problems, try this:
HOWTO='pack c5,41*2,sqrt 7056,unpack(c,H)-2,oct 115' && perl -le "print $HOWTO"
Ich beantworte keine Supportfragen per PM!
byron1778
Hacker
Hacker
Beiträge: 443
Registriert: 25. Nov 2004, 13:19

Beitrag von byron1778 »

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!
Benutzeravatar
TeXpert
Guru
Guru
Beiträge: 2166
Registriert: 17. Jan 2005, 11:22

Beitrag von TeXpert »

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: Alles auswählen

#!/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: Alles auswählen

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

Code: Alles auswählen

# to resolve all your problems, try this:
HOWTO='pack c5,41*2,sqrt 7056,unpack(c,H)-2,oct 115' && perl -le "print $HOWTO"
Ich beantworte keine Supportfragen per PM!
Benutzeravatar
TeXpert
Guru
Guru
Beiträge: 2166
Registriert: 17. Jan 2005, 11:22

Beitrag von TeXpert »

ich antworte mir mal :) eine kleine Änderung und jetzt gibts auch keine Duplikate mehr:

Code: Alles auswählen

#!/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]
	    
    

Code: Alles auswählen

# to resolve all your problems, try this:
HOWTO='pack c5,41*2,sqrt 7056,unpack(c,H)-2,oct 115' && perl -le "print $HOWTO"
Ich beantworte keine Supportfragen per PM!
byron1778
Hacker
Hacker
Beiträge: 443
Registriert: 25. Nov 2004, 13:19

Beitrag von byron1778 »

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

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
Hacker
Hacker
Beiträge: 443
Registriert: 25. Nov 2004, 13:19

Beitrag von byron1778 »

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?
Benutzeravatar
TeXpert
Guru
Guru
Beiträge: 2166
Registriert: 17. Jan 2005, 11:22

Beitrag von TeXpert »

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: Alles auswählen

# 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

Code: Alles auswählen

# to resolve all your problems, try this:
HOWTO='pack c5,41*2,sqrt 7056,unpack(c,H)-2,oct 115' && perl -le "print $HOWTO"
Ich beantworte keine Supportfragen per PM!
byron1778
Hacker
Hacker
Beiträge: 443
Registriert: 25. Nov 2004, 13:19

Beitrag von byron1778 »

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
Hacker
Hacker
Beiträge: 443
Registriert: 25. Nov 2004, 13:19

Beitrag von byron1778 »

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
Benutzeravatar
TeXpert
Guru
Guru
Beiträge: 2166
Registriert: 17. Jan 2005, 11:22

Beitrag von TeXpert »

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

Code: Alles auswählen

# 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: Alles auswählen

#!/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: Alles auswählen

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

Code: Alles auswählen

# to resolve all your problems, try this:
HOWTO='pack c5,41*2,sqrt 7056,unpack(c,H)-2,oct 115' && perl -le "print $HOWTO"
Ich beantworte keine Supportfragen per PM!
byron1778
Hacker
Hacker
Beiträge: 443
Registriert: 25. Nov 2004, 13:19

Beitrag von byron1778 »

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
Antworten