decrypt_problem_5, C++ (gcc)

Language: Layout:

#include <iostream>
#include <string>
#include <set>
#include <array>
#include <sstream>
#include <algorithm>

// poorman's kind of zip 
template <typename INPUT_TYPE, typename FUNC_TYPE>
void zip(const INPUT_TYPE& e1, const INPUT_TYPE& e2, FUNC_TYPE func)
{
	auto  v2 = e2.begin();
	for (auto v1 : e1)
	{
		func(v1, *v2);		
		v2++;
	}
}

using InputWords = std::set<std::string>;
using WordsByLength = std::array<InputWords, 16>;

auto getCharIndex(char c) { return c - 'a'; }

template <typename T>
auto prepareInput(const T& input)
{
	WordsByLength output{};
	for (auto v : input) {	output[v.size()].insert(v);	}

return output;
}

using Dict = std::array<char, 26>;

// try adding more details to the hypothesis but only if these new details don't override previous ones
bool extendHypothesis(char c1, char c2, Dict* hypothesis)
{
	size_t offset = getCharIndex(c2);

char &cur = (*hypothesis)[offset];
	if (cur != 0 && cur != c1) return false; // some other hypothessis is already in place here, we have a contradiction

auto it = std::find(hypothesis->begin(), hypothesis->end(), c1);
	if (it != hypothesis->end())
	{
		size_t ofs = std::distance(hypothesis->begin(), it);
		// we have already mapped to this character, can't reuse it 
		return offset == ofs; // it's ok if original character is the same as we assumed now
	}

cur = c1;

return true;
}

auto setSubtract(const InputWords& s1, const InputWords& s2)
{
	InputWords diff;
	std::set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(), std::inserter(diff, diff.begin()));

return diff;
}

// see if there's any contradiction with the existing hypothesis details when trying to map i1 -> i2 (using all possible combinations)
auto isContradiction(const InputWords& i1, const InputWords& i2, Dict* hypothesis )
{
	if (i2.empty()) return false; // nothing else we need to match 
	if (i1.empty()) return true; // nothing to choose from (in case we have to match something)

bool is_fail = false;
	if (i1.size() == 1)
	{	
		Dict hypothesis_cur = *hypothesis; // save temp copy as we'll be adjusting it here to see if it's any good

zip(*i1.begin(), *i2.begin(), [&](auto v1, auto v2) { if (is_fail) return;  is_fail = !extendHypothesis(v1, v2, &hypothesis_cur); });

if (!is_fail) *hypothesis = hypothesis_cur; // save this hypothesis

return is_fail;
	}
	
	for (auto v1 : i1) for (auto v2 : i2)
	{
		Dict hypothesis_cur = *hypothesis; // save temp copy as we'll be adjusting it here to see if it's any good
				
		InputWords tmp1 = { v1 };
		InputWords tmp2 = { v2 };

if (isContradiction(tmp1, tmp2, &hypothesis_cur))
		{
			continue; // this idea didn't work, don't need to check other combinations
		}

// now remove these two elements and check the rest
		InputWords diff1 = setSubtract(i1, tmp1);
		InputWords diff2 = setSubtract(i2, tmp2);

if (!isContradiction(diff1, diff2, &hypothesis_cur))
		{
			*hypothesis = hypothesis_cur; // save this hypothesis
			return false;
		}
	}

return true;
}

auto isContradiction(const WordsByLength& i1, const WordsByLength& i2, Dict* hypothesis)
{
    // start matching from longest words as they provide more data and we'll encounter contradictions faster
	for (auto it1 = i1.rbegin(), it2 = i2.rbegin(); it1 != i1.rend(); it1++, it2++)
	{
		if (it1->size() < it2->size()) return true; // we can't match all unique words in the output as we don't have enough in the input
		if (isContradiction(*it1, *it2, hypothesis)) return true; 
	}

return false;
}

auto mapResult(const std::string& input, const Dict& hypothesis, bool is_valid)
{
	auto out = input;
	size_t i = 0;
	for (auto c : input) 
	{ 
		out[i++] = (c == ' ' ? ' ' : (is_valid ? hypothesis[getCharIndex(c)] : '*'));
	}

return out;
}

