Mystery sum with placeholder digits

Question

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;
}

Answer 1

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).

Answer 2

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.