Skip to content

Instantly share code, notes, and snippets.

@WindAzure
Last active April 28, 2019 15:26
Show Gist options
  • Save WindAzure/189b6b6733b66d552245765039efcf82 to your computer and use it in GitHub Desktop.
Save WindAzure/189b6b6733b66d552245765039efcf82 to your computer and use it in GitHub Desktop.
UVa 508
#include <algorithm>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <regex>
#include <string>
#include <vector>
using namespace std;
map<char, string> m_characterToMorseMappingTable;
map<string, string> m_contextMorseWordsMappingTable;
map<string, bool> m_isMorseRepeated;
vector<string> splitSpaces(const string &targetString)
{
regex pattern(" ");
auto splitContents = vector<string> {};
copy_if(sregex_token_iterator(targetString.begin(), targetString.end(), pattern, -1), sregex_token_iterator(), back_inserter(splitContents),
[](const string &data) { return !data.empty(); });
return splitContents;
}
void createCharacterMappingTable(const vector<string> &mappingStringList)
{
m_characterToMorseMappingTable.clear();
for (const auto &mappingString: mappingStringList)
{
auto splitContents = splitSpaces(mappingString);
if (!splitContents.empty())
{
auto character = splitContents[0].at(0);
auto morseWords = accumulate(splitContents.begin() + 1, splitContents.end(), string {});
m_characterToMorseMappingTable[character] = morseWords;
}
}
}
void createContextTable(vector<string> &contextStringList)
{
m_isMorseRepeated.clear();
m_contextMorseWordsMappingTable.clear();
sort(contextStringList.begin(), contextStringList.end(),
[](const string &s1, const string &s2) { return strcmp(s1.c_str(), s2.c_str()) == -1; });
for (const auto &contextString: contextStringList)
{
auto morseWords = accumulate(contextString.begin(), contextString.end(), string {},
[&](string &baseString, const char &c) { return baseString + m_characterToMorseMappingTable[c]; });
if (morseWords.empty())
{
continue;
}
m_isMorseRepeated[morseWords] = m_isMorseRepeated.count(morseWords);
if (!m_isMorseRepeated[morseWords])
{
m_contextMorseWordsMappingTable[contextString] = morseWords;
}
}
}
vector<string> createMorseWordsQuery(const vector<string> &contentStringList)
{
auto contentList = vector<string> {};
for (const auto &contentString: contentStringList)
{
auto splitContentList = splitSpaces(contentString);
copy(splitContentList.begin(), splitContentList.end(), back_inserter(contentList));
}
return contentList;
}
int calculateMaxPrefixMorseNumber(const string &morseWords, const string &morseContent)
{
auto currentIndex = 0;
auto sameCharacterNumber = 0;
while (currentIndex < morseWords.size() && currentIndex < morseContent.size())
{
if (morseWords[currentIndex] != morseContent[currentIndex])
{
break;
}
sameCharacterNumber++;
currentIndex++;
}
return sameCharacterNumber;
}
int getRedundantNumber(int length1, int length2, int matchedNumber)
{
if (length1 == matchedNumber)
{
return length2 - matchedNumber;
}
else if (length2 == matchedNumber)
{
return length1 - matchedNumber;
}
return numeric_limits<int>::max();
}
string findMostClosestContext(const string &morseWordsQuery)
{
auto minRedundantNumber = numeric_limits<int>::max();
auto paritalMatchedContextWords = m_contextMorseWordsMappingTable.begin()->first;
for (const auto &mappingPair: m_contextMorseWordsMappingTable)
{
auto contextWords = mappingPair.first;
auto morseWords = mappingPair.second;
auto matchedNumber = calculateMaxPrefixMorseNumber(morseWords, morseWordsQuery);
auto redundantNumber = getRedundantNumber(morseWordsQuery.size(), morseWords.size(), matchedNumber);
if (minRedundantNumber > redundantNumber)
{
minRedundantNumber = redundantNumber;
paritalMatchedContextWords = contextWords;
}
}
return paritalMatchedContextWords;
}
void solve(const vector<string> &contentStringList)
{
auto morseWordsQueryList = createMorseWordsQuery(contentStringList);
for (const auto &morseWordsQuery: morseWordsQueryList)
{
auto postFixWords = string {"?"};
auto closestContextWords = findMostClosestContext(morseWordsQuery);
if (m_contextMorseWordsMappingTable[closestContextWords] == morseWordsQuery)
{
postFixWords = m_isMorseRepeated[morseWordsQuery] ? "!" : "";
}
cout << closestContextWords + postFixWords << endl;
}
}
vector<string> inputMultiLineData()
{
auto inputString = string {};
auto multiLineStringList = vector<string> {};
while (getline(cin, inputString))
{
if (inputString.find('*') != string::npos)
{
break;
}
multiLineStringList.push_back(inputString);
}
return multiLineStringList;
}
int main()
{
auto morseMappingList = inputMultiLineData();
auto contextWordsList = inputMultiLineData();
auto contentStringList = inputMultiLineData();
createCharacterMappingTable(morseMappingList);
createContextTable(contextWordsList);
solve(contentStringList);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment