-
Notifications
You must be signed in to change notification settings - Fork 36
/
Cryptarithm.js
60 lines (50 loc) · 1.76 KB
/
Cryptarithm.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
// https://www.codingame.com/training/hard/cryptarithm
/**
* Generates all permutations of a set.
* @param {Array|String} arr - The set of elements.
* @param {Number} size - Number of elements to choose from the set.
*/
function* permutation(arr, size = arr.length) {
const data = [];
const indicesUsed = [];
yield* permutationUtil(0);
/**
* @param {Number} index of permutation
* @return {Generator}
*/
function* permutationUtil(index) {
if (index === size) {
return yield this.clones ? data.slice() : data;
}
for (let i = 0; i < arr.length; i++) {
if (!indicesUsed[i]) {
indicesUsed[i] = true;
data[index] = arr[i];
yield* permutationUtil(index + 1);
indicesUsed[i] = false;
}
}
}
}
// We generate a permutation and checking if the sum is valid
const r = () => readline().split('');
const words = [...Array(+readline())].map(() => r());
const wordsTotal = r();
const dictionary = [...new Set([...words, wordsTotal].flat())].sort();
const permutationGenerator =
permutation([...Array(10).keys()], dictionary.length);
for (let permutation of permutationGenerator) {
const keyValueArray = dictionary.map((v, i) => [v, permutation[i]]);
const cryptMap = new Map(keyValueArray);
if (cryptMap.get(wordsTotal[0]) === 0) continue;
const wordToNumber =
(arr) => +arr.map((char) => cryptMap.get(char)).join('');
const sumWords =
words.map((word) => wordToNumber(word))
.reduce((sum, curr) => sum+=curr);
const sumTotal = wordToNumber(wordsTotal);
if (sumWords === sumTotal) {
cryptMap.forEach((value, key) => console.log(key, value));
break;
}
}