Searching words in a matrix
-
Hi! I am doing a project about a game - a 5x5 grid with letter. The player must search words from the grid.
//I have removed some parts of the method
void SeekWords(string word, int[,] visited, int x, int y)
{
if (!(x < 0 || x > 4 || y < 0 || y > 4) && visited[x, y] == 0)
{
visited[x, y] = 1;
SeekWords(word + Grid[x, y], visited, x - 1, y - 1);
SeekWords(word + Grid[x, y], visited, x - 1, y);
SeekWords(word + Grid[x, y], visited, x - 1, y + 1);
SeekWords(word + Grid[x, y], visited, x, y - 1);
SeekWords(word + Grid[x, y], visited, x + 1, y - 1);
SeekWords(word + Grid[x, y], visited, x + 1, y);
SeekWords(word + Grid[x, y], visited, x + 1, y + 1);
visited[x, y] = 0;
}
}This method is good, but for words longer than 6 letters it's too slow. Are there other algorithms for searching the matrix which are faster? Thanks :)
Still learning...
-
Hi! I am doing a project about a game - a 5x5 grid with letter. The player must search words from the grid.
//I have removed some parts of the method
void SeekWords(string word, int[,] visited, int x, int y)
{
if (!(x < 0 || x > 4 || y < 0 || y > 4) && visited[x, y] == 0)
{
visited[x, y] = 1;
SeekWords(word + Grid[x, y], visited, x - 1, y - 1);
SeekWords(word + Grid[x, y], visited, x - 1, y);
SeekWords(word + Grid[x, y], visited, x - 1, y + 1);
SeekWords(word + Grid[x, y], visited, x, y - 1);
SeekWords(word + Grid[x, y], visited, x + 1, y - 1);
SeekWords(word + Grid[x, y], visited, x + 1, y);
SeekWords(word + Grid[x, y], visited, x + 1, y + 1);
visited[x, y] = 0;
}
}This method is good, but for words longer than 6 letters it's too slow. Are there other algorithms for searching the matrix which are faster? Thanks :)
Still learning...
I can understand this code is slow :P. But I don't really get what you want to achieve? Can you maybe clearify that? Is it like a snake? which will check for a word like this: {a, b, c} {d, e, f} {h, i, j} and if you try the word 'abf' it will find it and starts at point 0,0 and ends at 2,1. But if you try 'abj', it won't find anything? If it is, I think it is funny and I'll try to code it :D, if it isn't please explain how and what you mean exactly.
-
I can understand this code is slow :P. But I don't really get what you want to achieve? Can you maybe clearify that? Is it like a snake? which will check for a word like this: {a, b, c} {d, e, f} {h, i, j} and if you try the word 'abf' it will find it and starts at point 0,0 and ends at 2,1. But if you try 'abj', it won't find anything? If it is, I think it is funny and I'll try to code it :D, if it isn't please explain how and what you mean exactly.
Yes, it is like a snake. The word 'abj' form your example isn't valid according to the rules of the game. Each next letter must be a neighbor to the previous. For example: 'adi', 'hec'...the word 'ada' is not valid (a letter from a box of the matrix is used only once). I was thinking of a solution with combinations and a check if the letters are neighbors (this is only an idea, I haven't thought about it much) .
Still learning...
-
Hi! I am doing a project about a game - a 5x5 grid with letter. The player must search words from the grid.
//I have removed some parts of the method
void SeekWords(string word, int[,] visited, int x, int y)
{
if (!(x < 0 || x > 4 || y < 0 || y > 4) && visited[x, y] == 0)
{
visited[x, y] = 1;
SeekWords(word + Grid[x, y], visited, x - 1, y - 1);
SeekWords(word + Grid[x, y], visited, x - 1, y);
SeekWords(word + Grid[x, y], visited, x - 1, y + 1);
SeekWords(word + Grid[x, y], visited, x, y - 1);
SeekWords(word + Grid[x, y], visited, x + 1, y - 1);
SeekWords(word + Grid[x, y], visited, x + 1, y);
SeekWords(word + Grid[x, y], visited, x + 1, y + 1);
visited[x, y] = 0;
}
}This method is good, but for words longer than 6 letters it's too slow. Are there other algorithms for searching the matrix which are faster? Thanks :)
Still learning...
Hi, I have several remarks: 1. From every position you could move to 8 adjacent squars, however you only have 7 SeekWords calls; you skipped one, it will become even slower! 2. I don't see the word length anywhere in your code; the code as it is will search for all the longest words; i.e. on a 5*5 board it will find several 25-character words, and a lot of shorter ones because "the head of the snake" gets caught in a dead-end. On a 6*6 board, it will find several 36-character words, and a lot of shorter ones, including all the ones found for a 5*5 board. The complexity of the job is more than exponential in z, where z is the size of the board. Therefore, there is no decent general solution; it grows at an enormous pace. 3. However, there are ways to improve, not so much by changing the algorithm (you have to investigate all possibilities, there is no escape), but rather by changing the implementation. The biggest factor I can see is the matrix. I suggest you smash it into a linear array, i.e. let Grid[0]...Grid[z-1] represent the first row, Grid[z]...Grid[2*z-1] be the second row, etc. That means the current position (former x,y) becomes p, and a line such as
SeekWords(word + Grid[x, y], visited, x - 1, y - 1);becomesSeekWords(word + Grid[p], visited, p-z-1);which just is simpler, hence faster. 4. visited[] could hold booleans instead of ints with values 0 and 1; I don't expect that to influence performance. Also visited[] could be a class member, making it unnecessary to pass it as a method parameter; doing this probably would slow things down, since class members are "farther away" than method parameters. 5. if x equals 0 there is no need to try three SeekWords(x-1) since they will fail their initial test. similar for y==0, x==z-1 and y==z-1 you could perform one test inside SeekWords as inSeekWords(...) {
if (...) {
if (x>0) {
SeekWords(... x-1 y-1)
SeekWords(... x-1 y)
SeekWords(... x-1 y+1)
}
if (x<z-1)>etc.Of course, in a one-dimensional array it becomes slightly more complex. One easy and fast way is to make 8 extra boards, one for each direction, initialize them properly and then just do eight times something like
if (canStepInDirectionMM[p]) SeekWords( p-z-1)canStepInDirectionMM[] would contain true everywhere except for those starting positions that don't allow a step in the direction (use M for minus, Z for none, P for plus in b -
Hi, I have several remarks: 1. From every position you could move to 8 adjacent squars, however you only have 7 SeekWords calls; you skipped one, it will become even slower! 2. I don't see the word length anywhere in your code; the code as it is will search for all the longest words; i.e. on a 5*5 board it will find several 25-character words, and a lot of shorter ones because "the head of the snake" gets caught in a dead-end. On a 6*6 board, it will find several 36-character words, and a lot of shorter ones, including all the ones found for a 5*5 board. The complexity of the job is more than exponential in z, where z is the size of the board. Therefore, there is no decent general solution; it grows at an enormous pace. 3. However, there are ways to improve, not so much by changing the algorithm (you have to investigate all possibilities, there is no escape), but rather by changing the implementation. The biggest factor I can see is the matrix. I suggest you smash it into a linear array, i.e. let Grid[0]...Grid[z-1] represent the first row, Grid[z]...Grid[2*z-1] be the second row, etc. That means the current position (former x,y) becomes p, and a line such as
SeekWords(word + Grid[x, y], visited, x - 1, y - 1);becomesSeekWords(word + Grid[p], visited, p-z-1);which just is simpler, hence faster. 4. visited[] could hold booleans instead of ints with values 0 and 1; I don't expect that to influence performance. Also visited[] could be a class member, making it unnecessary to pass it as a method parameter; doing this probably would slow things down, since class members are "farther away" than method parameters. 5. if x equals 0 there is no need to try three SeekWords(x-1) since they will fail their initial test. similar for y==0, x==z-1 and y==z-1 you could perform one test inside SeekWords as inSeekWords(...) {
if (...) {
if (x>0) {
SeekWords(... x-1 y-1)
SeekWords(... x-1 y)
SeekWords(... x-1 y+1)
}
if (x<z-1)>etc.Of course, in a one-dimensional array it becomes slightly more complex. One easy and fast way is to make 8 extra boards, one for each direction, initialize them properly and then just do eight times something like
if (canStepInDirectionMM[p]) SeekWords( p-z-1)canStepInDirectionMM[] would contain true everywhere except for those starting positions that don't allow a step in the direction (use M for minus, Z for none, P for plus in bIn the code I have posted, some parts are missing, including the one with the word length. For word with maximum length 5 and minimum length 3 is very good. I will consider your suggestions. :) I have an idea. If the current word is 4 characters, the program will also search the first four characters of the dictionary words. If there isn't a match, the words which derive from the current also won't have a match. Current word: ac Dictionary: abcde abefg abegh In the example there is no word starting with 'ac', so the words derived from 'ac' won't be in the dictionary. This will save a lot of roaming in the grid.
Still learning...
-
Hi! I am doing a project about a game - a 5x5 grid with letter. The player must search words from the grid.
//I have removed some parts of the method
void SeekWords(string word, int[,] visited, int x, int y)
{
if (!(x < 0 || x > 4 || y < 0 || y > 4) && visited[x, y] == 0)
{
visited[x, y] = 1;
SeekWords(word + Grid[x, y], visited, x - 1, y - 1);
SeekWords(word + Grid[x, y], visited, x - 1, y);
SeekWords(word + Grid[x, y], visited, x - 1, y + 1);
SeekWords(word + Grid[x, y], visited, x, y - 1);
SeekWords(word + Grid[x, y], visited, x + 1, y - 1);
SeekWords(word + Grid[x, y], visited, x + 1, y);
SeekWords(word + Grid[x, y], visited, x + 1, y + 1);
visited[x, y] = 0;
}
}This method is good, but for words longer than 6 letters it's too slow. Are there other algorithms for searching the matrix which are faster? Thanks :)
Still learning...