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[0].split("\\+");
String rhs = breakUp[1];
HashSet<Character> charSet = new HashSet<Character>();
for (char charVal : equation.toCharArray()) {
if (!(charVal == '+' || charVal == '=')) {
charSet.add(new Character(charVal));
}
}
char[] refCharVals = new char[10];
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++) {
if (current.add(chars[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;
}