3
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ Is this how your code is really indented? (Use Ctrl-K to indent a whole code block.) \$\endgroup\$ – 200_success Jun 3 '15 at 8:47
2
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ What happened to 10? You said BB>=11, and A<=9. \$\endgroup\$ – Evan Bechtol Jun 3 '15 at 12:37
  • \$\begingroup\$ BB has 2 identical digits... the lowest is 11. \$\endgroup\$ – Caduchon Jun 3 '15 at 12:46
  • \$\begingroup\$ Only in that particular instance though. May be good Rio note that \$\endgroup\$ – Evan Bechtol Jun 3 '15 at 12:57
  • \$\begingroup\$ 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. \$\endgroup\$ – Caduchon Jun 3 '15 at 13:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.