Mystery sum with placeholder digits

I came across this coding problem.

Back in primary school, maybe you were sometimes asked to solve a fill-in-the-blank sum - or "mystery sum" - in which certain digits are removed and you had to figure out what they originally were.

Now, it's time for serious business: sums with no digits, where every digit is replaced by a letter. Within each seperate sum, a letter replaces one digit and it is always the same letter for that one digit.

For example, in the sum below: A+BB=ACC The aim is to figure out which digits are hidden behind the letters A, B and C so that the sum turns out correct. Here, the solution is that A replaces 1, B replaces 9 and C replaces 0; resulting in: 1+99=100

Finally, there is the constraint that the length of the given word is equal to the length of the hidden number. Thus, in the sum CHEVAL+VACHE=OISEAU, CHEVAL is indeed a 6 digit number: the C (more precisely the first letter of any word) cannot correspond to a zero.

For each given sum, there is only one possible solution to the problem. You are asked to write the result value of the sum to the standard output.

INPUT: One line : a sum in the form WORD1+WORD2=RESULT, in which each word is a sequence of capital letters.

OUTPUT: The result of the solved sum.

CONSTRAINTS: Each sum has 2 to 20 words, each made up of 1 to 20 capital letters

I solved it using brute force checking against each permutation of assigned integers to the unique characters. Can anybody suggest a better strategy or algorithm?

public static void mysterySum(String equation) {
String[] breakUp = equation.split("=");
String[] lhs = breakUp.split("\\+");
String rhs = breakUp;

HashSet<Character> charSet = new HashSet<Character>();
for (char charVal : equation.toCharArray()) {
if (!(charVal == '+' || charVal == '=')) {
}
}

char[] refCharVals = new char;

int i = 0;
for (Character charVal : charSet) {
refCharVals[i++] = charVal;
}
while (i < 10)
refCharVals[i++] = '=';

String refString = new String(refCharVals);
StringBuilder currRef = new StringBuilder();
checkAllPermutations(refString, currRef, lhs, rhs);

}

private static void checkAllPermutations(String string, StringBuilder outstr,   String[] lhs, String rhs) {

if (resultMatched)
return;

HashSet<Character> current = new HashSet<>();
if (string.length() == 0) {
HashMap<Character, Integer> refChars = getRefMap(outstr);

int sumLhs = 0;
for (String strNumber : lhs) {
int number = getnumber(strNumber, refChars);
sumLhs += number;
}

int rhsNumber = getnumber(rhs, refChars);
if(rhsNumber == sumLhs) {
resultMatched = true;
System.out.println(rhsNumber);}
return;
}

char[] chars = string.toCharArray();

for (int i = 0; i < chars.length; i++) {
outstr.append(chars[i]);
checkAllPermutations(string.substring(0, i) + string.substring(i + 1, string.length()), outstr, lhs, rhs);
outstr.setLength(outstr.length() - 1);
if(resultMatched) break;
}

}

}

private static int getnumber(String strNumber,  HashMap<Character, Integer> refChars) {
int number = 0;
for (int i = 0; i < strNumber.length(); i++) {
number = number * 10 + refChars.get(strNumber.charAt(i));
}
return number;

}

private static HashMap<Character, Integer> getRefMap(StringBuilder outstr) {
HashMap<Character, Integer> refChars = new HashMap<>();

for (int i = 0; i < outstr.length(); i++) {
if (outstr.charAt(i) != '=')
refChars.put(outstr.charAt(i), i);
}

return refChars;
}
• Is this how your code is really indented? (Use Ctrl-K to indent a whole code block.) Jun 3 '15 at 8:47

As for a review of the code I would suggest to avoid acronyms (also recommend, as @200_success did, to better indent the code, in case this is how your code is indented).

As for the solution, I would strongly avoid brute force ones. This is a cryptarithmetic problem and, if you work only on base 10, you have 10! possible assignments, but if you generalize (for any base) then the problem is NP-complete. I would suggest to look for solutions for cryptarithmetic problems (usually they are described on texts/sources on AI).

I think a good idea can be start by some "bounds steps" where you try to obtain bounds on your digits. For example, in A + BB = ACC you have A >= 1 and A <= 9, BB >= 11 and BB <= 99. From that, you can obtain that ACC <= 108 and then A=1. Then, you inject A=1 in the equation, and you restart this process.

If I should implement it, I think I start by a renaming of the variables in A,B,...,J. Then I work with :

• list of possible digits for each letter
• list of possible letters for each digit
• bounds on each word

and I update that at each new observation, and restart the step with the new constraints.

• What happened to 10? You said BB>=11, and A<=9. Jun 3 '15 at 12:37
• BB has 2 identical digits... the lowest is 11. Jun 3 '15 at 12:46
• Only in that particular instance though. May be good Rio note that Jun 3 '15 at 12:57
• It's an example... Moreover, if you consider AB numbers, you have AB >= 10 but AB <= 98. The bound depends of the word, of course. Jun 3 '15 at 13:05