1

I'm doing a text twist program, and I'm having a problem checking whether a word can be created out of the given group of letters. It's very easy if there are no repeating letters, but how do I do it if a user inputs a word which has repeating letters? I used tuple but it does not work if the letters repeat.

To make it clearer, I'm providing this example:

Say your group of letters is (d,n,a,e,l,i) and the user inputs the word need. We can see that the letter e was used here twice, but since the code (using tuple) that I made just checks if a list is a subset of a list, it counts need as a correct answer when it is not. How do I fix it?

smci
  • 32,567
  • 20
  • 113
  • 146
ahnhoney92
  • 21
  • 1
  • 2
  • 4
    Please provide examples of what you have already tried. – Victory May 17 '15 at 02:25
  • You'll need to check both that the necessary words are in your group, and that you have enough occurrences of each letter. – James Thompson May 17 '15 at 02:29
  • post some more valid and invalid examples. – Avinash Raj May 17 '15 at 02:32
  • Please [edit] your question and post the contents of your program. We can't help you if we don't know what you are doing. – MattDMo May 17 '15 at 02:32
  • It's an interesting question although the OP hasn't posted any code attempt of their own. But I can see how they could be stumped. – smci May 17 '15 at 02:45
  • 1
    Here's a related question based on the information provided thus far: http://stackoverflow.com/questions/15208369/test-if-set-is-a-subset-considering-the-number-of-each-element-in-the-set – sgallen May 17 '15 at 02:47
  • @sgallen: True, but a) the wording of this question is more applied and infinitely more likely to be found by newbies and b) that question references 'multiplicity of an element in a set', which really means it needs to be tagged [tag:multiset] – smci May 17 '15 at 03:00

3 Answers3

2

One way, using collections.Counter:

from collections import Counter
bag = Counter('dnaeli')
>>> Counter({'a': 1, 'e': 1, 'd': 1, 'i': 1, 'l': 1, 'n': 1})

bag.subtract(Counter('need'))
>>> Counter({'a': 1, 'i': 1, 'l': 1, 'd': 0, 'n': 0, 'e': -1})

if all(v >= 0 for v in bag.values()):
    print 'Word is contained'

# or as a three-line function:
def is_contained(a, b):
    """Test if all the letters of word a are contained in word b"""
    letters = Counter(b)
    letters.subtract(Counter(a))
    return all(v >= 0 for v in letters.values())

Note: Counter.subtract() is different to the - operation i.e. Counter.__sub__(). Counter.subtract() will also propagate negative (and zero) counts, which is what you need to check [¹].

([¹] @StefanPochmann's approach subtracts the letters from the candidate word; mine does the reverse. In SP's case positive leftover counts are bad; in mine negative are bad. So his approach doesn't need to care about negative or zero counts but mine does. His is less complex hence better.)

smci
  • 32,567
  • 20
  • 113
  • 146
1

Yes, sets don't work, but multisets do. Counter can be used for this.

letters = 'dnaeli'
words = 'line', 'linda', 'need', 'den', 'x'

from collections import Counter
for word in words:
    if not Counter(word) - Counter(letters):
        print(word)

Prints:

line
linda
den

Alternatively:

for word in words:
    if all(letters.count(c) >= word.count(c) for c in word):
        print(word)

This would be slow if both your letter set were very large and your words were very long, but "normal usage" it's alright.

Stefan Pochmann
  • 27,593
  • 8
  • 44
  • 107
  • Note: `Counter.subtract()` is different to the `-` operation i.e. `Counter.__sub__()`. `Counter.subtract()` will also propagate negative and zero counts – smci May 17 '15 at 02:43
  • Well I'm not using `subtract`, so I don't understand why you're saying that. – Stefan Pochmann May 17 '15 at 02:47
  • Hmm. Your approach subtracts the letters from the candidate word; mine does the reverse. In your case positive leftover counts are bad; in mine negative are bad. So yeah, your approach doesn't need to care about negative or zero counts but mine does. Interesting. – smci May 17 '15 at 02:54
  • To be honest I didn't know what `subtract` does; I'm not sure I ever used it. Or maybe I did and then didn't like it and never looked back :-) – Stefan Pochmann May 17 '15 at 03:01
  • Me neither :-) I only knew that the builtin set operations necessarily needed to act 'different' on `Counters` to get the 'right' result. Well now we know. – smci May 17 '15 at 03:02
0

You could just try removing each letter from the allowed list until you either finish or something goes wrong (meaning you can't construct that word):

def TestInput(user_input_string, avia_letters_list):
    for each_letter in user_input_string:
        try:
            avia_letters_list.remove(each_letter)
        except ValueError:
            return 'sorry "%s" can not be constructed' % user_input_string  
    return 'good job, "%s" can be constructed' % user_input_string

usable_letters = ['d', 'n', 'a', 'e', 'l', 'i']

print TestInput('need', usable_letters[:])
print TestInput('lid', usable_letters[:])
print TestInput('nail', usable_letters[:])

Output:

sorry "need" can not be constructed
good job, "lid" can be constructed
good job, "nail" can be constructed
Abd Azrad
  • 301
  • 2
  • 10