2

With a list of thousands of words and a small list of letters I am trying to find the least amount of words to make use of all given letters, assuming my dictionary of words covers all letters.

The first step is obviously to remove all words with none of the letters. Then I approached this by calculating the relative rareness of each letter for the remaining words, and sort words by combined relative rarity of the letters they contain relative to their length. So this would put words with relatively rare letters first, assuming it will be increasingly easy to satisfy the remaining, more common letters. After picking the best word with the most "coverage" of letters, I remove those from the list of letters, then loop to recalculate the words rareness for the remaining letters until all letters are satisfied.

This certainly works, but sometimes I get odd results that show how this is not ideal. For example a 5 letter requirement would still find a single best match covering all letters, but adding a 6th letter, all of a sudden I get 4 words returned, because of the sequence of returned words and rareness shifts in an unfavorable way.

What strategy could I use to improve this algorithm? Also I currently iterate over all words several times per loop, counting rareness etc, which gets increasingly expensive with a vast dictionary. Any suggestions welcome :)

  • Specific examples showing data and how the algorithm treats it would help. I am a little unclear as to how the current algorithm actually works. – user22815 Feb 1 '18 at 17:48
  • 1
    "the least amount of words to make use of all given letters" - I don't understand what this means. – Deacon Feb 1 '18 at 17:49
  • 1
    This is the set cover problem. – Karl Bielefeldt Feb 1 '18 at 18:00
  • @Deacon Should have included the very example Becuzz shows in his answer. – kontur Feb 1 '18 at 20:13
  • 1
    Are your letters a set of letters that can be reused as many times as needed or a bag of letters that can only be used as many times as each letter appears in the bag? – OldFart Feb 2 '18 at 16:03
3

While there may be a more ideal solution out there than this, I think it will get you closer. Right now your algorithm is rating words that have "rare" letters as more important than overall coverage for the list of letters. Probably the best way of reducing the number of words you use will be to pick words that contain the most letters you still need.

For example, say you're trying to find the least number of words that, together, contain the following letters:

Letters
--------
a
b
c
d
e
f

Words
--------
ace
bread
fork
whistle
crab
monkey
car
fork
dog
diamond

An easy way to figure out how useful each word is would be to look at each word and calculate which of the desired letters it contains. We can make this using an array of boolean flags for each word.

Words    | a | b | c | d | e | f
---------------------------------
ace      | T | F | T | F | T | F
bread    | T | T | F | T | T | F
fear     | T | F | F | F | T | T
whistle  | F | F | F | F | T | F
crab     | T | T | T | F | F | F
monkey   | F | F | F | F | T | F
car      | T | F | T | F | F | F
fork     | F | F | F | F | F | T
dog      | F | F | F | T | F | F
diamond  | T | F | F | T | F | F
coffee   | F | F | T | F | T | T
---------------------------------
Total    | 6 | 2 | 4 | 3 | 6 | 3

Since we are just starting, we need everything. So lets just give each word a score based on how many letters it has that we still need.

Used Words: 
Letters Remaining: a, b, c, d, e, f

Words    | a | b | c | d | e | f | Score
-----------------------------------------
ace      | T | F | T | F | T | F | 3
bread    | T | T | F | T | T | F | 4
fear     | T | F | F | F | T | T | 3
whistle  | F | F | F | F | T | F | 1
crab     | T | T | T | F | F | F | 3
monkey   | F | F | F | F | T | F | 1
car      | T | F | T | F | F | F | 2
fork     | F | F | F | F | F | T | 1
dog      | F | F | F | T | F | F | 1
diamond  | T | F | F | T | F | F | 2
coffee   | F | F | T | F | T | T | 3

So let's take the one that knocks out the most letters. In this case "bread". Which means the only letters we have left to use are "c, f". Let's give each word a new score based on the letters we need.

Used Words: bread
Letters Remaining: c, f

Words    | a | b | c | d | e | f | Score | Score 2 
--------------------------------------------------
ace      | T | F | T | F | T | F | 3     | 1
bread    | T | T | F | T | T | F | 4     | -
fear     | T | F | F | F | T | T | 1     | 1
whistle  | F | F | F | F | T | F | 1     | 1
crab     | T | T | T | F | F | F | 3     | 0
monkey   | F | F | F | F | T | F | 1     | 1
car      | T | F | T | F | F | F | 2     | 1
fork     | F | F | F | F | F | T | 1     | 1
dog      | F | F | F | T | F | F | 1     | 0
diamond  | T | F | F | T | F | F | 2     | 0
coffee   | F | F | T | F | T | T | 3     | 2

Now we can take "coffee" which has a score of 2 and that uses up all the letters we wanted to use. Obviously this has some flaws. First, your subsequent choices depend on what your first choice was. If you picked a word that got a lot of common letters but didn't hit the rarer ones, you will likely end up with one word that hits a lot of letters and a bunch that only get one or two. This could be solved by weighting the scores such that more rare letters are worth more (kinda like playing Scrabble).

