title: Same word when missing letters

text:
# Question
Title: Same word when missing letters
### Idea

From a **given** word dictionary (containing only plain letters, i.e: no accent or other special chars), with a **given** fixed word length, find every *same* when a **given** number letters are missing.

For sample: `un--ed` could match: `united, untied or unused`

> Using my dictionnary: */usr/share/dict/american-english*, searching for *same* 6 letters words, having 2 letters missing let me find:
>
> * 19242 different possible combination (shapes),
> * The most matching shape is `-a-ing`, that will match `saving, gaming, hating` and more than 80 other words
> * There is 11209 matching shapes for which only two words match, like `-hre-d` that would only match `shrewd` or `thread`.

The goal of this challenge is to write the most efficient algorithm (and implement them in any language) for

1. extract all given fixed length words from a dictionnary
2. find all possible multiple words that could be match same shape containing a given fixed number of missing letter.
3. Sort and present output from the *most matching shape* to the *less matching shape*.

There are 3 variables:

1. Dictionnary file name (could be *STDIN*)
2. Fixed words length
3. Number of missing chars

This could be transmitted in any way you may find usefull.

### Samples

A quick sample could better explain: Searching for same shape of 18 letters, having 2 missing letters give only one match:

```
same /usr/share/dict/american-english 18 2
electrocardiogra--: electrocardiograms,electrocardiograph

```

or

```
same /usr/share/dict/american-english 8 2
17: --ddling: coddling,cuddling,diddling,fiddling,fuddling,huddling,meddling,middling,muddling,paddling,peddling,piddling,puddling,riddling,saddling,toddling,waddling
17: -us-iest: bushiest,cushiest,duskiest,dustiest,fussiest,fustiest,gushiest,gustiest,huskiest,lustiest,mushiest,muskiest,mussiest,mustiest,pushiest,pussiest,rustiest
16: --tching: batching,bitching,botching,catching,ditching,fetching,hatching,hitching,latching,matching,notching,patching,pitching,retching,watching,witching
15: sta--ing: stabbing,stabling,stacking,staffing,staining,stalking,stalling,stamping,standing,stapling,starling,starring,starting,starving,stashing
15: --ttered: battered,bettered,buttered,fettered,guttered,lettered,littered,mattered,muttered,pattered,pottered,puttered,tattered,tittered,tottered
...
 2: -e-onate: detonate,resonate
 2: c-mmune-: communed,communes
 2: trou-le-: troubled,troubles
 2: l-t-rals: laterals,literals
 2: sp-ci-us: spacious,specious
 2: -oardi-g: boarding,hoarding
 2: pre-ide-: presided,presides
 2: blen-he-: blenched,blenches
 2: sw-llin-: swelling,swilling
 2: p-uc-ing: plucking,pouching

```

or

> The shape `---l-` match `hello` and `world` as well as 297 other words.:
>
> ```
> same /usr/share/dict/american-english 5 4 |
>     sed -ne '/hello/{s/^ *\([0-9]*: [a-z-]*\):.*,world,.*$/\1/p}'
> 299: ---l-
>
> ```

### Test file

For testing, I've posted this 62861 length extract from my dict file in plain ascii, useable from *jsfiddle*, *jsbin* or even from your filesystem (because of the directive *access-control-allow-origin*) ( sample: @edc65 answer, with *score* count ).

### Ranking

This is a *fastest algorithm* challenge.

The goal of this is to find quickest way for building shape, making comparissions and sorting list.

But the natural speed of language have to not be matter. So if a solution using is slower, but simplier, using more efficient algorithm than another based solution, the simplier (maybe slower) have to win.

The score is the number of logical steps required by the whole job, using any dictionary file (my personal english dictionary: `wc -l /usr/share/dict/american-english -> 99171`) and different combinations of word length and number of missing letters.

The lowest score win.

# Answer
> 6 votes
# C++11

Excuse the variable names.

Calculates hamming distance between each pair of words then tries replacing characters in words with '-', and calculates hamming distance between the word with '-' and the words without (that had a low enough hamming distance). See comments for details.

```
#include <algorithm>
#include <cassert>
#include <cstdio>
#include <fstream>
#include <ios>
#include <iostream>
#include <map>
#include <string>
#include <utility>
#include <vector>

// Calculates hamming distance between a and b, both of which are length m
inline int fries(const std::string &a, const std::string &b, int m){
    int c = 0;
    for(int i = 0; i < m; ++i)
        a[i]==b[i] || ++c;
    return c;
}
using namespace std;

int main(int eggs, char **bagels){
    ios_base::sync_with_stdio(false);
    // make sure proper number of arguments are passed
    assert(eggs == 4);

    int m, k;
    // read in m (word length) and k (number of '-'s)
    sscanf(bagels[2], "%i", &m);
    sscanf(bagels[3], "%i", &k);

    // bacon will store all words that are of length m
    vector<string> bacon;
    bacon.reserve(500000);

    // Save only words that are of length m
    ifstream milk(bagels[1]);
    {
        string toast;
        while(getline(milk, toast))
            if(toast.length() == m)
                bacon.push_back(toast);
    }

    // ham[i] will store the indices of strings with a hamming distance from bacon[i] that is at most k
    vector<vector<int>> ham(bacon.size());

    // Calculate hamming distance, if <=k, add to ham.
    for(int i = 0, sz = bacon.size(); i < sz; ++i){
        // Uses i+1 to ensure each PAIR is only checked once
        for(int j = i+1; j < sz; ++j){
            unsigned strip = fries(bacon[i], bacon[j], m);
            if(strip && strip <= k)
                ham[i].push_back(j);
        }
    }

    // cereal[string], where string is the matching shape, and the vector is a vector of indices of strings that are matched by string
    map<string, vector<int>> cereal;
    for(int i = 0, sz = ham.size(); i < sz; ++i){
        // skip words that are not similar enough to other words
        if(ham[i].size() == 0) continue;

        // Iterate through all versions of bacon[i] with k '-'s
        // THIS ONLY ITERATES THROUGH COMBINATIONS NOT PERMUTATIONS
        vector<bool> cream(m);
        fill(cream.begin()+k,cream.end(),true);
        do{
            std::string juice = bacon[i];
            // Add in '-'s
            for(int i = 0; i < m; ++i){
                if(!cream[i]) juice[i] = '-';
            }
            // Ensure that this pattern has not yet been processed
            if(!cereal.count(juice)){
                // For each of the words with hamming distance<=k, check hamming distance with the matching shape
                // If hamming distance == k, then it matches, so save to cereal
                for(int j = 0, ssz = ham[i].size(); j < ssz; ++j){
                    if(fries(juice, bacon[ham[i][j]], m) == k)
                        cereal[juice].push_back(ham[i][j]);
                }
                // In the case that there ARE matches, put the index of the original string at the end
                if(cereal.count(juice))
                    cereal[juice].push_back(i);
            }
        }while(next_permutation(cream.begin(), cream.end()));
    }
    // Sorts all the matching shapes by number of matches
    vector<pair<string, vector<int>>> orange_juice;
    copy(cereal.begin(), cereal.end(), back_inserter(orange_juice));
    sort(orange_juice.begin(), orange_juice.end(), [](const pair<string, vector<int>> &a, const pair<string, vector<int>> &b){
        return a.second.size() > b.second.size();
    });
    // Iterate through sorted matching shapes, print
    for(auto cake:orange_juice){
        // bacon[cake.second.back()] is the original string from which the pattern was derived
        cout << cake.second.size() << ": " << cake.first << ": " << bacon[cake.second.back()];
        // do not print original string twice
        cake.second.pop_back();
        // print other strings
        for(auto coffee:cake.second){
            cout << "," << bacon[coffee];
        }
        cout << "\n";
    }
    return 0;
}

```

# Answer
> 4 votes
## C++,

*Where **l** is the word length, **m** is the number of "wildcards" (or dashes) and **n** is the number of words (of length **l**.)*

Skimming over the submissions, it seems that they're all either inherently quadratic with the number of words or are *very* liberal with their use of resources, while there is a very straight-forward O(n log n) solution: For every possible pattern (l choose m), sort the word list (n log n) while ignoring the masked-out letters (l - m). Now all the words that compare equal (modulo masked-out letters) are grouped together and can be collected with a linear scan. This not only scales better but is also very easy to parallelize over different patterns.

Another thing worth noting, I bet most of the submissions spend a significant amount of time just doing I/O. Buffer more and avoid I/O like the plague.

Compile with: `g++ wildcards.cpp -owildcards -std=c++11 -pthread -O3`.

Run with: `./wildcards <word-list> <l> <m>`.

