Word Solver - Tutte le direzioni

Question

Ho creato un risolutore di parole per tutte le direzioni. Trova parole orizzontalmente, verticalmente e inversa. Tuttavia, ho problemi a farlo andare tutte le direzioni. Quindi per prendere "ciao" in:

H  E  i  l
x  L  p  q
c  L  O  m

Qualcuno può indicarmi come farlo? Ecco il mio algoritmo a quella ricerca delle parole (in C ++):

/*
 * For loops that search each row, each column in all 8 possible directions.
 */
void Scramble::solve() {

cout << "Output:" << endl;

for (int row = 0; row < getRows(); row++) {
    for (int col = 0; col < getCols(); col++)
        for (int rowDir = -1; rowDir <= 1; rowDir++)
            for (int colDir = -1; colDir <=1; colDir++)
                if (rowDir != 0 || colDir != 0)
                    findWords(row, col, rowDir, colDir);
}
}

/*
 * Finds the matches in a given direction. Also calls verifyWord() to verify that the
 * current sequence of letters could possibly form a word. If not, search stops.
 */
void Scramble::findWords(int startingRow, int startingCol, int rowDir, int colDir) {

int searchResult;
string sequence = "";
sequence = sequence + wordsArr[startingRow][startingCol];

for (int i = startingRow + rowDir, j = startingCol + colDir; i >= 0 && j >= 0
&& i < getRows() && j < getCols(); i = i + rowDir, j = j + colDir) {

    sequence = sequence + wordsArr[i][j];

    if (sequence.length() >= 3) {

        searchResult = verifyWord(words, sequence);

        if ((unsigned int)searchResult == words.size())
            break;

        if (words[searchResult].rfind(sequence) > words[searchResult].length())
            break;

        if (words[searchResult] == (sequence))
            cout << sequence << endl;
    }
}
}

/*
 * Performs the verifyWord search method.
 * Searches the word to make sure that so far, there is possibly that the current sequence
 * of letter could form a word. That is to avoid continuing to search for a word
 * when the first sequence of characters do not construct a valid word in the dictionary.
 *
 * For example, if we have 'xzt', when this search is done it prevents the search
 * to continue since no word in the dictionary starts with 'xzt'
 */
int Scramble::verifyWord(vector<string> words, string str) {

int low = 0;
int mid = 0;
int high = words.size();

while (low < high) {

    mid = (low + high) / 2;

    if (str > words[mid]) {
        low = mid + 1;
    }

    else if (str < words[mid]) {
        high = mid - 1;
    }

    else
        return mid;
}
}

Answer 1

1) Attualmente, il tuo solve() La funzione cerca una parola in linea retta A partire da ogni punto: è questo quello che intendi? Chiedo solo perché "ciao" non appare come una linea retta nella tua matrice di esempio:

H  E  i  l
x  L  p  q
c  L  O  m

Se vuoi retta solo parole, allora va bene (è così che ho sempre capito Questi enigmi per lavorare comunque), ma se in realtà vuoi trovare parole in a Per quanto riguarda il serpente La moda, quindi una ricerca ricorsiva come Zilchonum e Blueraja, suggeriscono che sarebbe una buona scommessa. Fai solo attenzione a non finire per tornarti alle lettere che hai già usato.

2) In entrambi i casi, il tuo verifyWord() La funzione ha anche alcuni problemi: almeno deve restituire un valore nel caso in cui si esce while (low < high) ciclo continuo.

Anche così, non farà ancora quello che vuoi: per esempio, dì che il tuo dizionario contiene {"ant", "bat" "hello", "yak", "zoo"}, e tu chiami verifyWord() insieme a str="hel", vorresti restituire un valore di 2, ma al momento lo fa:

step  low   mid  high
 0     0     0     5   // initialise
 1     0     2     5   // set mid = (0+5)/2 = 2... words[2] == "hello" 
 2     0     2     1   // "hel" < "hello" so set high = mid - 1
 3     0     0     1   // set mid = (0+1)/2 = 0... words[0] == "ant"
 4     1     0     1   // "hel" > "ant" so set low = mid + 1     
 5  // now (low<high) is false, so we exit the loop with mid==0

Piuttosto che confrontare "Hel" con "Hello", forse starai meglio a troncando le parole nel dizionario alla stessa lunghezza di STR: IE Confronto str a word[mid].substr(0,str.length())?

Answer 2

Ecco un modo interessante di pensarci: trovare la parola è simile a risolvere un labirinto. Il "inizio" e "fine" corrispondono all'inizio e alla fine della parola che stai cercando, un "vicolo cieco" corrisponde a una mancata corrispondenza tra il percorso e la tua parola, e "successo" è quando la stringa lungo il tuo percorso è una partita.

