3
\$\begingroup\$

Inspired by this question on Puzzling.StackExchange, I've decided to write a small python script that determines if a word is a BFF Word. Below are the parameters, solved by Puzzling user Stiv, also discussed in the program module docstring:

If you remove two letters, you are left with an anagram of an animal which is a common household pet ("man's best friend", hence 'BFF' - Best Friends Forever). Furthermore, the non-BFF Words exhibit a different but related pattern - namely that if you remove two letters, you are left with an anagram of an animal which is not a common household pet!

The main this I want improvements on is performance. I use requests to retrieve list of around 475k english words to determine if they are BFF words. I then use itertools.permutations to get all the possible combinations of the english word, based on the length of the pet it's being tested against, then test it against an already existing list of common/uncommon animals.

After about 15 minutes of running the program is still in the ab... part of the english words. I presume the part thats taking the longest is generating the permutations, so I'm wondering if there's any better way to do this.

script.py

"""
A function that determines if a string is a BFF Word.

If you remove two letters, and the remaining letters are
an anagram for a household pet, then it's a BFF Word.

Example:

GOURD -> remove UR -> DOG = Common Pet
ALBINO -> remove AB -> LION = Uncommon Pet
HELLO -> remove any 2 -> None = Neither
"""

from enum import Enum
from itertools import permutations
import requests

REPOSITORY = "https://raw.githubusercontent.com/dwyl/english-words/master/words.txt"

COMMON_PET = ["dog", "cat", "lizard", "rabbit", "hamster", "fish"]
UNCOMMON_PET = ["bear", "rhino", "lion", "tiger", "viper", "hyena"]

class PetType(Enum):
    COMMON = 1
    UNCOMMON = 2
    NEITHER = 3

def type_of_pet(word: str) -> PetType:
    """
    Returns the type of pet that the passed word is.
    """
    for pet in COMMON_PET:
        for string in permutations(word, len(pet)):
            if pet == ''.join(string):
                return PetType.COMMON

    for pet in UNCOMMON_PET:
        for string in permutations(word, len(pet)):
            if pet == ''.join(string):
                return PetType.UNCOMMON

    return PetType.NEITHER

def main():
    req = requests.get(REPOSITORY)
    if req.status_code == 200:
        words = req.text.split()
    for word in words:
        print(f"Word: {word.lower()} | Type of Pet: {type_of_pet(word.lower())}")


if __name__ == "__main__":
    main()
\$\endgroup\$
  • \$\begingroup\$ This was fun to write a sample implementation. \$\endgroup\$ – Reinderien Mar 27 at 3:22
4
\$\begingroup\$

The easiest speed-up I can think of is a letter-counting pass. In other words: apply collections.Counter() to the word in question, and keep a pre-computed tuple of Counters for both pet types.

The thing that's killing your performance is order - there are many, many, many re-ordered results from permutations, but they literally don't matter since you're dealing with an anagram. So when you compare with the Counters suggested above, check to see that

  • there are no letters that have increased, and
  • the total decrease is exactly two.

Here is a very rough implementation that seems to be fast-ish:

from collections import Counter
import requests


class Pet:
    __slots__ = ('name', 'counter', 'is_common', 'letters')
    def __init__(self, name: str, is_common: bool):
        self.name, self.is_common = name, is_common
        self.counter = Counter(self.name)
        self.letters = set(self.counter.keys())

    def matches(self, word: str) -> bool:
        if len(word) != 2 + len(self.name): return False
        wcounter = Counter(word)
        total = 0
        for letter in self.letters | set(wcounter.keys()):
            diff = wcounter[letter] - self.counter[letter]
            if diff < 0: return False
            total += diff
            if total > 2: return False
        return total == 2

    def __str__(self): return self.name


pets = [
    *(Pet(name, True) for name in ('dog', 'cat', 'lizard', 'rabbit', 'hamster', 'fish')),
    *(Pet(name, False) for name in ('bear', 'rhino', 'lion', 'tiger', 'viper', 'hyena')),
]

print('Downloading...', end=' ')
resp = requests.get('https://github.com/dwyl/english-words/blob/master/words.txt?raw=true')
resp.raise_for_status()
words = resp.text.splitlines()
print(f'{len(words)} downloaded.')

