Find all words of length at least 3 on a given NxN board. The words must appear in a given dictionary.
The board is defined by N strings of length N, separated by commas. For example:
AZI,RCA,EVE
The valid words are perhaps easier found with the board written as:
A Z I
R C A
E V E
A word is valid if it appears on the board (i.e. can be read in any, not necessarily straight direction) and is listed in a given dictionary. In the example we can see not only straight words like ACE, ARE, ERA, EVE, and ICE, but also words like CAVER.
There are two HttpGet endpoints, here explained by example:
- api/Words/TTZZA,ONIZU,TEIUQ,EPZUQ,ISAUQ/QUINT
- api/Words/TTZZA,ONIZU,TEIUQ,EPZUQ,ISAUQ
The first one responds with true or false, depending on whether a given word (QUINT in the example) appears on the board (and in the dictionary). The second responds with a Json object that contains two arrays of strings: the board definition and the words that were found on the board.
- The URLs listed above are a bit unconventional because they do not deal with persisted resources.
- Upon startup, the whole given dictionary is read into memory, which takes a few seconds. After this, lookup of words is fast and hence the endpoints respond promptly.
- The implementation uses System.Reactive, which allows us to process the candidate words generated by the board as a data stream and stop looking at a predefined time.
Microsoft Visual Studio Community 2017 can be used to run the solution.
Hit F5 to run. Depending on your computer speed, you can see the app find the word DEMOCRACY using URL api/Words/DEM,RCO,AOY in the allotted 5 seconds. If you change the allotted time to 1 (second) it may not find the word DEMOCRACY.