Wie man eine Liste möglicher Wörter aus einer Buchstabenmatrix findet [Boggle Solver]

Question

In letzter Zeit habe ich auf meinem iPhone ein Spiel namens Scramble gespielt. Einige von euch kennen dieses Spiel vielleicht als Boggle. Wenn das Spiel beginnt, erhält man im Wesentlichen eine Matrix von Buchstaben, etwa so:

F X I E
A M L O
E W B X
A S T U

Das Ziel des Spiels ist es, so viele Wörter wie möglich zu finden, die durch Aneinanderreihen von Buchstaben gebildet werden können. Sie können mit einem beliebigen Buchstaben beginnen, und alle Buchstaben, die ihn umgeben, sind Freiwild, und sobald Sie zum nächsten Buchstaben weitergehen, sind alle Buchstaben, die diesen Buchstaben umgeben, Freiwild, mit Ausnahme der bereits verwendeten Buchstaben . In dem obigen Raster könnte ich zum Beispiel die folgenden Wörter finden LOB , TUX , SEA , FAME , usw. Die Wörter müssen aus mindestens 3 Zeichen bestehen und dürfen nicht mehr als NxN Zeichen haben, was in diesem Spiel 16 Zeichen sind, aber in einigen Implementierungen variieren können. Obwohl dieses Spiel Spaß macht und süchtig macht, bin ich offensichtlich nicht sehr gut darin und wollte ein wenig schummeln, indem ich ein Programm erstellte, das mir die bestmöglichen Wörter liefert (je länger das Wort ist, desto mehr Punkte erhält man).

_{(Quelle: <a href="http://www.boggled.org/sample.gif" rel="noreferrer">verblüfft.org </a>)}

Leider kenne ich mich mit Algorithmen, ihrer Effizienz usw. nicht besonders gut aus. Mein erster Versuch verwendet ein Wörterbuch wie zum Beispiel dieses (~2.3MB) und führt eine lineare Suche durch, um Kombinationen mit Wörterbucheinträgen zu finden. Dies dauert eine よほど lange Zeit, um die möglichen Wörter zu finden, und da man nur 2 Minuten pro Runde hat, ist das einfach nicht ausreichend.

Ich bin gespannt, ob Stackoverflowers effizientere Lösungen anbieten können. Ich bin vor allem auf der Suche nach Lösungen mit den Big 3 Ps: Python, PHP und Perl, obwohl alles mit Java oder C++ auch cool ist, da Geschwindigkeit entscheidend ist.

AKTUELLE LÖSUNGEN :

• Adam Rosenfield, Python, ~20s
• John Fouhy, Python, ~3s
• Kent Fredric, Perl, ~1s
• Darius Bacon, Python, ~1s
• rvarcher, VB.NET, ~1s
• Paolo Bergantino, PHP (Live-Link) , ~5s (~2s lokal)

Answer 1

Ich habe dies in C# gelöst, indem ich einen DFA-Algorithmus verwendet habe. Du kannst meinen Code unter

https://github.com/attilabicsko/wordshuffler/

Neben dem Finden von Wörtern in einer Matrix speichert mein Algorithmus auch die tatsächlichen Pfade für die Wörter, so dass du für das Entwerfen eines Wortfinde-Spiels überprüfen kannst, ob es ein Wort auf einem tatsächlichen Pfad gibt.

Answer 2

Wie wäre es mit einfacher Sortierung und Verwendung der binären Suche im Wörterbuch?

Gibt die gesamte Liste in 0,35 Sekunden zurück und kann weiter optimiert werden (zum Beispiel durch Entfernen von Wörtern mit unbenutzten Buchstaben usw.).

from bisect import bisect_left

f = open("dict.txt")
D.extend([line.strip() for line in f.readlines()])
D = sorted(D)

def neibs(M,x,y):
    n = len(M)
    for i in xrange(-1,2):
        for j in xrange(-1,2):
            if (i == 0 and j == 0) or (x + i < 0 or x + i >= n or y + j < 0 or y + j >= n):
                continue
            yield (x + i, y + j)

