If you have suggestions on how to best break down the problem, feel free to tell me some additional scenarios to insert into these ones to allow shorter steps in refactoring and modifying the solution.Other languages: How to use WordOn solverĪrrows: use to move forward/backward between tiles.
#Ruzzle helper code#
Not only tests give feedback to the code, but also the code tells you what are the next tests to write. You can then extend these scenarios to the 2x2, 3x3 and 4x4 cases, skipping intermediate steps depending on your implementation.
#Ruzzle helper series#
I realize I'm doing some of the analysis work for you, but when you just have a timebox I prefer to give out a series of scenarios to be tackled one at the time, to let coders concentrate on the interesting algorithmic aspects of the problem instead of on making up words. If you want to try out this kata, here is a set of free test cases to get started. When an algorithm doesn't work, the last thing you want to do is to fire up a debugger or inserting echo statements: even if it's possible to just debug with print() in a test suite, unit tests will tell you where exactly is the problem to fix along with the red bar, while end-to-end tests will only tell you "something's wrong". TDD always needs tests at the unit level, especially in an unfamiliar domain.The same domain logic was still necessary, but it had to be composed differently. Even if we threw away the outer part of the search algorithm when starting to look for words instead of generating paths, most of the code could be reused (e.g.
#Ruzzle helper software#
This kata is ideal for training on performance optimization.Here are some sparse findings on our experience while developing the solver in TDD and the shock of having to drop the current approach. Lets you exclude all words containing letters from E to Z without starting a new search, but also words like Aaron after just two steps. This is a problem prone to optimization, since you can exclude many words without starting to search them (if they contain a letter that is not in the grid) or even in the first few branches in the tree, when no 2-cell path match them. Thus, to avoid this explosion in complexity, we inverted the problem and started searching every single word in the dictionary into the grid. However, each cell has an average of 5.25 neighbors (from a maximum of 8 in the middle to just 3 in the corners) so when this search arrives at 7-letter words, is already a number of paths 16*5.25^7=1.7M, which is more than the number of words in the English language (less than 1M). The simplest solutions that comes to mind, and that everyone of us dived into, was to generate all the possible paths starting from each cell, and check if any path of length L is a valid word in the given dictionary.įirst of all, caution is needed to implement this strategy: a breadth-first search will probably perform better, and lets you define an arbitrary maximum word length. However, the strongest requirement is that of maintaining an acceptable performance, since Ruzzle is a time-limited game (2 minutes length). We didn't go into the grid-as-a-graph-route, but I guess good results can come from this model due to the wide availability of algorithms that work on graphs. This kata has a medium algorithmic difficulty: the main problem to solve is the generation of valid paths inside the graph composed of the 16 cells. The score is calculated in the Scrabble way, by summing up the weight of all the letters involved in your words (but there is no score calculation involved in this kata). Words can be constructed by moving from one cell to the (at most) 8 adjacent ones, but without using cells more than once in each word. Each solver can suppose to have a list of all the valid words for the language stored in a file: this information is a prerequisite to build a solver.Īll 26 letters can be used, and can be repeated inside a grid. Words must be valid in a chosen language, which for us was Italian, but it doesn't really matter for the purpose of the kata. On the train to Rome last week, me and my colleagues from the Onebip team exercised with a new kata: a solver for Ruzzle that would find as many words as possible in the given time frame. Ruzzle is a popular word game that has as an objective to find as many words as possible into a 4x4 grid like this: