Overview
I've created an asynchronous and recursive method of generating word squares, of any size (known as the order of the square), from a known word list. If you're unfamiliar with word squares:
A word square is a special type of acrostic. It consists of a set of words written out in a square grid, such that the same words can be read both horizontally and vertically. The number of words, which is equal to the number of letters in each word, is known as the "order" of the square. For example, this is an order 5 square:
H E A R T E M B E R A B U S E R E S I N T R E N D
Dependencies
I'm presently using my hard coded copy of YAWL (Yet Another Word List), which is available on my GitHub. In the code that follows, this is what provides WordLists.AllWords and the using directive using BruteForceDictionary.
The Code
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Threading.Tasks;
using BruteForceDictionary;
namespace puzzlr {
class Program {
#region Fields
private static int _registeredSquares = 0;
private static Dictionary<int, List<List<string>>> _wordSquares = new Dictionary<int, List<List<string>>>();
#endregion
#region Entry
static void Main(string[] args) {
int[] orders = { 3, 5 };
foreach (int order in orders) {
_wordSquares.Add(order, new List<List<string>>());
BuildSquares(order);
}
Console.WriteLine("Done");
Console.ReadKey();
}
#endregion
#region Processing
private static async Task BuildSquares(int order) {
Task.Run(async () => {
var wordList = WordLists.AllWords.Where(w => w.Length == order);
foreach (var word in wordList) {
Task.Run(async () => {
var existingWords = new List<string> { word };
await TraverseSquare(order, wordList, existingWords);
});
}
});
}
private static async Task TraverseSquare(int order, IEnumerable<string> wordList, List<string> existingWords) {
string startsWith = string.Empty;
for (int i = 0; i < existingWords.Count; i++)
startsWith += existingWords.ToArray()[i][existingWords.Count];
if (existingWords.Count + 1 == order) {
string lastWord = wordList.FirstOrDefault(w => !existingWords.Any(a => a.Equals(w)) && w.StartsWith(startsWith));
if (!string.IsNullOrWhiteSpace(lastWord)) {
existingWords.Add(lastWord);
await RegisterSquare(order, existingWords);
}
} else {
foreach (var word in wordList.Where(w => !existingWords.Any(a => a.Equals(w)) && w.StartsWith(startsWith))) {
Task.Run(async () => {
var candidateList = new List<string>(existingWords);
candidateList.Add(word);
await TraverseSquare(order, wordList, candidateList);
});
}
}
}
#endregion
#region Reporting
private static async Task RegisterSquare(int order, List<string> words) {
string filename = $@"C:\Users\JamieDavis\Desktop\Squares\squares_{ order}x{ order}.txt";
string data = $"{string.Join(", ", words)}";
await WriteSquareAsync(filename, data);
if (_registeredSquares++ % 25 == 0)
Console.WriteLine(data);
}
private static async Task WriteSquareAsync(string filename, string square) {
using (var stream = new FileStream(filename, FileMode.Append, FileAccess.Write, FileShare.None, 4096, true))
using (var sw = new StreamWriter(stream))
await sw.WriteLineAsync(messaage);
}
#endregion
}
}
My Concern
For squares of order 5 and higher, this seems incredibly slow. I've had it running for 8 hours and it's still presenting 5 letter words starting with "ab" and my output file has added about 1MB since I went to bed 6 hours ago. My thought on how this would process is that it would start a new asynchronous process to work on all words possible for a given word set, recursively. So if I use the example square above, the processing would:
- Look at all possible 2nd words for "heart".
- Look at all possible 3rd words for "heart" and the specified second word.
- Look at all possible 4th words for "heart" and the specified second and third words.
- Get the first word that fits for "heart" and the specified second, third and fourth words.
Is this really what's going on though? I've been unable to prove it, and I'm still new to asynchronous processing, especially in the aspect of async/await.
How can I speed up the generation of squares with higher orders?
I understand that the search chain gets exponentially larger as the order of the square increases, but I believe this can still be improved from a performance aspect.
