Verbal Arithmetic Puzzle Problem in Java
The definition of Alphametics, also referred to as verbal arithmetic, is "a kind of mathematical game that involves a mathematical equation among unknown numbers, where digits are represented by letters." Determining the value of every letter is the objective." Given an equation, the result is shown on the right side, while the words are displayed on the left.
The first step is to determine whether the problem can be solved using the following criteria:
- From 0 to 9, every character is encoded as a single digit.
- A character cannot map to a digit twice.
- The decoded result and each word[i] are both one number with no leading zeros.
- The total of the numbers on the left (words) will match the number on the right (outcome).
If it is able to solve the equation, return true; if not, return false.
Note: 1) The only letters in the string "result" and the array "words" are uppercase English letters.
2) There are at most 10 distinct characters utilized in the statement.
3) There is no way for the two different characters to be assigned to the same number.
Example 1:
Input:
words = ["SEND", "MORE"], result = "MONEY"
Output:
The puzzle is solvable
Explanation:
For the given words, the string "result" and the input words are compared such that the characters present in the result are there in the input words. Hence Mapping takes place as 'S'-> 9, 'E'->5, 'N'->6, 'D'->7, 'M'->1, 'O'->0, 'R'->8, 'Y'->'2'. Now "SEND" + "MORE" = "MONEY", 9567 + 1085 = 10652 (10652 = 10652). Therefore, the puzzle is solvable.
Example 2:
Input:
words = ["SIX", "SEVEN", "SEVEN"], result = "TWENTY"
Output:
The puzzle is solvable
Explanation:
For the given words, the string "result" and the input words are compared such that the characters present in the result are there in the input words. Hence Mapping takes place as 'S'-> 6, 'I'->5, 'X'->0, 'E'->8, 'V'->7, 'N'->2, 'T'->1, 'W'->'3', 'Y'->4. Now "SIX" + "SEVEN" + "SEVEN" = "TWENTY", 650 + 68782 + 68782 = 138214 (138214 = 138214). Therefore, the puzzle is solvable.
Example 3:
Input:
words = ["JAVA", "CODE"], result = "JAVATPOINT"
Output:
The puzzle is not solvable
Explanation:
For the given words, the "result" string characters do not match the characters of the input words. We return false since there isn't a mapping that can satisfy the equation.
Approach: Using Backtracking
The objective is to apply the backtracking with a single condition, which is stated clearly in the problem statement that each word should be decoded to a single integer without any leading zeros. We are aware that if a + b = c, then a + b - c = 0 must also be true. Thus, we will be using this condition in addition to the other ones in our approach.
Algorithm:
Step 1: Insert the string "RESULT" into the "WORDS" array of strings.
Step 2: Make two variables, "TOTALCOLUMNS" and "TOTALROWS."
Step 3: Set 'TOTALCOLUMNS' to the length of the longest string in the array and 'TOTALROWS' to the size of the array 'WORDS.'
Step 4: Make a hash map called "LETTERTODIGMAP" to hold the correspondence between the letter and the number.
Step 5: To identify the current Mapping of a specific digit to the letter, this step involves creating an array of data type char of size ten called 'LETTERTODIGMAP.' Put the character "-" at the beginning of this array.
Step 6: In this, it calls the function isMapping('WORD', 'R', 'C', 'BAL', 'LETTERTODIGMAP', 'DIGTOLETTERMAP', 'TOTALR', 'TOTALC'), where 'ROW', 'COLUMNS', and 'WORDS' represent the array of the string, 'COLUMNS' indicates the (COLUMNS)-th char in the (ROW)-th word from right to left, which is initially 0, and bal indicates the current balance, which is also initially 0.
Step 7: The function isMapping will return "true" if there is a possible mapping from the letters to the digits. Otherwise, false is returned.
Step 8: This step is to return the value that the previous function returned.
Algorithm for isMapping() function:
Step 1: Return true if 'C' == 'TOTALCOLS' and 'BAL' == 0. Return false if not.
Step 2: It indicates that we have reached the end of the column if 'R' == 'TOTALR'. Returning ('BAL' % 10 == 0 and isMapping('WORD', 0, 'C' + 1, 'BAL' / 10, 'LETTERTODIGMAP', 'DIGTOLETTERMAP', 'TOTALR', 'TOTALC' ) is thereafter necessary.
Step 3: To save the current word, create a new string called "W," where "W" = "WORD[ROW]".
Step 4: Should 'C' exceed the length of 'W' (which may occur if the present word is shorter), then the function isMapping('WORD', 'R' + 1, 'C', 'BAL', 'LETTERTODIGMAP', 'DIGTOLETTERMAP', 'TOTALR', 'TOTALCOL' ) will be returned.
Step 5: Create a data type char variable called "LETTER" and assign its value to the word's current character.
Step6: Make a new variable called "SIGN." If we are not in the last row, then mark it as 1. Otherwise, the value is -1. This variable is used to determine if the digit needs to be added or subtracted.
Step 7: Call the function again using the previous Mapping if we have one and it is legitimate, meaning it won't contain leading zeros. The following criteria can be applied to determine the validity of the previous Mapping:
Step 7.1.1: return isMapping('WORDS', 'R' + 1, 'C', 'BAL' + 'SIGN' * 'LETTERTODIGMAP[LETTER]', 'LETTERTODIGMAP', 'DIGTOLETTERMAP', 'TOTALR', 'TOTALC' ).
Step 7.2: A new mapping must be found if not. Thus, execute a loop wherein each iteration of variable i ranges from 0 to 10:
Step 7.2.1: if('DIGTOLETTERMAP[i]' == '-' and ('i' != 0 or ('i' == 0 and W.length() == 1) or 'C' != W.length() - 1), then:
'DIGTOLETTERMAP[i]' = 'LETTER'
'LETTERTODIGMAP'[LETTER]' = 'i'
'X' = isMapping('WORDS', 'R' + 1, 'C', 'BAL' + 'SIGN' * 'LETTERTODIGMAP[LETTER]', 'LETTODIG', 'DIGTOLET', 'TOTALROWS', 'TOTALCOLS' ).
Step 8: Return true in the case that 'X' is true.
'DIGTOLETTERMAP[i]' = '-'.
Step 9: Remove the Mapping if the letter to digit mapping is included in the HashMap "LETTERTODIGMAP."
Step 10: In the end, return false.
Implementation:
FileName: VerbalArithmeticPuzzle.java
import java.util.ArrayList;
import java.util.HashMap;
import java.io.*;
public class VerbalArithmeticPuzzle
{
// A function for determining the best possible Mapping.
public static boolean isMapping(ArrayList < String > word, int r, int c, int bal, HashMap < Character, Integer > letterToDigMap, char[] digToLetterMap, int totalR, int totalC)
{
// If every column was checked.
if (c == totalC)
{
if(bal == 0)
{
return true;
}
else
{
return false;
}
}
// At the end of a specific column.
if (r == totalR)
{
return (bal % 10 == 0 && isMapping(word, 0, c + 1, bal / 10, letterToDigMap, digToLetterMap, totalR, totalC));
}
String w = word.get(r);
// In the case that the ('COLUMN')th index of the current string 'W' contains no characters.
if (c >= w.length())
{
return isMapping(word, r + 1, c, bal, letterToDigMap, digToLetterMap, totalR, totalC);
}
// Select the current character in the letter that is variable.
char letter = w.charAt(w.length() - 1 - c);
// In order to determine whether to add or subtract it, create the variable "SIGN."
int sign;
if (r < totalR - 1)
{
sign = 1;
}
else
{
sign = -1;
}
// Use the previous valid Mapping if we have one.
// The leading zeros are the second condition.
if (letterToDigMap.containsKey(letter) && (letterToDigMap.get(letter) != 0 || (letterToDigMap.get(letter) == 0 && w.length() == 1) || c != w.length() - 1))
{
return isMapping(word, r + 1, c, bal + sign * letterToDigMap.get(letter), letterToDigMap, digToLetterMap, totalR, totalC);
}
// Select a new mapping.
else
{
for (int i = 0; i < 10; i++)
{
// Choose it if the 'i'th Mapping is valid.
if (digToLetterMap[i] == '-' && (i != 0 || (i == 0 && w.length() == 1) || c != w.length() - 1))
{
digToLetterMap[i] = letter;
letterToDigMap.put(letter, i);
// Using the updated Mapping, call the method once more.
boolean x = isMapping(word, r + 1, c, bal + sign * letterToDigMap.get(letter),
letterToDigMap, digToLetterMap, totalR, totalC);
if (x == true)
{
return true;
}
// Unselect the Mapping.
digToLetterMap[i] = '-';
if (letterToDigMap.containsKey(letter))
{
letterToDigMap.remove(letter);
}
}
}
}
// Simply return false if nothing is correct.
return false;
}
public static boolean isSolvable(int m, ArrayList < String > word, String result)
{
// Expand the vector "WORDS" to include the string "RESULT."
word.add(result);
int totalR;
int totalC;
// Set 'TOTALROWS' to the vector's size during initialization.
totalR = word.size();
// Determine which string in the vector is the longest, then set the size of that string for 'TOTAL COLUMNS'.
totalC = 0;
for (int i = 0; i < word.size(); i++)
{
// Update 'TOTALCOLUMNS' with the length of the current string if it is the longest.
if (totalC < word.get(i).length())
{
totalC = word.get(i).length();
}
}
// For the letter to digit mapping, create a hash map.
HashMap < Character, Integer > letterToDigMap = new HashMap < Character, Integer >();
// Construct a vector for the Mapping of numbers to letters.
char[] digToLetterMap = new char[10];
for(int i = 0; i < 10; i++)
{
digToLetterMap[i] = '-';
}
return isMapping(word, 0, 0, 0, letterToDigMap, digToLetterMap, totalR, totalC);
}
public static void main(String[] args)
{
VerbalArithmeticPuzzle solpuzzle = new VerbalArithmeticPuzzle();
// Construct an ArrayList with the phrases that make up the puzzle.
ArrayList<String> word = new ArrayList<>();
word.add("SEND");
word.add("MORE");
String result = "MONEY";
// In order to solve the puzzle, call the isSolvable method.
boolean isSolvable = solpuzzle.isSolvable(word.size(), word, result);
// The puzzle's outcome will be displayed.
if (isSolvable)
{
System.out.println("The puzzle is solvable!");
}
else
{
System.out.println("The puzzle is not solvable.");
}
}
}
Output:
The puzzle is solvable!
Complexity Analysis:
O(N!) is the time complexity, where N is the total number of characters in the expression. At best, we can have N distinct letters; in the worst case, we have to examine every possible combination of the letter to the digit mapping. Thus, O(N!) will be the time complexity.
The number of distinct characters in the expression, N, determines the space complexity, which is O(N). In order to create a hash map for the letter to digit mapping, we must first create a recursion stack that can store a maximum of N characters in the worst situation. This stack will be utilized for all N characters in the Mapping. Because of this, the total space complexity will be O(N).