boggleNet

1) using System;

2) using System.Collections.Generic;
3) using System.Text;
4) using System.Threading;
5) 
6) namespace Boggle
7) {
8)     public class BoggleSolver
9)     {
10)         BoggleList _WordList;
11)         WordComparer _wordEqualityComparer;
12)         BoggleBoard _Board;
13)         int _MinWordLength;
14)         HashSet<WordOnBoard> _wordsOnBoard;

15)         //WaitHandle.WaitAll can wait at most for 64 handles.
16)         int _MaxParallelSolvers;
17)         ManualResetEvent[] doneEvents;
18)         Queue<int> openSlots;
19)         int[] correspondingSlots;
20) 
21)         static int doneEventCount;

22) 
23)         /// <summary>
24)         /// Constructor.
25)         /// </summary>
26)         /// <param name="board">Board on which we need to run the solution,</param>
27)         /// <param name="words">List of valid words.</param>
28)         /// <param name="minWordLength">Length of smallest word in number of tiles.</param>
29)         public BoggleSolver(BoggleBoard board, BoggleList words, int minWordLength)
30)         {
31)             _Board = board;
32)             _WordList = words;
33)             _MinWordLength = minWordLength;
34)             _wordEqualityComparer = new WordComparer();
35)             _wordsOnBoard = new HashSet<WordOnBoard>(_wordEqualityComparer);

36)             _MaxParallelSolvers = _Board.Tiles.Length > 64 ? 64 : _Board.Tiles.Length;
37)             doneEvents = new ManualResetEvent[_MaxParallelSolvers];
38)             openSlots = new Queue<int>();
39)             correspondingSlots = new int[_Board.Tiles.Length];
40) 
41)             for (int i = 0; i < _MaxParallelSolvers; i++)
42)                 openSlots.Enqueue(i);

43)         }
44) 
45)         /// <summary>
46)         /// Get the set of words existing on the board.
47)         /// </summary>
48)         /// <returns>Set of words on the board. We are using a Hashset because it automatically takes care of duplicate words.</returns>
49)         public HashSet<WordOnBoard> GetWordsOnBoard(bool useThreads = false)
50)         {
51)             if (!useThreads)
52)                 return GetWordsOnBoardNoThreads();
53) 
54)             return GetWordsOnBoardThreaded();
55)         }
56) 

57)         

58) 
59)         /// <summary>
60)         /// Entry point for getting all possible words on board in threaded manner.
61)         /// </summary>

62)         /// <remarks>
63)         /// There can be two approaches: 
64)         /// 1. Start scanning from each tile on the board and add new tile if any of
65)         /// it is left over.
66)         /// 2. Divide the number of tiles on the board by max number of threads that the
67)         /// system can support and wait for each chunk to complete. This is less efficient 
68)         /// than the first approach because there can be chunks that exit earlier compared
69)         /// to most time consuming chunk.
70)         /// 
71)         /// Hence this function implements the first approach.
72)         /// </remarks>

73)         /// <returns>Hashset of all words that can appear on the board.</returns>
74)         private HashSet<WordOnBoard> GetWordsOnBoardThreaded()
75)         {

76)             int i = 0, j = 0;
77)             int tileIndex = 0;
78)             int nextSlot;
79)             while (tileIndex < _Board.Tiles.Length)

80)             {

81)                 while (openSlots.Count > 0 && tileIndex < _Board.Tiles.Length)

82)                 {

83)                     //Resume from the previous value
84)                     i = tileIndex / _Board.SideLength;
85)                     j = tileIndex % _Board.SideLength;
86)                     nextSlot = openSlots.Dequeue();
87)                     if (doneEvents[nextSlot] != null)
88)                         doneEvents[nextSlot].Reset();
89)                     else
90)                         doneEvents[nextSlot] = new ManualResetEvent(false);

91)                     ThreadPool.QueueUserWorkItem(CollectWordsFromPivotThreaded, _Board[i, j]);