One thing you might have noticed is having to recalculate the score on every pass. And that's going to be a pain. But what if we used some clever computer tricks to make that easier? What if, instead of an array of booleans for each word, we just turned that into a sequence of bits? (Same thing, but easier to work with for this.)

So if we rewrote the table where as bits, it might look like this:

Words    | Bits (a|b|c|d|e|f)
---------------------------------
ace      | 101010
bread    | 110110
fear     | 100011
whistle  | 000010
crab     | 111000
monkey   | 000010
car      | 101000
fork     | 000001
dog      | 000100
diamond  | 100100
coffee   | 001011

Calculating the score now becomes a simple XOR with a mask for the letters you need (at the beginning, 111111 then subsequently 001001) then you just count the true bits. Pretty simple recalculation.

If you want to weight the algorithm, it gets a bit easier to execute but harder to set up. If you took a count of each letter to find the rarest ones (like I did in the first part), you could arrange the bitmask to no longer be in say alphabetical order but in order of rarity (most rare being first). In this case your bitmask would look like (b|d|f|c|a|e). Then comparisons of score are just ordering by the highest integer after applying the mask. (Note this does run into some problems when two letters are tied for rarity. Just be aware it can skew your results. Hopefully there won't be many cases of this in larger lists of words.)

This isn't perfect, but it's a good start.

  • This seems computationally more elegant than my solution, but pretty similar and susceptible to the same problem: What if the first word picked happens to introduce a sequence of consequent picks that is unfortunate and unnecessarily long. In my solution the weighting of the letter rareness is even more aggressive, making sure rare letters really get prioritized (my particular use case is finding sample words from more exotic language that contain very rarely used letters in proportion to my decent sized dictionary). – kontur Feb 1 '18 at 20:17
  • 1
    @kontur Depending on how much effort you want to put in (and how important it is to find an optimal solution), you could do what I suggested and rearrange the mask to get the rareness weighting. If you want an optimal solution every time, you could implement a breadth-first / depth-first / A* type search algorithm. You are going to have a hard time getting a perfect solution without brute forcing your way through the search space of solutions. This is more aimed at cutting out searching through solutions that are never going to be optimal. – Becuzz Feb 1 '18 at 20:35
  • Yes, I see. I was wondering if there is anything that is specific to natural languages that I could leverage, like certain letter combinations that are generally rare, but disproportionately common for some languages. Also maybe I could perform some more pre-processing on the words first to eliminate words whose letters are subsets of others, like dropping "car" if the dictionary contains "racket", which has more wide application due to more letter variation. – kontur Feb 2 '18 at 16:58
  • I should point out that users can add to the dictionary, but while I might perform the search often, I only cache the dictionary on startup, so that would speak in favor of spending more times on the dictionary first, to reduce breadth. – kontur Feb 2 '18 at 17:00
  • This is still the best answer. My current implementation differs in that it doesn't use bitmap masks, but arrays of values for each letter match, so compiling the overall word value from matched letters can be weighted. I've focused on working on the dictionary more, so that the I have more diverse words to start my search with. – kontur Feb 13 '18 at 11:28
4

If you throw out all the uninteresting letters and words, then reduce each word to the subset of interesting letters contained, you have a Set cover problem. This is NP-complete. If you don't want to do an exhaustive search, the best you can do is repeatedly take the word that contains the largest number of unused letters.

  • 1
    That would be the "greedy" set cover approach, yes? Is @Becuzz's answer in effect that, always taking the word with the most occurrences? – kontur Feb 2 '18 at 16:44
0

I would pre-process each word in the dictionary to map the word to its list of unique letters. Then just look for the map entry with your desired letters.

In a perl one-liner:

perl -MList::Util=uniq -slne '
    ($word = $_) =~ s/\W//g;     # remove punctuation, etc
    $key = join "", uniq sort split //, lc $word; 
    push @{$map{$key}}, $_;
  } END {
    print join "\n", @{$map{$letters}};
' -- -letters=aehilpst  /usr/share/dict/words
philatelist
philatelist's
philatelists
shapeliest
slaphappiest
splashiest
  • More of a hack answer than an engineering answer. – glenn jackman Feb 1 '18 at 20:39
  • Thanks for the effort and showing your approach. My problem is exactly cases where a single word does not cover all required letters. – kontur Feb 2 '18 at 16:48
  • I must say, I don't quite understand your request. Perhaps you could provide some sample input and output. – glenn jackman Feb 2 '18 at 16:58
  • @Becuzz's answer has a very good sample. It's an arbitrary selection of letters I have, and from my dictionary I want to spell words to use all of the letters, with using as little words as possible. – kontur Feb 2 '18 at 17:02

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.