```
#define THREAD_COUNT 2
#define WILDCARD '-'

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <iterator>
#include <algorithm>
#include <utility>
#include <thread>
#include <atomic>
#include <sstream>
#include <cstdlib>
#include <cstddef>

using namespace std;

/* Writes an integer to a string. */
template <typename String, typename T>
void write_int(String& str, T n) {
    if (n < 0) {
        str += '-';
        n = -n;
    }
    int p10 = 1;
    for (T m = n; m; m /= 10, p10 *= 10);
    if (p10 > 1) p10 /= 10;
    for (; p10; p10 /= 10) str += '0' + (n / p10 % 10);
}

/* Function object that lexicographically compares a starting segment of two
 * containers. */
struct fixed_size_lexicographical_compare {
    /* Starting segment size. */
    size_t size;

    explicit fixed_size_lexicographical_compare(size_t size): size(size) {}

    /* If we ever actually need a generic version... */
    template <typename Container>
    bool operator()(const Container& x, const Container& y) const = delete;
    /* Fast specialized case for strings. */
    bool operator()(const char* x, const char* y) const {
        for (size_t i = 0; i < size; ++i) {
            int c = x[i] - y[i];
            if (c) return c < 0;
        }
        return false;
    }
};

/* A pattern is an array of boolean values (avoiding the dreaded vector<bool>)
 * where a truth value represensts a wildcard. */
typedef vector<char> pattern_type;
typedef vector<pattern_type> patterns_type;
/* We ues a buffer of type `word_data_type` to hold all the word data in one big
 * chunk, and a separate array of type `words_type` to point to individual words
 * in the buffer. */
typedef vector<char> word_data_type;
typedef vector<const char*> words_type;
/* The result type. */
struct result {
    /* The pattern and matching set of words. */
    const pattern_type* pattern;
    const words_type* word_list;
    /* Index range into word_list. */
    pair<size_t, size_t> words;

    words_type::const_iterator begin() const {
        return next(word_list->begin(), words.first);
    }
    words_type::const_iterator end() const {
        return next(word_list->begin(), words.second);
    }
    size_t size() const { return words.second - words.first; }

    /* Write the result to a string. */
    void write(string& str) const {
        size_t word_length = pattern->size();
        write_int(str, size());
        str += ": "; {
            const char* w = *begin();
            for (size_t i = 0; i < word_length; ++i)
                str += (*pattern)[i] ? WILDCARD : w[i];
        }
        str += ':';
        for (const char* w : *this) {
            str += ' ';
            copy(w, w + word_length, back_inserter(str));
        }
        str += '\n';
    }
};
typedef vector<result> results_type;

/* Thread context. */
struct context {
    size_t word_length, wildcards;
    const patterns_type* patterns;
    atomic<size_t>* next_pattern;
    const word_data_type* word_data;
    results_type results;
    words_type result_words;
};
void thread_proc(context& ctx) {
    const char* ctx_word_data = &ctx.word_data->front();
    const size_t ctx_word_data_size = ctx.word_data->size();

    const size_t word_length = ctx.word_length, wildcards = ctx.wildcards;
    const size_t masked_word_length = word_length - wildcards;
    const size_t word_count = ctx_word_data_size / word_length;

    /* For each pattern, we make a copy of the word data buffer without the
     * masked out letters. We can already allocate space for the buffer and
     * initialize the array of pointers into the buffer. */
    word_data_type word_data(word_count * masked_word_length);
    words_type words;
    words.reserve(word_count);
    for (auto i = word_data.begin(); i != word_data.end(); i += masked_word_length)
        words.push_back(&*i);

    while (true) {
        /* Grab a pattern. */
        size_t pattern_index; {
            pattern_index = (*ctx.next_pattern)++;
            if (pattern_index >= ctx.patterns->size())
                break;
        }
        const pattern_type& pattern = (*ctx.patterns)[pattern_index];

        /* Copy the word data while skipping the wildcards. */
        for (size_t i = 0, j = 0; i < ctx_word_data_size; ++i) {
            if (!pattern[i % word_length])
                word_data[j++] = ctx_word_data[i];
        }
        /* Sort the words. */
        sort(
            words.begin(), words.end(),
            fixed_size_lexicographical_compare(masked_word_length)
        );

        /* Traverse the list of words while ... */
        for (auto i = words.begin(); i != words.end(); ) {
            /* ... looking for adjacent words that compare equal (when
             * masked.) */
            auto j = find_if(
                next(i), words.end(),
                bind(
                    fixed_size_lexicographical_compare(masked_word_length),
                    *i, placeholders::_1
                )
            );
            /* If more than one word compares equal, add a result. */
            if (j != next(i)) {
                size_t begin_index = ctx.result_words.size();
                for (; i != j; ++i)
                    /* Make sure to index the word from the global word buffer,
                     * not the local copy. */
                    ctx.result_words.push_back(
                        ctx_word_data +
                        (*i - &word_data.front()) / masked_word_length * word_length
                    );
                /* Sort the words alphabetically (not really part of the
                 * algorithm, just for neatness.) */
                sort(
                    next(ctx.result_words.begin(), begin_index), ctx.result_words.end(),
                    fixed_size_lexicographical_compare(word_length)
                );
                ctx.results.push_back(
                    {&pattern, &ctx.result_words, {begin_index, ctx.result_words.size()}}
                );
            } else
                i = j;
        }
    }
}

int main(int argc, const char* argv[]) {
    ios_base::sync_with_stdio(false);

    if (argc != 4) {
        cerr << "Wrong number of arguments" << endl;
        return 1;
    }

    int word_length = atoi(argv[2]), wildcards = atoi(argv[3]);
    if (word_length <= 0 || wildcards <= 0 || word_length < wildcards) {
        cerr << "Invalid arguments" << endl;
        return 1;
    }

    /* Generate all possible patterns. */
    patterns_type patterns; {
        pattern_type pattern(word_length);
        fill_n(pattern.begin(), wildcards, true);
        do
            patterns.push_back(pattern);
        while (prev_permutation(pattern.begin(), pattern.end()));
    }

    /* Read the word list. */
    clog << "Reading word list..." << endl;
    word_data_type word_data; {
        string word;
        ifstream file(argv[1]);
        if (!file.is_open()) {
            cerr << "Failed to open `" << argv[1] << "'" << endl;
            return 1;
        }
        while (getline(file, word)) {
            if (word.size() == word_length)
                /* Add the word to the end of the buffer. */
                move(word.begin(), word.end(), back_inserter(word_data));
        }
    }

    context ctx[THREAD_COUNT];
    thread threads[THREAD_COUNT];
    results_type results;
    atomic<size_t> next_pattern(0);

    /* Run the threads. */
    clog << "Searching..." << endl;
    for (int i = 0; i < THREAD_COUNT; ++i) {
        ctx[i].word_length = size_t(word_length);
        ctx[i].wildcards = size_t(wildcards);
        ctx[i].patterns = &patterns;
        ctx[i].next_pattern = &next_pattern;
        ctx[i].word_data = &word_data;
        threads[i] = thread(thread_proc, ref(ctx[i]));
    }
    /* Collect the results. */
    for (int i = 0; i < THREAD_COUNT; ++i) {
        threads[i].join();
        results.reserve(results.size() + ctx[i].results.size());
        move(ctx[i].results.begin(), ctx[i].results.end(), back_inserter(results));
        results_type().swap(ctx[i].results);
    }
    sort(
        results.begin(), results.end(),
        [] (const result& r1, const result& r2) { return r1.size() > r2.size(); }
    );
    /* Print the results. */
    clog << "Writing results..." << endl; {
        string str;
        for (const result& r : results) {
            r.write(str);
            if (str.size() >= (1 << 20)) {
                cout << str;
                str.clear();
            }
        }
        cout << str;
    }
}

```

# Answer
> 3 votes
# JavaScript ~~(E6)~~ \+ HTML or C# console or C++ console

**Edit 3** At last, here is the C++ version. It's not exactly C++11 as it compiles with Visual Studio 2010, but requires -std=c++11 with gcc. Compiled with max optimization and 64bit is marginally faster than C#. Time for 11,3 is ~7 sec
Sorry, no funny variable names, but on the other hand it's at least 10 times faster of the other C++ answer.
Side note: many C++ libraries have weak hashing functions, that cause more collisons and bad performance using hash tables. I included in the C++ source one of the better hashing functions freely available.

**Edit 2** Added an implementation in C# - same algorithm, no parallelism - Time for 11,3 is ~11.5 sec

**Edit** Removed dependencies on EcmaScript 6, Chrome is *really* faster:

For 18,2 found 965 in 80sec

```
chlorophylli-e-ous:3:chlorophylliferous,chlorophylligenous,chlorophylligerous
intercommunicati--:3:intercommunicating,intercommunication,intercommunicative
non--structiveness:3:nondestructiveness,noninstructiveness,nonobstructiveness
oversentimentali--:3:oversentimentalism,oversentimentality,oversentimentalize
transubstantiati--:3:transubstantiating,transubstantiation,transubstantiative
...

```

Using a hashtable (a javascript object). It is quite fast beeing a scripting language.
The score ... uuu ... help!!!

Time for 11,3 with my huge 351k word list is 4min 10sec

Problems (for javascript version)

1. needs to load the dictionary from local storage, so I can't make a jsfiddle. It works locally opening the file with any compatible browser (even a recent MSIE will do well)
2. hits the time limit for javascript execution in some browser (that I already keep high to 1 minute)

Next time I'll try in C++

**Javascript Code**

```
<!DOCTYPE html>
<html>
<head>
<title>Same word when missing letters</title>
</head>
<body>
Load dictionary<input type="file" id="dictinput" /><span id="spWords"></span><br>
Word size: <input id="tbWordSize"><br>
Missing letters: <input id="tbLetters"><br>
<button id="gobutton" onclick="go()">GO</button><br>
<div id="Info" style="width:95%"></div>
<pre id="Output" style="width:95%; height: 600px; overflow: auto; border: 1px solid #000"></pre>
<script type="text/javascript">
var words
  function readWordFile(evt) {
    var f = evt.target.files[0];
    if (f) {
      var r = new FileReader();
      r.onload = function(e) {
          words = e.target.result.match(/[a-z]+/gi)
        console.log( "Got the file " + f.name + "\nWords " + words.length);
                document.getElementById('spWords').innerHTML = 'Words: ' + words.length;

      }
      r.readAsText(f);
    } else {
      console.log   ("Failed to load file");
    }
  }

  function bitcount(u) {
    for (var n=0; u; ++n, u=u&(u-1));
    return n;
  }

  function elab(word, mask, wordSize, letters, store)
  {
    var chars, p, bit
    for (; --mask;)
    {
      if (bitcount(mask) == letters)
      {
        chars='';
        for (bit=1, p = 0; p < wordSize; p++, bit+=bit)
        {
          chars += bit & mask ? '-' : word[p];
        }
        if (!store[chars]) store[chars] = [];
        store[chars].push(word);
      }
    }
  }

  function go()
  {
    document.getElementById('Output').innerHTML = '...';
    document.getElementById('Info').innerHTML = '...running...';
    store = {};

    setTimeout( function() {
      var tstop, tstart = new Date;
      var wordSize = document.getElementById('tbWordSize').value;
      var letters = document.getElementById('tbLetters').value;
      var result, found, i, mask;
      console.log(tstart);
      console.log(wordSize, letters, words.length);

      mask = 1<<wordSize;
      for (i = 0; i < words.length; i++)
      {
        if (words[i].length == wordSize)
          elab(words[i], mask, wordSize, letters, store);
      }
      keys = Object.keys(store);
      keys.sort(function(a,b) { return store[b].length - store[a].length});
      tstop = new Date;
      console.log(tstop);
      console.log('Time to scan (ms) '+ (tstop-tstart));

      found = 0;
      result = keys.map(function(key) { return store[key][1] ? (found++, key + ':' + store[key].length + ':' + store[key] + '\n'): ''});

      document.getElementById('Output').innerHTML = result.join('');
      tstop = new Date;
      console.log(tstop);
      console.log('Total ' + found + ' time (ms) ' + (tstop-tstart));

      document.getElementById('Info').innerHTML = "#Found " + found + " in time (ms) " + (tstop-tstart);
    }, 100);
  }
  document.getElementById('dictinput').addEventListener('change', readWordFile, false);
</script>
</body>
</html>

```

**C# Code**

```
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

namespace SameWord
{
    class Program
    {
        Dictionary<String, List<String>> store = new Dictionary<string, List<string>>(100000); // start big

        string wordfile;
        int wordsize;
        int letters;
        int tmask;

        Program(string[] args)
        {
            wordfile = args[0];
            wordsize = Convert.ToInt32(args[1]);
            letters = Convert.ToInt32(args[2]);
            tmask = 1 << wordsize;
        }

        void Dowork()
        {
            DateTime start = DateTime.UtcNow;
            String word;
            using (StreamReader input = new StreamReader(wordfile))
            {
                while ((word = input.ReadLine()) != null)
                {
                    if (word.Length == wordsize)
                    {
                        Elab(word);
                    }
                }
            }

            var results = store
              .Where(x => x.Value.Count > 1)
              .OrderByDescending(x => x.Value.Count)
              .Select(x => new { x.Key, x.Value });
            int found = 0;
            using (StreamWriter output = new StreamWriter(wordfile + "." + wordsize + "." + letters + ".txt"))
            {
                foreach (var line in results)
                {
                    found++;
                    output.WriteLine(line.Key + ":" + line.Value.Count + ":" + String.Join(",", line.Value));
                }
            }
            Console.WriteLine("Time {0}. Found {1}", DateTime.UtcNow - start, found);
        }

        int BitCount(int u)
        {
            int n;
            for (n = 0; u > 0; ++n, u = u & (u-1));
            return n;
        }

        void Elab(string word)
        {
            for(int mask = tmask; --mask > 0; )
            {
                if (BitCount(mask) == letters)
                {
                    int p, bit;
                    var chars = word.ToCharArray();
                    for (bit = 1, p = 0; bit <= mask; p++, bit += bit)
                    {
                        if ((bit & mask) != 0) chars[p] = '-';
                    }
                    string key = new String(chars);
                    List<String> wordskey;

                    if (!store.TryGetValue(key, out wordskey))
                    {
                        store.Add(key, wordskey = new List<String>());
                    }
                    wordskey.Add(word);
                }
            }
        }

        static void Main(string[] args)
        {
            new Program(args).Dowork();
        }
    }
}

