My solution to https://www.reddit.com/r/dailyprogrammer/comments/3b668g/20150626_challenge_220_hard_substitution/

Daily Programmer.cpp

#include <iostream>
#include <string>
#include <set>
#include <fstream>
#include <vector>
#include <sstream>
#include <unordered_map>
#include <algorithm>
#include <limits>

using namespace std;

set<string> dictionary;
vector<set<string> > dictionaryWithLength;
set<string> finalSolutions;
string encrypted;

void buildDictionary(const string& path)
{
    ifstream file(path);

    string line;

    size_t maxLength = 0;

    while(getline(file, line))
    {
        maxLength = max(line.length(), maxLength);
        dictionary.emplace(line);
    }

    dictionaryWithLength.resize(maxLength + 1);
    for(const auto& word : dictionary)
    {
        dictionaryWithLength[word.length()].insert(word);
    }
}

vector<string> splitString(const string& toSplit)
{
    vector<string> output;
    string tmp = "";
    for(const auto& character : toSplit)
    {
        if(char(' ') == character || char('\'') == character)
        {
            output.push_back(tmp);
            tmp = "";
        } else
        {
            tmp += character;
        }
    }
    output.push_back(tmp);
    output.shrink_to_fit();
    return output;
}

void readInput(const string& path, vector<string>& mangledWords, unordered_map<char, char>&  knownReplacements)
{
    ifstream file(path);
    string line;
    getline(file, line);
    encrypted = line;
    mangledWords = splitString(line);
    getline(file, line);
    auto numberOfHints = 0;
    istringstream(line) >> numberOfHints;
    for(auto i = 0; i < numberOfHints; ++i)
    {
        getline(file,line);
        knownReplacements.insert(make_pair(line[1],line[0]));
    }
}

void printFinal()
{
    cout << encrypted << "\n" << endl;
    for(const auto& solution : finalSolutions)
    {
        cout << solution << "\n";
    }
    flush(cout);
}

void print(const vector<string>& mangledWords, const vector<vector<string> >& candidates)
{
    for(auto word : mangledWords)
    {
            cout << word << " ";
    }
    cout << "\n" << endl;

    auto maxCandidates = max_element(candidates.begin(), candidates.end(), [](const vector<string>& a, const vector<string>& b) -> bool
    {
        return a.size() < b.size();
    })->size();

    vector<string> output(maxCandidates);

    for(size_t id = 0; id < candidates.size(); ++id)
    {
        const auto& candidate = candidates[id];
        size_t i = 0;
        auto wordSize = mangledWords[id].length();
        for(const auto& wordCandidate : candidate)
        {
            output[i] += wordCandidate + " ";
            wordSize = wordCandidate.size();
            ++i;
        }
        while(i < maxCandidates)
        {
            for(size_t j = 0; j < wordSize; ++j)
            {
                output[i] += " ";
            }
            output[i] += " ";
            ++i;
        }
    }

    for(const auto& out : output)
    {
        cout << out << endl;
    }
}

vector<vector<string> > getCandidates(vector<string>& mangledWords, const vector<vector<string> >& oldCandidates)
{
    vector<vector<string> > candidates;
    candidates.resize(mangledWords.size());
    for(size_t id = 0; id < mangledWords.size(); ++id)
    {
        const auto& word = mangledWords[id];
        const auto& size = word.size();
        const auto& dict = oldCandidates[id];
        std::unordered_map<int, char> matcher;

        for(size_t pos = 0; pos < size; ++pos)
        {
            if(islower(word[pos]))
            {
                matcher.insert(make_pair(pos, word[pos]));
            }
        }

        auto& wordCandidates = candidates[id];
        for(const auto& dicWord : dict)
        {
            bool isMatch = true;
            for(auto match : matcher)
            {
                if(dicWord[match.first] != match.second)
                {
                    isMatch = false;
                    break;
                }
            }
            if(isMatch)
            {
                wordCandidates.emplace_back(dicWord);
            }
        }
        if(wordCandidates.empty())
        { // Discard everything
            return vector<vector<string> >();
        }
    }

    return candidates;
}

vector<vector<string> > getCandidatesFromDictionary(vector<string>& mangledWords)
{
    vector<vector<string> > candidates(mangledWords.size());
    for(size_t id = 0; id < mangledWords.size(); ++id)
    {
        const auto& correspondingDirectory = dictionaryWithLength[mangledWords[id].length()];
        vector<string> tmpCands;
        tmpCands.reserve(correspondingDirectory.size());
        for(const auto& entry : correspondingDirectory)
        {
            tmpCands.emplace_back(entry);
        }
        candidates[id] = tmpCands;
    }
    return getCandidates(mangledWords, candidates);
}

