Get Set and Code: PREPARING TEST

PROBLEM CODE: MATH88

In this article, we are going to see how to solve the problem PREPARING TEST of GET SET AND CODE contest.

Problem link:

Contest Page | CodeChef

Difficulty- Hard

Prerequisites — Backtracking, Verbal Arithmetic, DFS

Problem Description:

Two friends David and Rojer were preparing for their weekly class-test. The are preparing for the math test, but because of continuously adding big integers and solving equations they got exhausted. They decided to take break and play a game. They play a game which will help them in both(for having fun and will also help to prepare for math test). There are N words and they have to find RESULT with the help of these words (just like they have N integers and they have to find integer RESULT=sum of N integers) . Since they are playing this game for the first time! They are not too good in this. Help them in finding weather their RESULT is correct or not.

NOTE:- Total number of unique characters in N words are not greater than 10. All input words and RESULT are in UPPER-CASE only!

Input:

• First line consist of an integer N (total number of words).
• Next N line contains words with which they have to find RESULT.
• Last line consist of the RESULT they found.

Output:

If RESULT is correct print “true” else print “false”.

Sample Input:

3
THIS
IS
TOO
FUNNY

Sample Output:

true

Constraints

• 2≤N≤102≤N≤10
• 1≤LengthofTheword≤101≤LengthofTheword≤10
• 1≤LengthofTheResult≤11

Quick Understanding of problem:

There will be N-words and a result word. We have to assign each character to a number(1 to 9) and replace the characters of N-words and result words with corresponding numbers. If the sum of numbers of N words are equal to the result word number then print True.

EXPLANATION:

Suppose we have an equation; expressions are represented by words on left side and the result on right side. We have to check whether the equation is solvable under the following rules or not −
• Each character is decoded as one digit (0 to 9).
• Every pair of different characters must map to different digits.
• Each word[i] and result are decoded as a number where no leading zeros are present.
• Sum of numbers on the left side will equal to the number on the right side.
• We will check whether the equation is solvable or not.
So, if the input is like words = [“SEND”,“MORE”], result = “MONEY”,
Then the output will be True, as when we map the letters as follows:

Map ‘S’-> 9, ‘E’->5, ‘N’->6, ‘D’->7, ‘M’->1, ‘O’->0,‘R’->8, ‘Y’->‘2’,
Then “SEND” + “MORE” = “MONEY” is same as 9567 + 1085 = 10652.
For more details please refer this LINK

Solution :

Time Complexity — O(n!).

Java Code:

import java.*;
import java.util.*;
class Solution {
  public boolean isSolvable(String[] words, String result) {
     reverseWords(words);
     result = new StringBuilder(result).reverse().toString();       
    return isSolvable(words, result, new HashMap<>(), 
new HashSet<>(), 0, 0, 0);
}
private void reverseWords(String[] words) {
    for (int i = 0; i < words.length; i++) {
        words[i] = new StringBuilder(words[i]).reverse().toString();
    }
}
private boolean isSolvable(String[] words, String result, Map<Character, Integer> map, Set<Integer> used, int i, int j, int sum) {
    if (i >= result.length()) {
        return sum == 0;
    }
    
    if (j >= words.length) {
        if (map.containsKey(result.charAt(i))) {
            if (map.get(result.charAt(i)) != sum % 10) {
                return false;
            }
            
            if (i + 1 == result.length() && map.get(result.charAt(i)) == 0) {
                return false;
            }
  
            return isSolvable(words, result, map, used, i + 1, 0, sum / 10);
         } 
 else if (!used.contains(sum % 10) && !(i + 1 == result.length() && sum % 10 == 0)) {
            map.put(result.charAt(i), sum % 10);
            used.add(sum % 10);
  
            if (isSolvable(words, result, map, used, i + 1, 0, sum / 10)) {
                return true;
            }
            used.remove(sum % 10);
            map.remove(result.charAt(i));
        }
        return false;
    }
    if (i >= words[j].length()) {
        return isSolvable(words, result, map, used, i, j + 1, sum);
    }
    if (map.containsKey(words[j].charAt(i))) {
        if (i + 1 == words[j].length() && map.get(words[j].charAt(i)) == 0) {
            return false;
        } 
        return isSolvable(words, result, map, used, i, j + 1, sum + map.get(words[j].charAt(i)));
    }
    for (int g = 0; g < 10; g++) {
        if (used.contains(g)) {
            continue;
        }
        if (g == 0 && i + 1 == words[j].length()) {
            continue;
        }
        map.put(words[j].charAt(i), g);
        used.add(g);
        if (isSolvable(words, result, map, used, i, j + 1, sum + g)) {
            return true;
        }
        used.remove(g);
        map.remove(words[j].charAt(i));
    }
    
    return false;
   }
}
class Main{
     public static void main(String args[]){
     Scanner sc=new Scanner(System.in);
     int n;
     n=sc.nextInt();
     String vec[]=new String[n];
     for(int i=0;i<n;i++){
         vec[i]=sc.next();
     }
     String result;
     result=sc.next();
     Solution sol=new Solution();
     if(sol.isSolvable(vec,result)){
         System.out.println("true");
     }
     else{
         System.out.println("false");
     }
    
 }
}