Как найти список возможных слов из буквенной матрицы [Boggle Solver]

Question

В последнее время я играю в игру на своем iPhone под названием Scramble. Некоторые из вас могут знать эту игру как Boggle. По сути, когда игра начинается, вы получаете матрицу букв примерно так:

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

Цель игры - найти как можно больше слов, которые можно составить, объединяя буквы. Вы можете начать с любой буквы, и все буквы, которые ее окружают, являются честной игрой, а затем, как только вы перейдете к следующей букве, все буквы, которые окружают эту букву, являются честной игрой, , за исключением любых ранее использованных букв . Так, например, в приведенной выше таблице я мог бы найти слова LOB, TUX, SEA, FAME и т. Д. Слова должны содержать не менее 3 символов и не более NxN символов, что было бы 16 в этой игре, но может варьироваться в некоторых реализациях. Хотя эта игра веселая и затягивающая, я, видимо, не очень хорош в этом, и я хотел немного обмануть, создав программу, которая дала бы мне наилучшие возможные слова (чем длиннее слово, тем больше очков вы получите).

_{(источник: boggled.org )}

Я, к сожалению, не очень хорош с алгоритмами или их эффективностью и так далее. Моя первая попытка использует словарь , такой как этот (~ 2.3MB), и выполняет линейный поиск, пытаясь сопоставить комбинации со словарными статьями. Для поиска возможных слов требуется очень много времени, и, поскольку вы получаете только 2 минуты за раунд, этого просто недостаточно.

Мне интересно посмотреть, могут ли какие-либо Stackoverflowers предложить более эффективные решения. Я в основном ищу решения, использующие Big 3 Ps: Python, PHP и Perl, хотя что-нибудь с Java или C ++ тоже здорово, так как скорость важна.

ТЕКУЩИЕ РЕШЕНИЯ :

• Адам Розенфилд, Питон, ~ 20 с
• Джон Фухи, Python, ~ 3 с
• Кент Фредрик, Perl, ~ 1с
• Дариус Бэкон, Питон, ~ 1с
• rvarcher, VB.NET (прямая ссылка) , ~ 1 с
• Паоло Бергантино, PHP (прямая ссылка) , ~ 5 с (~ 2 с локально)

Answer 1

Как насчет простой сортировки и использования двоичного поиска в словаре?

Возвращает весь список за 0,35 с и может быть дополнительно оптимизирован (например, путем удаления слов с неиспользованными буквами и т. Д.).

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]

    # find word in dict by binary search
    found = bisect_left(D,prefix)

    # if found then yield
    if D[found] == prefix: 
        yield prefix

    # if what we found is not even a prefix then return
    # (there is no point in going further)
    if len(D[found]) < len(prefix) or D[found][:len(prefix)] != prefix:
        return

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

def solve(M,D):
    # check each starting point
    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 2

Я решил это в C #, используя алгоритм DFA. Вы можете проверить мой код на

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

В дополнение к поиску слов в матрице, мой алгоритм сохраняет фактические пути для слов, поэтому при разработке игры для поиска слов вы можете проверить, есть ли слово на реальном пути.

Answer 3

Я тоже решил это с помощью Java. Моя реализация имеет длину 269 строк и довольно проста в использовании. Сначала вам нужно создать новый экземпляр класса Boggler, а затем вызвать функцию решения с сеткой в ​​качестве параметра. Загрузка словаря из 50 000 слов на мой компьютер занимает около 100 мс, и он находит слова примерно за 10-20 мс. Найденные слова хранятся в ArrayList, foundWords.

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.net.URISyntaxException;
import java.net.URL;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

public class Boggler {
    private ArrayList<String> words = new ArrayList<String>();      
    private ArrayList<String> roundWords = new ArrayList<String>(); 
    private ArrayList<Word> foundWords = new ArrayList<Word>();     
    private char[][] letterGrid = new char[4][4];                   
    private String letters;                                         

