CareerCup

It's called cryptarithmetic puzzle. Here's few examples: s4.zetaboards.com/science/topic/7693756/1/

I doubt there exists some simple polynomial solution for this.

Making it easier we can solve this by using the method of solving two equation having two unknown values...i mean that v can assign only two values X,Y for each character.

1.find number of occurrence of each character in both S1 and S2 using hash1
2.similarly find in S3 in hash2
sum(odd positions of hash1)*X+sum(even position of hash1)*Y=sum(odd positions of hash2)*X+sum(even positions of hash2)*Y

since X,Y are in the bound of 0-9,we can solve..
s1 = "hard" s2 = "work", s3 = "success"
hash1:
a=1 d=1 h=1 k=1 o=1 r=2 w=1
hash2:
c=2 e=1 s=3 u=1

(a+k+o+w)*X+(d+h+r)*y=(c+e+s+u)*X+0*Y
4X+4Y=7X+0
by solving X=4 Y=3...finally the sum will be same on both side 28...

First off, HARD+WORK=SUCCESS can't be solved because there are more than 10 unique characters and SUCCESS is too long so has no solution.

I tried the following in c#:

namespace Crytarithmetic
{
    class Program
    {
        static void Main(string[] args)
        {
            new Puzzle().solve("SEND", "MORE", "MONEY");
        }

    }

    public class Puzzle
    {
        List<Char> _characters = new List<Char>();
        bool[] _used = {false, false, false, false, false, false, false, false, false, false};
        int[] _values;


        String _word1, _word2, _word3;

        public void solve(String word, String word2, String word3)
        {
            _word1 = word;
            _word2 = word2;
            _word3 = word3;

            addWord(word);
            addWord(word2);
            addWord(word3);  
         
            _values = new int[_characters.Count];

            solve(0);
        }

        private bool solve(int n)
        {

            if (n < _characters.Count())
            {
                for (int i = 0; i < 10; ++i)
                {
                    if (!_used[i])
                    {
                        _used[i] = true;
                        _values[n] = i;
                        if(solve(n+1))
                            return true;
                        _used[i] = false;
                    }
                }
            }
            else
            {
                if (validWord(_word1) && validWord(_word2) && validWord(_word3) && toInt(_word1) != 0 && toInt(_word1) + toInt(_word2) == toInt(_word3))
                {
                    Console.Write("Solved: " + toInt(_word1) + " + " + toInt(_word2) + " = " + toInt(_word3));
                    return true;
                }
            }
            return false;
            
        }
        private bool validWord(String word)
        {
            if (_values[_characters.IndexOf(word[0])] != 0)
                return true;
            return false;

        }
        private int toInt(String word)
        {
            int result = 0;
            foreach (Char c in word)
            {
                result *= 10;
                result += _values[_characters.IndexOf(c)];
            }
            return result;
        }

        private void addWord(String word)
        {
            foreach (Char c in word)
            {
                if (!_characters.Contains(c))
                {
                    _characters.Add(c);                    
                }
            }
        }
    }
}

Not sure what its complexity is, O(N^10) where N is number of unique characters ?

One observation: If I assign 0 to all characters then the condition of sum as well as all occurrences having same value are met. So, the algorithm will never return -1 in any case.

Plz clear my doubt ...Can two diff character can have same digit ???

The OP's backtracking algorithm is polynomial. There are 10^26 ways of assigning digits to letters. For each of these assignments all you have to do is an addition to check if it is right. So the worst case is O(length of shorter addend), with a humongous multiplier.

see dot stanford dot edu/materials/icspacs106b/H19-RecBacktrackExamples.pdf

s1 = "hard" s2 = "work", s3 = "success" ;
isnt this -1 , since hard and work is 4 digits and "success" is 7 digits.
I think we can never satisfy s1 + s2 = s3, for this case

This problem couldn't be solved in polynomial time because in worst case there would be exponential number of solutions.

