Puzzle: Solve a cryptarithm problem with Go

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 non-empty 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 non-empty 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 to 9.
It is guaranteed that solution only contains entries for the letters present in crypt 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 the solution represents the correct solution to the cryptarithm crypt, otherwise return false.

Solution

The first step is to parse the input parameters of the function solution, which are the crypt array and the solution 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 the solution 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 function concatInt 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 returns true. Otherwise, it returns false.
Finally, the main function solution is called with the crypt array and solution 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