암호화를 효율적으로 해결하는 방법

Question

안녕하세요 저는 유명한 종류의 단어와 숫자 기반 퍼즐의 하위 집합 인이 퍼즐을 발견했습니다. 암호화. 표현이 있다고 가정 해 봅시다

+ more = money를 보내십시오

이제 흥미로운 부분은 각 알파벳이 0-9의 고유 한 자릿수를 나타냅니다. 나는 일반화 된 솔버를 쓰고 싶었지만 결국 무차별적인 강제 솔루션을 작성하게되었습니다. 어떻게 해결할 수 있습니까?

술어 논리 또는 세트 이론을 사용하여 해결할 수 있다고 생각합니다. 그리고 특히 C# 또는 Python 기반 솔루션을 찾는 데 관심이 있습니다. 누구나.?

Answer 1

올해의 Pycon Raymond Hettinger는 Python의 AI 프로그래밍에 대해 이야기했으며 암호화를 다루었습니다.

전체 대화의 비디오를 볼 수 있습니다 여기, 솔루션이있는 요리 책은 찾을 수 있습니다 이 링크.

Answer 2

이것은 무차별적인 솔루션이 나쁜 방법이 아니라는 작은 문제입니다. 각 문자가 고유 한 숫자를 나타내야한다고 가정하면 (즉, 솔루션 S = 9, M = 1, * = 0을 허용하지 않을 것입니다) 시도 할 조합 수는 N!, 어디 N 암호화에있는 고유 한 글자 수입니다. 평가할 이론적 최대 조합 수는 IS입니다 10! = 3 628 800, 컴퓨터의 경우 실제로 적은 수입니다.

여러 글자가 동일한 수를 나타내도록 허용하면 시도 할 조합 수는 다음과 같습니다. 10^n, 다시 어디에 N 독특한 글자의 수입니다. 자본 영어 편지 만 가정하면 이론적 인 최대 조합 수가 있습니다. 10^26, 따라서 이론적 인 최악의 경우에는 휴리스틱이 필요할 수 있습니다. 대부분의 실용적인 암호화는 26 개 이상의 고유 문자를 가지므로 일반적인 경우는 아마도 N 10 미만으로 컴퓨터에 다시 합리적입니다.

Answer 3

글쎄, 기능 목록으로 작성해보십시오.

 SEND
 MORE
----+
MONEY

저의 낮은 학교 수학을 기억한다면 이것은 다음과 같습니다.

Y = (D+E) mod 10
E = ((N+R) + (D+E)/10) mod 10
...

Answer 4

다음은 모든 가능성을 재귀 적으로 순환하는 효율적인 무차별 인력 방법입니다. 또한 문제를 단축시키기 위해 특정 문제의 구조를 기록합니다.

각 방법에 대한 처음 몇 가지 인수는 각 지점에 대한 시험 값을 나타내고, 인수 v1, v2 등은 아직 할당되지 않은 값이며 어떤 순서로든 전달 될 수 있습니다. 이 방법은 Brute Force에 의한 10!/2 가능한 솔루션이 아닌 최대 8x7x5 가능한 시험 솔루션을 갖기 때문에 효율적입니다.

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;
        }
    }
}

Answer 5

이것 도움이 될 수 있습니다

편집 : 게시 한 Wiki 링크의 답변도 유용합니다!