There is a better solution than permutation. The trick is when given digital from s1 and s2, there is only one possible digital on s3.
0+1 => 1
1+1 => 2
9+8 => 7.

Take the example "send" "more" "money", I can get s=9 & m=1, and others = 0

// assume s1 and s2 the same length
	bool testCombination(string s1, string s2, string s3, int p, int c, int e, int e3, unordered_map<char, int> &map)
	{
		int p12 =e - p;
		int p3 =e3 - p;

		if (p12 < 0)
		{
			// s3 same length as s1, s2
			if (p3 < 0 && c == 0)
			{
				for (unordered_map<char,int>::iterator ite = map.begin(); ite != map.end(); ite++)
				{
					cout<<ite->first<<" = "<<ite->second<<endl;
				}
				return true;
			}
			else if (c > 0 && (map.find(s3[p3]) == map.end() || map[s3[p3]] == c))
			{
				map[s3[p3]] = c;
				for (unordered_map<char,int>::iterator ite = map.begin(); ite != map.end(); ite++)
				{
					cout<<ite->first<<" = "<<ite->second<<endl;
				}
				return true;
			}
			return false;
		}

		int start1 = map.find(s1[p12]) == map.end()? 0 : map[s1[p12]];
		int end1 = map.find(s1[p12]) == map.end()? 9 : map[s1[p12]];

		int start2 = map.find(s2[p12]) == map.end()? 0 : map[s1[p12]];
		int end2 = map.find(s2[p12]) == map.end()? 9 : map[s1[p12]];

		for(int i=start1; i<= end1; i++)
		{
			int cv1 = i;
			unordered_set<char> newValues1;
			if (map.find(s1[p12]) == map.end())
			{
				map[s1[p12]] = i;
				newValues1.insert(s1[p12]);
			}
			else if (i > start1) // already tested once
			{
				break;
			}
			else
			{
				cv1 = map[s1[p12]]; 
			}

			for(int j=start2; j<= end2; j++)
			{
				unordered_set<char> newValues2;
				int cv2 = j;
				if (map.find(s2[p12]) == map.end())
				{
					map[s2[p12]] = j;
					newValues2.insert(s2[p12]);
				}
				else if (j > start2)
				{
					break;
				}
				else
				{
					cv2 = map[s2[p12]]; 
				}

				int cv3 = cv1+cv2+c;
				int cv31 = cv3 % 10;
				int cv32 = cv3 / 10;
				// never seen before
				if (map.find(s3[p3]) == map.end())
				{
					map[s3[p3]] = cv31;
					newValues2.insert(s3[p3]);
					if (testCombination(s1, s2, s3, p+1, cv32, e, e3, map))
					{
						return true;
					}
				}
				else if (map[s3[p3]] == cv31)
				{
					if (testCombination(s1, s2, s3, p+1, cv32, e, e3, map))
					{
						return true;
					}
				}
				// recover back
				for (unordered_set<char>::iterator ite = newValues2.begin(); ite != newValues2.end(); ite++)
				{
					map.erase(*ite);
				}
			}
			// recover back
			for (unordered_set<char>::iterator ite = newValues1.begin(); ite != newValues1.end(); ite++)
			{
				map.erase(*ite);
			}
		}
		return false;
	}

	bool testCombination(string s1, string s2, string s3)
	{
		unordered_map<char, int> map;
		return testCombination(s1, s2, s3, 0, 0, s1.length()-1, s3.length()-1, map);
	}

Assume s1.length == s2.length, I give a simplied code. Take s1.length != s2.length, more code is needed.

