code. compile. run. debug. share.
Source Code
Language
/**
* Algorytm prostych zmian
* @param {number[]} a
*/
function* plainChanges(a) {
let n = a.length;
// tablice c oraz o będą o 1 element większe niż oryginalna, ponieważ będziemy indeksować od 1
let c = Array(n + 1);
let o = Array(n + 1);
let j, q, s;
// przesuwamy tablicę a, aby prawidłowe indeksy nam się numerowały od 1
a.unshift(undefined); // unshift wstawia element na początku tablicy
// 1. inicjalizacja
for (let i = 1; i <= n; i++) {
c[i] = 0;
o[i] = 1;
}
while (true) {
// 2. odwiedź
yield a.slice(1); // slice tworzy wycinek tablicy od n elementu do końca
// 3. przygotuj do zmiany
j = n;
s = 0;
while (true) {
// 4. gotowy do zmiany?
q = c[j] + o[j];
let skipSwap = false;
let skipIncrease = false;
if (q < 0) {
skipSwap = true;
skipIncrease = true;
}
if (q === j) {
skipSwap = true;
skipIncrease = false;
}
// 5. zmiana
if (!skipSwap) {
swap(a, j - c[j] + s, j - q + s);
c[j] = q;
break;
}
// 6. zwiększ s
if (!skipIncrease) {
if (j === 1) {
return;
} else {
s++;
}
}
// 7. zmień kierunek
o[j] = -o[j];
j--;
}
}
}
/**
* Funkcja zwracająca litery, które nie mogą być zerem
* @param {string[]} words
*/
function getNonZeroLetters(words) {
return new Set(words.map((x) => x[0]));
}
/**
* Funkcja sprawdzająca, czy litery które nie miały być zerem faktycznie nim nie są
* @param {Map<string, number>} letterMap
* @param {Set<string>} nonZeroLetters
*/
function checkZeroLetters(letterMap, nonZeroLetters) {
for (const nonZero of nonZeroLetters) {
if (letterMap.get(nonZero) === 0) {
return false;
}
}
return true;
}
/**
* Funkcja podstawiająca cyfry pod litery w słowach
* @param {string[]} words
* @param {Map<string, number>} letterMap
*/
function wordsToNumbers(words, letterMap) {
const result = [];
for (const word of words) {
let number = "";
for (const letter of word) {
number += letterMap.get(letter);
}
result.push(parseInt(number));
}
return result;
}
/**
* Funkcja rozbijająca słowa na poszczególne składniki dodawania
* @param {number[]} numbers
*/
function getSummationParts(numbers) {
return {
sum: numbers[numbers.length - 1],
addends: numbers.slice(0, -1),
};
}
/**
* Funkcja sprawdzająca czy rozwiązanie jest poprawne
* @param {string[]} words
* @param {Map<string, number>} letterMap
*/
function isCorrect(words, letterMap) {
const numbers = wordsToNumbers(words, letterMap);
const { sum, addends } = getSummationParts(numbers);
return addends.reduce((prev, curr) => prev + curr) === sum;
}
/**
* Funkcja wypisująca wyniki w konsoli
* @param {string[]} words
* @param {Map<string, number>[]} letterMaps
*/
function logResults(words, letterMaps) {
console.log(`Znalezionych rozwiązań: ${letterMaps.length}`);
for (const letterMap of letterMaps) {
const numbers = wordsToNumbers(words, letterMap);
const { sum, addends } = getSummationParts(numbers);
console.log(`${addends.join(" + ")} = ${sum}`);
}
}
/**
* Funkcja normalizująca wyrazy do wspólnej formy
* @param {string[]} words
*/
function normalizeWords(words) {
return words.map((x) => x.toUpperCase());
}
/**
* Funkcja wyciągająca unikalne litery ze słów
* @param {string[]} words
*/
function getLetters(words) {
const letterSet = new Set(words.flatMap((x) => [...x]));
if (letterSet > 10) {
throw new Error("Nie może być więcej niż 10 unikalnych liter!");
}
return [...letterSet];
}
/**
* Funkcja generująca klucz do tablicy wyników
* @param {Map<string, number>} letterMap
*/
function getKeyForResultsMap(letterMap) {
return JSON.stringify([...letterMap.entries()]);
}
/**
* Funkcja generująca mapę litera-wartość
* @param {string[]} letters
* @param {number[]} values
*/
function generateLetterMap(letters, values) {
const result = new Map();
for (let i = 0; i < letters.length; i++) {
result.set(letters[i], values[i]);
}
return result;
}
/**
* Zamienia miejscami elementy i oraz j w tablicy
* @param {[]} array
* @param {number} i
* @param {number} j
*/
function swap(array, i, j) {
let tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
function runner(words, algorithm) {
const results = new Map();
const fixedWords = normalizeWords(words);
const letters = getLetters(fixedWords);
const nonZeroLetters = getNonZeroLetters(fixedWords);
const startTime = process.hrtime();
for (const permutation of algorithm([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])) {
const result = generateLetterMap(letters, permutation);
if (!checkZeroLetters(result, nonZeroLetters)) {
continue;
}
if (!isCorrect(fixedWords, result)) {
continue;
}
const key = getKeyForResultsMap(result);
results.set(key, result);
}
const endTime = process.hrtime(startTime);
console.log(`Czas wykonania: ${endTime[0]}s ${endTime[1] / 1000000}ms`);
logResults(fixedWords, [...results.values()]);
}
const sendMoreMoney = ["SEND", "MORE", "MONEY"];
const doubleTrue = ["THREE", "THREE", "TWO", "TWO", "ONE", "ELEVEN"];
const manySolutions = ["TRZY", "TRZY", "SZEŚĆ"];
const twoLetters = ["X", "YYYY", "YYYY", "YYYY", "YYYY", "XYYYY"];
const noSolutions = ["JAN", "PAWEL", "DRUGI"];
const algorithm = plainChanges;
console.log(sendMoreMoney);
runner(sendMoreMoney, algorithm);
console.log("");
console.log(doubleTrue);
runner(doubleTrue, algorithm);
console.log("");
console.log(manySolutions);
runner(manySolutions, algorithm);
console.log("");
console.log(twoLetters);
runner(twoLetters, algorithm);
console.log("");
console.log(noSolutions);
runner(noSolutions, algorithm);
Compiling Program...
Standard Input:
Interactive Console
Text
Program is not being debugged. Click "Debug" button to start program in debug mode.
| # | Function | File:Line |
|---|
| Variable | Value |
|---|
| Register | Value |
|---|
| Expression | Value |
|---|
| # | Description |
|---|