for word in words:
    for pet in pets:
        if pet.matches(word.lower()):
            print(f'{word} -> {pet} = {"Common" if pet.is_common else "Uncommon"} Pet')

It can be sped up with the use of multiple threads, etc.

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

Use The Rule

Don't search for words that match the rule! You already know the rule. Use it to generate the BFF words. That is, start with a common pet and filter out all the words that aren't two letters longer or that don't have all the letters in the common pet. The result is a list of the BFF words for that pet. The non-BFF words are generated using the same rule, but starting from an uncommon pet. Runs in about 125 ms.

import random
from collections import Counter

COMMON_PET = ["dog", "cat", "lizard", "rabbit", "hamster", "fish"]
UNCOMMON_PET = ["bear", "rhino", "lion", "tiger", "viper", "hyena"]

def BFF_word(pet, word_list):
    word_len = len(pet) + 2
    count = {letter:pet.count(letter) for letter in pet}

# only keep words that have the right length, no punctuation,
# and the right numbers of letters, and also don't contain
# the common pet, e.g. 'rabbited' -> 'rabbit' (too easy). 
BFFs = [word for word in word_list
            if len(word) == word_len
            if word.isalpha()
            if all(count[letter]<=word.count(letter) for letter in count)
            if pet not in word
            ]


    # uncomment to see how many BFFs there are and the first few
    #print(pet, len(BFFs), BFFs[:5])

    return random.choice(BFFs)

    
def main():
    # I just used a local word list
    with open("/usr/share/dict/words") as f:
        words = [line.strip().lower() for line in f]

    print("BFF words")
    for pet in COMMON_PET:
        word = BFF_word(pet, words)
        print(f'{word} -> {pet}')

    print("non-BFF words")
    for pet in UNCOMMON_PET:
        word = BFF_word(pet, words)
        print(f'{word} -> {pet}')

if __name__ == "__main__":
    main()
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I don't think this works for all edge cases. For a word like "rabbit" it is not enough that the BFF word is longer and has all letters in it. It needs to have at least two "b" in order to be valid, i.e. the count of each letter in word must be greater or equal to the count of each letter in pet. \$\endgroup\$ – Graipher Mar 27 at 11:08
  • \$\begingroup\$ An example of a matching word that should not match is "arbiters". \$\endgroup\$ – Graipher Mar 27 at 11:12
  • \$\begingroup\$ Also, TIL that you can have multiple if in a list comprehension and don't have to chain them with and. Thought that would be a syntax error, but it works just fine. \$\endgroup\$ – Graipher Mar 27 at 11:13
  • \$\begingroup\$ @Graipher, good catch. Fixed. With the bug, there are 42 reported BFF words for 'rabbit', of which only 3 are correct. Naturally, the one time I checked the output in detail, it randomly picked one of the correct answers. \$\endgroup\$ – RootTwo Mar 27 at 16:01
3
\$\begingroup\$

Now for something completely different: an implementation in C.

This is somewhat simple and stupid, and for all intents and purposes it executes instantly. It does not have any hash maps or hash sets. It tracks, for each pet, a letter frequency counting array that is sparse - it technically tracks the whole ASCII-extended range for efficiency's sake.

This makes some blatant assumptions:

  • Locale is ignored
  • Letter case is ignored
  • words.txt is assumed to have already been downloaded
  • This is possibly only compatible with Unix-like operating systems due to the file calls
  • Punctuation, spaces, etc. count as "characters that can be removed" to satisfy the criteria
#include <fcntl.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <sys/stat.h>
#include <unistd.h>

#define FILENAME "words.txt"

typedef struct {
    const bool common; // Is this a common pet?
    const char *name;  // Pet's name, capitalized
    int len,           // Length of pet's name, excluding null
        *counts;       // Array of letter frequencies
} Pet;

// Assume ASCII everywhere; this is the number of symbols whose frequency we count
#define N_COUNTS 256
// The size of a frequency-counting array for the above character set
#define N_COUNT_BYTES (N_COUNTS * sizeof(int))
// The number of bytes if we only care about counting the upper-case alphabet
#define BYTES_TO_Z ((1 + (int)'Z') * sizeof(int))
// The number of letters that the word must lose to get to the pet name
#define COUNT_DIFF 2