def findWords(M,D,x,y,prefix):
    prefix = prefix + M[x][y]

    # Wort im Wörterbuch mit binärer Suche finden
    found = bisect_left(D,prefix)

    # falls gefunden, dann ausgeben
    if D[found] == prefix: 
        yield prefix

    # Falls das Gefundene nicht einmal ein Präfix ist, dann zurückgeben
    # (es macht keinen Sinn, weiter zu gehen)
    if len(D[found]) < len(prefix) or D[found][:len(prefix)] != prefix:
        return

    # Rückführung
    for neib in neibs(M,x,y):
        for word in findWords(M,D,neib[0], neib[1], prefix):
            yield word

def solve(M,D):
    # jeden Startpunkt überprüfen
    for x in xrange(0,len(M)):
        for y in xrange(0,len(M)):
            for word in findWords(M,D,x,y,""):
                yield word

grid = "fxie amlo ewbx astu".split()
print [x for x in solve(grid,D)]

Answer 3

    Paket ProblemSolving;

import java.util.HashSet;
import java.util.Set;

/**
 * Gegeben ist ein 2-dimensionales Array von Zeichen und ein
 * Wörterbuch, in dem ein Wort in O(1) Zeit gesucht werden kann.
 * Alle Wörter aus dem Array müssen gedruckt werden, die im
 * Wörterbuch vorhanden sind. Das Wort kann in jede Richtung gebildet werden,
 * aber muss an einer Kante des Arrays enden.
 * (Machen Sie sich nicht allzu viele Gedanken über das Wörterbuch)
 */
public class DictionaryWord {
    private static char[][] matrix = new char[][]{
            {'a', 'f', 'h', 'u', 'n'},
            {'e', 't', 'a', 'i', 'r'},
            {'a', 'e', 'g', 'g', 'o'},
            {'t', 'r', 'm', 'l', 'p'}
    };
    private static int dim_x = matrix.length;
    private static int dim_y = matrix[matrix.length -1].length;
    private static Set wordSet = new HashSet();

    public static void main(String[] args) {
        // Wörterbuch
        wordSet.add("nach");
        wordSet.add("hassen");
        wordSet.add("haar");
        wordSet.add("Luft");
        wordSet.add("essen");
        wordSet.add("tee");

        for (int x = 0; x < dim_x; x++) {
            for (int y = 0; y < dim_y; y++) {
                checkAndPrint(matrix[x][y] + "");
                int[][] visitedMap = new int[dim_x][dim_y];
                visitedMap[x][y] = 1;
                recursion(matrix[x][y] + "", visitedMap, x, y);
            }
        }
    }

    private static void checkAndPrint(String word) {
        if (wordSet.contains(word)) {
            System.out.println(word);
        }
    }

    private static void recursion(String word, int[][] visitedMap, int x, int y) {
        for (int i = Math.max(x - 1, 0); i < Math.min(x + 2, dim_x); i++) {
            for (int j = Math.max(y - 1, 0); j < Math.min(y + 2, dim_y); j++) {
                if (visitedMap[i][j] == 1) {
                    continue;
                } else {
                    int[][] newVisitedMap = new int[dim_x][dim_y];
                    for (int p = 0; p < dim_x; p++) {
                        for (int q = 0; q < dim_y; q++) {
                           newVisitedMap[p][q] = visitedMap[p][q];
                        }
                    }
                    newVisitedMap[i][j] = 1;
                    checkAndPrint(word + matrix[i][j]);
                    recursion(word + matrix[i][j], newVisitedMap, i, j);
                }
            }
        }
    }

}

Answer 4

import java.util.HashSet;
import java.util.Set;

/**
 * @author Sujeet Kumar (mrsujeet@gmail.com) Druckt alle Zeichenfolgen aus, die durch Bewegen nach links, rechts, oben, unten oder diagonal gebildet werden können und in einem gegebenen Wörterbuch existieren, ohne dass eine Zelle wiederholt wird. Nimmt an, dass Wörter aus Kleinbuchstaben bestehen. Druckt derzeit Wörter so oft aus, wie sie erscheinen, nicht nur einmal. *
 */