void replaceChars(vector<string>& words, const unordered_map<char, char>& replaceMents)
{
    for(auto& word : words)
    {
        for(auto& character : word)
        {
            auto hit = replaceMents.find(character);
            if(hit != replaceMents.end())
            {
                character = hit->second;
            }
        }
    }
}

unordered_map<char, char> getReplacements(const string& mangledWord, const string& dictWord)
{
    unordered_map<char, char> output;
    for(size_t i = 0; i < mangledWord.size(); ++i)
    {
        if(isupper(mangledWord[i]))
        {
            output.emplace(make_pair(mangledWord[i], dictWord[i]));
        }
    }
    return output;
}

bool stringIsLower(const string& word)
{
    for(const auto character : word)
    {
        if(isupper(character))
        {
            return false;
        }
    }
    return true;
}

bool checkSolution(const string& solution)
{
    unordered_map<char, char> backTranslator;
    if(solution.length() != encrypted.length())
        return false;
    for(size_t i = 0; i < solution.length(); ++i)
    {
        backTranslator.insert(make_pair(solution[i], encrypted[i]));
    }
    string tmp = encrypted;
    for(const auto& pair : backTranslator)
    {
        std::replace(tmp.begin(), tmp.end(), pair.second, pair.first);
    }
    return (tmp.compare(solution) == 0);
}

void addFinalSolution(const vector<vector<string> >& solution)
{
    string finalString;
    for(const auto& word : solution)
    {
        finalString += word[0];
        if(word != solution.back())
            finalString += " ";
    }
    for(size_t i = 0; i < encrypted.length(); ++i)
    {
        if(encrypted[i] == '\'')
        {
            finalString[i] = '\'';
        }
    }
    if(checkSolution(finalString))
        finalSolutions.insert(finalString);
}

vector<vector<string> > solve(const vector<string>& words, const vector<vector<string> >& candidates)
{
    size_t minValue = SIZE_MAX;
    size_t bestId = SIZE_MAX;
    for(size_t id = 0; id < words.size(); ++id)
    {
        if(stringIsLower(words[id]))
        { // word already final
            continue;
        }
        const auto& size = candidates[id].size();
        if(size < minValue)
        {
            minValue = size;
            bestId = id;
        }
    }

    if(bestId == SIZE_MAX)
    {
        return candidates;
    }

    vector<vector<string> > bestCandidateSet;
    if(minValue == 0)
    {
        return bestCandidateSet; // return empty
    }

    auto computeRemainingOptions = [](const vector<vector<string> >& candidates) -> size_t
    {
        size_t count = 0;
        for(const auto& candidate : candidates)
        {
            count += candidate.size();
        }
        if(count > 0)
            return count;
        else
            return SIZE_MAX;
    };

    size_t leastOptions = SIZE_MAX;
    vector<vector<string> > bestCandidates;

    const auto& word = words[bestId];

    for(const auto& candidate : candidates[bestId])
    {
        auto wordsCopy = words;
        auto replacements = getReplacements(word, candidate);
        replaceChars(wordsCopy, replacements);
        auto remainingCandidates = getCandidates(wordsCopy, candidates);
        if(remainingCandidates.empty())
        { // Don't use result, impossible solution
            continue;
        }
        auto newCandidates = solve(wordsCopy, remainingCandidates);
        auto optionsRemaining = computeRemainingOptions(newCandidates);

        if(optionsRemaining < leastOptions)
        {
            leastOptions = optionsRemaining;
            bestCandidates = newCandidates;
        }

        if( optionsRemaining == leastOptions &&
            leastOptions == bestCandidates.size() && leastOptions == words.size())
        {
            addFinalSolution(newCandidates);
        }
    }
    return bestCandidates;
}

void purgeWrongSolutions()
{

}

int main(int argc, char* argv[])
{
    string dictionary = "words.txt";
    string inputFile = "input4.txt";
    if(argc > 2)
    {
        dictionary = argv[1];
        inputFile = argv[2];
    }
    buildDictionary(dictionary);
    vector<string> mangledWords;
    unordered_map<char, char> knownReplacements;

    readInput(inputFile, mangledWords, knownReplacements);

    auto mangledWordsCopy = mangledWords;

    replaceChars(mangledWordsCopy, knownReplacements);

    auto candidates = getCandidatesFromDictionary(mangledWordsCopy);

    if(candidates.empty())
    {
        cout << "Unable to solve problem with current dictionary." << endl;
        return 1;
    }

    solve(mangledWordsCopy, candidates);

    printFinal();

    return 0;
}