Puzzle: Solve a cryptarithm problem with Go
April 3, 2023
Problem
A cryptarithm can be defined as a type of mathematical puzzle that involves the arrangement of letters and digits in an arithmetic expression. The main objective of this puzzle is to decipher the correct correspondence between the letters and digits so that the equation holds true when the letters are replaced by their corresponding digits.
You have an array of strings crypt
, the cryptarithm, and an an array containing the mapping of letters and digits, solution
. The array crypt
will contain three nonempty strings that follow the structure: [word1, word2, word3]
, which should be interpreted as the word1 + word2 = word3
cryptarithm.
If crypt
, when it is decoded by replacing all of the letters in the cryptarithm with digits using the mapping in solution
, becomes a valid arithmetic equation containing no numbers with leading zeroes, the answer is true
. If it does not become a valid arithmetic solution, the answer is false
.
Note that number 0
doesn't contain leading zeroes (while for example 00
or 0123
do).
Example
For crypt = ["SEND", "MORE", "MONEY"]
and
solution = [['O', '0'], ['M', '1'], ['Y', '2'], ['E', '5'], ['N', '6'], ['D', '7'], ['R', '8'], ['S', '9']]
the output should be
solution(crypt, solution) = true
.
When you decrypt "SEND"
, "MORE"
, and "MONEY"
using the mapping given in crypt
, you get 9567 + 1085 = 10652
which is correct and a valid arithmetic equation.
For crypt = ["TEN", "TWO", "ONE"]
and
solution = [['O', '1'], ['T', '0'], ['W', '9'], ['E', '5'], ['N', '4']]
the output should be
solution(crypt, solution) = false
.
Even though 054 + 091 = 145
, 054
and 091
both contain leading zeroes, meaning that this is not a valid solution.
Input/Output

[execution time limit] 4 seconds (go)

[input] array.string crypt
An array of three nonempty strings containing only uppercase English letters.
Guaranteed constraints:
crypt.length = 3
,
1 ≤ crypt[i].length ≤ 14
. 
[input] array.array.char solution
An array consisting of pairs of characters that represent the correspondence between letters and numbers in the cryptarithm. The first character in the pair is an uppercase English letter, and the second one is a digit in the range from
0
to9
.It is guaranteed that
solution
only contains entries for the letters present incrypt
and that different letters have different values.Guaranteed constraints:
solution[i].length = 2
,
'A' ≤ solution[i][0] ≤ 'Z'
,
'0' ≤ solution[i][1] ≤ '9'
,
solution[i][0] ≠ solution[j][0], i ≠ j
,
solution[i][1] ≠ solution[j][1], i ≠ j
. 
[output] boolean
Return
true
if thesolution
represents the correct solution to the cryptarithmcrypt
, otherwise returnfalse
.
Solution

The first step is to parse the input parameters of the function
solution
, which are thecrypt
array and thesolution
array. 
The next step is to create a dictionary or hash map that maps each letter in the
solution
array to its corresponding digit. This is done using a loop that iterates through thesolution
array and assigns the corresponding digit to each letter. 
After creating the mapping, the next step is to decode each string in the
crypt
array to its corresponding integer value. This is done by using a helper functionconcatInt
that takes a string and the mapping and returns the corresponding integer value. 
The
concatInt
function converts each character in the string to its corresponding digit using the mapping and concatenates them to form the integer value. It also checks for the presence of leading zeros by verifying if the first character in the string maps to 0 and the length of the string is greater than 1. 
The decoded integer values of the first two strings in the
crypt
array are added and compared with the decoded integer value of the third string to check if the equation holds true. If the equation holds true and no leading zeros are present in the decoded integer values, the function returnstrue
. Otherwise, it returnsfalse
. 
Finally, the main function
solution
is called with thecrypt
array andsolution
array as input parameters, and the output is returned.
Code
func solution(crypt []string, solution [][]string) bool { pair:=map[byte]int{} for i:= range solution{ pair[solution[i][0][0]] = int(solution[i][1][0]'0') } a,validA := concatInt(crypt[0], pair) b, validB := concatInt(crypt[1], pair) c, validC := concatInt(crypt[2], pair) if !validA  !validB  !validC{ return false } return (a+b) == c}func concatInt(crypt string, keys map[byte]int) (result int, valid bool){ str:="" for i:= range crypt{ str+=fmt.Sprintf("%d",keys[crypt[i]]) result = result*10 + keys[crypt[i]] } return result, !(keys[crypt[0]]==0 && len(crypt)>1)}
Try on playground https://go.dev/play/p/GzFUMpo0hax (opens in a new tab)