fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <string>
  4. #include <set>
  5. #include <vector>
  6. using IntVec = std::vector<int>;
  7.  
  8. class Combination
  9. {
  10. public:
  11.     Combination(int n, int k) : n(n), k(k), data(k)
  12.     { std::iota(begin(data), end(data), 0); }
  13.     bool next_combination()
  14.     {
  15. 	    if (n - k == data[0]) return false;
  16. 	    int i = k - 1;
  17. 	    while (i > 0 && data[i] == n-k+i) --i;
  18. 	    ++data[i];
  19. 	    for (int j = i; j < k-1; ++j) data[j+1] = data[j] + 1;
  20. 	    return true;
  21. 	}
  22.     const IntVec& array()const { return data; }
  23. private:
  24.     int n, k;
  25.     IntVec data;
  26. };
  27.  
  28. struct ArrayMap {
  29. 	ArrayMap(const std::string* s) : id(26,-1), values(), nUnique(0)
  30. 	{
  31. 		for (int i = 0; i < 3; ++i) for (char c : s[i])
  32. 			if (id[c-'A'] == -1) id[c-'A'] = nUnique++;
  33. 	}
  34. 	int operator[](char c)const { return values[id[c-'A']]; }
  35. 	int operator()(const std::string* s, int k)const
  36. 	{
  37. 		int ret = 0, coef = 1;
  38. 		for (int i = s[k].size(); i--; coef *= 10) ret += coef*(*this)[s[k][i]];
  39. 		return ret;
  40. 	}
  41. 	IntVec id, values;
  42. 	int nUnique;
  43. };
  44.  
  45. void solve(const std::string* s, bool unique=true)
  46. {
  47. 	std::cout << s[0] << " + " << s[1] << " = " << s[2] << "\n";
  48. 	// Prepare character map
  49. 	ArrayMap p(s);
  50. 	if (p.nUnique > 10)
  51. 	{
  52. 		std::cout << "Too many characters (" << p.nUnique << ")\n\n";
  53. 		return;
  54. 	}
  55. 	// Solve
  56. 	Combination comb(10, p.nUnique);
  57. 	bool hasSolution = false;
  58. 	do {
  59. 		p.values = comb.array();
  60. 		do {
  61. 			if (p[s[0][0]]&&p[s[1][0]]&&p[s[2][0]] && p(s,0)+p(s,1)==p(s,2))
  62. 			{
  63. 				std::cout<<p(s,0)<<" + "<<p(s,1)<<" = "<<p(s,2)<<"\n";
  64. 				hasSolution = true;
  65. 				if (unique) break;////////////////
  66. 			}
  67. 		} while (std::next_permutation(begin(p.values), end(p.values)));
  68. 	} while (comb.next_combination());
  69. 	if (!hasSolution) std::cout << "No solution\n";
  70. 	std::cout << "\n";
  71. }
  72.  
  73. int main()
  74. {
  75. 	std::string s[3];
  76. 	while(std::cin >> s[0] >> s[1] >> s[2]) solve(s, false);
  77. }
  78.  
Success #stdin #stdout 1.19s 3420KB
comments (?)
stdin
copy 
GERALD
DONALD
ROBERT 

 QUANG
 TRUNG
TAYSON

 TRUE
 FACT
FALSE

 TAKE
 THAT
SHEET

 CROSS
 ROADS
DANGER

 SEND
 MORE
MONEY
stdout
copy 
GERALD + DONALD = ROBERT
197485 + 526485 = 723970

QUANG + TRUNG = TAYSON
92084 + 15284 = 107368

TRUE + FACT = FALSE
No solution

TAKE + THAT = SHEET
7460 + 7547 = 15007

CROSS + ROADS = DANGER
96233 + 62513 = 158746

SEND + MORE = MONEY
9567 + 1085 = 10652
https://ideone.com/VNI5LG
gerald donald=robert abitrary cases
language:
C++14 (gcc 8.3)
created:
7 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!