Verbal Arithmetic Puzzle

Posted: 14 Mar, 2021
Difficulty: Ninja

PROBLEM STATEMENT

Try Problem

You are given an array of the strings “words” of size 'M' and another string “result”. You have to treat it as an equation in which the left side is represented by the array “words” and the right side is represented by the string "result". Your task is to determine whether the equation is solvable or not under the following conditions:

1. Each character is decoded as a digit in the range [0, 9].
2. Each character must have only one mapping, and every pair of characters must map to different digits.
3. Each element of the array “words” and the string “result” are decoded as one number without the leading zeros.
4. The sum of the numbers on the left-hand side (words) must equal the number on the right-hand side (result).

Note:

1) The array “words”, and the string “result” contain only the uppercase English letters.
2) The number of different characters used in the expression is at most 10.
Input Format:
The first line contains an integer T, which denotes the number of test cases or queries to be run. Then, the T test cases follow. 

The first line of each test case contains a positive integer M denoting the size of the array “words”, as described in the problem statement.

The second line of each test case contains a sequence of M space-separated strings denoting the elements of the array.

The third line of each test case contains a string denoting the result string.
Output Format:
For each test case, print in a new line "true" if the equation is solvable and "false" otherwise.

Output for each test case will be printed in a separate line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 100
2 <= M <= 5
1 <= |WORDS[i]|, |RESULT| <= 7

The number of different characters used in the expression is at most 10.

Time Limit: 1sec
Approach 1

The idea here is to use the backtracking with one condition, which is explicitly mentioned in the problem itself that each word will decode as one number with no leading zeros. We know that if a + b = c, then a + b - c = 0 is also correct. So this is another condition which we are going to use in this approach.

 

First, add the ‘RESULT’ string in the array of string ‘WORDS’. We are traversing the array ‘WORDS’ from right to left column-wise. At each position, we have to know the ‘SUM’ we have so far, and for this, we'll use a variable named 'BALANCE', and we want it to be exactly zero at the end of all columns. So, if the 'BALANCE' is zero at the end of all columns, then return “true” as we have successfully found a valid mapping of the letter to the digit. If we completed a column and 'BALANCE' % 10 is not 0, then return “false”. Else we have to search in another column with balance as 'BALANCE' / 10. Because when we subtract the result string, we want each column’s last value to be zero, which we get by using the % function and the remaining part we’ll send for the further steps in the form of a carry, which is nothing but the updated 'BALANCE'.

 

If we are at the letter for which there is a prior mapping to digit, then we are going to use this mapping if the mapping is not zero. If it is zero, then the word has to be of length one, or the column in which we are currently at is not to be the last for that letter. Else, we have to assign a new mapping and call the function again.

 

Steps:

 

  1. Add 'RESULT' string into the array of string ‘WORDS’.
  2. Create two variables, 'TOTALROWS', and 'TOTALCOLS'.
  3. Initialize 'TOTALROWS' to the size of the array ‘WORDS and 'TOTALCOLS' to the size of the longest string in that array.
  4. Create a HashMap named 'LETTODIG' which is used to store the mapping of the letter to the digit.
  5. Create an array of data type char of size 10 named 'LETTODIG', which is used to find the current mapping of a particular digit to the letter. Initialize this array with the character ‘-’.
  6. Call the function isAnyMapping(‘WORDS, ‘ROW’, ‘COL’, ‘BAL’, 'LETTODIG', ‘DIGTOLET’, 'TOTALROWS', 'TOTALCOLS'), where ‘WORDS is the array of the string, ‘ROW’, and ‘COL’ denote the (COL)-th char in the (ROW)-th word from right to left which is initially 0, bal is the current balance which is also initially 0.
  7. isAnyMapping function will return “true” if there exists any possible mapping of the letters to the digits. Else it returns false.
  8. Return the value which is returned by the above function.

 

bool isAnyMapping(string words[], int row, int col, int bal, HashMap letToDig, char digToLet[], int totalRows, int totalCols):

 

  1. If ‘COL’ == 'TOTALCOLS'  and ‘BAL’ == 0, then return true. Else, return false.
  2. If ‘ROW’ ==  'TOTALROWS', then it implies that we are at the end of the column. So, return ('BAL' % 10 == 0 and isAnyMapping('WORDS', 0, ‘COL’ + 1, ‘BAL’ / 10, 'LETTODIG', ‘DIGTOLET’,  'TOTALROWS', 'TOTALCOLS' ).
  3. Create a new string ‘W’ to store the current word, ‘W’ = ‘WORDS[ROW]'.
  4. If ‘COL’ >= length of the ‘W’ (this can happen if the current word has a smaller length), then return the function isAnyMapping('WORDS', ‘ROW’ + 1, ‘COL’, ‘BAL’, 'LETTODIG', ‘DIGTOLET’,  'TOTALROWS', 'TOTALCOLS' ).
  5. Create a variable ‘LETTER’ of data type char and set it with the current character of the word.
  6. Create a new variable ‘SIGN’. Make it as 1 if we are not in the last row. Else, it is -1. This variable is used to find whether we have to add the digit or subtract the digit.
  7. If we have a prior mapping and if this mapping is valid, i.e., it will not have leading zeros, then call the function again by using the prior mapping. To check whether the prior mapping is valid or not, we can use the following conditions:
    • If ‘LETTER’ is present in the HashMap 'LETTODIG' and ('LETTODIG[LETTER]' != 0 or (if ‘LETTODIG[LETTER]’ == 0 and W.length() == 1) or ‘COL’ != W.length() - 1), then:
      • return isAnyMapping('WORDS', ‘ROW’ + 1, ‘COL’, ‘BAL’ + ‘SIGN’ * ‘LETTODIG[LETTER]’, 'LETTODIG', ‘DIGTOLET’, 'TOTALROWS', 'TOTALCOLS' ).
  8. Else, we have to find a new mapping. So, run a loop with variable i from 0 to 10, in each iteration:
    • if('DIGTOLET[i]' == ‘-’ and ('i' != 0 or ('i' == 0 and W.length() == 1) or ‘COL’ != W.length() - 1), then:
      • ‘DIGTOLET[i]’ = ‘LETTER’
      • ‘LETTODIG[LETTER]’ = ‘i’
      • ‘X’ = isAnyMapping( 'WORDS', ‘ROW’ + 1, ‘COL’, ‘BAL’ + ‘SIGN’ * ‘LETTODIG[LETTER]’, 'LETTODIG', ‘DIGTOLET’, 'TOTALROWS', 'TOTALCOLS' ).
      • If ‘X’ is true, then return true.
      • ‘DIGTOLET[i]’ = ‘-’
      • If the letter to digit mapping present in the HashMap 'LETTODIG', then remove this mapping.
  9. Finally, return false.
Try Problem