BoggleSolver.cs (56106ca) - boggleNet

BoggleSolver.cs

#define CONCURRENT

using System;
#if CONCURRENT
using System.Collections.Concurrent;
#endif
using System.Collections.Generic;
using System.Text;
using System.Threading;

namespace Boggle
{
    public class BoggleSolver
    {
        BoggleList _WordList;
        WordComparer _wordEqualityComparer;
        BoggleBoard _Board;
        int _MinWordLength;
        HashSet<WordOnBoard> _wordsOnBoard;
        //WaitHandle.WaitAll can wait at most for 64 handles.
        int _MaxParallelSolvers;
        ManualResetEvent[] doneEvents;
#if CONCURRENT
        ConcurrentQueue<int> openSlots;
#else
        Queue<int> openSlots;
#endif
        int[] correspondingSlots;

/// <summary>
        /// Constructor.
        /// </summary>
        /// <param name="board">Board on which we need to run the solution,</param>
        /// <param name="words">List of valid words.</param>
        /// <param name="minWordLength">Length of smallest word in number of tiles.</param>
        public BoggleSolver(BoggleBoard board, BoggleList words, int minWordLength)
        {
            _Board = board;
            _WordList = words;
            _MinWordLength = minWordLength;
            _wordEqualityComparer = new WordComparer();
            _wordsOnBoard = new HashSet<WordOnBoard>(_wordEqualityComparer);
            _MaxParallelSolvers = _Board.Tiles.Length > 64 ? 64 : _Board.Tiles.Length;
            doneEvents = new ManualResetEvent[_MaxParallelSolvers];
#if CONCURRENT
            openSlots = new ConcurrentQueue<int>();
#else
            openSlots = new Queue<int>();
#endif
            correspondingSlots = new int[_Board.Tiles.Length];

for (int i = 0; i < _MaxParallelSolvers; i++)
                openSlots.Enqueue(i);
        }

/// <summary>
        /// Get the set of words existing on the board.
        /// </summary>
        /// <returns>Set of words on the board. We are using a Hashset because it automatically takes care of duplicate words.</returns>
        public HashSet<WordOnBoard> GetWordsOnBoard(bool useThreads = false)
        {
            if (!useThreads)
                return GetWordsOnBoardNoThreads();

return GetWordsOnBoardThreaded();
        }

/// <summary>
        /// Entry point for getting all possible words on board in threaded manner.
        /// </summary>
        /// <remarks>
        /// There can be two approaches: 
        /// 1. Start scanning from each tile on the board and add new tile if any of
        /// it is left over.
        /// 2. Divide the number of tiles on the board by max number of threads that the
        /// system can support and wait for each chunk to complete. This is less efficient 
        /// than the first approach because there can be chunks that exit earlier compared
        /// to most time consuming chunk.
        /// 
        /// Hence this function implements the first approach.
        /// </remarks>
        /// <returns>Hashset of all words that can appear on the board.</returns>
        private HashSet<WordOnBoard> GetWordsOnBoardThreaded()
        {
            int i = 0, j = 0;
            int tileIndex = 0;
            int nextSlot;
            while (tileIndex < _Board.Tiles.Length)
            {
#if CONCURRENT
                while (openSlots.TryDequeue(out nextSlot) && tileIndex < _Board.Tiles.Length)
#else
                while (openSlots.Count > 0 && tileIndex < _Board.Tiles.Length)
#endif
                {
                    //Resume from the previous value
                    i = tileIndex / _Board.SideLength;
                    j = tileIndex % _Board.SideLength;
#if !CONCURRENT
                    nextSlot = openSlots.Dequeue();
#endif
                    if (doneEvents[nextSlot] != null)
                        doneEvents[nextSlot].Reset();
                    else
                        doneEvents[nextSlot] = new ManualResetEvent(false);
                    ThreadPool.QueueUserWorkItem(CollectWordsFromPivotThreaded, _Board[i, j]);
                    correspondingSlots[tileIndex] = nextSlot;
                    tileIndex++;
                }

//If all the slots have filled up, then wait for atleast one to get free before
                //queueing another thread.
                WaitHandle.WaitAny(doneEvents);
            }

WaitHandle.WaitAll(doneEvents);
            
            return _wordsOnBoard;
        }

private void CollectWordsFromPivotThreaded(Object obj)
        {
            Tile passedTile = (Tile)obj;
            //Copy the board. TODO: SHIT LOADS OF CONTENTION HERE BECAUSE BOGGLEBOARD IS NOT THREAD-FRIENDLY YET.
            BoggleBoard boardForThisThread = new BoggleBoard(this._Board);
            //Initialize a list that will hold the tiles that will make up the word. Its max size will be square of side.
            List<Tile> newWordList = new List<Tile>(_Board.Tiles.Length);
            //Figure out the tile in the new board
            Tile t = boardForThisThread[passedTile.X, passedTile.Y];
            //Initialize this list with the tile that we will start finding words from.
            newWordList.Add(t);
            //Collect all the possible words from this tile. End result should be in the Hashset.
            CollectWordsFromPivot(boardForThisThread, _WordList.Wordlist[t.Alphabet].Next, newWordList);
            int tileNumberOnBoard = (t.X * _Board.SideLength + t.Y) ;
            doneEvents[correspondingSlots[tileNumberOnBoard]].Set();
            openSlots.Enqueue(tileNumberOnBoard % _MaxParallelSolvers);
        }

private HashSet<WordOnBoard> GetWordsOnBoardNoThreads()
        {
            for (int i = 0; i < _Board.SideLength; i++)
            {
                for (int j = 0; j < _Board.SideLength; j++)
                {
                    //Collect all the tiles that make up the word.
                    List<Tile> newWordList = new List<Tile>(_Board.Tiles.Length);
                    //Initialize this list with the tile that we will start finding words from.
                    newWordList.Add(_Board[i, j]);
                    //Collect all the possible words from this tile. End result should be in the Hashset.
                    CollectWordsFromPivot(this._Board, _WordList.Wordlist[_Board[i, j].Alphabet].Next, newWordList);
                    //Set everything visited to false so that next traversal has the proper state.
                    ResetBoard();
                }
            }

return _wordsOnBoard;
        }

/// <summary>
        /// Sets IsVisited of every tile in the board to false.
        /// </summary>
        private void ResetBoard()
        {
            for (int i = 0; i < _Board.SideLength; i++)
            {
                for (int j = 0; j < _Board.SideLength; j++)
                {
                    _Board[i, j].IsVisited = false;
                }
            }

}

/// <summary>
        /// Extracts the word from tiles and stores it in a synchronized fashion.
        /// </summary>
        /// <param name="wordTiles">Tiles making up the word.</param>
        private void StoreWord(List<Tile> wordTiles)
        {
            StringBuilder builder = new StringBuilder(wordTiles[0].Alphabet);
            for (int i = 1; i < wordTiles.Count; i++)
            {
                builder.Append(wordTiles[i].Alphabet);
            }

string word = builder.ToString();
            int score = Constants.MIN_SCORE;
            if (word.Length <= _MinWordLength + 1)
                score = Constants.MIN_SCORE;
            else if (word.Length == _MinWordLength + 2)
                score = Constants.MIN_SCORE + 1;
            else if (word.Length == _MinWordLength + 3)
                score = Constants.MIN_SCORE + 2;
            else if (word.Length == _MinWordLength + 4)
                score = Constants.MIN_SCORE + 4;
            else
                score = Constants.MIN_SCORE + 10;
            lock (_wordsOnBoard)
            {
                _wordsOnBoard.Add(new WordOnBoard(word, score));
            }
        }

/// <summary>
        /// Recursive function to get all the possible words from a tile.
        /// </summary>
        /// <param name="t">Tile that needs to be analyzed for words.</param>
        /// <param name="validNextSubstrings">A dictionary containing all letters that can come after the one contained in the tile.</param>
        /// <param name="currentSubstring">List of tiles that make up all or part of the word.</param>
        private void CollectWordsFromPivot(BoggleBoard board, Dictionary<string, ListWord> validNextSubstrings, List<Tile> currentSubstring)
        {
            Tile t = currentSubstring[currentSubstring.Count - 1];
            t.IsVisited = true;

string validWord = string.Empty;

int adjPosX = -1, adjPosY = -1;
            for (int x = -1; x <= 1; x++)
            {
                adjPosX = t.X + x;
                if (adjPosX < 0 || adjPosX >= board.SideLength) //we don't want to hit anything outside the boundries of the board.
                    continue;

for (int y = -1; y <= 1; y++)
                {
                    adjPosY = t.Y + y;
                    if (adjPosY < 0 || adjPosY >= board.SideLength || (adjPosX == t.X && adjPosY == t.Y))    //in third condition, it will  point to itself and we dont want that
                        continue;

Tile adjacentTile = board[adjPosX, adjPosY];
                    //no need to parse the tile if it has been already visited or there is no word possible with current string
                    if (adjacentTile.IsVisited || !validNextSubstrings.ContainsKey(adjacentTile.Alphabet))
                        continue;

//either we now have a word or have a part of the word
                    currentSubstring.Add(adjacentTile);

//if we have the complete word that has minimum word length we require, add it to the hashet of words
                    if (validNextSubstrings[adjacentTile.Alphabet].IsWord && currentSubstring.Count >= _MinWordLength)
                        StoreWord(currentSubstring);

//now we want to see if there is any good reason to proceed with passing control to the adjacent tile.
                    Dictionary<string, ListWord> validNextSubstringsAdjTile = validNextSubstrings[adjacentTile.Alphabet].Next;

//there will no more words to make after this... no need to recurse.
                    if (validNextSubstringsAdjTile == null)
                    {
                        //remove the alphabet just added from the end of the string as it will not be hitting the appropriate statement later.
                        currentSubstring.RemoveAt(currentSubstring.Count - 1);
                        continue;
                    }

//collect words from the new pivot
                    CollectWordsFromPivot(board, validNextSubstringsAdjTile, currentSubstring);

//once used, remove the alphabet from the string and mark the tile as not visited. This is because this tile maybe involved in paths from other tiles.
                    currentSubstring.RemoveAt(currentSubstring.Count - 1);
                    adjacentTile.IsVisited = false;
                }
            }
        }
    }
}

boggleNet

Added pre-processor directive to control verbosity of output and another pre-processor to control use of ConcurrentQueue instead of normal Queues. No differences observed, but I was able to find the point of thread contention is copy constructor of BoggleBoard :)