master
1<<-DOC
2A cryptarithm is a mathematical puzzle for which the goal is to find the correspondence between letters and digits,
3such that the given arithmetic equation consisting of letters holds true when the letters are converted to digits.
4
5You have an array of strings crypt, the cryptarithm, and an an array containing the mapping of letters and digits, solution.
6The array crypt will contain three non-empty strings that follow the structure: [word1, word2, word3],
7which should be interpreted as the word1 + word2 = word3 cryptarithm.
8
9If crypt, when it is decoded by replacing all of the letters in the cryptarithm with digits using the mapping in solution,
10becomes a valid arithmetic equation containing no numbers with leading zeroes, the answer is true.
11If it does not become a valid arithmetic solution, the answer is false.
12
13Example
14
15For crypt = ["SEND", "MORE", "MONEY"] and
16
17solution = [['O', '0'],
18 ['M', '1'],
19 ['Y', '2'],
20 ['E', '5'],
21 ['N', '6'],
22 ['D', '7'],
23 ['R', '8'],
24 ['S', '9']]
25the output should be
26isCryptSolution(crypt, solution) = true.
27
28When you decrypt "SEND", "MORE", and "MONEY" using the mapping given in crypt,
29you get 9567 + 1085 = 10652 which is correct and a valid arithmetic equation.
30
31For crypt = ["TEN", "TWO", "ONE"] and
32
33solution = [['O', '1'],
34 ['T', '0'],
35 ['W', '9'],
36 ['E', '5'],
37 ['N', '4']]
38the output should be
39isCryptSolution(crypt, solution) = false.
40
41Even though 054 + 091 = 145, 054 and 091 both contain leading zeroes, meaning that this is not a valid solution.
42
43Input/Output
44
45[time limit] 4000ms (rb)
46[input] array.string crypt
47
48An array of three non-empty strings containing only uppercase English letters.
49
50Guaranteed constraints:
51crypt.length = 3,
521 ≤ crypt[i].length ≤ 14.
53
54[input] array.array.char solution
55
56An array consisting of pairs of characters that represent the correspondence between letters and numbers in the cryptarithm.
57The first character in the pair is an uppercase English letter, and the second one is a digit in the range from 0 to 9.
58
59Guaranteed constraints:
60solution[i].length = 2,
61'A' ≤ solution[i][0] ≤ 'Z',
62'0' ≤ solution[i][1] ≤ '9',
63solution[i][0] ≠ solution[j][0], i ≠ j,
64solution[i][1] ≠ solution[j][1], i ≠ j.
65
66It is guaranteed that solution only contains entries for the letters present in crypt and that different
67letters have different values.
68
69[output] boolean
70
71Return true if the solution represents the correct solution to the cryptarithm crypt, otherwise return false.
72DOC
73
74describe "#is_crypt_solution" do
75 def crypt_solution?(crypt, solution)
76 mapping = solution.to_h
77 decoded = crypt.map do |word|
78 word.chars.map { |x| mapping[x] }.join
79 end
80
81 return false if decoded.any? { |x| x.size > 1 && x[0] == "0" }
82 decoded[0].to_i + decoded[1].to_i == decoded[2].to_i
83 end
84
85 [
86 { crypt: ["SEND", "MORE", "MONEY"], solution: [["O","0"], ["M","1"], ["Y","2"], ["E","5"], ["N","6"], ["D","7"], ["R","8"], ["S","9"]], x: true },
87 { crypt: ["TEN", "TWO", "ONE"], solution: [["O","1"], ["T","0"], ["W","9"], ["E","5"], ["N","4"]], x: false },
88 { crypt: ["ONE", "ONE", "TWO"], solution: [["O","2"], ["T","4"], ["W","6"], ["E","1"], ["N","3"]], x: true },
89 { crypt: ["ONE", "ONE", "TWO"], solution: [["O","0"], ["T","1"], ["W","2"], ["E","5"], ["N","6"]], x: false },
90 { crypt: ["A", "A", "A"], solution: [["A","0"]], x: true },
91 { crypt: ["A", "B", "C"], solution: [["A","5"], ["B","6"], ["C","1"]], x: false },
92 { crypt: ["AA", "AA", "AA"], solution: [["A","0"]], x: false },
93 { crypt: ["A", "A", "A"], solution: [["A","1"]], x: false },
94 { crypt: ["AA", "AA", "BB"], solution: [["A","1"], ["B","2"]], x: true },
95 { crypt: ["BAA", "CAB", "DAB"], solution: [["A","0"], ["B","1"], ["C","2"], ["D","4"]], x: false },
96 { crypt: ["BAA", "CAB", "DAB"], solution: [["A","0"], ["B","1"], ["C","2"], ["D","3"]], x: true },
97 { crypt: ["BAA", "BAA", "CAA"], solution: [["A","0"], ["B","1"], ["C","2"]], x: true },
98 { crypt: ["AA", "BB", "AA"], solution: [["A","1"], ["B","0"]], x: false },
99 { crypt: ["FOUR", "FOUR", "EIGHT"], solution: [["F","5"], ["O","2"], ["U","3"], ["R","9"], ["E","1"], ["I","0"], ["G","4"], ["H","7"], ["T","8"]], x: true },
100 { crypt: ["AAAAAAAAAAAAAA", "BBBBBBBBBBBBBB", "CCCCCCCCCCCCCC"], solution: [["A","0"], ["B","1"], ["C","2"]], x: false },
101 { crypt: ["AAAAAAAAAAAAAA", "BBBBBBBBBBBBBB", "CCCCCCCCCCCCCC"], solution: [["A","1"], ["B","2"], ["C","3"]], x: true },
102 { crypt: ["WASD", "IJKL", "OPAS"], solution: [["W","2"], ["A","4"], ["S","7"], ["D","9"], ["I","1"], ["J","0"], ["K","6"], ["L","8"], ["O","3"], ["P","5"]], x: true },
103 { crypt: ["WASD", "IJKL", "OPAS"], solution: [["W","2"], ["A","0"], ["S","4"], ["D","1"], ["I","5"], ["J","8"], ["K","6"], ["L","3"], ["O","7"], ["P","9"]], x: true },
104 { crypt: ["WASD", "IJKL", "AOPAS"], solution: [["W","2"], ["A","0"], ["S","4"], ["D","1"], ["I","5"], ["J","8"], ["K","6"], ["L","3"], ["O","7"], ["P","9"]], x: false },
105 { crypt: ["BLACK", "BLUE", "APPLE"], solution: [["B","5"], ["L","8"], ["A","6"], ["C","7"], ["K","0"], ["U","1"], ["E","9"], ["P","4"]], x: true },
106 { crypt: ["A" * 13, "A" * 13, "Z" * 13], solution: [["A", "1"], ["Z", "2"]], x: true },
107 { crypt: ["A" * 13, "Z", "Z" + ("B" * 13)], solution: [["A", "9"], ["B", "0"], ["Z", "1"]], x: true },
108 { crypt: [('A'..'Z').to_a.join, ('A'..'Z').to_a.join, "C"], solution: ('A'..'Z').each_with_index.map { |x, y| [x, (y + 1).to_s] }, x: false },
109 ].each do |x|
110 it do
111 expect(crypt_solution?(x[:crypt], x[:solution])).to eql(x[:x])
112 end
113 end
114end