BoggleSolver.cs (645335e) - boggleNet

BoggleSolver.cs

using System;
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;

/// <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);
        }

/// <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();
        }

private ManualResetEvent[] doneEvents;

/// <summary>
        /// Entry point for getting all possible words on board in threaded manner.
        /// </summary>
        /// <returns>Hashset of all words that can appear on the board.</returns>
        private HashSet<WordOnBoard> GetWordsOnBoardThreaded()
        {
            doneEvents = new ManualResetEvent[_Board.SideLength * _Board.SideLength];
            for (int i = 0; i < _Board.SideLength; i++)
            {
                for (int j = 0; j < _Board.SideLength; j++)
                {
                    doneEvents[i * _Board.SideLength + j] = new ManualResetEvent(false);

ThreadPool.QueueUserWorkItem(CollectWordsFromPivotThreaded, _Board[i, j]);
                }
            }
            WaitHandle.WaitAll(doneEvents);
            return _wordsOnBoard;
        }

private void CollectWordsFromPivotThreaded(Object obj)
        {
            Tile passedTile = (Tile)obj;
            //Copy the board
            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>(boardForThisThread.SideLength * boardForThisThread.SideLength);
            //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);
            doneEvents[t.X * _Board.SideLength + t.Y].Set();
        }

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.SideLength * _Board.SideLength);
                    //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

Revert "Removing byte order mark in file using for f in `ls`; do awk '{if(NR==1)sub(/^\xef\xbb\xbf/,"");print}' $f > $f; done"