An algorithm contest has recently been posted in the Osaka/Kyoto Web Designers and Developpers Meetup community by Sacha Greif. The goal of the contest was to calculate possible grids for a word game idea Sacha had. The details are available here (I assumed you've read it in what follows). In this article I introduce the solution I've designed and implemented in C.

Dictionaries

The pool of words is provided as 3 dictionaries of 2k, 5k and 10k most common english words. They are simple text file formatted as follow:

[ "the", "of", "in", ... "reveal", "bone", "sustained" ]

Reading and parsing these files is cumbersome. Instead, by changing just the first and last line we can bake them into the code with a simple #include ...:

char const* const words[10000] = { "the", "of", "in", ... "reveal", "bone", "sustained" };

Tokens

The first step is to calculate the tokens from the dictionary. A first filtering is applied to ignore "plural form" words and words whose length is incompatible with prefix's and suffix's length requirement.

#define MIN_LEN_PREFIX 1 #define MAX_LEN_PREFIX 3 #define MIN_LEN_SUFFIX 2 #define MAX_LEN_SUFFIX 6 #define MIN_LEN_WORD (MIN_LEN_PREFIX + MIN_LEN_SUFFIX) #define MAX_LEN_WORD (MAX_LEN_PREFIX + MAX_LEN_SUFFIX) int const prefixSizes[2] = {MIN_LEN_PREFIX, MAX_LEN_PREFIX}; int const suffixSizes[2] = {MIN_LEN_SUFFIX, MAX_LEN_SUFFIX}; typedef struct { char const* str; int len; } Word; bool IsValidWord(Word const* const word) { return word->len >= MIN_LEN_WORD && word->len <= MAX_LEN_WORD && (word->str[word->len - 2] == 's' || word->str[word->len - 1] != 's'); } int main() { int nbPair = 0; loop(iWord, nbWords) { Word const word = { .str = words[iWord], .len = strlen(words[iWord]) }; if(IsValidWord(&word)) nbPair += CreatePairs(&word); } ... }

Tokens from valid words are obtained by calculating the range of possible cutting positions inside the word, looping on that range and creating the prefix/suffix token with the part before/after the cut.

typedef struct Pair Pair; struct Pair { char token[2][MAX_LEN_WORD]; ... }; int CreatePairs(Word const* const word) { int const iMinCut = MAX(prefixSizes[0], word->len - suffixSizes[1]); int const iMaxCut = MIN(prefixSizes[1], word->len - suffixSizes[0]); for (int iCut = iMinCut; iCut <= iMaxCut; ++iCut) { Pair pair = {0}; loop(iPref, iCut) pair.token[0][iPref] = word->str[iPref]; loop(iSuf, word->len - iCut) pair.token[1][iSuf] = word->str[iCut + iSuf]; ... } int const nbPair = iMaxCut - iMinCut + 1; return nbPair; }

To store the tokens I use two hash tables: one hashing on the prefix, and the other hashing on the suffix. I also keep a reference of a token in one table to its sibling in the other table. The search algorithm will explain why. Pair and CreatePairs are completed as follow:

struct Pair { ... Pair* sibling; ... }; typedef struct { int iKey; ... } Hash; Hash hashes[2] = {[1] = {.iKey = 1}}; int CreatePairs(Word const* const word) { ... Pair* newEntries[2]; loop(i, 2) newEntries[i] = HashAddPair(hashes + i, &pair); loop(i, 2) newEntries[i]->sibling = newEntries[1 - i]; ... }

Hashing

For hashing, I use the FNV1a function. No particular reason why, I just came accross it recently and that's the one I had in mind at that time.

uint64_t FNV1a(char const* const key) { uint64_t hash = 0xcbf29ce484222325UL; char const* ptr = key; while(*ptr) { hash ^= (uint64_t)(*ptr); hash *= 0x100000001b3UL; ++ptr; } return hash; }

The hash table's size is calculated as a multiple of the number of threads (cause of course the search will be multithreaded). There is absolutely no need to do it that way except that it simplifies my life when creating the threads. The actual numbers are choosen as what feels good to me.

While adding entries to the hash table I also take care of keeping them sorted (on the key, within a same hash index). Again, the search algorithm will explain why.

#define NB_THREAD 10 #define HASH_PER_THREAD 100 #define HASH_SIZE (NB_THREAD * HASH_PER_THREAD) struct Pair { ... Pair* next; ... }; typedef struct { ... Pair* pairs[HASH_SIZE]; } Hash; Pair* HashAddPair(Hash* const hash, Pair const* const pair) { Pair* const newEntry = malloc(sizeof(Pair)); *newEntry = *pair; char* const newKey = newEntry->token[hash->iKey]; size_t const iHash = FNV1a(newKey) % HASH_SIZE; Pair* entry = hash->pairs[iHash]; if(entry == NULL) hash->pairs[iHash] = newEntry; else if(strcmp(entry->token[hash->iKey], newKey) >= 0) { newEntry->next = hash->pairs[iHash]; hash->pairs[iHash] = newEntry; } else { Pair* prevEntry = hash->pairs[iHash]; entry = hash->pairs[iHash]->next; while(entry && strcmp(entry->token[hash->iKey], newKey) < 0) { prevEntry = entry; entry = entry->next; } prevEntry->next = newEntry; newEntry->next = entry; } return newEntry; } Pair* HashGetPair(Hash const* const hash, char const* const key) { size_t const iHash = FNV1a(key) % HASH_SIZE; Pair* entry = hash->pairs[iHash]; while(entry && strcmp(entry->token[hash->iKey], key) != 0) entry = entry->next; return entry; }

Iteration on hash tables

I'll need to iterate on entries in the hashes and I'll do it in three ways which I'll call HashIterNext, HashIterSubNext, HashIterStep. The first one loops on all entries. The second one loops on the entries of the current key only. The third one loops on all entries but jump over entries with the same key. The second and third ways of iterating take advantage of the fact I have sorted entries when creating the tokens. The search algorithm will explain why I need these three ways of iterating.

typedef struct HashIter { int idxHash; Pair* entry; Hash* hash; } HashIter; Pair* HashIterReset(HashIter* const iter) { iter->entry = NULL; iter->idxHash = 0; while(iter->idxHash < HASH_SIZE && iter->hash->pairs[iter->idxHash] == NULL) ++(iter->idxHash); if(iter->idxHash < HASH_SIZE) iter->entry = iter->hash->pairs[iter->idxHash]; return iter->entry; } void HashIterNext(HashIter* const iter) { if(iter->entry != NULL) { if(iter->entry->next) iter->entry = iter->entry->next; else { do { ++(iter->idxHash); } while( iter->idxHash < HASH_SIZE && iter->hash->pairs[iter->idxHash] == NULL); if(iter->idxHash < HASH_SIZE) iter->entry = iter->hash->pairs[iter->idxHash]; else iter->entry = NULL; } } } Pair* HashIterResetTo(HashIter* const iter, char const* const key) { iter->idxHash = FNV1a(key) % HASH_SIZE; iter->entry = HashGetPair(iter->hash, key); return iter->entry; } void HashIterSubNext(HashIter* const iter) { if(iter->entry != NULL) { if(iter->entry->next) { char const* const fromStr = iter->entry->token[iter->hash->iKey]; iter->entry = iter->entry->next; if(strcmp(fromStr, iter->entry->token[iter->hash->iKey]) != 0) iter->entry = NULL; } else iter->entry = NULL; } } void HashIterStep(HashIter* const iter) { if(iter->entry != NULL) { if(iter->entry->next != NULL) { char const* const fromStr = iter->entry->token[iter->hash->iKey]; do { iter->entry = iter->entry->next; } while( iter->entry != NULL && strcmp(fromStr, iter->entry->token[iter->hash->iKey]) == 0); } else iter->entry = NULL; if(iter->entry == NULL) { ++(iter->idxHash); while(iter->idxHash < HASH_SIZE && iter->hash->pairs[iter->idxHash] == NULL) ++(iter->idxHash); if(iter->idxHash < HASH_SIZE) iter->entry = iter->hash->pairs[iter->idxHash]; else iter->entry = NULL; } } }

Token pruning

We know from the game specification that only prefix tokens appearing at least in two pairs will be used, and at least six pairs for suffix tokens. So, we can prune all the tokens from the dictionary which appear in less than these number of pairs. Actually we could also prune on larger number of pairs. The less the number of pairs a token appears into, the more "difficult" it will be to used, in other words the less probable it will appear in a solution. As pruning more tokens will speed up the search (less combination to check), that could be a way to optimize (in speed): sacrifice the tokens which will probably not lead to solution to save time. In the end I haven't pruned more than the obvious thresholds (2, 6) as my solution was fast enough.

Here I've been lazy. Instead of actually removing the tokens from the hash table, I just flagged them as "pruned" and ignored them during the search. Removing them should speed up a little more the search.

struct Pair { ... bool pruned; ... }; int PrunePairs(Hash* const hash, int const pruneThreshold) { HashIter iter = {.hash = hash}; HashIterReset(&iter); int nbPrune = 0; while(iter.entry) { int nb = 0; HashIter subIter = iter; while(subIter.entry) { ++nb; HashIterSubNext(&subIter); } if(nb < pruneThreshold) { nbPrune += nb; subIter = iter; while(subIter.entry) { subIter.entry->pruned = true; HashIterSubNext(&subIter); } } HashIterStep(&iter); } return nbPrune; } int main() { ... int nbPrune[2]; int pruneThreshold[2] = {2, 6}; loop(i, 2) nbPrune[i] = PrunePairs(hashes + i, pruneThreshold[i]); ... }

Search for the solutions

Now I need a representation of the edge graph of the board and node types (prefix/suffix), which implies I also need to assign an index for each nodes.

#define NB_GRAPH_NODE 13 int graphEdge[NB_GRAPH_NODE][NB_GRAPH_NODE] = { [ 0]={[ 1]=1, [ 2]=1, [ 3]=1, [ 4]=1}, [ 1]={[ 0]=1, [ 5]=1, [ 6]=1, [ 8]=1, [ 9]=1, [10]=1}, [ 2]={[ 0]=1, [ 5]=1, [ 6]=1, [ 7]=1, [10]=1, [11]=1}, [ 3]={[ 0]=1, [ 6]=1, [ 7]=1, [ 8]=1, [11]=1, [12]=1}, [ 4]={[ 0]=1, [ 5]=1, [ 7]=1, [ 8]=1, [ 9]=1, [12]=1}, [ 5]={[ 1]=1, [ 2]=1, [ 4]=1}, [ 6]={[ 1]=1, [ 2]=1, [ 3]=1}, [ 7]={[ 2]=1, [ 3]=1, [ 4]=1}, [ 8]={[ 1]=1, [ 3]=1, [ 4]=1}, [ 9]={[ 1]=1, [ 4]=1}, [10]={[ 1]=1, [ 2]=1}, [11]={[ 2]=1, [ 3]=1}, [12]={[ 3]=1, [ 4]=1}, }; int graphNode[NB_GRAPH_NODE] = {0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0};

The choice of indices is also made such as it will simplify things later.

I'm now ready to search for the solutions. The brute force method would be to loop over all token combinations and check if it's a valid one. That's \(\Pi_{i=0}^8(n-i)*\Pi_{i=0}^3(m-i)\) combinations, where \(n\) is the number of prefix tokens and \(m\) is the number of suffix tokens. Obviously way too much.

We can do much better: when a node is set, the possible values for all its neighbour nodes reduce to the existing pairs containing that node's token. So, except for a first initial node which needs to be checked for all possible tokens, we can loop on only very small subsets for its neighbours, and by propagation fill in the whole board very quickly (or give up if we find a node with no solution). Hence the choice to use two hash tables: one can access quickly any given token, and switch easily between looping over its paired prefix or suffix.

For the initial node, we want one that filter out as much as possible neighbours, i.e. one with many edges. That would be one of the suffix nodes. However, given the graph of the board, choosing the center node instead makes the implementation much easier, thus I choose that one as initial node.

The propagation occurs then from the central node outward, hence the choice in nodes' indice. To make things easier to understand I split the nodes into "levels": the center node is "level 0", the surrounding suffix nodes are " level 1", and the remaining prefix nodes are "level 2".

In pseudo code the search algorithm becomes as follow:

Search(): board = empty board results = empty list for token in all possible prefix tokens: set token as node 0 in board solutions = SolveLvl1(board, 1) append solutions to results return results SolveLvl1(board, iNode): results = empty list for token in suffixes paired with node 0 of board if that pair is not already used set token as the iNode-th node in board if iNode is less than 4 solutions = SolveLvl1(board, iNode + 1) else if not symmetric board solutions = SolveLvl2(board, iNode + 1) append solutions to results return results SolveLvl2(board, iNode) results = empty list jNode = index of one of the suffix node connected to iNode-th node in board for token in prefixes paired with the token of the jNode-th node in board if that pair is not already used set token as the iNode-th node in board if the token is valid relative to its other neighbour suffixes if iNode + 1 is less than nb nodes in graph solutions = SolveLvl2(board, iNode + 1) append solutions to results else add board to results return results

Used pairs

During the search I need to check if a pair is already used in the board. To make it efficient I add one last flag to Pair, which is also the only property needing to be managed per thread.

struct Pair { ... bool used[NB_THREAD]; };

As I'm juggling between the two hash tables, I must not forget to update that flag in both tables. That's where the sibling property of the Pair becomes handy.

Symmetry

Beside pairs being used only once, another constraint needs to be checked: symmetry. Rotated or mirrored boards are obviously the same from the point of view of the game, and should be counted as one in the result. They can be easily avoided by imposing \(t_2\gt t_1\), \(t_3\gt t_1\) and \(t_4\gt t_2\) where \(t_i\) is the iteration index of the token used by the i-th node. Note that we need to allow \(t_4\lt t_3\): it leads to different solutions for level 2 nodes with 3 edges. In the implementation, instead of iterating on the whole range and checking indices, a more efficient way is to clone iterators appropriately to immediately start the search from the right index.

Multithreading

The algorithm above brings computation time in reachable range, of the order of \(ne^9(e-1)(e-2)^2\) where \(e\) is the average number of pairs per token. Multithreading will help a little more.

(Edit on 2023/11/27: correction of the formula for the computation time above).

There is an immediate solution for multithreading: in the algorithm above, after the initial node is set the execution branches are completely decorrelated. Then I just need to split the set of possible prefixes between each thread and I'm good to go. Given that this set is stored as a hash table, splitting can be done as choosing ranges of hash indices. And as I took care to choose hash table's size dividable by the number of threads, the range calculation is straight forward.

In term of conflict in data access, there is only one points to take care of: when updating the list of results. A mutex will manage that.

typedef struct WorkerData { uint64_t nbFoundBoard; int idxHashes[2]; int iWorker; } WorkerData; void CreateBoards(void) { uint64_t nbFoundBoard = 0; WorkerData workerDatas[NB_THREAD]; loop(i, NB_THREAD) { workerDatas[i].nbFoundBoard = 0; workerDatas[i].idxHashes[0] = i * HASH_PER_THREAD; workerDatas[i].idxHashes[1] = (i + 1) * HASH_PER_THREAD; workerDatas[i].iWorker = i; } pthread_mutex_init(&mutex, NULL); loop(i, NB_THREAD) { int ret = pthread_create( workers + i, NULL, CreateBoardsWorker, workerDatas + i); assert(ret == 0); } loop(i, NB_THREAD) { pthread_join(workers[i], NULL); nbFoundBoard += workerDatas[i].nbFoundBoard; } pthread_mutex_destroy(&mutex); }

Early quit

What's above is sufficient for implementation, however the first results I've obtained show that for a given quadruple of suffix there exists in general many possible solutions. The game as it is described by Sacha uses these quadruples as starting states for the game, and it's up to the player to find the prefixes. So, what we are actually interested in is to find those quadruples. It means we can early quit the search for one quadruple as soon as we have found one solution.

In my algorithm it's easy to early quit in SolveLvl2 and come back to SolveLvl1, however at that point we still have the center node set in the board. The algorithm is convenient enough as it is so I don't want to break everything. Instead I choose to loop on the list of current results to see if the quadruple exists, and actually add the result only if it doesn't. That's a pain to have to do it, especially because the probability for a quadruple to have several possible center nodes seems very low (in other words, that check is probably useless). But I'm too lazy to look for a better solution...

Implementation

Finally, I have all I need and can implement the search.

Board* resBoards = NULL; bool IsValidToken( Board const* const board, int const iNode, char const* const prefix, Pair* collateralEdge[static 3], int const iWorker) { HashIter initIter = {.hash = hashes}; HashIterResetTo(&initIter, prefix); int iCollateral = 0; loop(jNode, 5) if(graphEdge[jNode][iNode] == 1) { HashIter iter = initIter; bool flagFound = false; while(iter.entry != NULL && flagFound == false) { if( iter.entry->used[iWorker] == false && strcmp(iter.entry->token[1], board->tokens[jNode]) == 0 ) { flagFound = true; collateralEdge[iCollateral] = iter.entry; ++iCollateral; } else HashIterSubNext(&iter); } if(flagFound == false) return false; } return true; } bool AddBoardToResults(Board const* const board) { if(resBoards) { Board* ptrBoard = resBoards; while(ptrBoard) { if( strcmp(ptrBoard->tokens[1], board->tokens[1]) == 0 && strcmp(ptrBoard->tokens[2], board->tokens[2]) == 0 && strcmp(ptrBoard->tokens[3], board->tokens[3]) == 0 && strcmp(ptrBoard->tokens[4], board->tokens[4]) == 0) return false; ptrBoard = ptrBoard->next; } } Board* newBoard = calloc(1, sizeof(Board)); *newBoard = *board; newBoard->next = resBoards; resBoards = newBoard; return true; } uint64_t SolveNodeLvl2(Board* const board, int const iNode, int const iWorker) { int iSuffix = 0; while(graphEdge[iNode][iSuffix] == 0 || graphNode[iSuffix] == 0) ++iSuffix; char const* const suffix = board->tokens[iSuffix]; HashIter iter = {.hash = hashes + 1}; HashIterResetTo(&iter, suffix); uint64_t nbFoundBoard = 0; while(iter.entry != NULL) { Pair* collateralEdges[3] = {NULL, NULL, NULL}; if( iter.entry->used[iWorker] == false && iter.entry->pruned == false && IsValidToken(board, iNode, iter.entry->token[0], collateralEdges, iWorker) ) { loop(i, 3) if(collateralEdges[i] != NULL) { collateralEdges[i]->used[iWorker] = true; collateralEdges[i]->sibling->used[iWorker] = true; } strcpy(board->tokens[iNode], iter.entry->token[0]); if(iNode < NB_GRAPH_NODE - 1) { nbFoundBoard += SolveNodeLvl2(board, iNode + 1, iWorker); } else { pthread_mutex_lock(&mutex); if(AddBoardToResults(board)) ++nbFoundBoard; pthread_mutex_unlock(&mutex); } loop(i, 3) if(collateralEdges[i] != NULL) { collateralEdges[i]->used[iWorker] = false; collateralEdges[i]->sibling->used[iWorker] = false; } board->tokens[iNode][0] = 0; if(nbFoundBoard > 0) return nbFoundBoard; } HashIterSubNext(&iter); } return nbFoundBoard; } uint64_t SolveNodeLvl1( Board* const board, int const iNode, HashIter* const initIterA, HashIter* const initIterB, int const iWorker) { HashIter iter; if(iNode == 1) iter = *initIterA; else if(iNode == 2) iter = *initIterB; else if(iNode == 3) iter = *initIterA; else if(iNode == 4) iter = *initIterB; uint64_t nbFoundBoard = 0; while(iter.entry != NULL) { if(iter.entry->used[iWorker] == false) { iter.entry->used[iWorker] = true; iter.entry->sibling->used[iWorker] = true; strcpy(board->tokens[iNode], iter.entry->token[1]); if(iNode < 4) { if(iNode == 1) nbFoundBoard += SolveNodeLvl1(board, iNode + 1, &iter, &iter, iWorker); else if(iNode == 2) nbFoundBoard += SolveNodeLvl1(board, iNode + 1, initIterA, &iter, iWorker); else if(iNode == 3) nbFoundBoard += SolveNodeLvl1(board, iNode + 1, initIterA, initIterB, iWorker); } else nbFoundBoard += SolveNodeLvl2(board, iNode + 1, iWorker); iter.entry->used[iWorker] = false; iter.entry->sibling->used[iWorker] = false; board->tokens[iNode][0] = 0; } HashIterSubNext(&iter); } return nbFoundBoard; } static void* CreateBoardsWorker(void* ptr) { WorkerData* data = ptr; int* idxHashes = data->idxHashes; int const iWorker = data->iWorker; Board board = {0}; int const iNode = 0; HashIter iter = {.hash = hashes}; HashIterReset(&iter); while(iter.entry != NULL) { if(iter.idxHash >= idxHashes[0] && iter.idxHash < idxHashes[1]) { if(iter.entry->pruned == false) { strcpy(board.tokens[iNode], iter.entry->token[0]); uint64_t nb = SolveNodeLvl1(&board, 1, &iter, &iter, iWorker); if(nb > 0) data->nbFoundBoard += nb; board.tokens[iNode][0] = 0; } } HashIterStep(&iter); } pthread_exit(NULL); }

Results

I've run the search for several suffix lengths on all dictionaries. The 2k dictionary does not produce any results, the 5k one very few, and the 10k one quite a lot. Increasing suffix length significantly increases the search time without significantly increasing the number of solutions. For a same quadruple of suffix there seems to be many solutions in general.

result01.txt: pruning [2,6], no unique, [1,3], [2,4], 5k, 32s, 180 boards result02.txt: pruning [2,6], unique, [1,3], [2,4], 5k, 31s, 14 boards (checked) result03.txt: pruning [2,6], unique, [1,3], [2,5], 5k, 2.3mn, 14 boards (checked) result04.txt: pruning [2,6], unique, [1,3], [2,6], 5k, 6.9mn, 14 boards (checked) result07.txt: pruning [2,6], unique, [1,3], [2,30], 5k, 32mn, 14 boards (checked) result05.txt: pruning [2,6], unique, [1,3], [2,4], 10k, 23mn, 22323 boards (checked) result06.txt: pruning [2,6], unique, [1,3], [2,5], 10k, 121mn, 22389 boards (checked)

I've picked several solutions at random and checked them manually. I've also made a Python script to independently check that there are no duplicates in the results, and that returned boards are actual solutions. I've spent enough time on it to be sufficiently confident in the results to share my solution here, but I wouldn't bet my life on it. Use it at your own risk !

The C implementation and results are available for download here. Extract with tar xvf okwddm.tar.gz, and then refer to README.md.