БлогNot. Решение крипторитма (числового ребуса) на C++, нерешение на JS

Решение крипторитма (числового ребуса) на 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 просмотров]


теги: textprocessing c++ javascript числа алгоритм

К этой статье пока нет комментариев, Ваш будет первым