Решение крипторитма (числового ребуса) на C++, нерешение на JS
Это только заготовка консольной программы на C++, иллюстрирующей переборный алгоритм.
Она проверяет, есть ли решение у числового ребуса (крипторитма) вида s1+s2=s3
, заданного тремя строками std::string
.
Функции приложения используют глобальные данные и печатают информацию прямо в консоль, что в реальных проектах, где никакой консоли может не быть, не есть хорошо.
Программка проверялась в Visual Studio 2019, но должна сработать и в версиях помладше. Более удобную печать решения, думаю, в проект легко добавить.
#include <algorithm> #include <iostream> #include<vector> using namespace std; struct node { //узел поиска char letter; //символ int value; //числовое значение }; int isValid (node* nodeList, const int count, string s1, string s2, string s3) { int val1 = 0, val2 = 0, val3 = 0, m = 1, j, i; for (i = s1.length() - 1; i >= 0; i--) { //найти итоговое число для первой строки char ch = s1[i]; for (j = 0; j < count; j++) if (nodeList[j].letter == ch) break; //ch уже есть в списке val1 += m * nodeList[j].value; m *= 10; } m = 1; for (i = s2.length() - 1; i >= 0; i--) { //найти итоговое число для второй строки char ch = s2[i]; for (j = 0; j < count; j++) if (nodeList[j].letter == ch) break; val2 += m * nodeList[j].value; m *= 10; } m = 1; for (i = s3.length() - 1; i >= 0; i--) { //найти число для третьей строки char ch = s3[i]; for (j = 0; j < count; j++) if (nodeList[j].letter == ch) break; val3 += m * nodeList[j].value; m *= 10; } if (val3 == (val1 + val2)) return 1; return 0; } vector<int> use(10); //1, если символ уже использован bool permutation(int count, node* nodeList, int n, string s1, string s2, string s3) { if (n == count - 1) { //все цифры назначены for (int i = 0; i < 10; i++) { if (use[i] == 0) { //для неиспользованных nodeList[n].value = i; //назначить значение i if (isValid(nodeList, count, s1, s2, s3) == 1) { //проверить cout << "Solution found: "; for (int j = 0; j < count; j++) //напечатать решение cout << " " << nodeList[j].letter << " = " << nodeList[j].value; return true; } } } return false; } for (int i = 0; i < 10; i++) { //для всех цифр if (use[i] == 0) { //если не использованы nodeList[n].value = i; //назначить значение i и пометить, что уже использовано use[i] = 1; if (permutation(count, nodeList, n + 1, s1, s2, s3)) //вызвать следующую перестановку return true; use[i] = 0; //если вернулись сюда, снять пометку об использовании цифры } } return false; } bool IsLetters(string input) { //Истина, если строка состоит из латинских букв for (int i = 0; i < input.size(); i++) { int uppercaseChar = toupper(input[i]); if (uppercaseChar < 'A' || uppercaseChar > 'Z') return false; } return true; } bool solvePuzzle(string s1, string s2, string s3) { int uniqueChar = 0; //Количество уникальных символов std::transform(s1.begin(), s1.end(), s1.begin(), ::toupper); std::transform(s2.begin(), s2.end(), s2.begin(), ::toupper); std::transform(s3.begin(), s3.end(), s3.begin(), ::toupper); if (!IsLetters(s1)) { cout << "Invalid string (need latin letters only): " + s1; return 0; } if (!IsLetters(s2)) { cout << "Invalid string (need latin letters only): " + s2; return 0; } if (!IsLetters(s3)) { cout << "Invalid string (need latin letters only): " + s3; return 0; } int len1 = s1.length(); int len2 = s2.length(); int len3 = s3.length(); vector <int> freq(26); //Всего 26 различных букв //Заполняем таблицу частот: for (int i = 0; i < len1; i++) ++freq[s1[i] - 'A']; for (int i = 0; i < len2; i++) ++freq[s2[i] - 'A']; for (int i = 0; i < len3; i++) ++freq[s3[i] - 'A']; for (int i = 0; i < 26; i++) if (freq[i] > 0) uniqueChar++; if (uniqueChar > 10) { //не больше ли 10 различных чисел вышло? cout << "Invalid strings, used more then 10 digits in decimal system"; return 0; } node * nodeList = new node [uniqueChar]; for (int i = 0, j = 0; i < 26; i++) { //Назначаем найденные символы списку узлов if (freq[i] > 0) nodeList[j++].letter = char(i + 'A'); } return permutation(uniqueChar, nodeList, 0, s1, s2, s3); //делаем перестановки } int main() { string s1 = "send"; string s2 = "more"; string s3 = "money"; if (solvePuzzle(s1, s2, s3) == false) cout << "No solution"; cin.get(); return 0; }
Недоделанная вариация на JavaScript по той же теме. Если решения нет, может и затормозить браузер, ищет решение "неправильно" с применением удачи, то есть, random
. Зато вывод решения "нормальный" (в виде объекта JavaScript), может решать "по цепочке" (см. второй тест). Файл .html в кодировке Юникода utf-8.
<meta charset="utf-8"> <pre id="rebusResult"></pre> <script> const inputs = [ 'send + more = money', 'WHAT + WAS + THY == CAUSE' // 'seva+masha=love' ]; var tokenize = function(input) { // Извлечь лексемы const parts = input.toUpperCase().replace(/\s/g, '').split(/[\+\= ]/).filter(part => part !== ''); // Извлечь токены let tokens = {}; parts.forEach(part => { //Извлечь токены, с учётом, что нет лидирующих нулей for (let i=0; i<part.length; i++) { const token = part[i]; tokens[token] = { value: i === 0 ? 1 : (tokens[token] ? tokens[token].value : 0), first: tokens[token] && tokens[token].first || i === 0 }; } }); return { parts: parts, tokens: tokens }; } var encode = function(parts, tokens) { let equation = []; for (let i=0; i<parts.length; i++) { const part = parts[i]; let number = ''; for (let j=0; j<part.length; j++) { const ch = part[j]; const value = tokens[ch].value; number += value; } equation.push(parseInt(number)); } return equation; } var complete = function(equation) { let sum = 0; for (let i=0; i<equation.length - 1; i++) sum += equation[i]; return { sum: sum, target: equation[equation.length - 1], success: (sum === equation[equation.length - 1]) }; } var random = function(max) { return Math.floor(Math.random() * Math.floor(max)); } var solve = function(input, tokens, verbose, limit) { let count = 0; var fringe = [ tokens ]; let result = null; while (fringe.length) { if (count++ > limit) { return null; } const values = fringe.shift(); const equation = encode(input, values) const balance = complete(equation); if (balance.success) { // Есть решение result = { values: values, equation: equation, balance: balance }; break; } else { let child = {}; const keys = Object.keys(values); for (let i=0; i<keys.length; i++) { const key = keys[i]; const first = values[key].first; let r = random(10); r = first && !r ? 1 : r; child[key] = { value: r, first: first }; } fringe.push(child); } } return result; } inputs.forEach(input => { const data = tokenize(input); let limit = Math.min(1e4,Math.pow(10,Array.from(new Set(data.parts)).join('').length)); //намеренно ограничили количество шагов! console.log(limit); const result = solve(data.parts, data.tokens, limit); console.log(result); document.getElementById('rebusResult').innerHTML = JSON.stringify(result,null,' '); }); </script>
23.03.2020, 00:31 [1925 просмотров]