Find Anagrams in the Dictionary

Question

This a code challenge. The winner will be the person to provide the most efficient implementation of the solution in terms of algorithmic complexity.

Using the dictionary found in '/usr/share/dict' (on OS X and Linux), your task is to find the word with the most anagrams of itself in the dictionary, and print all of the words that are the anagrams.

Answer 1

Python 2

Efficient to write, and reasonably efficient to run.

groups = {}
for word in open('/usr/share/dict/words'):
    word = word.strip()
    signature = ''.join(sorted(list(word)))
    if signature not in groups:
        groups[signature]=[]
    groups[signature].append(word)
anagrams = groups.values()
maxlen = max(len(x) for x in anagrams)
for group in (x for x in anagrams if len(x) == maxlen):
    print ' '.join(sorted(group))

produces:

carets caster caters crates reacts recast traces
pares parse pears rapes reaps spare spear

in about 0.4 seconds.

The algorithm has O(n) complexity. The full word list is processed in 0.42 seconds. A half-size word list is processed in the expected 0.21 seconds.

Answer 2

C++ 14 - 0.077 seconds for 52875 words

---

Code:

#include <thread>
#include <mutex>
#include <string>
#include <map>
#include <vector>
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;


void thread_func(mutex& file_lock, mutex& map_lock, map<string, vector<string>>& anagrams, ifstream& file) {
    string word;
    string sorted_word;
    while (true) {
        {
            lock_guard<mutex> locker(file_lock);
            if (file.eof()) {
                return;
            }
            file >> word;
        }
        sorted_word = word;
        sort(sorted_word.begin(), sorted_word.end());
        {
            lock_guard<mutex> locker(map_lock);
            anagrams[sorted_word].push_back(word);
        }
    }
}

void nothread_func(map<string, vector<string>>& anagrams, ifstream& file) {
    string word;
    string sorted_word;
    while (true) {
        if (file.eof()) {
            return;
        }
        file >> word;
        sorted_word = word;
        sort(sorted_word.begin(), sorted_word.end());
        anagrams[sorted_word].push_back(word);
    }
}

int main(int argc, char *argv[]) {
    string fname = "/usr/share/dict/words";
    int number_of_threads = 1;

    if (argc > 1) {
        fname = argv[1];
    }
    if (argc > 2) {
        number_of_threads = atoi(argv[2]);
    }

    mutex file_lock;
    mutex map_lock;
    map<string, vector<string>> anagrams;
    cout << "Opening file '" << fname << "'" << endl;
    ifstream file(fname);
    if (!file) {
        cerr << "Could not open file" << endl;
        return 1;
    }
    if (number_of_threads == 1) {
        nothread_func(anagrams, file);
    }
    else {
        cout << "Starting " << number_of_threads << " threads" << endl;

        vector<thread> threads;
        for (int i = 0; i < number_of_threads; ++i) {
            thread th(thread_func, ref(file_lock), ref(map_lock), ref(anagrams), ref(file));
            threads.push_back(move(th));
        }
        for (auto& thread : threads) {
            thread.join();
        }
        cout << "Threads done" << endl;
    }
    int largest_size = max_element(anagrams.begin(), anagrams.end(), [](const auto& a, const auto& b){return a.second.size() < b.second.size();})->second.size();
    for (auto p : anagrams) {
        if (p.second.size() == largest_size) {
            for (auto word : p.second) {
                cout << word << " ";
            }
            cout << endl;
        }
    }
}

Compile: g++ anagrams.cpp -o anagrams --std=c++14 -pthread -ggdb -O3

CLI: ./anagrams <wordfile, defaults to /usr/share/dict/words> <number of threads, defaults to 1>

Example:

$ wc -l /usr/share/dict/cracklib-small
52875 /usr/share/dict/cracklib-small
$ time ./anagrams /usr/share/dict/cracklib-small
Opening file '/usr/share/dict/cracklib-small'
caret carte cater crate react recta trace 
pares parse pears rapes reaps spare spear 

real    0m0.077s
user    0m0.073s
sys     0m0.000s

The code does have multithreaded built in, but it slows things down on my system. Might be useful on slower systems / bigger files. If the number of threads is 1, it disables threads and does everything normally. Algorithm is essentially the same as CarpetPython's, but my code is slightly longer (well, 81 lines).