I am trying to solve the skill test at CodeFights and I have encountered a problem while I was trying to solve their word boggle algorithm. here is the description of the challenge :
Boggle is a popular word game in which players attempt to find words in sequences of adjacent letters on a rectangular board.
Given a two-dimensional array board that represents the character cells of the Boggle board and an array of unique strings words, find all the possible words from words that can be formed on the board.
Note that in Boggle when you're finding a word, you can move from a cell to any of its 8 neighbors, but you can't use the same cell twice in one word.
I wrote a code that looks like it works , however it doesn't pass the hidden test that they have , and now I am stuck at that point.
Here is my code :
string[] wordBoggle(char[][] board, string[] words)
{
string[] foundWords = new string[words.Length];
for (int i = 0; i < words.Length; i++)
{
List<int[]> Prefixs = new List<int[]>();
for (int j = 0; j < board.Length; j++)
{
for (int k = 0; k < board[j].Length; k++)
{
if (board[j][k] == words[i][0])
{
int[] match = new int[] { j, k };
Prefixs.Add(match);
}
}
}
if (Prefixs.Count > 0)
{
for (int l = 0; l < Prefixs.Count; l++)
{
bool[][] bitMap = new bool[board.Length][];
ResetBitMap(bitMap, board.Length, board[0].Length);
bitMap[Prefixs[l][0]][Prefixs[l][1]] = true;
bool match = search(Prefixs[l][0], Prefixs[l][1], board, words[i], bitMap, 1);
if (match)
{
foundWords[i] = words[i];
break;
}
}
}
}
var res = foundWords.Where(q => q != null).OrderBy(e => e).Distinct().ToArray();
return res;
}
bool search(int col, int row, char[][] board, string word, bool[][] bitMap, int index)
{
var found = false;
if (index == word.Length)
{
return true;
}
Dictionary<int[], char> neighbors = getNeightbors(col, row, board);
var allNextMatchs = neighbors.Where(a => a.Value == word[index]).ToArray();
if (allNextMatchs.Length < 1 && index < word.Length - 1)
{
return false;
}
var count = 0;
for (int i = 0; i < bitMap.Length; i++)
{
for (int k = 0; k < bitMap[i].Length; k++)
{
if (bitMap[i][k] == true)
{
count++;
}
}
}
if (count == word.Length)
{
return true;
}
foreach (var item in allNextMatchs)
{
if (item.Value != 0 && bitMap[item.Key[0]][item.Key[1]] == false)
{
col = item.Key[0];
row = item.Key[1];
bitMap[col][row] = true;
if (index < word.Length - 1)
{
index += 1;
}
found = search(col, row, board, word, bitMap, index);
if (found)
{
return true;
}
else
{
ResetBitMap(bitMap, board.Length, board[0].Length);
}
}
else
{
continue;
}
}
return found;
}
Dictionary<int[], char> getNeightbors(int col, int row, char[][] board)
{
Dictionary<int[], char> neighbors = new Dictionary<int[], char>(8);
try
{
int[] cr = new int[] { col - 1, row - 1 };
neighbors.Add(cr, board[col - 1][row - 1]); ; // left up
}
catch (IndexOutOfRangeException e) {
Console.WriteLine(e.Message);
}
try
{
int[] cr = new int[] { col, row - 1 };
neighbors.Add(cr, board[col][row - 1]);
}
catch (IndexOutOfRangeException e) { Console.WriteLine(e.Message); }
try
{
int[] cr = new int[] { col + 1, row - 1 };
neighbors.Add(cr, board[col + 1][row - 1]);
}
catch (IndexOutOfRangeException e) { Console.WriteLine(e.Message); }
try
{
int[] cr = new int[] { col - 1, row };
neighbors.Add(cr, board[col - 1][row]);
}
catch (IndexOutOfRangeException e) { Console.WriteLine(e.Message); }
try
{
int[] cr = new int[] { col + 1, row };
neighbors.Add(cr, board[col + 1][row]);
}
catch (IndexOutOfRangeException e) { Console.WriteLine(e.Message); }
try
{
int[] cr = new int[] { col + 1, row + 1 };
neighbors.Add(cr, board[col + 1][row + 1]);
}
catch (IndexOutOfRangeException e) { Console.WriteLine(e.Message); }
try
{
int[] cr = new int[] { col, row + 1 };
neighbors.Add(cr, board[col][row + 1]);
}
catch (IndexOutOfRangeException e) { Console.WriteLine(e.Message); }
try
{
int[] cr = new int[] { col - 1, row + 1 };
neighbors.Add(cr, board[col - 1][row + 1]);
}
catch (IndexOutOfRangeException e) { Console.WriteLine(e.Message); }
return neighbors;
}
void ResetBitMap(bool[][] map, int col, int row)
{
for (int i = 0; i < map.Length; ++i)
{
map[i] = new bool[row];
}
for (int j = 0; j < map.Length; ++j)
{
for (int k = 0; k < map[0].Length; ++k)
{
map[j][k] = false;
}
}
}
Does anyone have any idea what am I missing here ?