    public Boggler() throws FileNotFoundException, IOException, URISyntaxException {
        long startTime = System.currentTimeMillis();

        URL path = GUI.class.getResource("words.txt");
        BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(new File(path.toURI()).getAbsolutePath()), "iso-8859-1"));
        String line;
        while((line = br.readLine()) != null) {
            if(line.length() < 3 || line.length() > 10) {
                continue;
            }

            this.words.add(line);
        }
    }

    public ArrayList<Word> getWords() {
        return this.foundWords;
    }

    public void solve(String letters) {
        this.letters = "";
        this.foundWords = new ArrayList<Word>();

        for(int i = 0; i < letters.length(); i++) {
            if(!this.letters.contains(letters.substring(i, i + 1))) {
                this.letters += letters.substring(i, i + 1);
            }
        }

        for(int i = 0; i < 4; i++) {
            for(int j = 0; j < 4; j++) {
                this.letterGrid[i][j] = letters.charAt(i * 4 + j);
            }
        }

        System.out.println(Arrays.deepToString(this.letterGrid));               

        this.roundWords = new ArrayList<String>();      
        String pattern = "[" + this.letters + "]+";     

        for(int i = 0; i < this.words.size(); i++) {

            if(this.words.get(i).matches(pattern)) {
                this.roundWords.add(this.words.get(i));
            }
        }

        for(int i = 0; i < this.roundWords.size(); i++) {
            Word word = checkForWord(this.roundWords.get(i));

            if(word != null) {
                System.out.println(word);
                this.foundWords.add(word);
            }
        }       
    }

    private Word checkForWord(String word) {
        char initial = word.charAt(0);
        ArrayList<LetterCoord> startPoints = new ArrayList<LetterCoord>();

        int x = 0;  
        int y = 0;
        for(char[] row: this.letterGrid) {
            x = 0;

            for(char letter: row) {
                if(initial == letter) {
                    startPoints.add(new LetterCoord(x, y));
                }

                x++;
            }

            y++;
        }

        ArrayList<LetterCoord> letterCoords = null;
        for(int initialTry = 0; initialTry < startPoints.size(); initialTry++) {
            letterCoords = new ArrayList<LetterCoord>();    

            x = startPoints.get(initialTry).getX(); 
            y = startPoints.get(initialTry).getY();

            LetterCoord initialCoord = new LetterCoord(x, y);
            letterCoords.add(initialCoord);

            letterLoop: for(int letterIndex = 1; letterIndex < word.length(); letterIndex++) {
                LetterCoord lastCoord = letterCoords.get(letterCoords.size() - 1);  
                char currentChar = word.charAt(letterIndex);                        

                ArrayList<LetterCoord> letterLocations = getNeighbours(currentChar, lastCoord.getX(), lastCoord.getY());

                if(letterLocations == null) {
                    return null;    
                }       

                for(int foundIndex = 0; foundIndex < letterLocations.size(); foundIndex++) {
                    if(letterIndex != word.length() - 1 && true == false) {
                        char nextChar = word.charAt(letterIndex + 1);
                        int lastX = letterCoords.get(letterCoords.size() - 1).getX();
                        int lastY = letterCoords.get(letterCoords.size() - 1).getY();

                        ArrayList<LetterCoord> possibleIndex = getNeighbours(nextChar, lastX, lastY);
                        if(possibleIndex != null) {
                            if(!letterCoords.contains(letterLocations.get(foundIndex))) {
                                letterCoords.add(letterLocations.get(foundIndex));
                            }
                            continue letterLoop;
                        } else {
                            return null;
                        }
                    } else {
                        if(!letterCoords.contains(letterLocations.get(foundIndex))) {
                            letterCoords.add(letterLocations.get(foundIndex));

                            continue letterLoop;
                        }
                    }
                }
            }

            if(letterCoords != null) {
                if(letterCoords.size() == word.length()) {
                    Word w = new Word(word);
                    w.addList(letterCoords);
                    return w;
                } else {
                    return null;
                }
            }
        }

        if(letterCoords != null) {
            Word foundWord = new Word(word);
            foundWord.addList(letterCoords);

            return foundWord;
        }

        return null;
    }

    public ArrayList<LetterCoord> getNeighbours(char letterToSearch, int x, int y) {
        ArrayList<LetterCoord> neighbours = new ArrayList<LetterCoord>();

        for(int _y = y - 1; _y <= y + 1; _y++) {
            for(int _x = x - 1; _x <= x + 1; _x++) {
                if(_x < 0 || _y < 0 || (_x == x && _y == y) || _y > 3 || _x > 3) {
                    continue;
                }

                if(this.letterGrid[_y][_x] == letterToSearch && !neighbours.contains(new LetterCoord(_x, _y))) {
                    neighbours.add(new LetterCoord(_x, _y));
                }
            }
        }

        if(neighbours.isEmpty()) {
            return null;
        } else {
            return neighbours;
        }
    }
}

class Word {
    private String word;    
    private ArrayList<LetterCoord> letterCoords = new ArrayList<LetterCoord>();

    public Word(String word) {
        this.word = word;
    }

    public boolean addCoords(int x, int y) {
        LetterCoord lc = new LetterCoord(x, y);

        if(!this.letterCoords.contains(lc)) {
            this.letterCoords.add(lc);

            return true;
        }

        return false;
    }

    public void addList(ArrayList<LetterCoord> letterCoords) {
        this.letterCoords = letterCoords;
    } 

    @Override
    public String toString() {
        String outputString = this.word + " ";
        for(int i = 0; i < letterCoords.size(); i++) {
            outputString += "(" + letterCoords.get(i).getX() + ", " + letterCoords.get(i).getY() + ") ";
        }

        return outputString;
    }

    public String getWord() {
        return this.word;
    }

    public ArrayList<LetterCoord> getList() {
        return this.letterCoords;
    }
}

class LetterCoord extends ArrayList {
    private int x;          
    private int y;          

    public LetterCoord(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int getX() {
        return this.x;
    }

    public int getY() {
        return this.y;
    }

    @Override
    public boolean equals(Object o) {
        if(!(o instanceof LetterCoord)) {
            return false;
        }

        LetterCoord lc = (LetterCoord) o;

        if(this.x == lc.getX() &&
                this.y == lc.getY()) {
            return true;
        }

        return false;
    }

    @Override
    public int hashCode() {
        int hash = 7;
        hash = 29 * hash + this.x;
        hash = 24 * hash + this.y;
        return hash;
    }
}

Answer 4

Я решил это отлично и очень быстро. Я положил его в приложение для Android. Посмотрите видео по ссылке в магазине воспроизведения, чтобы увидеть его в действии.

Word Cheats - приложение, которое «взламывает» любую игру в стиле матрицы. Это приложение было построено чтобы помочь мне обмануть слова скремблер. Может использоваться для поиска слов, словечко, слова, поиск слов, словечко, смущение и многое другое!

Это можно увидеть здесь https://play.google.com/store/apps/details?id=com.harris.wordcracker

Просмотр приложения в действии на видео https://www.youtube.com/watch?v=DL2974WmNAI

Answer 5

Я решил это в с. Для запуска на моей машине требуется около 48 мс (примерно 98% времени уходит на загрузку словаря с диска и создание файла). Словарь / usr / share / dict / american-english, в котором 62886 слов.

Исходный код