How many words can be made from these letters?

There is a python script that does the job here . However, I think the filtering can be improved upon. I'm curious to see what other people can come up with.

The number of calls to filter_words has a bound of about 250,000. So, that's high but constant, O(235674) . Within filter_words , however, we see that the calls to count with this code grows somewhat aggressively .. is that O(log n) ?:

    for letter in word:
        if word.count(letter) > countsd[letter]:
            return False

Here is the profile of the given problem:

In [33]: %prun find_allwords("skylarowensavelandandstevebaker")
     758752 function calls in 1.013 seconds

   Ordered by: internal time

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
235674    0.803    0.000    0.907    0.000 ana_final.py:37(filter_words)
   29    0.105    0.004    1.012    0.035 {filter}
235674    0.052    0.000    0.052    0.000 {method 'keys' of 'dict' objects}
235674    0.037    0.000    0.037    0.000 {method 'issubset' of 'set' objects}
51609    0.016    0.000    0.016    0.000 {method 'count' of 'str' objects}
....

Compare that with:

In [34]: %prun find_allwords("skylarowensavelandandstevebakerwhatifImakeitreallylongsothatbasicallyallwordsinthedictionarywillbeselectedwellmostofthematleast")
     1515734 function calls in 1.595 seconds

Ordered by: internal time

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
235674    1.144    0.000    1.470    0.000 ana_final.py:37(filter_words)
808141    0.215    0.000    0.215    0.000 {method 'count' of 'str' objects}
  125    0.110    0.001    1.580    0.013 {filter}
235674    0.062    0.000    0.062    0.000 {method 'issubset' of 'set' objects}
235674    0.054    0.000    0.054    0.000 {method 'keys' of 'dict' objects}
...

Not bad. But, I bet you can do better.

Not altogether unlike Mr Trailblazer's.

My Python solution

from time import clock

# Initializes our clock
clock()


def valid(text):
    string = 'skylarowensavelandandstevebaker'
    for character in text:
        if string.count(character) < text.count(character):
            return False
    return True

with open('words.txt') as file:
    total = 0
    for word in file.readlines():
        word = word[:-1]
        if len(word) > 2 and word.islower() and valid(word):
            total += 1
    print(total, '\nUsed %f seconds.' % clock())

Returns

7025 
Used 0.620612 seconds.

Here is a simple python program:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

from string import ascii_uppercase, ascii_lowercase
from collections import Counter

letters_to_use = 'skylarowensavelandandstevebaker'
letters_to_discard = set(ascii_lowercase).union(set(ascii_uppercase)).difference(set(letters_to_use))
letter_counts = Counter(letters_to_use)
found_words = 0

with open("words.txt") as input_file:
    for line in input_file:
        word = line.strip('\n')

        if len(word)<3: 
            continue

        if any(letter in letters_to_discard for letter in word): 
            continue

        word_counts = Counter(word)
        found = True

        for w,c in word_counts.items():
            if letter_counts[w] < c:
                found = False
                break

        if found: 
            found_words += 1

found_words
# 7025

Here's my solution -

Absolute running time: 1.34 sec, cpu time: 0.83 sec, memory peak: 43 Mb, absolute service time: 1.36 sec Online code testing at http://rextester.com/MGZYD14575

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

    import urllib
    import urllib.request

    def toMap(s):
        d = {}
        for c in s:
            if c in d:
                d[c] += 1
            else:
                d[c] = 1
        return d

    def isSubsetOf(ds, dss):
        isit = True
        for c in dss:
            if c in ds:
                if ds[c] < dss[c]:
                    isit = False
                    break
            else:
                isit = False
                break
        return isit

    resp = urllib.request.urlopen('https://raw.github.com/skyl/data-repository/master/data/words.txt')
    data = resp.read()

    words = [x.decode("utf-8") for x in data.split()]
    word = "skylarowensavelandandstevebaker"
    atlest = 3

    count = 0
    wordmap = toMap(word)

    for w in words:
        wmap = toMap(w) 
        if isSubsetOf(wordmap, wmap) and len(w)>=3:
            count += 1               

    print("Total: " + str(count))