La buona notizia qui è che ci sono molte risorse sugli algoritmi di risoluzione del labirinto. Un algoritmo particolare con cui ho familiarità e non è troppo difficile da implementare, è ricorsione con backtracking.

Ovviamente dovranno essere apportate alcune modifiche affinché questo funzioni per il tuo problema. Non sai dove sia l'inizio, per esempio, ma per fortuna non importa. Puoi controllare ogni possibile posizione di partenza e molti di essi saranno comunque scartati al primo passo a causa di una mancata corrispondenza.

Answer 3

Trattalo solo come un grafico in cui ogni lettera è collegata a tutte le lettere adiacenti e fai una ricerca profondità/ampiezza a partire da ogni lettera, accettando solo quei nodi la cui lettera è uguale alla lettera successiva che stai cercando.

Answer 4

Questo è un semplice programma di Word Sleuth che ho scritto --->

#include<iostream>

using namespace std;

int main()
{
    int a, b, i, j, l, t, n, f, g, k;
    cout<<"Enter the number of rows and columns: "<<endl;               
    cin>>a>>b;                                                              //Inputs the number of rows and columns
    char mat[100][100], s[100];
    cout<<"Enter the matrix: "<<endl;
    for (i = 0; i < a; i++) for (j = 0; j < b; j++) cin>>mat[i][j];         //Inputs the matrix
    cout<<"Enter the number of words: "<<endl;
    cin>>t;                                                                 //Inputs the number of words to be found
    while (t--)
    {
        cout<<"Enter the length of the word: "<<endl;
        cin>>n;                                                             //Inputs the length of the word
        cout<<"Enter the word: "<<endl;
        for (i = 0; i < n; i++) cin>>s[i];                                  //Inputs the word to be found
        for (i = 0; i < a; i++)                                         //Loop to transverse along i'th row
        {
            for (j = 0; j < b; j++)                                     //Loop to transverse along j'th column
            {
                f = i;
                g = j;
                for (k = 0; s[k] == mat[f][g] && k < n; k++, g++);          //Loop to find the word if it is horizontally right
                if (k == n)
                {
                    cout<<"The coordinates and direction are ---> "<<j+1<<","<<i+1<<" right"<<endl;
                    goto A;
                }
                f = i;
                g = j;
                for (k = 0; s[k] == mat[f][g] && k < n; k++, g--);      //Loop to find the word if it is horizontally left
                if (k == n)
                {
                    cout<<"The coordinates and direction are ---> "<<j+1<<","<<i+1<<" left"<<endl;
                    goto A;
                }
                f = i;
                g = j;
                for (k = 0; s[k] == mat[f][g] && k < n; k++, f++);      //Loop to find the word if it is vertically down
                if (k == n)
                {
                    cout<<"The coordinates and direction are ---> "<<j+1<<","<<i+1<<" down"<<endl;
                    goto A;
                }
                f = i;
                g = j;
                for (k = 0; s[k] == mat[f][g] && k < n; k++, f--);      //Loop to find the word if it is vertically up
                if (k == n)
                {
                    cout<<"The coordinates and direction are ---> "<<j+1<<","<<i+1<<" up"<<endl;
                    goto A;
                }
                f = i;
                g = j;
                for (k = 0; s[k] == mat[f][g] && k < n; k++, f++, g++); //Loop to find the word if it is down right
                if (k == n)
                {
                    cout<<"The coordinates and direction are ---> "<<j+1<<","<<i+1<<" down right"<<endl;
                    goto A;
                }
                f = i;
                g = j;
                for (k = 0; s[k] == mat[f][g] && k < n; k++, f--, g--); //Loop to find the word if it is up left
                if (k == n)
                {
                    cout<<"The coordinates and direction are ---> "<<j+1<<","<<i+1<<" up left"<<endl;
                    goto A;
                }
                f = i;
                g = j;
                for (k = 0; s[k] == mat[f][g] && k < n; k++, f++, g--); //Loop to find the word if it is down left
                if (k == n)
                {
                    cout<<"The coordinates and direction are ---> "<<j+1<<","<<i+1<<" down left"<<endl;
                    goto A;
                }
                f = i;
                g = j;
                for (k = 0; s[k] == mat[f][g] && k < n; k++, f--, g++); //Loop to find the word if it is up right
                if (k == n)
                {
                    cout<<"The coordinates and direction are ---> "<<j+1<<","<<i+1<<" up right"<<endl;
                    goto A;
                }
            }
        }
        A:;                                                             //If the word has been found the program should reach this point to start the search for the next word
    }
    return 0;
}

Nel mio programma, controlla prima la prima lettera della parola e poi le lettere successive. Se viene trovata la parola, stampa le coordinate iniziali della parola e la direzione in cui viene trovata la parola.