Manera eficiente de resolver criptoritmos
https://stackoverflow.com/questions/750984
-
09-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Hola, me encontré con este acertijo que es un subconjunto de acertijos famosos basados en palabras y números llamados Criptaritmos.Digamos que tienes una expresión como
S E N D + M O R E = M O N E Y
Ahora, lo interesante es que cada alfabeto representa un dígito único del 0 al 9.Quería escribir un solucionador generalizado, pero terminé escribiendo una solución de fuerza bruta.¿Alguien interesado en cómo puedo resolverlo?
Creo que se puede resolver mediante lógica de predicados o teoría de conjuntos.Y estoy particularmente interesado en encontrar soluciones basadas en C# o Python.Alguien.?
Solución
En este año PyCon Raymond Hettinger habló de AI programación en Python, y ha cubierto Cryptarithms.
El vídeo de toda la charla se puede ver aquí , y libro de cocina con solución se puede encontrar en < a href = "http://code.activestate.com/recipes/576615/" rel = "noreferrer"> este enlace .
Otros consejos
Este es un pequeño problema que una solución de fuerza bruta no es un mal método. Suponiendo que cada carta debe representar un dígito único (es decir, que no permitirá que la solución S = 9, M = 1, * = 0), vemos que el número de combinaciones para intentar es n , donde n es el número de letras únicas en el cryptarithm. El número máximo teórico de combinaciones para evaluar es 10! = 3 628 800 , que es realmente pequeño número de un ordenador.
Si permitimos varias letras para representar el mismo número, el número de combinaciones para tratar será delimitada por 10 ^ n , de nuevo, donde n es el número de único letras. Suponiendo letras inglesas único capital que tenemos un número máximo teórico de combinaciones de 10 ^ 26 , por lo que para peor de los casos teórica que podríamos necesitar algo de heurística. cryptarithms más prácticas tienen mucho menos de 26 letras únicas, sin embargo, por lo que el caso normal, probablemente estará delimitada por un n menos de 10, que a su vez es bastante razonable para un ordenador.
Bueno, trate de escribir como una lista de funciones:
SEND
MORE
----+
MONEY
Si no recuerdo mi matemáticas de la escuela inferior, esto debería ser:
Y = (D+E) mod 10
E = ((N+R) + (D+E)/10) mod 10
...
Aquí hay un método eficiente de fuerza bruta que recorre todas las posibilidades de forma recursiva pero también toma nota de la estructura del problema particular para atajar el problema.
Los primeros argumentos a cada método representan valores de prueba para cada rama, los argumentos V1, V2, etc. son los valores que aún no se han asignado y pueden aprobarse en cualquier orden.El método es eficiente porque tiene un máximo de 8x7x5 posibles soluciones de prueba en lugar de 10!/2 posibles soluciones por fuerza bruta.
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;
}
}
}
este puede ser de alguna ayuda
Editar: la respuesta en el enlace wiki informados también es útil