int main()
{
	InputWords input = { "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "banana", "apple", "cucumber", "something", "else", "must", "do", "for", "this", "is", "boring" };

std::string lines_input =	"aa\n"
								"abcdefg\n"
								"qlc pcf xvotq qlxhix pvix nsnsdjxf\n"
								"lmen cu jfjfxaeb smeyne sdcbseez sdcu wlfb wcwseez uco wcne aizizi albczk sez\n"
								"its ibnz kwwqd fncd zsxdibnrj phphxlda fshaiddr itdqcd nz\n"
								"bfupxiim xcre fmi duex re ztmtmt zfprmv eisim irvcx\n"
								"nbi nsbmlb xirydqqn inq siylnh dalk nlnq xljq lk kqjqn\n"
								"obf okzc brbmbf tngx czp tnx ojn tngxobbf\n"
								"hthyhv uirqohhv xi ohv bhyhv aiqgvj bifhosgvj ivh bgd frbo\n"
								"za yplplp asphn ajazak qtin moxskp\n"
								"ejn eiftbqjak xrxrfdtu je ajat ixbt dxxju zdbdbd\n"
								"iona ettka flfluyaz ulcm yxzowp akca canaw mvx xwa cod mhozmaaw aophm maw ixlz\n"
								"vewii fpi irsev myyni gf ru vlf prpi kfw\n"
								"koe vrxrg se ruvr egr\n"
								"gj jev qsj xjt qmnb bvyve bno izbq vfvyve raeaea xjztqvve qmtvv\n"
								"aip tzbcc tdq ia lflfuscb cwcncr xqb xqfb sqbire tcr svrvrv xixtccr ciezt xinc\n"
								"sfsysl ozgss itithusg arp ovsfys jrys uegrlc htao jrjossl osl jeg\n"
								"kuv mk qedo alzqub eqck dkcku eliz elz kykcku pskyck\n"
								"laaug bixfjggw bixf gung ngmgw\n"
								"ushg cost ciym cicgmmd ko orugf fgrafooe mwzofgreu mrb\n"
								"zuml sbscsx vursatwxk zumlassx egxgxg atwv uxs vwj asx zwzassx atlss vscsx\n"
								"iecdn yjl kpwn xj rgvgvg yjplniiv upupkril nqj niv jvi ndelniiv wez yeoi\n"
								"evl ncococ ad hstawm yjyxyw\n"
								"giiej fnhp qrqj lrv whwhzxjp ujq usn xgqgqg\n"
								"bubycck un ywuzycck djny cuqwy ywzcc vlwlk iuuzl otwl ojb ejbtkq vtc ojsb lzvl\n"
								"lqj kfrfrf nimecm gq myuxn nca njtxqhcmp xrnx wjlcmp qhlxx\n"
								"vdvk zwckk zwdczkkv ujekzwdvy kxuk mjc\n"
								"fuo xfjaboou odhpb xdno ndti lx iabss srts vxbjcg iyx\n"
								"hwx vxar hwqbmq lx pggbq okoq\n"
								"evck lzhuexxs lclexxs efz lzu ck mhmhwixu evuxx scsx xdxnxs kzwxevcso lzhu izucso efxdnx\n"
								"ngrgc nmt omrg fxxhg ueymcs lqghrg cmcg\n"
								"xdkbxjjg xdkn xvw gkgj xdbjj qkzj jkfdx qwmbxjjg qkqxjjg lmt bx qnxd detcut\n"
								"iaqu wh teqt bhdlsz uph ucdtt lq slst jljutts mamaibtd uclq\n"
								"ljdxv rql vglyhl kjhl srolvxjqd ir js\n"
								"df nxrn yfjpts yctctc rpl\n"
								"hukl vspbnj kodon ltpoo oqodon bk abdo iccqo objtl ksholtbnj\n"
								"ybyqyl gmqy sumpsyyl gxep svybqy supyy svx\n"
								"tmjfuj odpztjje tmd odz nh onuj jnbxt onotjje\n"
								"dmdldz ihxzinna bdgzinna bdgz kd uhyt gygc\n"
								"oupxk hed hesd kxdoo koy kroqco zeduyp huco\n"
								"kakm zigc zic bykyky ikm tao dqat demwjm dqacdmmk jn mr\n"
								"hpbwdinax ctctbqwg optg onmw drp hny kp anaw hwmwa drwemw bthd paw";

auto input_words = prepareInput(input);

std::stringstream all_in(lines_input);

std::string line;
	while (std::getline(all_in, line) )
	{
		std::stringstream ss(line);

std::set<std::string> input_tokens;

std::string tmp;
		while (ss >> tmp) input_tokens.insert(tmp);

auto interim_input = prepareInput(input_tokens);

Dict hypothesis{};

bool not_ok = isContradiction(input_words, interim_input, &hypothesis);

//std::cout << line << "\n";
		std::cout << mapResult(line, hypothesis, !not_ok) << "\n";
	}

return 0;
}

Show compiler warnings [ + ] Compiler args [ + ] Show input
Compilation time: 1.12 sec, absolute running time: 0.1 sec, cpu time: 0.04 sec, memory peak: 3 Mb, absolute service time: 1,23 sec