Build a Plinko board of words from a dictionary

• A+
Category：Languages

Consider the following arrangement of letters:

``    B    O A   N R I  D E N T ``

Start at the top letter and choose one of the two letters below, Plinko-style, until you reach the bottom. No matter what path you choose you create a four-letter word: BOND, BONE, BORE, BORN, BARE, BARN, BAIN, or BAIT. The fact that DENT reads across the bottom is just a nice coincidence.

I'd like help figuring out an algorithm that can design such a layout, where each possible path from the top to the bottom generates a distinct word from a (provided) dictionary. The inputs to the program would be a starting letter (B, in this example) and a word length n (4, in this example). It would return either the letters that make up such a layout, or a message saying that it's not possible. It doesn't have to be deterministic, so it could possibly generate different layouts with the same input.

I haven't thought of anything better than a brute-force approach so far. I considered some sort of prefix-tree, but the fact that paths can cross and share letters messed with me. I'm most comfortable in Python, but at minimum I'd just like the idea for an algorithm or approach that would work for this problem. Thanks.

I find this a quite interesting problem.

The first attempt was a random solver; in other words it just fills the triangle with letters and then counts how many "errors" are present (words not in the dictionary). Then a hill-climbing is performed by changing a one or more letter randomly and seeing if the error improves; if the error remains the same the changes are still accepted (so making a random-walk on plateau areas).

Amazingly enough this can solve in reasonable time non-obvious problems like 5-letter words starting with 'b':

``    b    a u   l n r  l d g s o y s a e ``

I then tried a full-search approach to be able to answer also "no-solution" part and the idea was to write a recursive search:

First step

Just write down all acceptable words on the left side; e.g.

``    b    a ?   l ? ?  l ? ? ? o ? ? ? ? ``

and call recursively until we find an acceptable solution or fail

Step 2

Write down all acceptable words on the right side if the second letter is greater than the second letter of the first word, e.g.

``    b    a u   l ? r  l ? ? k o ? ? ? e ``

This is done to avoid searching symmetric solutions (for any given solution another one can be obtained by simply mirroring on the X axis)

Other steps

In the general case the first question mark is replaced with all letters in the alphabet if for all words that use the chosen question mark either

1. the word has no question marks and is in the dictionary, or
2. there are words in the dictionary that are compatible (all characters except question marks are a match)

If no solution is found for the specific question mark chosen there's no point in keeping searching so `False` is returned. Probably using some heuristics for choosing which question mark for fill first would speed up search, I didn't investigate that possibility.

For the case 2 (searching if there are compatible words) I am creating `26*(N-1)` sets of words that have a prescribed character in a certain position (position 1 is not considered) and I'm using set intersection on all non-question-mark characters.

This approach is able to tell in about 30 seconds (PyPy) that there are no solution for 5-letter words starting with `w` (there are 468 words in the dictionary with that starting letter).

The code for this implementation can be seen at

https://gist.github.com/6502/26552858e93ce4d4ec3a8ef46100df79

(the program expects a file named `words_alpha.txt` containing all valid words and then must be called specifiying the initial letter and the size)