#include <unordered_map>
#include <string>
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
using namespace std;
class Solution {
public:
unordered_map<char,int> res;
bool exist[10];
bool isValid(string& s1, string& s2, string& s3, int num, int depth, int x, int y) {
int s1len = s1.length(), s2len = s2.length(), s3len = s3.length();
return (x != y)&&(y != num%10)&&(x != num%10)&&(!exist[x] && res[s1[s1len-depth]] == -1 || res[s1[s1len-depth]] == x)&&(!exist[y] && res[s2[s2len-depth]] == -1 || res[s2[s2len-depth]] == y)&&(!exist[num%10] && res[s3[s3len-depth]] == -1 || res[s3[s3len-depth]] == num%10);
}
void setFlg(string& s1, string& s2, string& s3, int depth, int x, int y, int z, bool flgX, bool flgY, bool flgZ) {
int s1len = s1.length(), s2len = s2.length(), s3len = s3.length();
res[s1[s1len-depth]] = x, res[s2[s2len-depth]] = y,res[s3[s3len-depth]] = z;
exist[x] = flgX, exist[y] = flgY, exist[z] = flgZ;
}
bool dfs(string& s1, string& s2, string& s3, int carry, int depth) {
int s1len = s1.length(), s2len = s2.length(), s3len = s3.length(),i,j,x = 0,y = 0, saveX, saveY, saveZ;
bool saveFlgX, saveFlgY, saveFlgZ;

for (i = 0; i <= 9; ++i)
for (j = 0; j <=9; ++j) {
int num = i + j + carry;
if (isValid(s1, s2, s3, num, depth, i, j)) {
saveX = res[s1[s1len-depth]], saveY = res[s2[s2len-depth]], saveZ = res[s3[s3len-depth]], saveFlgX = exist[i], saveFlgY = exist[j], saveFlgZ = exist[num%10];
setFlg(s1, s2, s3, depth, i, j, num%10, true, true, true);
if (depth == s2len) {
if (s3len - s2len == 0 && num / 10 == 0)
return true;
else if (s3len > s2len && (res[s3[s3len-depth-1]] == -1 && !exist[num/10] || res[s3[s3len-depth-1]] == num/10)) {
res[s3[s3len-depth-1]] = num/10;
exist[num/10] = true;
return true;
}
}
else {
if (dfs(s1, s2, s3, num / 10, depth + 1))
return true;
}
res[s1[s1len-depth]] = saveX, res[s2[s2len-depth]] = saveY, res[s3[s3len-depth]] = saveZ, exist[i] = saveFlgX, exist[j] = saveFlgY,exist[num%10] = saveFlgZ;
}
}
return false;
}
bool check(string& s1, string& s2, string& s3) {
int s1len = s1.length(), s2len = s2.length(), s3len = s3.length(),i,j;
string s = s1 + s2 + s3;
for (i = 0; i < s.length(); ++i)
if (res.find(s[i]) == res.end()) {
res.insert(make_pair(s[i],-1));
}
memset(exist, false, sizeof(exist));
if (res.size() >10 ||s1len > s3len)
return false;
int s1s2len = max(s1len, s2len);
for (i = 0; i < (s3len - s1s2len - 1); ++i) {
if (res[s3[i]] == -1 && !exist[0]) {
res[s3[i]] = 0;
exist[0] = true;
}
else if (exist[0])
return false;
}
return s1len < s2len ? dfs(s2, s1, s3, 0, 1):dfs(s1, s2, s3, 0, 1);
}
};

int main() {
Solution s;
string a = "SEND", b = "MORE", c = "MONEY";
bool res = s.check(a,b,c);
return 0;
}

Assuming we can assign any numeric value and any two characters can have same value.
First count the number of characters in s1= count(s1),s2= count(s2) and s3= count(s3).
int diff = 0;
if ( count(s1) > count(s2) )
{ diff = count(s3)-count(s1);
}else{
diff = count(s3)-count(s2);
}

if (diff ==0){
//assign any one numeric value between (1-4)to all the characters
}else if(diff ==1){
//assign any one numeric value between (5-9)to all the characters
}
else{
return -1;
}

If s1 and s2 are both 4-letter words ("hard" and "work"), can the resulting s3 have more than 5 letters, like "success?

yes. s, u can be assigned zero, since the question didnt say the letters should have unique numbers