Today started our official capstone prototype groups! That said, I actually kept working on the Boggle assignment.
Setting up the board with proper allocation of memory was a simple task in comparison to the strange myriad of rules that would come up in getting Boggle to work. I had a recursive function that would search through every letter of a string until it found an answer, something like that of a depth-first search.
However! I had to check for all special cases that would stop the search early. What if the next word had a greater letter (Z > A, in character terms) than where I was checking? What if the word was smaller for the next check? What if, by strange circumstances, I could go to the word that contained the same third letter but not the second letter? What if the word already was found? All these and more required special checks, even moreso tracking what was already traversed.
The solution? Lots of memory allocation. The traversal charts would differ for each and every single branch of traversal, so I had to be careful to only allocate when necessary. For example, when testing every adjacent cube from the target, I could use memcpy and reset the traversal for each and every single recursive traversal, saving up on allocation of memory by reusing it as necessary.
What next? There are some edge cases involving words in the dictionary that contain punctuation, but I'll get em' settled out.
No comments:
Post a Comment