static Pet pets[] = {
    { true, "DOG"     },
    { true, "CAT"     },
    { true, "LIZARD"  },
    { true, "RABBIT"  },
    { true, "HAMSTER" },
    { true, "FISH"    },
    { false, "BEAR"  },
    { false, "RHINO" },
    { false, "LION"  },
    { false, "TIGER" },
    { false, "VIPER" },
    { false, "HYENA" },
};
#define N_PETS (sizeof(pets)/sizeof(Pet))

static void init_pet(Pet *restrict pet) {
    pet->len = strlen(pet->name);

    pet->counts = aligned_alloc(16, BYTES_TO_Z);
    if (!pet->counts) {
        perror("Failed to allocate buffer");
        exit(1);
    }
    memset(pet->counts, 0, BYTES_TO_Z);
    for (int i = 0; i < pet->len; i++)
        pet->counts[(uint8_t)pet->name[i]]++;
}

static bool compare(
    const Pet *restrict p,     // The pet whose name we will compare
    const char *restrict word, // The dictionary word
    int wlen,                  // Length of the dictionary word
    int *restrict counts       // Memory we use for count differences
 ) {
    // The word must have more letters than the pet, in total
    if (wlen != p->len + COUNT_DIFF)
        return false;

    memcpy(counts, p->counts, BYTES_TO_Z);

    for (const char *w = word; *w; w++) {
        // This difference is effectively:
        // frequency of this letter in pet - frequency of this letter in word
        // It starts off at the pet# and decreases.
        // Its permissible range for a valid word is -COUNT_DIFF <= c <= 0.
        int *c = counts + (uint8_t)*w;
        (*c)--;
        // Does the word have greater than COUNT_DIFF of this letter more than
        // the pet name?
        if (*c < -COUNT_DIFF)
            return false;
    }

    // There cannot be any counts left over that are positive. Loop over the
    // letters of the pet name, which in nearly all cases are unique; so this is
    // more efficient than looping over the whole alphabet.
    for (const char *c = p->name; *c; c++)
        if (counts[(uint8_t)*c] > 0)
            return false;

    return true;
}

static char *read_file(const char **restrict end) {
    int fdes = open(FILENAME, O_RDONLY);
    if (fdes == -1) {
        perror("Failed to open " FILENAME);
        exit(1);
    }
    struct stat fs;
    if (fstat(fdes, &fs) == -1) {
        perror("Failed to get size of " FILENAME);
        exit(1);
    }

    char *start = malloc(fs.st_size+1);
    if (!start) {
        perror("Failed to allocate dictionary buffer");
        exit(1);
    }

    ssize_t nread = read(fdes, start, fs.st_size);
    if (nread != fs.st_size) {
        perror("Failed to read " FILENAME);
        exit(1);
    }

    *end = start + fs.st_size;
    start[fs.st_size] = '\0';
    return start;
}

static int upper_and_len(char *restrict str) {
    // Capitalize all letters, find non-printable newline
    int n;
    for (n = 0; str[n] >= ' '; n++)
        if (str[n] >= 'a' && str[n] <= 'z')
            str[n] &= ~('A' ^ 'a');
    str[n] = '\0'; // Replace newline with null
    return n;      // Return length of string to the null
}

int main() {
    for (Pet *p = pets; p < pets+N_PETS; p++)
        init_pet(p);

    int *counts = aligned_alloc(16, N_COUNT_BYTES);
    if (!counts) {
        perror("Failed to allocate working memory buffer");
        exit(1);
    }

    const char *words_end;
    int wlen;
    for (char *word = read_file(&words_end); word < words_end; word += wlen + 1) {
        wlen = upper_and_len(word);
        for (Pet *p = pets; p < pets+N_PETS; p++)
            if (compare(p, word, wlen, counts))
                    printf("%s -> %s = %s Pet\n",
                        word, p->name, p->common ? "Common" : "Uncommon");
    }

    return 0;
}
| improve this answer | |
\$\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.