5
$\begingroup$

I am trying to find an algorithmic solution to a thought experiment that occurred to me recently. Please excuse me if the question is a bit naïve as I am not a CS expert.


Basically I have a tree with $n$ nodes, each of which is assigned a numeric label $l\in\{0,\ldots,k\}$, $k\in\mathbb{Z}, k\geq0$. More than one node can have the same label. An example of such a tree is shown below.

enter image description here

Please excuse me for the poor quality of my drawing.

My aim is to find a mapping $m$ of the labels $\{0,\ldots,k\}$ to the set $s\in\{A,\ldots,Z\}$ (i.e., from numbers to letters) such that each path from a root node to a leaf node becomes a human-readable English word.

In the example above, a possible mapping could be $1\to S, 2\to E, 3\to L, 4\to A, 5\to N, 6\to W, 7\to D$, yielding the following resulting tree:

enter image description here

As you can see, each path from the root node to a leaf node produces an intelligible English word, which is from left to right $SEA, SELL, SAW$ and $SAND$.

Having a complete English dictionary at our disposal with all possible letter combinations that form intelligible English words, how could one find such a mapping $m:=l\to s$, assuming that any tree given as input is mappable?


EDIT: Any mapping needs to map different numbers to different letters, i.e., be injective.

$\endgroup$
3
  • 1
    $\begingroup$ Does a mapping need to map different numbers to different letters? In other words, should it be injective? $\endgroup$
    – Nathaniel
    May 30 at 19:41
  • $\begingroup$ @Nathaniel Yes, thank you for your comment. I have amended the question. $\endgroup$
    – Klangen
    May 30 at 20:11
  • 2
    $\begingroup$ Just as a comment, if you build a trie out of the dictionary, then you almost have a labelled subtree isomorphism problem. It's "almost" because the root of the "pattern" needs to be one level from the root of the "text" tree, and the leaves also need to match. $\endgroup$
    – Pseudonym
    May 31 at 1:43

1 Answer 1

1
+100
$\begingroup$

What you're trying to build is kind of a crossword. This link shows an algorithm that generates crosswords. It's not quite your case, but it's close enough. Basically the algorithm does this (starting from the first word $w$ of the ordered dictonary):

  1. If $w$ can be placed in a path and if it hasn't already been placed in every path possible: insert it. Else, we'll call $w$ the next avaible word and start again.
  2. Search for a word $w_1$ that matches the conditions, hasn't already been placed in every path possible and insert it. If every path is full, then you have a solution. If you can't find it, go back to 1. and insert $w$ in another path
  3. Search for a word $w_2$ that matches the conditions, hasn't already been placed in every path possible and insert it. If every path is full, then you have a solution. If you can't find it, go back to 2. and insert $w_1$ in another path
  4. [...]

This is a backtracking algorithm.

I would suggest to sort all the words alphabetically and then by length (you'll have something like $a, aa, ab, b, ba, bb, c, ccc,\ [...]$). I think an example will clarify why.

Let's say you just inserted $SEA$ in your example. To fill the path $1-4-6$ you'll have to search words that start with $SA$. This can be done easly with the sort. Starting from words with length $3$ wich start with $S$: if you encounter $S\_\ $, where $\_\ $ can be every letter other then $A$, or a word with length $>3$ then $SEA$ can't be placed in that specific path.

To be more specific, let's say this is a portion of the ordered list of words: $[...], RAW, SAA, SAW, SEA, [...]$. Then we can be sure that if the path $1-4-6$ can be fulfilled by a word, it needs to be after $RAW$ and before $SEA$.

For an implementation you could perhaps use a list of lists like this one: $[[1, 2, 4], [1, 2, 3, 3], [1, 4, 6],\ ...]$. Whenever you place a word in a path you replace every number of the list with the corrisponding letter: $[[S, E, A], [S, E, 3, 3], [S, A, 6],\ ...]$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.