```

**C++ Code**

```
#include <stdio.h>
#include <stdint.h>

#include <string>
#include <unordered_map>
#include <forward_list>
#include <list>
#include <vector>
#include <iostream>
#include <iomanip>
#include <fstream>
#include <sstream>
#include <ctime>

using namespace std;

// SuperFastHash by Paul Hsieh 2008

#define get16bits(d) (*((const uint16_t *) (d)))

    uint32_t SuperFastHash (const char * data, int len) {
    uint32_t hash = len, tmp;
    int rem;

    if (len <= 0 || data == NULL) return 0;

    rem = len & 3;
    len >>= 2;

    /* Main loop */
    for (;len > 0; len--) {
        hash  += get16bits (data);
        tmp    = (get16bits (data+2) << 11) ^ hash;
        hash   = (hash << 16) ^ tmp;
        data  += 2*sizeof (uint16_t);
        hash  += hash >> 11;
    }

    /* Handle end cases */
    switch (rem) {
        case 3: hash += get16bits (data);
                hash ^= hash << 16;
                hash ^= ((signed char)data[sizeof (uint16_t)]) << 18;
                hash += hash >> 11;
                break;
        case 2: hash += get16bits (data);
                hash ^= hash << 11;
                hash += hash >> 17;
                break;
        case 1: hash += (signed char)*data;
                hash ^= hash << 10;
                hash += hash >> 1;
    }

    /* Force "avalanching" of final 127 bits */
    hash ^= hash << 3;
    hash += hash >> 5;
    hash ^= hash << 4;
    hash += hash >> 17;
    hash ^= hash << 25;
    hash += hash >> 6;

    return hash;
}

size_t fast_hash( const string & value )
{
    return SuperFastHash(value.data(), value.length());
}

typedef unordered_map<string, vector<string>, decltype(&fast_hash)> MyStore;
MyStore store(100000, fast_hash);

int wordSize, letters;

int BitCount(int u)
{
    int n;
    for (n = 0; u; ++n, u = u & (u-1));
    return n;
}

void Elab(string word)
{
    char chars[100];
    for(int mask = 1<<wordSize; --mask; )
    {
        if (BitCount(mask) == letters)
        {
            int p, bit;
            const char *wdata = word.data();
            for (bit = 1, p = 0; p < wordSize; p++, bit += bit)
            {
                chars[p] = bit & mask ? '-' : wdata[p];
            }
            vector<string> &wordsKey = store[string(chars, wordSize)];
            wordsKey.push_back(word);
        }
    }
}

bool mycomp (const pair<const string,vector<string>> &a, const pair<const string,vector<string>> &b)
{
    return (a.second.size() > b.second.size());
}

int main(int argc, char **argv)
{
    string wordFile = argv[1];
    sscanf(argv[2], "%d", &wordSize);
    sscanf(argv[3], "%d", &letters);

    ifstream infile(wordFile);
    {
        string word;
        while(getline(infile, word))
            if(word.length() == wordSize)
                Elab(word);
    }
    forward_list<pair<const string,vector<string>>> results;
    int found = 0;
    for (MyStore::iterator it = store.begin();  it != store.end(); ++it)
    {
        if (it->second.size() > 1)
        {
            found++;
            results.push_front(*it);
        }
    }
    cerr << "Found " << found << "\n";

    results.sort(mycomp);

    stringstream sf;
    sf << wordFile << '.' << wordSize << '.' << letters << ".txt";
    ofstream outfile(sf.str());

    for(forward_list<pair<const string,vector<string>>>::iterator it = results.begin(); it != results.end(); ++it)
    {
        int size = it->second.size();
        outfile << it->first << ':' << size << ':' << it->second[0];
        for(size_t i = 1; i < size; ++i)
        {
            outfile << ',' << it->second[i];
        }
        outfile << '\n';
    }
}

```

# Answer
> 3 votes
Because this needs more Java Streaming:

Running the unofficial 351k word list at 11, 3 in ~7 seconds, beating the JavaScript version by only 4 minutes and 3 seconds. ;)

**My secret:** instead of comparing every possible strike-out combination for each word, I just calculate the word distance (amount of different letters) between each two words, generate a strike-out word for that match if applicable and add it to an incremental map. In this way only those strike-out words are generated that actually have at least one match.

**Input:** *wordListFile wordSize wordDistanceLimit*

```
public class WordList {

  static boolean acceptableWordDistance(final String a, final String b, final int maxWordDistance) {
    int result = 0;
    for (int i = a.length() - 1; i >= 0; --i) {
      if (a.charAt(i) != b.charAt(i)) {
        ++result;
        if (result > maxWordDistance) {
          return false;
        }
      }
    }
    return (result > 0);
  }

  public static void main(String[] args) throws IOException {
//    args = new String[]{"wordlist.txt", "11", "3"};
    final String fileName = args[0];
    final int wordLength = Integer.parseInt(args[1]);
    final int maxWordDistance = Integer.parseInt(args[2]);

    final List<String> allWords = Files.lines(Paths.get(fileName)).parallel()
            .filter(s -> s.length() == wordLength)
            .distinct()
            .collect(Collectors.toList());

    final HashMap<String, Set<String>> result = new HashMap<>();
    allWords.parallelStream()
            .forEach(a -> {
              allWords.stream()
              .filter(b -> acceptableWordDistance(a, b, maxWordDistance))
              .forEach(b -> {
                final StringBuilder buildA = new StringBuilder(a);
                for (int i = b.length() - 1; i >= 0; --i) {
                  if (buildA.charAt(i) != b.charAt(i)) {
                    buildA.replace(i, i + 1, "-");
                  }
                }
                result.merge(buildA.toString(), new TreeSet<>(Arrays.asList(b)), (list, v) -> {
                  list.addAll(v);
                  return list;
                });
              });
            });

    result.entrySet().parallelStream()
            .sorted((a, b) -> -Integer.compare(a.getValue().size(), b.getValue().size()))
            .forEachOrdered(e -> System.out.println(e.getKey() + ": " + Arrays.toString(e.getValue().toArray())));
  }
}

```

# Answer
> 2 votes
# Python

This is an exceptionally naive approach. Runtime is abysmal for even moderate use cases.

n = number of words of length l

l = length of words

m = number of missing letters (ish)

I think my runtime complexity is O(n\*n\*l\*l\*m).

The slowest internal function is the string masking. I'm not sure of the optimal way to do that in Python. I tried representing words and masks as strings, as lists, and ended up with the method below where words are strings and masks are a list of integer positions.

The algorithm itself could be sped up by filtering out words more effectively than comparing them for every mask.

```
#!/usr/bin/env python

import sys
import itertools

if len(sys.argv)!=4:
    print "Usage: same.py dictionaryfile wordlength missingletters"
    exit(1)

dictionaryfile = sys.argv[1]
wordlength = int(sys.argv[2])
missingletters = int(sys.argv[3])

words = [line.strip() for line in open(dictionaryfile) if line==line.lower() and len(line.strip())==wordlength]

# print words

def mask_string(string,mask):
    new_string = ""
    for i in range(len(string)):
        if i in mask:
            new_string += "-"
        else:
            new_string += string[i]
    return new_string

masks = itertools.permutations(range(wordlength),missingletters)

results = {}

for mask in masks:
    patterns = set()
    for word in words:
        masked_word = mask_string(word,mask)
        if masked_word in patterns:
            continue
        results[masked_word] = set()
        results[masked_word].add(word)
        patterns.add(masked_word)
        for word2 in words:
            masked_word2 = mask_string(word2,mask)
            if masked_word2 == masked_word and word2 != word:
                # print word + " and " + word2 + " match with mask " + "".join(mask)
                results[masked_word].add(word2)

for k,v in sorted(results.items(), key=lambda x: (-len(x[1]),x[0])):
    if len(v)>1:
        print str(len(v)) + ": " + k + ": " + ",".join(v)

```

Sample output for 3,1 (1.8 seconds):

```
19: -at: bat,cat,eat,fat,gat,hat,kat,lat,mat,nat,oat,pat,rat,sat,tat,vat,wat,yat,zat
19: ta-: taa,tab,tad,tae,tag,tai,taj,tal,tam,tan,tao,tap,tar,tat,tau,tav,taw,tax,tay
...
2: zi-: zig,zip
2: zo-: zoa,zoo

```

And for 3,2 (0.5 seconds):

```
237: -a-: aal,aam,baa,bac,bad,bae,bag,bah,bal,bam,ban,bap,bar,bas,bat,baw,bay,cab,cad,cag,cal,cam,can,cap,car,cat,caw,cay,dab,dad,dae,dag,dah,dak,dal,dam,dan,dao,dap,dar,das,daw,day,ean,ear,eat,fad,fae,fag,fam,fan,far,fat,fay,gab,gad,gag,gaj,gal,gam,gan,gap,gar,gas,gat,gau,gaw,gay,gaz,had,hag,hah,hak,ham,han,hao,hap,hat,hau,haw,hay,iao,jab,jag,jam,jap,jar,jaw,jay,kai,kan,kat,kay,lab,lac,lad,lag,lai,lak,lam,lan,lap,lar,las,lat,law,lax,lay,mac,mad,mae,mag,mal,man,mao,map,mar,mas,mat,mau,maw,may,naa,nab,nae,nag,nak,nam,nan,nap,nar,nat,naw,nay,oaf,oak,oam,oar,oat,pac,pad,pah,pal,pam,pan,pap,par,pat,pau,paw,pax,pay,rab,rad,rag,rah,raj,ram,ran,rap,ras,rat,raw,rax,ray,saa,sab,sac,sad,sag,sah,sai,saj,sal,sam,san,sao,sap,sar,sat,saw,sax,say,taa,tab,tad,tae,tag,tai,taj,tal,tam,tan,tao,tap,tar,tat,tau,tav,taw,tax,tay,vag,van,vas,vat,vau,wab,wad,wae,wag,wah,wan,wap,war,was,wat,waw,wax,way,yad,yah,yak,yam,yan,yap,yar,yas,yat,yaw,zac,zad,zag,zak,zar,zat,zax
198: -o-: boa,bob,bod,bog,bom,bon,boo,bop,bor,bot,bow,boy,cob,cod,coe,cog,col,con,coo,cop,cor,cos,cot,cow,cox,coy,coz,dob,doc,dod,doe,dog,dom,don,dop,dor,dos,dot,dow,eon,fob,fod,foe,fog,foo,fop,for,fot,fou,fow,fox,foy,goa,gob,god,gog,goi,gol,gon,goo,gor,gos,got,goy,hob,hod,hoe,hog,hoi,hop,hot,how,hox,hoy,ion,job,joe,jog,jot,jow,joy,koa,kob,koi,kon,kop,kor,kos,kou,loa,lob,lod,lof,log,loo,lop,lot,low,lox,loy,mob,mog,mon,moo,mop,mor,mot,mou,mow,moy,noa,nob,nod,nog,non,nor,not,now,noy,pob,pod,poe,poh,poi,pol,pom,pon,pop,pot,pow,pox,poy,rob,roc,rod,roe,rog,roi,rot,row,rox,sob,soc,sod,soe,sog,soh,sok,sol,son,sop,sot,sou,sov,sow,soy,toa,tod,toe,tog,toi,tol,ton,too,top,tor,tot,tou,tow,tox,toy,voe,vog,vol,vow,wob,wod,woe,wog,won,woo,wop,wot,wow,woy,yoe,yoi,yok,yom,yon,yor,yot,you,yow,yox,yoy,zoa,zoo
...
2: -x-: axe,oxy
2: q--: qua,quo

