fork(10) download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <map>
  5. #include <sstream>
  6. #include <algorithm>
  7. #include <functional>
  8. #include <chrono>
  9.  
  10. // 修正
  11.  
  12. template <typename unit, typename Clock = std::chrono::high_resolution_clock>
  13. struct StopWatch {
  14.     typename Clock::time_point start;
  15.     StopWatch() : start(Clock::now()) {}
  16.  
  17. 	unsigned getDifference(){
  18. 		 return std::chrono::duration_cast<unit>(Clock::now() - start).count();
  19. 	}
  20. };
  21.  
  22. template <typename Integer>
  23. struct Resolver {
  24. 	using WordType = std::vector<Integer>;
  25.  
  26. 	std::string line;
  27. 	std::array<WordType,3> words;
  28. 	std::string operatorSymbol;
  29.  
  30.     std::vector<Integer> combinationMap;
  31. 	std::map<char,Integer> charMap;
  32.  
  33. 	Resolver(std::string& aLine) : line(aLine) {
  34. 		std::array<std::string, 3> rawWords;
  35. 		std::string eq;
  36. 		std::stringstream(line) >> rawWords[0] >> operatorSymbol >>  rawWords[1] >> eq >> rawWords[2];
  37.  
  38. 		{
  39. 			int i = 0;
  40. 			for( auto rawWord: rawWords )
  41. 				for( auto ch: rawWord )
  42. 					if(charMap.count(ch) <= 0)
  43. 						charMap[ch] = i++;
  44. 		}
  45.  
  46. 		for( int i = 0; i < rawWords.size(); i++ ){
  47. 			std::vector<Integer> word;
  48. 			for( auto ch: rawWords[i] )
  49. 				word.push_back( charMap[ch] );
  50.  
  51. 			words[i] = word;
  52. 		}
  53. 	}
  54.  
  55. 	std::string getResultString(){
  56. 		std::string buffer;
  57. 		std::stringstream stream(buffer);
  58. 		stream << toInteger(words[0]) << " " << operatorSymbol << " " << toInteger(words[1])
  59. 		       << " = " << toInteger(words[2]);
  60.  
  61. 		return stream.str();
  62. 	}
  63.  
  64.  
  65. 	bool validate(){
  66. 		bool found;
  67. 		Integer n1 = toInteger(words[0]);
  68. 		Integer n2 = toInteger(words[1]);
  69. 		Integer n3 = toInteger(words[2]);
  70.  
  71. 		switch(operatorSymbol[0]){
  72. 			default:
  73. 			case '+': found = (n1 + n2) == n3; break;
  74. 			case '-': found = (n1 - n2) == n3; break;
  75. 			case '*': found = (n1 * n2) == n3; break;
  76. 			case '/': found = (n1 / n2) == n3; break;
  77. 		}
  78. 		if( !found )
  79. 			return false;
  80.  
  81. 		for( auto word: words )
  82. 			if( combinationMap[ word[0] ] == 0 )
  83. 				return false;
  84.  
  85. 		return true;
  86.  
  87. 	}
  88.  
  89. 	Integer toInteger(std::vector<Integer>& word){
  90. 		return std::accumulate( word.begin(), word.end(), 0, [&](Integer prev, Integer ch){
  91. 			return (prev * 10) + combinationMap[ch];
  92. 		});
  93. 	}
  94.  
  95. 	StopWatch<std::chrono::milliseconds> stopWatch;
  96. 	void print(){
  97. 		std::cout << line << " -> " << getResultString()
  98. 		          << " (in " << stopWatch.getDifference() << "ms)"
  99. 		          << std::endl;
  100. 	}
  101.  
  102. 	void resolve(){
  103. 	    std::vector<bool> taken(10);
  104.     	std::fill(taken.end() - charMap.size(), taken.end() , true);
  105.  
  106.    		combinationMap = std::vector<Integer>( charMap.size() );
  107.  
  108.     	do {
  109.     		int n = 0;
  110.    	        for (int i = 0; i < 10; ++i)
  111. 	            if ( taken[i] )
  112. 		            combinationMap[n++] = i;
  113.  
  114. 			do if( validate() )
  115. 				print();
  116. 		    while (std::next_permutation(combinationMap.begin(),combinationMap.end()));
  117.  
  118. 	    }
  119. 	    while (std::next_permutation(taken.begin(), taken.end()));
  120. 	}
  121. };
  122.  
  123. int main() {
  124. 	for( std::string line; std::getline(std::cin,line); )
  125. 		Resolver<int>(line).resolve();
  126.  
  127. 	return 0;
  128. }
Success #stdin #stdout 0.31s 3248KB
comments (?)
stdin
copy 
SEND + MORE = MONEY
WWWDOT - GOOGLE = DOTCOM
AB2DEF * 2 = 2DEFAB
ABA * ABA = CCDCC
stdout
copy 
SEND + MORE = MONEY -> 9567 + 1085 = 10652 (in 50ms)
WWWDOT - GOOGLE = DOTCOM -> 777589 - 188103 = 589486 (in 57ms)
WWWDOT - GOOGLE = DOTCOM -> 777589 - 188106 = 589483 (in 57ms)
AB2DEF * 2 = 2DEFAB -> 142857 * 2 = 285714 (in 2ms)
ABA * ABA = CCDCC -> 212 * 212 = 44944 (in 0ms)
https://ideone.com/9J5rml
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!