fork(2) download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <cassert>
  5. using namespace std;
  6.  
  7. struct solver_t
  8. {
  9. 	solver_t(string const& a, string const& b, string const& c)
  10. 		: lhs(a)
  11. 		, rhs(b)
  12. 		, res(c)
  13. 		, subst(128, -1)
  14. 		, used{}
  15. 	{
  16. 		cout << lhs << " + " << rhs << " == " << res << "\n";
  17. 	}
  18.  
  19. 	string lhs;
  20. 	string rhs;
  21. 	string res;
  22.  
  23. 	vector<int> subst;
  24. 	int used[10];
  25.  
  26. 	int to_number(string& s)
  27. 	{
  28. 		int ret = 0;
  29. 		for (char c : s)
  30. 		{
  31. 			assert(subst[c] >= 0);
  32. 			ret = ret * 10 + subst[c];
  33. 		}
  34. 		return ret;
  35. 	}
  36.  
  37. 	void check_and_print()
  38. 	{
  39. 		int left = to_number(lhs);
  40. 		int right = to_number(rhs);
  41. 		int result = to_number(res);
  42.  
  43. 		if (left + right == result)
  44. 		{
  45. 			cout << left << " + " << right << " == " << result << "\n";
  46. 		}
  47. 	}
  48.  
  49. 	void for_each_subst(string& s, int cr, int depth)
  50. 	{
  51. 		char c = s[s.size() - depth];
  52. 		for (int i = depth == s.size(); i < 10; ++i)
  53. 		{
  54. 			if (used[i]) { continue; }
  55.  
  56. 			subst[c] = i;
  57. 			used[i] = true;
  58.  
  59. 			solve(cr, depth);
  60.  
  61. 			used[i] = false;
  62. 			subst[c] = -1;
  63. 		}
  64. 	}
  65.  
  66. 	void solve(int cr = 0, int depth = 1)
  67. 	{
  68. 		if (depth > lhs.size() || depth > rhs.size() || depth > res.size())
  69. 		{
  70. 			check_and_print();
  71. 			return;
  72. 		}
  73.  
  74. 		char c = res[res.size() - depth];
  75. 		if (subst[c] >= 0)
  76. 		{
  77. 			char a = lhs[lhs.size() - depth];
  78. 			if (subst[a] >= 0)
  79. 			{
  80. 				char b = rhs[lhs.size() - depth];
  81. 				if (subst[b] >= 0)
  82. 				{
  83. 					int sum = subst[a] + subst[b] + cr;
  84. 					if (sum % 10 != subst[c])	{ return; }
  85. 					solve(sum / 10, depth + 1);
  86. 				}
  87. 				else
  88. 				{
  89. 					for_each_subst(rhs, cr, depth);
  90. 				}
  91. 			}
  92. 			else
  93. 			{
  94. 				for_each_subst(lhs, cr, depth);
  95. 			}
  96. 		}
  97. 		else
  98. 		{
  99. 			for_each_subst(res, cr, depth);
  100. 		}
  101. 	}
  102. };
  103.  
  104. int main() 
  105. {
  106. 	solver_t("send", "more", "money")
  107. 		.solve();
  108. }
Success #stdin #stdout 0s 4308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
send + more == money
9567 + 1085 == 10652
https://ideone.com/TocGUa
send + more == money - SOLVER
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!