92)                     correspondingSlots[tileIndex] = nextSlot;
93)                     tileIndex++;

94)                 }

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

99)             }

100) 

101)             WaitHandle.WaitAll(doneEvents);

102)             

103)             return _wordsOnBoard;
104)         }
105) 
106)         private void CollectWordsFromPivotThreaded(Object obj)
107)         {
108)             Tile passedTile = (Tile)obj;
109)             //Copy the board
110)             BoggleBoard boardForThisThread = new BoggleBoard(this._Board);
111)             //Initialize a list that will hold the tiles that will make up the word. Its max size will be square of side.

112)             List<Tile> newWordList = new List<Tile>(_Board.Tiles.Length);

113)             //Figure out the tile in the new board
114)             Tile t = boardForThisThread[passedTile.X, passedTile.Y];
115)             //Initialize this list with the tile that we will start finding words from.
116)             newWordList.Add(t);
117)             //Collect all the possible words from this tile. End result should be in the Hashset.
118)             CollectWordsFromPivot(boardForThisThread, _WordList.Wordlist[t.Alphabet].Next, newWordList);

119)             int tileNumberOnBoard = (t.X * _Board.SideLength + t.Y) ;
120)             doneEvents[correspondingSlots[tileNumberOnBoard]].Set();
121)             openSlots.Enqueue(tileNumberOnBoard % _MaxParallelSolvers);

122)         }
123) 
124)         private HashSet<WordOnBoard> GetWordsOnBoardNoThreads()
125)         {
126)             for (int i = 0; i < _Board.SideLength; i++)
127)             {
128)                 for (int j = 0; j < _Board.SideLength; j++)
129)                 {
130)                     //Collect all the tiles that make up the word.

131)                     List<Tile> newWordList = new List<Tile>(_Board.Tiles.Length);

132)                     //Initialize this list with the tile that we will start finding words from.
133)                     newWordList.Add(_Board[i, j]);
134)                     //Collect all the possible words from this tile. End result should be in the Hashset.
135)                     CollectWordsFromPivot(this._Board, _WordList.Wordlist[_Board[i, j].Alphabet].Next, newWordList);
136)                     //Set everything visited to false so that next traversal has the proper state.
137)                     ResetBoard();
138)                 }
139)             }
140) 
141)             return _wordsOnBoard;
142)         }
143) 
144)         /// <summary>
145)         /// Sets IsVisited of every tile in the board to false.
146)         /// </summary>
147)         private void ResetBoard()
148)         {
149)             for (int i = 0; i < _Board.SideLength; i++)
150)             {
151)                 for (int j = 0; j < _Board.SideLength; j++)
152)                 {
153)                     _Board[i, j].IsVisited = false;
154)                 }
155)             }
156) 
157)         }
158) 
159)         /// <summary>
160)         /// Extracts the word from tiles and stores it in a synchronized fashion.
161)         /// </summary>
162)         /// <param name="wordTiles">Tiles making up the word.</param>
163)         private void StoreWord(List<Tile> wordTiles)
164)         {
165)             StringBuilder builder = new StringBuilder(wordTiles[0].Alphabet);
166)             for (int i = 1; i < wordTiles.Count; i++)
167)             {
168)                 builder.Append(wordTiles[i].Alphabet);
169)             }
170) 
171)             string word = builder.ToString();
172)             int score = Constants.MIN_SCORE;
173)             if (word.Length <= _MinWordLength + 1)
174)                 score = Constants.MIN_SCORE;
175)             else if (word.Length == _MinWordLength + 2)
176)                 score = Constants.MIN_SCORE + 1;
177)             else if (word.Length == _MinWordLength + 3)
178)                 score = Constants.MIN_SCORE + 2;
179)             else if (word.Length == _MinWordLength + 4)
180)                 score = Constants.MIN_SCORE + 4;

181)             else