Scralphabet
Ein normaler Beutel mit Scrabble-Kacheln enthält die folgenden Buchstaben ( ?
ein leerer Kachel, der für jeden anderen Buchstaben stehen kann):
AAAAAAAAABBCCDDDDEEEEEEEEEEEEFFGGGHHIIIIIIIIIJKLLLLMMNNNNNNOOOOOOOOPPQRRRRRRSSSSTTTTTTUUUUVVWWXYYZ??
Die Buchstaben haben folgenden Wert:
{"A": 1,"B": 3,"C": 3,"D": 2,"E": 1,"F": 4,"G": 2,"H": 4,"I": 1,"J": 8,"K": 5,"L": 1,"M": 3,"N": 1,"O": 1,"P": 3,"Q": 10,"R": 1,"S": 1,"T": 1,"U": 1,"V": 4,"W": 4,"X": 8,"Y": 4,"Z": 10,"?": 0}
Konstruieren Sie bei einem normalen Beutel mit Scrabble-Kacheln den Satz mit der höchsten Punktzahl von sich nicht überschneidenden Wörtern (dh einzelne Wörter, nicht auf einer Scrabble-Tafel) unter folgenden Bedingungen:
- Die Punktzahl für jedes Wort ist
sum(letter_values) * length(word)
. - Sie dürfen maximal ein Wort eingeben, das mit jedem Buchstaben des Alphabets beginnt (also maximal 26 Wörter).
- Nur gültige Scrabble-Wörter (aus diesem Wörterbuch) ) enthalten sein. Sie können das Wörterbuch aus einer Datei lesen, fest codieren (ugh) oder von der Website entfernen.
- Sie müssen nicht jedes Plättchen verwenden, sondern alle nicht verwendeten Plättchen bilden ein einzelnes Wort, das auf die gleiche Weise gewertet wird und von Ihrer Punktzahl abgezogen wird.
Wenn Sie möchten, akzeptiert Ihr Code möglicherweise zwei Eingaben: den Tascheninhalt als Zeichenfolge und die Buchstabenwerte in einem Format, das einem Python ähnelt dict
(wie oben). Alternativ können Sie den Tascheninhalt und die Buchstabenwerte fest codieren. Es sollte die Wörter in Ihrem Satz, ihre jeweiligen Punktzahlen und Ihre Gesamtpunktzahl in einem angemessenen Format ausgeben.
Das Wortset mit der höchsten Punktzahl gewinnt, wobei die Krawatten zuerst veröffentlicht werden.
quelle
print"FOO18\nBAR15\nBAZ42\n...\n1523"
?Antworten:
C 2765 (optimal)
Bearbeiten
Jetzt alles in einer einzigen C-Datei. Dies findet nur die optimalen Lösungen. Sie müssen aus 6 Wörtern mit 15 Buchstaben und einem Wort mit 10 Buchstaben bestehen, das aus 8 Buchstaben mit dem Wert 1 und zwei Leerzeichen besteht. Dafür muss ich nur einen Bruchteil des Wörterbuchs laden und muss nicht nach Wörtern mit 15 Buchstaben und Leerzeichen suchen. Der Code ist eine einfache, erschöpfende Tiefensuche.
Verwendung:
Beachten Sie, dass jede Lösung zweimal gedruckt wird, da beim Hinzufügen eines 15-Buchstaben-Worts 2 Aufträge erstellt werden, da es 2 W-Kacheln gibt.
Die erste Lösung, die mit der Punktaufschlüsselung gefunden wurde:
Bearbeiten: Erklärung
Was macht das Durchsuchen des gesamten Raumes möglich? Beim Hinzufügen eines neuen Wortes berücksichtige ich nur Wörter mit dem seltensten verbleibenden Buchstaben. Dieser Buchstabe muss sowieso in einem Wort stehen (und ein Wort mit 15 Buchstaben, da dies ein nicht einwertiger Buchstabe ist, obwohl ich das nicht überprüfe). Also beginne ich mit Wörtern,
J, Q, W, W, X, Z
die zählen50, 100, 100, 100, 200, 500
. Auf niedrigeren Ebenen bekomme ich mehr Cutoff, weil einige Wörter durch das Fehlen von Buchstaben eliminiert werden. Breite des Suchbaums auf jeder Ebene:Natürlich wird eine Menge Cutoff erzielt, wenn nicht optimale Lösungen nicht überprüft werden (Leerzeichen in Wörtern mit 15 Buchstaben oder kürzeren Wörtern). Es ist also ein Glück, dass mit diesem Wörterbuch eine 2765-Lösung erzielt werden kann (aber es war knapp, nur 2 Kombinationen von 15-Buchstaben-Wörtern ergaben einen vernünftigen Rest). Andererseits ist es einfach, den Code zu modifizieren, um Kombinationen mit niedrigerer Punktzahl zu finden, bei denen nicht alle verbleibenden 10 Buchstaben 1-wertig sind, obwohl es schwieriger wäre, zu beweisen, dass dies eine optimale Lösung wäre.
Der Code zeigt auch den klassischen Fall einer vorzeitigen Optimierung. Diese Version der
matches
Funktion verlangsamt den Code nur um 30%:Ich habe sogar herausgefunden, wie ich den Bit Magic Parallel-Vergleich noch kürzer machen kann als in meinem ursprünglichen Code (das höchste Nibble kann in diesem Fall nicht verwendet werden, aber das ist kein Problem, da ich nur 26 von 32 Nibbles benötige):
Aber es gibt keinen Vorteil.
Bearbeiten
Beim Schreiben der obigen Erklärung wurde mir klar, dass die meiste Zeit für das Durchsuchen der Wortliste nach Wörtern verwendet wird, die einen bestimmten Buchstaben enthalten, der nicht in der
matches
Funktion enthalten ist. Die Berechnung der Listen im Voraus ergab eine 10-fache Beschleunigung.quelle
Python 2, Kerbe:
18402162Dieses Programm findet zuerst das mit den angegebenen Kacheln verfügbare Wort mit der besten Punktzahl (ohne Verwendung von Platzhaltern) und unternimmt dann 10000 Versuche, zufällige Wörter einzuschließen, die die Bedingungen eines eindeutigen ersten Zeichens erfüllen und über verfügbare Kacheln verfügen. Bei den aktuellen Konstanten dauert es 27 Sekunden, bis das Programm auf meinem Computer ausgeführt wird. Die Verwendung größerer Konstanten würde wahrscheinlich eine Kombination von Wörtern mit höherer Punktzahl ergeben.
UPDATE: Verwendet jetzt einen zweistufigen Auswahlalgorithmus, sodass in jeder Auswahlstufe die besten 50 Wörter gefunden werden. Die Strafpunktzahl wird nun auch im Auswertealgorithmus verwendet.
Ich füge hier das Beste aus ein paar Läufen hinzu:
Beachten Sie, dass ich keine Platzhalter verwende und eine größere Strafe zahle (aufgrund der Wortlänge). Eine zukünftige Verbesserung kann die Verwendung von Platzhaltern beinhalten.
quelle
Simuliertes Tempern (Punktzahl 2246)
Leider ist dies nicht deterministisch. Ich werde versuchen, das zu beheben und einen deterministischen Keim zu finden, der einen besseren Wert ergibt.
quelle
Python, Kerbe
263826752676268926992717Ergebnis:
Code:
Erläuterung:
Tiefensuche, die den gesamten Baum durchsucht und
picks
in jeder Phase zwischen den besten Wörtern wählt.Ich sortiere die gesamte Wortliste einmal nach Punktzahl am Anfang. Nachdem ich jedes Wort ausgewählt habe, filtere ich für die nächste Iteration alle Wörter heraus, die jetzt nicht mehr möglich sind, und behalte dabei die Reihenfolge bei, damit ich die Liste nicht bei jedem Schritt sortieren muss. Um mit Platzhaltern umzugehen, suche ich die 10000 besten Kandidaten aus, ersetze fehlende Buchstaben durch Platzhalter und sortiere sie nach den neuen (niedrigeren) Werten neu.
Dieser Ausgang ist für
picks=5
und nahm8m01s
auf meiner 8-Core - Maschine laufen zu lassen.quelle
Java 8, Score
26412681Das Programm beginnt mit den 40 besten Wörtern. Für jedes Wort werden die 40 besten Wörter gefunden. Von den 1600 Kombinationen nimmt das Programm die besten 40. Für jede Kombination werden die 40 besten Wörter gefunden und der Zyklus wiederholt sich.
Wenn nur noch wenige Kacheln übrig sind, werden die verbleibenden Buchstaben mit den beiden Leerzeichen für das letzte Wort kombiniert.
Aktualisieren
Ich habe die Schwelle auf die 50 besten Wörter angehoben. Außerdem werden mit jeder Kombination nur Wörter hinzugefügt, die kleiner sind als die bereits vorhandenen. Dies verhindert mehrere Permutationen derselben Gruppe.
Das Programm:
quelle
Perl, Kerbe: 2655
2630Verwenden:
Die Verwendung von Leerzeichen führt eigentlich nicht zu so viel Leistung, verlangsamt jedoch die Ausführung erheblich:
Nach dem Hinzufügen einiger Heuristiken:
quelle
Python 3, Punktzahl 2735
(Die optimale Punktzahl von 2765, "6 Wörter mit 15 Buchstaben und ein Wort mit 10 Buchstaben, bestehend aus 8 Buchstaben mit dem Wert 1 und zwei Leerzeichen", wurde von nutki erreicht .)
Ich habe einen gierigen Ansatz gewählt, der dem anderer ähnelt:
Ich beginne mit Listen mit einem Element, die die am besten bewerteten Wörter enthalten, die Qs enthalten.
Bei jedem Schritt für jedes Listenelement erstelle ich
k = 800
neue Listen mit den besten juristischen Wörtern für die Liste. Aus der aggregierten Liste der Listen behalte ich diek
Top-Scoring-Listen und wiederhole den Vorgang zehnmal.Beachten Sie, dass Sie die obersten
k
Elemente einern
-langen Liste in O (n + k * log n) erhalten können. Dies ist O (n), wenn Siek<<n
wie in unserem Fall (k = 800, n ~= 250000
) eine Heap-Warteschlange haben. Ich denke, diese Methode wird in anderen Einsendungen nicht verwendet, daher die kleinerenk
Werte.Ich benutze Platzhalter auf dem Weg, falls dies für die Wörter benötigt wird.
Die Laufzeit beträgt ein paar Minuten
k = 800
. Höhere Werte und andere Optimierungen haben noch keine besseren Ergebnisse erbracht.Ergebnis:
Ich habe mit dem Descartes-Produkt der besten Wörter experimentiert, die Q, J und X enthalten, da diese Buchstaben kaum Wörter gemeinsam haben. Mein bestes Ergebnis mit dieser Startegie war 2723 (
DEMISEMIQUAVERS OXYPHENBUTAZONE INTERSUBJECTIVE FLASHFORWARDING KNOWLEDGABILITY RADIOPROTECTION ANALOGUE EA
).Der unnötig komplizierte Spaghetti-Code (mit Spuren von Experimenten mit anderen Methoden):
quelle