```

And for 4,2 (39 seconds):

```
146: -a-e: babe,bade,bake,bale,bane,bare,base,bate,baze,cade,cage,cake,came,cane,cape,care,case,cate,cave,dace,dade,dale,dame,dare,date,daze,ease,eave,face,fade,fage,fake,fame,fare,fate,faze,gade,gage,gale,game,gane,gape,gare,gate,gave,gaze,hade,haje,hake,hale,hame,hare,hate,have,haze,jade,jake,jane,jape,kale,kame,lace,lade,lake,lame,lane,late,lave,laze,mace,made,mage,make,male,mane,mare,mate,maze,nace,nake,name,nane,nape,nave,naze,pace,page,pale,pane,pape,pare,pate,pave,race,rage,rake,rame,rane,rape,rare,rase,rate,rave,raze,sabe,sade,safe,sage,sake,sale,same,sane,sare,sate,save,tade,take,tale,tame,tane,tape,tare,tate,tave,vade,vage,vale,vane,vare,vase,wabe,wace,wade,wage,wake,wale,wame,wane,ware,wase,wave,yade,yaje,yale,yare,yate
121: -i-e: aide,aile,aire,bice,bide,bike,bile,bine,bite,cine,cise,cite,cive,dice,dike,dime,dine,dire,dite,dive,fice,fide,fife,fike,file,fine,fire,fise,five,gibe,give,hide,hike,hipe,hire,hive,jibe,jive,kibe,kike,kipe,kite,life,like,lile,lime,line,lire,lite,live,mice,mide,mike,mile,mime,mine,mire,mise,mite,nice,nide,nife,nine,oime,pice,pike,pile,pine,pipe,pise,pize,ribe,rice,ride,rife,rile,rime,rine,ripe,rise,rite,rive,sice,side,sife,sike,sile,sime,sine,sipe,sire,sise,site,size,tice,tide,tige,tile,time,tine,tipe,tire,tite,vice,vile,vine,vire,vise,vive,wice,wide,wife,wile,wime,wine,wipe,wire,wise,wite,wive,yite
...
2: z-z-: zizz,zuza
2: zy--: zyga,zyme

```

# Answer
> 1 votes
# Same shape when missing letters

My approach was to build lists of shapes for counting matches.

There is 3 version of same prototype: first, was usefull to build *charWalk* and a with a link to *JSFIDDLE*.

If execution time differ, all this version have to reach same score.

## perl version

There is my 1st perl version:

```
#!/usr/bin/perl -w

use strict;
use Time::HiRes qw|time|;

my $dict="/usr/share/dict/american-english";
my $fixLen=8;
my $numBlank=2;
$dict = $ARGV[0] if $ARGV[0] && -f $ARGV[0];
$fixLen=$ARGV[1] if $ARGV[1] && $ARGV[1] > 1 && $ARGV[1] <100;
$numBlank=$ARGV[2] if $ARGV[2] && $ARGV[2] > 0 && $ARGV[2] < $fixLen;

my %array;
my $cword;
my %counters;
my $started=time();

sub charWalk {
    my ( $word, $cnt, $lhs ) = @_;
    if ( $cnt gt 1 ) {
        my $ncnt=$cnt-1;
        for my $i ( 0 .. length($word) - $cnt ) {
            charWalk( substr( $word, $i + 1 ), $ncnt,
                $lhs . substr( $word, 0, $i ) . "-" );
        };
    } else {
        for my $i ( 0 .. length($word) - $cnt ) {
            push @{ $array{ $lhs.  substr( $word, 0, $i ).
                "-".  substr( $word, $i + 1 ) } },
              $cword;
        };
    };
}

open my $fh,"<".$dict or die;

while (<$fh>) {
    $counters{'words'}++;
    chomp;
    $cword = $_;
    charWalk( $cword, $numBlank,"" ) if $cword=~/^[a-z]{$fixLen}$/ &&
        $counters{'matchlen'}++;
}
map {
    $counters{'found'}++;
    printf "%2d: %s: %s\n", 1+$#{$array{$_} }, $_, join ",", @{ $array{$_} };
} sort {
    $#{ $array{$b} } <=> $#{ $array{$a} }
} grep {
    $#{ $array{$_} } > 0
} keys %array;

print "Counters: ".join(", ",map {sprintf "%s: %s",$_,$counters{$_}} keys %counters).". Time: ".(time()-$started)."\n";

```

## bash proto for *charWalk*

For the version, I've used an unreasonable small dictionary file by dropping 90% of my smallest dictionary file:

```
 sed -e 'p;N;N;N;N;N;N;N;N;N;d' <testdict.txt >tiny-dict.txt

```

Well, there it is:

```
#!/bin/bash

file=${1:-tiny-dict.txt}
wsiz=${2:-11}
mltr=${3:-3}

