-2

I have a task where I want to return the count and list of words (from the bag of words) that can be made from the bag of letters as a tuple. Imagine that the letters and words are physical pieces and you need to match the letters to the words to complete the words. You're not allowed to use the same physical letter twice, and you're not allowed to use the same physical word twice unless they exist repeatedly in their respective bags. I get how to go about getting the list of possible words, but I'm not sure how to optimize it to select the possible words other than a brute force effort of generating all possible combinations of words.

Here's an example. Imagine you have a bag of letters (similar to Scrabble):

[ g t o g l v o r d e a b ]

and a bag of possible words:

[word bag got we love]

In this case, the answer should be (3, ['bag', 'got', 'love'])

I've found some similar "Find list of possible words" or recursive sum questions that could probably be adapted, but none where they find the possible concurrent set of words from a set of letters in Python.

Here is an example I found for C#:

Finding the set of words that can be spelled with a given set of letters

Here is an example for finding any list of words:

Python: find possible words that can be made from 7 random letters

Optimus
  • 1,354
  • 1
  • 21
  • 40
  • 3
    With 1k+ rep, I'd expect you to follow the instructions I'm [ask] a bit better – Mad Physicist Jul 09 '21 at 11:44
  • Could you explain what you see as a problem with the question? I'm happy to make edits. I've read the How to Ask page many times and I'm not sure what you're pointing to as a problem. I can add links to my research and the code I've experimented with if you like. – Optimus Jul 09 '21 at 12:54
  • 2
    Can you clarify what exactly you are asking? As it stands right now, this seems like a task description directed *at you*, not a question directed at us. What is your problem approaching this task? What exactly do you need help with? What problem do you have adapting what you found to this related task? – MisterMiyagi Jul 09 '21 at 12:59
  • @MisterMiyagi, thanks for the suggestion. I was trying to be brief and more 'task' like in my description, but I see now it's frowned upon to format it that way. Hopefully my description is better now? – Optimus Jul 09 '21 at 13:04
  • 1
    FWIW, I don't get the task description either. Does the "use same letter twice" apply *per word* or across all words? Is the task to find the *maximum* number of words? What should be done if two bags of results have the same number of words? What do you consider a brute force approach, and by extension what do you consider a valid non-brute force answer? – MisterMiyagi Jul 09 '21 at 13:05
  • Sorry that it's confusing. Basically, imagine you have a bag of physical letters, and a bag of physical words. You have to match up the letters to the set of words so that you have the largest set of words. If you can produce more than one set with the largest number of words that's fine, you only have to return one set. – Optimus Jul 09 '21 at 13:08
  • Please read [ask] and [mcve]. Those pages explain it much better than I do. – Mad Physicist Jul 09 '21 at 13:40

1 Answers1

1

The best "not-so-brute-force" approach I can think of, as long as you have a fairly limited set of words, is:

letters=Counter('gtoglvordeaby')
words=['word', 'bag', 'got', 'we', 'love', 'doggy', 'dolly']
found = []
for word in words:
    wordbag=Counter(word)
    for wk,wv in wordbag.items():
        if wv > letters[wk]:
            break
    else:
        found.append(word)
print(len(found), found)

(I just added one letter and a couple of words to check that it behaves correctly when a word requires more than one occurrence of a certain letter).

I would be interested in knowing about better algorithms, of course

gimix
  • 3,431
  • 2
  • 5
  • 21
  • Thanks, but this breaks for the following inputs: `letters=Counter('gtoglvordeabyaaa')` and `words=['word', 'bag', 'got', 'we', 'vaa', 'love', 'doggy', 'dolly', 'a', 'a', 'a']` It doesn't take into account optimizing for a higher count of words which requires that you determine each possible set of words, or I think, use some kind of recursive search. – Optimus Jul 11 '21 at 10:57
  • How does it break? I get `8 ['bag', 'got', 'vaa', 'love', 'doggy', 'a', 'a', 'a']`, what would you expect? – gimix Jul 11 '21 at 15:52
  • There are only 4 a's in the bag of letters. Your output includes 5 a's – Optimus Jul 12 '21 at 20:00
  • There are 6 of them tbh, and four g's too. As MisterMiyagi asked in a previous comment, _Does the "use same letter twice" apply per word or across all words_? I assumed it was per word, if the assumption is wrong then my above code is not a solution – gimix Jul 13 '21 at 06:09
  • Right. After MisterMiyagi asked their question, I updated the post to try to be clearer with "You're not allowed to use the same physical letter twice, and you're not allowed to use the same physical word twice unless they exist repeatedly in their respective bags." – Optimus Jul 13 '21 at 10:45