public class BoggleGame 
{
  /* Ein Beispiel für ein 4X4-Board/2D-Matrix */
  private static char[][] board = { { 's', 'a', 's', 'g' },
                                  { 'a', 'u', 't', 'h' }, 
                                  { 'r', 't', 'j', 'e' },
                                  { 'k', 'a', 'h', 'e' }
};

/* Ein Beispielswörterbuch, das eine eindeutige Sammlung von Wörtern enthält */
private static Set dictionary = new HashSet();

private static boolean[][] visited = new boolean[board.length][board[0].length];

public static void main(String[] arg) {
    dictionary.add("sujeet");
    dictionary.add("sarthak");
    findWords();

}

// zeige alle Wörter, beginnend an jeder möglichen Startposition
private static void findWords() {
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[i].length; j++) {
            StringBuffer buffer = new StringBuffer();
            dfs(i, j, buffer);
        }

    }

}

// führe die Tiefensuche vom Zell (i, j) aus durch
private static void dfs(int i, int j, StringBuffer buffer) {
    /*
     * Basisfall: Geben Sie im rekursiven Aufruf einfach zurück, wenn der Index die Größe der Matrixdimension überschreitet
     */
    if (i < 0 || j < 0 || i > board.length - 1 || j > board[i].length - 1) {
        return;
    }

    /*
     * Basisfall: Geben Sie im rekursiven Aufruf zurück, wenn die gegebene Zelle bereits in einem gegebenen Wortstring besucht wurde
     */
    if (visited[i][j] == true) { // eine Zelle darf nicht mehr als einmal besucht werden
        return;
    }

    // Zulassen, dass eine Zelle nicht erneut verwendet wird
    visited[i][j] = true;

    // Kombinieren des Zellenzeichens mit anderen besuchten Zellenzeichen, um ein Wort zu bilden, das möglicherweise im Wörterbuch existiert
    buffer.append(board[i][j]);

    // ein Wort im Wörterbuch gefunden. Drucken Sie es.
    if (dictionary.contains(buffer.toString())) {
        System.out.println(buffer);
    }

    /*
     * Betrachten Sie alle Nachbarn. Für eine gegebene Zelle werden alle benachbarten Zellen in horizontaler, vertikaler und diagonaler Richtung betrachtet
     */
    for (int k = i - 1; k <= i + 1; k++) {
        for (int l = j - 1; l <= j + 1; l++) {
            dfs(k, l, buffer);

        }

    }
    buffer.deleteCharAt(buffer.length() - 1);
    visited[i][j] = false;
  }
}

Answer 5

Dies ist die Lösung, die ich für das lösen des Boggle-Problems entwickelt habe. Ich denke, es ist der "pythonischste" Weg, um die Dinge zu tun:

from itertools import combinations
from itertools import izip
from math import fabs

def isAllowedStep(current, step, length, doubleLength):
            # Damit Schritt == Länge -1 nicht gleich 0 ist => triviale Lösungen sind nicht erlaubt
    return length > 1 and \
           current + step < doubleLength and current - step > 0 and \
           ( step == 1 or step == -1 or step <= length+1 or step >= length - 1)

def getPairwiseList(someList):
    iterableList = iter(someList)
    return izip(iterableList, iterableList)

def isCombinationAllowed(combination, length, doubleLength):

    for (first,second) in  getPairwiseList(combination):
        _, firstCoordinate = first
        _, secondCoordinate = second
        if not isAllowedStep(firstCoordinate, fabs(secondCoordinate-firstCoordinate), length, doubleLength):
            return False
    return True

def extractSolution(combinations):
    return ["".join([x[0] for x in combinationTuple]) for combinationTuple in combinations]

length = 4
text = tuple("".join("fxie amlo ewbx astu".split()))
textIndices = tuple(range(len(text)))
coordinates = zip(text,textIndices)

validCombinations = [combination for combination in combinations(coordinates, length) if isCombinationAllowed(combination, length, length*length)]
solution = extractSolution(validCombinations)

Diesen Teil rate ich Ihnen freundlich davon ab für alle möglichen Treffer zu verwenden, aber es würde tatsächlich die Möglichkeit bieten zu überprüfen, ob die von Ihnen generierten Wörter tatsächlich gültige Wörter darstellen:

import mechanize
def checkWord(word):
    url = "https://de.oxforddictionaries.com/search?filter=dictionary&query="+word
    br = mechanize.Browser()
    br.set_handle_robots(False)
    response = br.open(url)
    text = response.read()
    return "no exact matches"  not in text.lower()

print [valid for valid in solution[:10] if checkWord(valid)]