charWalk () {
    local word=$1 wlen=${#1} cnt=${2:-1} lhs=$3 pnt;
    [ $cnt -gt $wlen ] && return;
    if [ $cnt -gt 1 ]; then
        for ((pnt=0; pnt<=wlen-cnt; pnt++))
        do
            charWalk ${word:pnt+1} $[cnt-1] $lhs${word:0:pnt}-;
        done;
    else
        for ((pnt=0; pnt<=wlen-cnt; pnt++))
        do
            store[$lhs${word:0:pnt}-${word:pnt+1}]+=" $cword";
        done;
    fi
}

declare -A store=();

while read cword ;do
    charWalk $cword $mltr
  done < <(
    grep "^[a-z]\{$wsiz\}$" <$file
)

count=0
for i in ${!store[@]};do
    if [ ${#store[$i]} -gt $[1+wsiz] ];then
        w=(${store[$i]})
        ((count+=1))
        echo ${#w[@]} $i : ${w[@]}
    fi
done > >( sort -rn )

echo "Found: $count matchs."

```

## javascript

Seeing @edc65 post, I've taked some part of his script to build a JSFIDDLE.

Mainly 3 parts (+HTML):

### charWalk for building all possible pattern

```
function charWalk(word,cnt,lhs) {
    if (cnt>1) {
        var ncnt=cnt-1;
        for (var k=0;k<=word.length-cnt;k++) {
            charWalk(word.substr(k+1),ncnt,lhs+word.substr(0,k)+"-");
        };
    } else {
        for (var k=0;k<=word.length-cnt;k++) {
            if (typeof(gS.shapes[lhs+word.substr(0,k)+"-"+word.substr(k+1)])
                == 'undefined') {
                gS.shapes[lhs+word.substr(0,k)+"-"+word.substr(k+1)]=[];
            };
            gS.shapes[lhs+word.substr(0,k)+"-"+
                      word.substr(k+1)].push(gS.currentWord);
        };
    };
}

```

### Main loop.

```
function go() {
    var wordSize = document.getElementById('tbWordSize').value;
    var letters = document.getElementById('tbLetters').value;
    gS.shapes={};
    for (var i = 0; i < gS.words.length; i++) {
        if (gS.words[i].length == wordSize) {
            gS.currentWord=gS.words[i];
            charWalk(gS.currentWord, letters, "" );
        };
    };
    var keys = Object.keys(gS.shapes).
        filter(
            function(i){
                return gS.shapes[i][1];
            }
        ).sort(
            function(a,b) {
                return gS.shapes[b].length - gS.shapes[a].length;
            }
        );
    var intLen=gS.shapes[keys[0]].length.toFixed(0).length;
    gS.result = keys.map(
        function(key) {
            return gS.shapes[key].length.toFixed(0)+ ' : '+
                key +' : '+ gS.shapes[key];
        });
    document.getElementById('Output').innerHTML = gS.result.join('\n');
};

```

### Init part

```
var gS={sharedDictUrl:'http://cartou.ch/sharedstuff/testdict.txt'};
window.onload=function() {
    var zrequest = new XMLHttpRequest();
    zrequest.open('GET',gS.sharedDictUrl,false);
    zrequest.onload = loadWords; zrequest.send(null);
    document.getElementById('gobutton').addEventListener('click',go);
}
function loadWords(e) {
    gS.words = e.target.responseText.match(/[a-z]+/g);
    document.getElementById('spWords').innerHTML = "Shared dict loaded: " +
        gS.words.length + ' words.)';
};

```

### HTML part

```
<!DOCTYPE html>
<html>
<head>
<title>Same word when missing letters</title>
</head>
<script type="text/javascript" src="same-missing.js"></script>
<body><button id="gobutton">GO</button>
 <span id="spWords">Loading dictionary...</span><br>
 Word size: <input id="tbWordSize" size="3" value="11">
 Missing letters: <input id="tbLetters" size="3" value="3">
 <br>
 <div id="Info">---</div>
 <pre id="Output"></pre>
</body>
</html>

```

# Answer
> 1 votes
# Haskell

Time complexity is O(C(**n**, **m**) * **m** * **L** * **n** \+ **k** log(**k**)), where

* C(n, m) = n ! / ((n - m)! * m !)
* **n**: number of words with length **L**
* **m**: mask count
* **L**: word length
* **k**: number of results

## Steps

* Read and filter words
* Generate all masks, each looks like "0011000"
* For each mask, apply it to all words. For example, applying mask "00110" for word "masks" results in "mas--s".
* Group the words by first applying mask on them and then group by a hashmap.
* For each group, process it and get a result.
* Concat , sort and then print all results.

## Usage

Name the file `wordcalc.hs` and then compile it with

```
ghc -O3 wordcalc.hs

```

Then run it with

```
./wordcalc testdict.txt 11 3

```

Or without arguments, that's profiling

```
./wordcalc

```

## Performence

Tested on my four years old i3 laptop with Archlinux.

```
testdict.txt 11 3 -> Time: 1.639882s Count: 31695
testdict.txt 11 5 -> Time: 5.328377s Count: 217138
wordlist.txt 11 3 -> Time: 18.316671s Count: 323347
wordlist.txt 11 5 -> Time: 63.536398s Count: 2069632

```

## Code

```
import Control.Monad
import Data.Function
import Data.Time.Clock
import Data.List
import qualified Data.HashMap.Strict as Map
import System.Environment
import System.IO

type Dict = [String]
type Mask = [Bool]
data Result = Result Int String [String]

instance Show Result where
  show (Result count mask words) = concat $ [show count, ": ", mask, ": ", concat $ intersperse "," words]

main = do
  args <- getArgs
  if length args == 3 then
    let [dictPath, wordLen, maskCount] = args
    in mapM_ print =<< run dictPath (read wordLen) (read maskCount)
  else
    profile [
      ("testdict.txt", 11, 3)
    , ("testdict.txt", 11, 5)
    , ("wordlist.txt", 11, 3)
    , ("wordlist.txt", 11, 5)
    ]

profile :: [(FilePath, Int, Int)] -> IO ()
profile cases = do
  forM_ cases $ \(path, n, m) -> do
    handle <- openFile ".profile-tmp" WriteMode
    t0 <- getCurrentTime
    results <- run path n m
    mapM_ (hPrint handle) results
    hClose handle
    t1 <- getCurrentTime
    putStrLn . unwords $ [
      path, show n, show m, "->", "Time:", show $ diffUTCTime t1 t0, "Count:", show $ length results]

run :: FilePath -> Int -> Int -> IO [Result]
run dictPath wordLen maskCount = do
  words <- readWords wordLen dictPath
  let sort = sortBy (compare `on` (\(Result c _ _) -> -c))
  let masks = genMasks wordLen maskCount
  return . sort $ calc masks words

readWords :: Int -> FilePath -> IO [String]
readWords n path = return . filter ((==n) . length) . lines =<< readFile path

calc :: [Mask] -> [String] -> [Result]
calc masks words = do
  mask <- masks
  let group = Map.elems . Map.fromListWith (++)
  words' <- group [(applyMask' mask w, [w]) | w <- words]
  let count = length words'
  if count > 1 then
    return $ Result count (applyMask mask . head $ words') words'
  else
    fail ""

genMasks :: Int -> Int -> [Mask]
genMasks n m
  | n < m = []
  | m == 0 = [replicate n False]
  | otherwise = map (True:) (genMasks (n-1) (m-1)) ++ map (False:) (genMasks (n-1) m)

applyMask, applyMask' :: Mask -> String -> String
applyMask = zipWith (\b c -> if b then '-' else c)
applyMask' mask word = [c | (b, c) <- zip mask word, not b]

```

---

## CoffeeScript Version

Try it on jsfiddle.

```
MASK_CHAR = '-'

output = (text) ->
  div = $('#output')
  div.html(div.html() + text + '\n')

clear = () ->
  $('#output').html('')

compare = (a, b) ->
  if a < b then return -1
  if a > b then return 1
  return 0

class Result
  constructor: (@mask, @words) ->
    @count = @words.length

  toString: () ->
    @count + ': ' + @mask + ': ' + @words.join ','

calc = (words, wordLen, maskCount) ->
  words1 = words.filter (w) -> w.length == wordLen
  results = []
  for mask in genMasks(wordLen, maskCount)
    calcForMask(words1, mask, results)
  results.sort (r1, r2) -> - compare(r1.count, r2.count)
  return results.filter (r) -> r.count > 1

applyMask = (mask, word) ->
  ((if mask[i] != MASK_CHAR then word[i] else MASK_CHAR) for i in [0..mask.length-1]).join ''

calcForMask = (words, mask, results) ->
  resultMap = {}
  for word in words
    maskedWord = applyMask(mask, word)
    if not resultMap[maskedWord]?
      resultMap[maskedWord] = [word]
    else
      resultMap[maskedWord].push(word)
  for maskedWord, words of resultMap
    results.push(new Result(maskedWord, words))

genMasks = (n, m) ->
  if n < m then return []
  if m == 0
    if n == 0 then return [[]]
    return [('x' for i in [1..n])]
  use = genMasks(n - 1, m - 1)
  notUse = genMasks(n - 1, m)
  for x in use
    x.push(MASK_CHAR)
  for x in notUse
    x.push('x')
  return use.concat notUse

run = (dictURL, wordLen, maskCount, onStart, onFinish) ->
  $.ajax
    method: 'get'
    url: dictURL
    dataType: 'text'
  .success (data) ->
    output('File size: ' + data.length)
    words = data.match(/[a-z]+/g)
    output('Calculating...')
    onStart(words)
    results = calc(words, wordLen, maskCount)
    onFinish(results)
  .fail (error) ->
    output('Failed to fetch words')
    output('Error: ' + arguments)

profile = (dictURL, wordLen, maskCount) ->
  timer = {}
  clear()
  # output(('-' for i in [1..120]).join '')
  output('Fetching words...')
  onStart = (words) ->
    output('Got ' + words.length + ' words')
    timer.timeStart = new Date()
  onFinish = (results) ->
    timer.timeEnd = new Date()
    timer.time = timer.timeEnd - timer.timeStart
    output('Time used: ' + (timer.time / 1000).toFixed(3) + ' sec')
    output('Count: ' + results.length)
    if $('#output_result').is(':checked')
      output((r.toString() for r in results).join '\n')
    output('Finished')

  run(dictURL, wordLen, maskCount, onStart, onFinish)

$ () ->
  $('#button').click () ->
    profile($('#url').val(), parseInt($('#word_len').val()), parseInt($('#mask_count').val()))
  # $('#button').click()

```

---

## Another version with same algorithm: Python 3

```
import sys
import itertools
from collections import defaultdict

def calc(words, n, m):
    words = [w for w in words if len(w) == n]
    results = []
    for mask in itertools.combinations(range(n), m):
        groups = defaultdict(list)
        for word in words:
            word1 = list(word)
            for i in mask:
                word1[i] = '-'
            word1 = ''.join(word1)
            groups[word1].append(word)
        for word1, words1 in groups.items():
            if len(words1) > 1:
                results.append((len(words1), word1, words1))
    results.sort(key=lambda x: -x[0])
    return results

def main():
    path, n, m = sys.argv[1:]
    words = list(map(str.rstrip, open(path)))
    for c, w, ws in calc(words, int(n), int(m)):
        print('{}: {}: {}'.format(c, w, ','.join(ws)))

main()

```

# Answer
> 1 votes
# C++11

Not quite sure how to define a "logical operation" so I may be a little more/less strict than you'd like, but I gave it a shot.

```
#include <algorithm>
#include <fstream>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <string>
#include <vector>

#include <cstring>

using namespace std;

static size_t _g_score = 0;

typedef vector<char> WordMask;
typedef vector<WordMask> WordMaskList;

typedef list<string const *> WordSet;

struct ScoredString : public string
{
    ScoredString(string s) : string(s) { }
    bool operator <(ScoredString const rhs) const
    {
            _g_score++;
            return strcmp(c_str(), rhs.c_str()) < 0;
    }
};

typedef map<ScoredString, WordSet *> WordMaskMap;

struct WordDatabase
{
    vector<string *> wordList;
    WordMaskMap maskMap;
};

static WordMaskList makeMaskList(int wordLen, int numBlanks);
static WordDatabase createWordDatabase(ifstream &file, int wordLen, WordMaskList const &masks);

int main(int argc, char **argv)
{
    if (argc < 4)
    {
            cout << "Usage:  perms <dict_file> <word_len> <num_blanks>";
            return 1;
    }

    ifstream file(argv[1]);
    if (!file.is_open())
    {
            cerr << "Failed to open dictionary file: [" << argv[1] << "]!" << endl;
            return 1;
    }

    int wordLen = atoi(argv[2]);

    // generate all mask permutations
    WordMaskList masks = makeMaskList(wordLen, atoi(argv[3]));

    // read file and create the database of words and their mappings
    WordDatabase db = createWordDatabase(file, wordLen, masks);

    // iterate the mapping database and created a priority (sorted) queue
    //   using the desired sorting criteria
    struct QueueData
    {
            string const *mask;
            WordSet const *ws;
            size_t wsSz;

            bool operator <(QueueData const rhs) const
            {
                    _g_score++;
                    if (wsSz == rhs.wsSz)
                    {
                            return strcmp(mask->c_str(), rhs.mask->c_str()) < 0 ? false : true;
                    }

                    return wsSz < rhs.wsSz;
            }
    };

    priority_queue<QueueData> q;

    for (auto i = db.maskMap.begin(); i != db.maskMap.end(); ++i)
    {
            if (i->second->size() > 1)
            {
                    QueueData qd = {&i->first, i->second, i->second->size()};
                    q.push(qd);
                    _g_score++;
            }
    }

    // and emit the queue by removing items from it
    while (!q.empty())
    {
            QueueData qd = q.top();
            cout << qd.wsSz << ": " << *(qd.mask) << ": { ";
            for(auto i = qd.ws->begin(); i != qd.ws->end(); ++i)
            {
                    cout << *(*i) << " ";
            }
            cout << "}" << endl;
            q.pop();
            _g_score++;
    }

    cout << endl << "Score:  " << _g_score << endl;
    return 0;
}

static WordMaskList makeMaskList(int wordLen, int numBlanks)
{
    WordMaskList masks;

    WordMask mask(wordLen);

    fill_n(mask.begin(), numBlanks, true);
    do
    {
            masks.push_back(mask);

    } while (prev_permutation(mask.begin(), mask.end()));

    return masks;
}

static void mapMaskedWord(WordMaskMap &mapInto, string const &word, WordMask const &mask)
{
    string mword;
    int i = 0;
    for (auto j=mask.begin(); j != mask.end(); ++j, ++i)
    {
            mword += *j ? '-' : word[i];
    }

    auto wsi = mapInto.find(mword);
    WordSet *ws;
    if (wsi != mapInto.end())
    {
            ws = wsi->second;
    }
    else
    {
            ws = new WordSet();

            mapInto.insert(make_pair(mword, ws));
    }

    ws->push_back(&word);
    _g_score++;
}

static WordDatabase createWordDatabase(ifstream &file, int wordLen, WordMaskList const &masks)
{
    WordDatabase db;
    string word;

    while (getline(file, word))
    {
            db.wordList.push_back(new string(word));

            if (word.size() == wordLen)
            {
                    for (auto mi = masks.begin(); mi != masks.end(); ++mi)
                    {
                            mapMaskedWord(db.maskMap, *(db.wordList.back()), *mi);
                    }
            }
    }

    return db;
}

```

The algoirthm is pretty straight-forward; I create a map of ("mask", word set) pairs as I read the dictionary file. Each word in the dictionary file having a matching length is inserted into the map's sets once per mask permutation. Then I iterate the entire map to create a sorted queue to print. This is filtered by only those map entries whose set has \> 1 element.

I define an operation as:

* any comparison performed by the map/queue to add elements
* any insertion/deletion/iteration

Like I said, I may have been a little more/less lenient. To be honest, I'd prefer just to count the comparisons as that's what you're trying to limit most during the execution.

# Answer
> 0 votes
## Counter draft (Not an answer!)

I would try to use this as draft for final counting.

### Scoreboard

There is a score tab where some try was counter or evaluated, by using shared dictionary file and the pairs (word length , missing chars): (4,1 5,2 11,3 11,9)

```
  Test pairs      4,1              5,2             11,3             11,9

```
* **1?** F.Hauri \- charwalk + hash Fiddle

```
          105 564          289 575        3 329 871        2 849 711

```
* **1?** Ray \- *`O(C(n, m) * m * L * n * log(n))`* \- Fiddle

```
           94 418          467 888       18 231 225        3 572 406

```
* **1?** DarwinBot \- *n log n* based - no fiddle no score.

```
TODO...

```
* **2?** edc65 \- bitcount + hash Fiddle

```
          258 457          992 807       83 344 443       70 071 001

```
* **2?** DreamWarrior \- filtered sorted queue - no fiddle

```
          322 239        1 563 388       55 460 636        8 471 745

```
* **3** es1024 \- eggs, fries milk and cream - Fiddle

```
       14 299 352       75 187 045          aborted        not tried

```
* **4** TwoThe \- parallelStream acceptableWordDistance - Fiddle

```
       22 991 392      112 794 153          aborted        not tried

```
* **5** Sparr \- *exceptionally naive approach* \- (no fiddle)

```
       70 234 852    1 081 946 020          aborted        not tried

```

Nota: There is a big difference between two 1st classified answer:

While pairs using small number seem present @Ray's solution a lot quicker than mine, for big numbers, this become totaly reversed:

```
pairs       2,1      3,2          9,4     18,2         18,8
F.Hauri  63 353   69 279    6 706 593   73 772    4 623 416
Ray         598    7 490   23 065 888   73 416   26 075 903

```

@Ray seem using same aproach than @DarwinBot, but I don't already understand hot it work... I have a lot to work all around, in order to finalize this scoreboard... :-b

### Masks generations

This challenge do contain a strong step: mask or pattern generation.

Now, if 4 answer, there is already 3 (maybe 4, i'm not totally sure) different meaning:

* @Sparr seem doing approx same than @es1024: doing base mask containing *WordLengt*-*missing* letters concatenated with *missing* number of `_`, than iterate over all possible combinations.
* @edc65 use binary based constructions, searching for shapes containing correct number of *missing*
* @TwoThe use a totaly different method where words pairs are knowns and from one pair we just have to search for differences.

If I rightly count, taking for sample `8` char length and `3` missing chars:

* Iterate over 8 chars implie `8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 40320` steps to be *unified*, regardless of missing number chars.
* Building binary masks for 8 chars generate 256 shapes to be filtered for having *missing* number of `0` (or `1` depending on how routine work): 256 shapes + 256 tests + 28 mask creation = 540 steps (et least).

Where, for 8 chars, having 2 missing, there are 28 different *masks*.

In a 1'st day comment @sparr was right when saying *it looks like you already have a solution* ;-)

For comparission, my 1st prototype algoritm was writed. I'ts really easy for counting steps (using `set -x`). So for 8 char length, and

* 1 missing -\> 8 masks, 32 steps
* 2 missing -\> 28 masks, 148 steps
* 3 missing -\> 56 masks, 392 steps
* 4 missing -\> 70 masks, 658 steps
* 5 missing -\> 56 masks, 728 steps
* 6 missing -\> 28 masks, 532 steps
* 7 missing -\> 8 masks, 248 steps

Note: Using `set -x` is very strict for counting steps, as each comparission, test or assing is counted as one step.

### Word iteration

There is mainly two different method:

Where @es1024, @ThoThe and @Sparr use double iteration for making comparission, @edc65 use only one iteration over all words for storing counters based on *shape*.

The second method seem more efficient for a big direcory file. (they was the one I've used in my first try;)

### Algorithm improvement

1. Instead of:

```
 for () { if () { ... } else { ... } }

```

prefer to write:

```
 if () { for () { ... } } else { for () { ... } }

```

whenever possible
2. Same as previous: do filtering over results **before** sorting!

prefer

```
  keys.filter(match).sort().map( printout )

```

than:

```
  keys.sort().map( if (match) { ... } )

```

... if you can.

---
Tags: string, fastest-algorithm, crossword
---


title: Calculate prime gaps

text:
# Question
Title: Calculate prime gaps
Finding primes is a programming rite of passage and very frequently the first serious program someone creates (usually with trial division).

But primes alone are already worn out. A next far more interesting thing is to get the prime gaps: the so-far-longest gaps between consecutive primes. These are quite rare and "precious". A first few pairs and their differences are:

```
2 3 1
3 5 2
7 11 4
23 29 6
89 97 8
113 127 14
...

```

My father used to calculate these by hand for fun up to 10k. Let's see how short a code you can get.

Write a program which goes through primes and produces a line of output every time the difference between two consecutive primes is bigger than that of any two previous consecutive primes.

Your output can either be the two primes followed by their gap, or just the gap. If you choose the later add 10 to your overall score.

For instance, between 3 and 5, there is a gap 2 units wide. The gap between 5 and 7 is also 2, but that's old news, we don't care any more. Only when you see a new biggest gap, you report it. This reflects how the primes are getting less and less frequent, as the gaps become wider and wider.

Rules:

* no builtin functions for prime testing, prime generation or prime gaps
* no retrieving http://oeis.org/A002386 or similar (I can smell you cheaters from far away :) )
* no precomputed arrays
* keep printing until your internal integer type fails on you

Answers are scored in characters, plus the potential 10 penalty. With lower scores being the goal.

You can also show off versions with builtin functions if they are interesting. Be creative.

---

*EDIT*: Most of the answers are brilliant and deserve more recognition. However, so far, a GolfScript entry with 48 characters is the shortest.

# Answer
# GolfScript 66 59 57 49 48

```
[2.0{:d{;\;.{).{(1$1$%}do(}do.2$-.d>!}do].p~.}do

```

Although I'm having trouble running it here http://golfscript.apphb.com/ (maybe that site doesn't like the infinite loop?) but it works fine when I run it on my computer with golfscript.rb. I'm pretty new to GolfScript so this can probably be golfed down even further. UPDATE: I don't think this can be golfed down much more without changing the algorithm somehow.

First few lines printed (If you do not like the "" being printed you can add ; at the beginning of the script, but that bumps it up to 49 chars) :

```
[2 3 1]
["" 3 5 2]
["" 7 11 4]
["" 23 29 6]
["" 89 97 8]
["" 113 127 14]
["" 523 541 18]
["" 887 907 20]
["" 1129 1151 22]
...

```

General human-readable idea of how this works (a few things slightly different since I'm not using a stack in this version) :

```
cur_prime = 2
next_prime = 2
gap = 0

do {
    do {
        cur_prime = next_prime
        do {
            next_prime = next_prime + 1
            possible_factor = next_prime
            do {
                possible_factor = possible_factor - 1
            } while (next_prime % possible_factor > 0)
        } while (possible_factor != 1)
    } while (next_prime - cur_prime <= gap)

    gap = next_prime - cur_prime
    print [cur_prime next_prime gap]
} while (true)

```
> 3 votes

# Answer
## Python, ~~121~~ ~~110~~ ~~109~~ ~~108~~ ~~104~~ 103 characters

```
p,n,m=[2],3,0
while 1:
 if all(n%x for x in p):
  c=n-p[0]
  if m<c:m=c;print(p[0],n,c)
  p=[n]+p
 n+=1

```

First time I tried to answer here, I hope I did it right... not sure I even counted the characters right.

Hmmm, I could save another character on the print by downgrading to Python 2.x...
> 11 votes

# Answer
# JavaScript, 90 85 78 74 chars

**Short Code** (Google Closure Compiler - Advanced Optimizations; some manual edits; more edits by @MT0)

```
for(a=b=2,c=0;b++;)for(d=b;b%--d;)d<3&&(c<b-a&&console.log(a,b,c=b-a),a=b)

```

**Long Code**

```
var lastPrime = 2,
    curNumber = lastPrime,
    maxDistance = 0,
    i;

// check all numbers
while( curNumber++ ) {

  // check for primes
  i = curNumber;
  while( curNumber % --i != 0 ) {}

  // if prime, then i should be equal to one here
  if( i == 1 ) {

    // calc distance
    i=curNumber-lastPrime;

    // new hit
    if( maxDistance < i ) {
      maxDistance = i;
      console.log( lastPrime, curNumber, maxDistance );
    }

    // remember prime
    lastPrime = curNumber;
  }
}

```

**Output**

```
2 3 1
3 5 2
7 11 4
23 29 6
89 97 8
113 127 14
523 541 18
887 907 20
1129 1151 22
1327 1361 34
9551 9587 36
15683 15727 44
19609 19661 52
31397 31469 72
...

```

Pretty inefficient test for primes, but that way it uses less characters.

First post here, so please excuse any mistakes.
> 4 votes

# Answer
# Mathematica, 114 108

Allows infinite output, although after a certain point in the sequence the fan spins up and you begin to suspect that your CPU is playing Freecell while doing its best to look busy.

```
p@x_:=NestWhile[#+1&,x+1,Divisors@#≠{1,#}&];m=0;q=1;While[1<2,If[p@q-q>m,Print@{q,p@q,p@q-q};m=p@q-q];q=p@q]

```

Output sample (These are the ones it picks up in the first ~30s):

```
{1,2,1}
{3,5,2}
{7,11,4}
{23,29,6}
{89,97,8}
{113,127,14}
{523,541,18}
{887,907,20}
{1129,1151,22}
{1327,1361,34}
{9551,9587,36}
{15683,15727,44}
{19609,19661,52}
{31397,31469,72}
{155921,156007,86}
{360653,360749,96}
{370261,370373,112}
{492113,492227,114}
{1349533,1349651,118}
{1357201,1357333,132}
{2010733,2010881,148}

```

Ungolfed code:

```
p@x_ := NestWhile[
   # + 1 &,
   x + 1,
   Divisors@# ≠ {1, #} &];
m = 0;
q = 1;
While[
 1 < 2,
 If[
  p@q - q > m,
  Print@{q, p@q, p@q - q}; m = p@q - q];
 q = p@q]

```
> 3 votes

# Answer
# Haskell - 122 116 114 112 110

```
q=[n|n<-[3..],all((>0).rem n)[2..n-1]]
d m((p,q):b)|q-p>m=print(p,q,q-p)>>d(q-p)b|q>p=d m b
main=d 0$zip(2:q)q

```

(Inefficient) prime list expression stolen from Will Ness.

-edit- I never knew `x|y=z|w=q` would be valid.
> 3 votes

# Answer
## MATLAB ~~104~~ 89

Just implemented the basic method by checking every possible division.

```
a=2;g=0;for n=3:inf;b=n*(sum(mod(n,1:n)<1)<3);h=b-a;if(h>g)g=h;[a,b,h]
end;a=max(a,b);end

```

Output:

```
  2     3     1
  3     5     2
  7    11     4
 23    29     6
 89    97     8
113   127    14
523   541    18
887   907    20

```
> 2 votes

# Answer
# 76 chars, dogelang

Converted from my Python version:

```
g=0
i=l=2
while i+=1=>all$map(i%)(2..i)=>(i-l>g=>(g=i-l),print(l,i,g)),(l=i)

```

Output:

```
(2, 3, 1)
(3, 5, 2)
(7, 11, 4)
(23, 29, 6)
(89, 97, 8)
(113, 127, 14)
(523, 541, 18)
(887, 907, 20)
(1129, 1151, 22)
...

```
> 2 votes

# Answer
# Golfscript, ~~59~~ ~~51~~ 50 chars

Man each character is extremely difficult to lose:

```
0[2.{).,2>{\.@%!},{.2$-.4$>{].p~\[}{;\;}if..}or}do

```

**Output**:

```
[2 3 1]
[3 5 2]
[7 11 4]
[23 29 6]
[89 97 8]
[113 127 14]
...

```

**Explanation**:

The stack is set up so each iteration starts with the stack like this, the top being to the right. The `[` indicates the current array marker, meaning when the interpreter encounters a `]`, everything on the stack from the mark to the top is put into an array.

```
g [ last | cur

```

`g` is the maximum gap so far. From the top down:

```
 command         | explanation
-----------------+----------------------------------------
 0[2.            | initialize vars g=0, last=2, cur=2
 {...}do         | loop forever...

```

Inside the loop:

```
 )               | cur += 1
 .,2>{\.@%!},    | put all divisors of cur into a list
 {...}or         | if the list is empty, cur is prime, so
                 | the block is executed. otherwise,
                 | 'do' consumes the stack, sees it is truthy,
                 | and loops again

```

How does it put all divisors into a list? Let's do it step by step

```
 Command         | explanation                                  | stack
-----------------+----------------------------------------------+----------------
                 | initial stack                                | n
 .,              | make list of 0..n-1                          | n [0,1,...,n-1]
 2>              | take elements at index 2 and greater         | n [2,3,...,n-1]
 {...},          | take list off stack, then iterate through    |
                 | the list. on each iteration, put the current |
                 | element on the stack, execute the block, and |
                 | pop the top of the stack. if the top is      |
                 | true then keep the element, else drop it.    |
                 | when done, push list of all true elements    |
                 | So, for each element...                      | n x
   \.            |   Swap & dup                                 | x n n
   @             |   Bring x around                             | n n x
   %             |   Modulo                                     | n (n%x)
   !             |   Boolean not. 0->1, else->0. Thus this is 1 |
                 |   if x divides n.                            | n (x divides n)
                 | So only the divisors of n are kept           | n [divisors of n]

```

What does it do if the divisors are empty?

```
 Command         | explanation                                  | stack
-----------------+----------------------------------------------+----------------
                 | initial stack                                | g [ last | cur
  .              | dup                                          | g [ l | c | c
  2$             | copy 3rd down                                | g [ l | c | c | l
  -              | sub. This is the current gap, cur-last       | g [ l | c | c-l
  .              | dup                                          | g [ l | c | c-l | c-l
  4$             | copy 4th down                                | g [ l | c | c-l | c-l | g
  >              | is cur gap > max gap so far?                 | g [ l | c | c-l | c-l>g
  {#1}{#2}if..   | #1 if c-l > g, #2 otherwise, and do ".." in  | ... | g [ c | c | c
                 | either situation                             |

```

Two paths: yes and no. If yes (note that `if` consumes the top value on the stack):

```
 Command         | explanation                                  | stack
-----------------+----------------------------------------------+----------------
                 | initial stack. note that now the old `g` is  | XX [ l | c | g
                 | garbage and `c-l` is the new `g`.            |
 ]               | close the array                              | XX [l, c, g]
 .p              | duplicate it and print it, consuming the dup | XX [l, c, g]
 ~               | pump array back onto the stack. Note now the | XX | l | c | j
                 | array marker [ is gone.                      |
 \               | swap.                                        | XX | l | g | c
 [               | mark the array                               | XX | l | g | c [
 .               | this is the part after the if. dups the top, | XX | l | g [ c | c
                 | but it does this in two steps, first popping |
                 | c then putting two copies on top, so the     |
                 | array marker moves                           |
 .               | dup again                                    | XX | l | g [ c | c | c

```

If no:

```
 Command         | explanation                                  | stack
-----------------+----------------------------------------------+----------------
                 | initial stack. In this case g is still the   | g [ l | c | c-l
                 | max gap so far                               |
 ;\;             | dump top of stack, swap, and dump again      | g [ c
 ..              | the part after the if. dup twice             | g [ c | c | c

```

Note in either case, our stack is now in the form `... | g [ c | c | c`.

Now the `do` pops the top value off the stack - always `c` \- and loops if it is positive. Since `c` always increasing, this is always true, so we loop forever.

Once popped, the top of the stack is `g [ c | c`, meaning last has been updated to `c`, the array mark is in the same place, and `g` is still where we expect it.

These are the convoluted operations of GolfScript. I hope you enjoyed following along!
> 2 votes

# Answer
# Ruby, 110

Only for Ruby 2.0 due to the `lazy`method:

```
(2..1.0/0).lazy.select{|n|!(2...n).any?{|m|n%m==0}}.reduce([2,0]){|(l,t),c|d=c-l;p [l,c,d]if d>t;[c,d>t ?d:t]}

```

Output:

```
[2, 3, 1]
[3, 5, 2]
[7, 11, 4]
[23, 29, 6]
[89, 97, 8]
[113, 127, 14]
[523, 541, 18]
[887, 907, 20]
[1129, 1151, 22]
[1327, 1361, 34]
[9551, 9587, 36]
[15683, 15727, 44]
[19609, 19661, 52]
[31397, 31469, 72]
[155921, 156007, 86]
[360653, 360749, 96]
[370261, 370373, 112]
[492113, 492227, 114]
...

```
> 1 votes

# Answer
## Perl, 105 bytes

```
$p=2;$d=0;L:for($i=2;++$i>2;){!($i%$_)&&next L for 2..$i-1;if($i-$p>$d){$d=$i-$p;print"$p $i $d\n"}$p=$i}

```

**Ungolfed:**

```
$p = 2;
$d = 0;
L: for ($i = 2; ++$i > 2; ){
    !($i % $_) && next L for 2..$i-1;
    if ($i - $p > $d) {
        $d = $i - $p;
        print "$p $i $d\n"
    }
    $p = $i
}

```

The algorithm is simple, `$p` remembers the previous prime number. Then `$i` goes from `3` up to, when the type $i "fails on me" or become negative because of overflow. `$i` is tested the crude way by checking all divisors from 2 to `$i-1`. A line is printed, if the current difference is larger than the previous printed difference `$d`.

With some more bytes the run-time can be improved:

```
$p = 2;
$d = 0;
L: for ($i=3; $i > 2; $i += 2){
    for ($j=3; $j <= sqrt($i); $j += 2){
        next L if !($i%$j)
    }
    if ($i - $p > $d) {
        $d = $i - $p;
        print "$p $i $d\n"
    }
    $p = $i
}

```

The **result** starts with:

```
2 3 1
3 5 2
7 11 4
23 29 6
89 97 8
113 127 14
523 541 18
887 907 20
1129 1151 22
1327 1361 34
9551 9587 36
15683 15727 44
19609 19661 52
31397 31469 72
155921 156007 86
360653 360749 96
370261 370373 112
492113 492227 114
1349533 1349651 118
1357201 1357333 132
2010733 2010881 148
4652353 4652507 154
17051707 17051887 180
20831323 20831533 210
47326693 47326913 220
...

```
> 1 votes

# Answer
# Python, ~~93~~ 91 chars

Naive prime checking (check if divisible by anything from 2 to `n` (less chars than to `n/2`)):

```
g=0;i=l=2
while 1:
 i+=1
 if all(i%x for x in range(2,i)):
    if i-l>g:g=i-l;print l,i,g
    l=i

```

Second level of indent is one tab character.

Output:

```
2 3 1
5 7 2
7 11 4
23 29 6
89 97 8
113 127 14
523 541 18
...

```
> 1 votes

# Answer
# **Bash and some Perl for prime regex (167 157 143 112 bytes)**

```
n=2
c=2
while p=$c
do perl -e\(1x$[++n]')=~/^(11+?)\1+$/&&exit 1'&&c=$n
((c-p>g))&&g=$[c-p]&&echo $p $c $g
done

```

some output:

```
$./golfd.sh
2 3 1
3 5 2
7 11 4
23 29 6
89 97 8
113 127 14
523 541 18
887 907 20
1129 1151 22

```
> 1 votes

# Answer
# C: 493 302 272 246

```
int e(int j){for(int i=2;i<j;i++)if(j%i<1)return 0;return 1;}void f(int a,int b,int c){if(e(a)&e(b))if(c<b-a){printf("%d %d %d\n",a,b,b-a);f(a+1,b+1,b-a);}else f(a+1,b+1,c);if(e(b))f(a+1,b,c);if(e(a))f(a,b+1,c);f(a+1,b+1,c);}int main(){f(2,3,0);}

```

I used recursion not the usual loop of `for` or `while`.

```
int isPrime(int num){
    for( int i=2; i<num; i++ )
        if(num%i < 0) return 0;
    return 1;
}
void fun(int n1, int n2, int gap){
   if( isPrime(n1) & isPrime(n2) ){
        if( gap < n2-n1 ){
           printf("%d %d %d\n", n1, n2, n2-n1);
           fun(n1+1, n2+1, n2-n1);
        }else{
           fun(n1+1, n2+1, gap);
        }
   }
   if( isPrime(n2) ){
       fun(n1+1, n2, gap);
   }
   if( isPrime(n1) ){
       fun(n1, n2+1, gap);
   }
   fun(n1+1, n2+1, gap);
}

int main(){
   fun(2,3,0);
}

```

Output:

```
2 3 1
3 5 2
7 11 4
23 29 6
89 97 8
113 127 14
523 541 18
887 907 20
1129 1151 22
1327 1361 34
9551 9587 36
15683 15727 44
19609 19661 52

```
> 1 votes

# Answer
# Perl 95 90 bytes

```
for($n=$c=2;$p=$c;$c-$p>$g&&printf"$p $c %d\n",$g=$c-$p){$c=$n if(1x++$n)!~/^(11+?)\1+$/}

```

old Non golf version:

```
$n=$c=2;
while($p=$c){
    $c=$n if (1x++$n)!~/^(11+?)\1+$/;
    if ($c-$p>$g) {$g=$c-$p;print "$p $c $g\n"}
}

```

This is similar to my other submission, sans bash.
> 1 votes

# Answer
# Oracle SQL, 216 202 196 172 + 10 = 182

Just noticed this in the question:

> Lowest character count wins. +10 characters if you only print the gaps without the primes.

As this is SQL and the keywords are so long it's actually better to take the penalty, giving the following. It's the same idea as the original.

```
with c as(select level+1n from dual connect by level<1e124)select lead(n)over(order by n) from(select*from c a where not exists(select*from c where n<a.n and mod(a.n,n)=0))

```

which prettifies to:

```
with c as (
 select level + 1 n
   from dual
connect by level < 1e124
        )
select lead(n) over ( order by n )
  from ( select *
           from c a
          where not exists( select *
                              from c
                             where n < a.n
                               and mod(a.n, n) = 0
                                   )
                )

```

---

Old answer (196)

```
with c as(select level+1n from dual connect by level<1e124)select n,p,p-n from(select n,lead(n)over(order by n)p from(select*from c a where not exists(select*from c where n<a.n and mod(a.n,n)=0)))

```

and in a readable format:

```
with c as (
 select level + 1 n
   from dual
connect by level < 1e124
        )
select n, p, p-n
  from ( select n, lead(n) over ( order by n ) p
           from ( select *
                    from c a
                   where not exists (
                                select *
                                  from c
                                 where n < a.n
                                   and mod(a.n, n) = 0
                                       )
                         )
                )

```

This creates a number generator in `c`, the innermost sub-select creates the primes numbers using a Sieve of Eratosthenes, the outer works out the previous prime and finally the last select subtract one from the other.

This won't return anything because it's performing 1 x 10 124 recursive queries... So, if you want it to work lower this number to something sensible.
> 1 votes

# Answer
# C (100)

My own contribution, no special algorithm, just golf:

```
i,g,r,p=2;main(){for(;r=p;p-r>g?printf("%d %d %d\n",r,p,g=p-r):0)for(i=0;i-p;)for(i=1,++p;p%++i;);}

```
> 1 votes

# Answer
## Haskell, 134C

Golfed:

```
c n=null[x|x<-[2..n-1],n`mod`x==0]&&n>1
p=filter c[1..]
g l(m:n:o)
 |(n-m)>l=do print(m,n,n-m);g(n-m)(n:o)
 |True=g l(n:o)
main=g 0 p

```

Ungolfed:

```
-- c function checks if n is a prime number
c n=null[x|x<-[2..n-1],n`mod`x==0]&&n>1

-- p is an infinite list of primes
p=filter c[1..]

-- g function prints a list of primes and differences.
--   l is the maximum difference seen so far
--   (m:n:o) is the list of unprocessed primes
g l(m:n:o)
 |(n-m)>l=do print(m,n,n-m);g(n-m)(n:o)
 |True=g l(n:o)

-- main starts the ball rolling with a default max-seen value of 0
main=g 0 p

```
> 1 votes

# Answer
## D - 153 + 10 = 163

I'm willingly taking the +10 penalty here, because the char count is still lower than it would have been if I had printed the primes as well.

**Golfed**:

```
import std.stdio;bool p(int l){int n;foreach(i;1..l+1)n+=l%i==0?1:0;return n==2;}void main(){int g;foreach(l;0..int.max)if(l.p){if(g>0)(l-g).write;g=l;}}

```

**Readable version**:

```
import std.stdio;

bool prime( int number )
{
    int divisors;

    foreach( i; 1 .. number + 1 )
        divisors += number % i == 0 ? 1 : 0;

    return divisors == 2;
}

void main()
{
    int lastPrime;

    foreach( number; 0 .. int.max )
        if( number.prime )
        {
            if( lastPrime > 0 )
                ( number - lastPrime ).write;

            lastPrime = number;
        }
}

```
> 0 votes

# Answer
# **JAVASCRIPT 174 char**

```
var p=[2],l=2,g=0;
for(var n=3;n>0;n+=2){
  var o=0;
  for(var t=0;t<p.length;++t){
    if(n/p[t] == parseInt(n/p[t])){
      o=1;
    }
  }
  if(o==0){
    p.push(n);
    if(n-l>g){
      g=n-l;
      console.log(l,n,g);
    }
    l=n;
  }
}

```

short version:

```
var p=[2],l=2,g=0;for(var n=3;n>0;n+=2){var o=0;for(var t=0;t<p.length;++t){if(n/p[t] == parseInt(n/p[t])){o=1;}}if(o==0){p.push(n);if(n-l>g){g=n-l;console.log(l,n,g);}l=n;}}

```
> 0 votes

# Answer
## Haskell, 154 144 137 123

The primes `p` are generated using the sieve of erasthotenes `#`, and then filtered and printed using `%`.

```
p=2:3#1
n#m|all((>0).mod n)$take m p=n:(n+1)#(m+1)|1<2=(n+1)#m
(l:u@(o:_))%k|o-l>k=print(l,o,o-l)>>u%(o-l)|1<2=u%k
main=p%0

```

The output looks like

```
(2,3,1)
(3,5,2)
(7,11,4)
(23,29,6)
(89,97,8)

```

which I hope is okay.
> 0 votes

# Answer
## Javascript 138

```
for(var a=2,b=0,c=0;a++;){var d;a:{for(var e=a,f=2;f<e;f++)if(0==e%f){d=!1;break a}d=!0}d&&(0!=b&&a-b>c&&(c=a-b,console.log(b,a,c)),b=a)}

```

Copy this code to your browser console. It will for like forever as the max number is something around `1.79*10^308`.

Ungolfed:

```
var number = 2;
var lastPrime = 0;
var gap = 0;

while(number++)
{
    if (isPrime(number)) {
        if (lastPrime != 0) {
            if (number - lastPrime > gap)
            {
                gap = number - lastPrime;
                console.log(lastPrime, number, gap);
            }
        }

        lastPrime = number;
    }
}

function isPrime(n){
    for (var i = 2; i < n; i++) {
        if (n % i == 0)
            return false;
    }
    return true;
}

```
> 0 votes

# Answer
## C# 162 161 chars

151 chars + 10 penalty chars = 161 chars

Short version:

```
using System;class P{static void Main(){int p=2,g=0;for(int i=3;;i++){for(int j=2;j<i;j++)if(i%j==0)goto e;if(i-p>g)Console.WriteLine(g=i-p);p=i;e:;}}}

```

Long version:

```
using System;

class PrimeGaps
{
    private static void Main()
    {
        int lastPrime = 2;
        int largestGap = 0;

        for (int i = 3; true; i++)
        {
            // Prime test
            for (int j = 2; j < i; j++)
                if (i%j == 0)
                    goto nextI; // Skip to next iteration of i

            // Largest gap check
            if (i - lastPrime > largestGap)
            {
                largestGap = i - lastPrime;
                Console.WriteLine(largestGap);
            }

            // Remember last prime
            lastPrime = i;

            nextI:
                ; // Do nothing
        }
    }
}

```

It was actually better to take 10 chars penalty, since it's shorter writing `g` (11 chars with penalty) than `p+" "+i+" "+g` (13 chars without penalty).
> 0 votes

# Answer
## Ruby 90 86 84 83 chars

```
r,i,g=2,2,0;while i+=1 do(2...i).all?{|j|i%j>0}&&((i-r<=g||p([r,i,g=i-r]))&&r=i)end

```

Some boolean short circuits, abuse of expression evaluation, etc.
> 0 votes

# Answer
**C 248**

Code compares consecutive prime numbers a, b and then checks if gaps are larger than g then finds next pair of primes.

```
#include <cstdio>
void f(int* a, int* b){*a =*b;int t=1;while (*b += 2){t=1;for(int i=3;i<*b;i+=2){if(*b%i==0){t=0; break;}}if(t)break;}}
int main(){int a=2,b=3,g=0;do{(b-a>g)?printf("%d %d %d\n",a,b,(g=b-a)): f(&a,&b);} while(b>=0);return 0;}

```
> 0 votes

# Answer
## Game Maker Language, 74 + 55 = 129

Assuming all uninitialized variables as `0` (this is the default with some versions of Game Maker).

```
n=2while(n++){if p(n){if l{if n-l>g{g=n-l;show_message_ext("",l,n,g)}}l=n}

```

Script `p` is below:

```
r=1a=argument0for(i=2i<a;i++){if a mod i=0r=0}return r}

```
> 0 votes

# Answer
## Game Maker Language, 85

Assuming all uninitialized variables as `0` (this is the default with some versions of Game Maker).

```
a=2b=2for(d=2;b++;1)for(c<b-a;b mod --d;1)d<3&&(c=b-a&&show_message_ext("",a,b,c)a=b)

```
> 0 votes

# Answer
# Perl, 87 bytes (*using a module*)

```
use Math::Prime::Util":all";$l=2;forprimes{if($_-$l>$m){say"$l $_ ",$m=$_-$l}$l=$_}1e14

```

I wrote the module, but we'd have to add an extra 565,000 characters to the tally. Mostly posting for fun, but also to give a performance alternative since I don't see any so far using builtins. 4.6s for gaps to 1e9, 36s for gaps to 1e10, 6.5min for 1e11.

Pari/GP 2.8 can be done basically the same way, albeit over 2x slower:

```
l=2;m=0;forprime(p=2,1e14,if(p-l>m,print(l," ",p," ",m=p-l));l=p)

```
> 0 votes

# Answer
# Perl 153

Short code:

```
$i=$a=2;while($a=$i++){if(p($i)){if($m<$m2=$i-$a){$m=$m2;print"$a $i $m$/"}}}sub p{$d=2;$s=sqrt$_[0];while(){return 0if!($_[0]%$d);return 1if$d>$s;$d++}}

```

easy to Read:

```
$i=$a=2;
while($a=$i++){
  if(p($i)){
    if($m<$m2=$i-$a){
      $m=$m2;
      print"$a $i $m$/"
    }
  }
}
sub p {
  $d=2;
  $s=sqrt$_[0];
  while(){
    return 0if!($_[0]%$d);
    return 1if$d>$s;
    $d++;
  }
}

```
> -1 votes

---
Tags: code-golf, primes
---


# Question
Title: Stack Exchange Stock Exchange Tournament
# Introduction

Greetings fellow traders, you have just entered the Stack Exchange stock exchange. Here you will compete to earn the money by buying and selling shares (unfortunately, we only have the single market).

# Gameplay

You will need to write a program that buys and sells shares. At the start, the market price is 200, you have $10000 and no shares. Each time you buy or sell a share, the market price goes up or down.

There will be ten games played, each game with fifty rounds. At the end, the person with the highest amount of money wins.

***The first game will start with at least ten entrants***

# Information

Your program will be supplied with three arguments:

```
Your bank balance
Number of shares
Market value
Round number

```

And you can supply one of three commands:

```
Name  | Command
Buy:  | b [no. shares]
Sell: | s [no. shares]
Pass: | p

```

For example, if you were to run the program straight:

```
python testprog.py 10000 0 200 1

b 100

```

I would suggest recording change to see if people are buying or selling shares to prevent a crash.

If you try to spend money you don't have or sell stocks that you don't have, your request will be rejected.

You are allowed to have ONE text file for recording change in stock price.

The program will be run on Ubuntu Linux.

## Controller program:

```
# Orchestration Program

from subprocess import Popen, PIPE
import time

class Program:
     money=None
     stocks=None
     command=None

# Define class instances here
programvars = {}
# Program names here
programs = []
leaderboard = {"1": 0,
               "2": 0,
               "3": 0,
               "4": 0,
               "5": 0,
               "6": 0,
               "7": 0,
               "8": 0,
               "9": 0,
               "10": 0}
scores = []

# Programs start in a different order each time
programs = sorted(programs, key=lambda k: random.random())

f = open("stockprice.txt", "r")
f = f.split('|')
stockprice = int(f[0])
roundnum = int(f[1])
f.close()

programsfifty = programs*50

# Initialising variables
for i in programsfifty:
    #try:
    g = open(i + "properties.txt", "r")
    print(i)
    properties = g.read()
    properties = properties.split("|")

    programvars[i].money = int(properties[0])
    programvars[i].stocks = int(properties[1])
    programvars[i].command = str(properties[2])

    g.close()

    #except:
    #    pass

# Main event loop
for j in programs:
    if stockprice < 0:
        stockprice = 0

    # Example: python3 test.py [money] [stocks] [price]
    command = programvars[j].command + ' ' + str(programvars[j].money) + ' ' + str(programvars[j].stocks) + ' ' + str(stockprice) + ' ' + str(roundnum)

    out = Popen(command, shell=True, stdout=PIPE).communicate()[0].decode('utf-8')
    out = out.replace('\n', '')
    # If run on Windows
    out = out.replace('\r', '')

    if out == 'p':
        pass

    else:
        action = out.split(' ')

        if action[0] == 'b':
            # Buying shares
            if programvars[j].money - int(action[1])*stockprice > -1:
                     programvars[j].money -= int(action[1])*stockprice
                     programvars[j].stocks += int(action[1])
                     stockprice += int(action[1])

        elif action[0] == 's':
             if programvars[j].stocks - int(action[1]) > -1:
                 # Selling shares
                 programvars[j].money += int(action[1])*stockprice
                 programvars[j].stocks -= int(action[1])
                 stockprice -= int(action[1])

for k in programs:
    # Writing properties to files
    n = open(k + "properties.txt", "w")
    n.write(str(programvars[k].money)+"|"+str(programvars[k].stocks)+"|"+str(programvars[k].command))
    n.flush()
    n.close

    # Add all scores to an array for sorting
    scores.append(programvars[k].money)

scores = sorted(scores, reverse=True)
print(scores)
# Find richest program
for l in programs:
    for m in range(0, len(scores)):
        if programs.index(l) == m:
            leaderboard[programs[m]] = leaderboard.pop(str(m+1))

scorekeys = sorted(leaderboard.keys(), reverse=True)
print(scorekeys)
# Write the leaderboard
s = open("leaderboard"+str(time.localtime()[0])+"-"+str(time.localtime()[1])+"-"+str(time.localtime()[2])+".txt", "w+")

# Some problems with this, but can be worked out manually
for n in scores:
    s.write(str(scores.index(n)+1) + ": " + scorekeys[scores.index(n)] + " " + str(n) + "\n")

s.flush()
s.close()

roundnum += 1

# Write the stockprice
b = open("stockprice.txt", "w")
b.write(str(stockprice) + '|' + str(roundnum))
b.flush()
b.close()

```

**Good luck!**

# Answer
# Short-Sighted Seller - Perl

This bot has the simple strategy of maximizing its score at the end of every trading opportunity. It acts as if every round were the last round.

```
($money,$stocks,$price) = @ARGV;
$value = $money + $stocks * $price;
if($price > 0){
 $optimal = $value / (2 * $price);
}
else{
 $optimal = 9x15 + $stocks; #suitably large number
}
$rounded = int($optimal + 0.5);
$delta = $rounded - $stocks;
if($delta > 0){
 print "b $delta";
}
elsif($delta < 0){
 $delta *= -1;
 print "s $delta";
}
elsif($delta == 0){
 print "p";
}

```

You can run it like so:

```
perl shortsightedseller.plx [money] [stocks] [price]

```
> 3 votes

---
Tags: king-of-the-hill
---