Эффективный способ решения крипторифмов
https://stackoverflow.com/questions/750984
-
09-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Привет, я наткнулся на эту головоломку, которая представляет собой подмножество известных головоломок на основе слов и чисел, называемых Криптарифмы.Скажем, у вас есть выражение как
С Е Н Д + М О Р Е = М О Н Е Y
Самое интересное то, что каждый алфавит представляет собой уникальную цифру от 0 до 9.Я хотел написать обобщенный решатель, но в итоге написал для него грубое решение.Есть желающие, как я могу это решить?
Я думаю, что эту проблему можно решить, используя логику предикатов или теорию множеств.И я особенно заинтересован в поиске решений на основе C# или Python.Любой.?
Решение
На PyCon в этом году Рэймонд Хеттингер рассказал о программировании искусственного интеллекта на Python и рассказал о крипторифмах.
Видео всего выступления можно посмотреть здесь, а кулинарную книгу с решением можно найти на сайте эта ссылка.
Другие советы
Это настолько маленькая проблема, что решение ее методом грубой силы — неплохой метод.Предполагая, что каждая буква должна представлять уникальную цифру (т.мы не допустим решения S = 9, M = 1, * = 0) мы видим, что количество комбинаций, которые нужно попробовать, равно н!, где н — количество уникальных букв в крипторифме.Теоретическое максимальное количество комбинаций для оценки составляет 10! = 3 628 800, что очень мало для компьютера.
Если мы позволим нескольким буквам обозначать одно и то же число, количество возможных комбинаций будет ограничено 10^н, опять же где н количество уникальных букв.Предполагая, что используются только заглавные английские буквы, мы имеем теоретическое максимальное количество комбинаций букв. 10^26, поэтому для этого теоретического худшего случая нам могут понадобиться некоторые эвристики.Однако большинство практичных крипторифмов содержат гораздо меньше 26 уникальных букв, поэтому нормальный регистр, вероятно, будет ограничен н меньше 10, что опять-таки вполне разумно для компьютера.
Что ж, попробуйте записать это в виде списка функций:
SEND
MORE
----+
MONEY
Если я помню свою школьную математику, это должно быть так:
Y = (D+E) mod 10
E = ((N+R) + (D+E)/10) mod 10
...
Вот эффективный метод грубой силы, который рекурсивно перебирает все возможности, но также учитывает структуру конкретной проблемы, чтобы сократить ее.
Первые несколько аргументов для каждого метода представляют собой значения испытаний для каждой ветви, аргументы V1, V2 и т. Д. - значения, которые еще предстоит выделить и могут быть переданы в любом порядке.метод эффективен, поскольку он имеет максимум 8x7x5 возможных пробных решений, а не 10!/2 возможных решений методом грубой силы.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication1
{
class Program
{
static void MESDYNR(int m, int s, int e, int d, int y, int n, int r, int v1, int v2, int v3)
{
// Solve for O in hundreds position
// "SEND" + "M?RE" = "M?NEY"
int carry = (10 * n + d + 10 * r + e) / 100;
int o = (10 + n - (e + carry))%10;
if ((v1 == o) || (v2 == o) || (v3 == o))
{
// check O is valid in thousands position
if (o == ((10 + (100 * e + 10 * n + d + 100 * o + 10 * r + e) / 1000 + m + s) % 10))
{
// "SEND" + "MORE" = "MONEY"
int send = 1000 * s + 100 * e + 10 * n + d;
int more = 1000 * m + 100 * o + 10 * r + e;
int money = 10000 * m + 1000 * o + 100 * n + 10 * e + y;
// Chck this solution
if ((send + more) == money)
{
Console.WriteLine(send + " + " + more + " = " + money);
}
}
}
}
static void MSEDYN(int m, int s, int e, int d, int y, int n, int v1, int v2, int v3, int v4)
{
// Solve for R
// "SEND" + "M*?E" = "M*NEY"
int carry = (d + e) / 10;
int r = (10 + e - (n + carry)) % 10;
if (v1 == r) MESDYNR(m, s, e, d, y, n, r, v2, v3, v4);
else if (v2 == r) MESDYNR(m, s, e, d, y, n, r, v1, v3, v4);
else if (v3 == r) MESDYNR(m, s, e, d, y, n, r, v1, v2, v4);
else if (v4 == r) MESDYNR(m, s, e, d, y, n, r, v1, v2, v3);
}
static void MSEDY(int m, int s, int e, int d, int y, int v1, int v2, int v3, int v4, int v5)
{
// Pick any value for N
MSEDYN(m, s, e, d, y, v1, v2, v3, v4, v5);
MSEDYN(m, s, e, d, y, v2, v1, v3, v4, v5);
MSEDYN(m, s, e, d, y, v3, v1, v2, v4, v5);
MSEDYN(m, s, e, d, y, v4, v1, v2, v3, v5);
MSEDYN(m, s, e, d, y, v5, v1, v2, v3, v4);
}
static void MSED(int m, int s, int e, int d, int v1, int v2, int v3, int v4, int v5, int v6)
{
// Solve for Y
// "SE*D" + "M**E" = "M**E?"
int y = (e + d) % 10;
if (v1 == y) MSEDY(m, s, e, d, y, v2, v3, v4, v5, v6);
else if (v2 == y) MSEDY(m, s, e, d, y, v1, v3, v4, v5, v6);
else if (v3 == y) MSEDY(m, s, e, d, y, v1, v2, v4, v5, v6);
else if (v4 == y) MSEDY(m, s, e, d, y, v1, v2, v3, v5, v6);
else if (v5 == y) MSEDY(m, s, e, d, y, v1, v2, v3, v4, v6);
else if (v6 == y) MSEDY(m, s, e, d, y, v1, v2, v3, v4, v5);
}
static void MSE(int m, int s, int e, int v1, int v2, int v3, int v4, int v5, int v6, int v7)
{
// "SE**" + "M**E" = "M**E*"
// Pick any value for D
MSED(m, s, e, v1, v2, v3, v4, v5, v6, v7);
MSED(m, s, e, v2, v1, v3, v4, v5, v6, v7);
MSED(m, s, e, v3, v1, v2, v4, v5, v6, v7);
MSED(m, s, e, v4, v1, v2, v3, v5, v6, v7);
MSED(m, s, e, v5, v1, v2, v3, v4, v6, v7);
MSED(m, s, e, v6, v1, v2, v3, v4, v5, v7);
MSED(m, s, e, v7, v1, v2, v3, v4, v5, v6);
}
static void MS(int m, int s, int v1, int v2, int v3, int v4, int v5, int v6, int v7, int v8)
{
// "S***" + "M***" = "M****"
// Pick any value for E
MSE(m, s, v1, v2, v3, v4, v5, v6, v7, v8);
MSE(m, s, v2, v1, v3, v4, v5, v6, v7, v8);
MSE(m, s, v3, v1, v2, v4, v5, v6, v7, v8);
MSE(m, s, v4, v1, v2, v3, v5, v6, v7, v8);
MSE(m, s, v5, v1, v2, v3, v4, v6, v7, v8);
MSE(m, s, v6, v1, v2, v3, v4, v5, v7, v8);
MSE(m, s, v7, v1, v2, v3, v4, v5, v6, v8);
MSE(m, s, v8, v1, v2, v3, v4, v5, v6, v7);
}
static void Main(string[] args)
{
// M must be 1
// S must be 8 or 9
DateTime Start = DateTime.Now;
MS(1, 8, 2, 3, 4, 5, 6, 7, 9, 0);
MS(1, 9, 2, 3, 4, 5, 6, 7, 8, 0);
Console.WriteLine((DateTime.Now-Start).Milliseconds);
return;
}
}
}
этот может быть чем-то помочь
Редактировать:ответ на размещенную вами вики-ссылку также полезен!
