طريقة فعالة لحل التشفير

Question

مرحبا، جئت عبر هذا اللغز الذي هو مجموعة فرعية من النوع الشهير من الكلمة والأرقام التي تسمى الألغاز القائمة cryptarithms. وبعد قل أن لديك تعبير كما

إرسال + المزيد = المال

الآن الجزء المثير للاهتمام هناك، كل الحروف الأبجدية يمثل رقما فريدا من 0-9. أردت أن أكتب حلالا عاما، لكنني انتهى بي الأمر إلى كتابة الحل القسري الغاشد لذلك. أي محتجزي كيف يمكنني حلها؟

أعتقد أنه يمكن حلها باستخدام المنطق المسند أو نظرية تعيين. وأنا مهتم بشكل خاص بإيجاد حلول C # أو Python. أي واحد.؟

Answer 1

في هذا العام، تحدث Pycon Raymond Hettinger عن برنامج AI في بيثون، وقد غطى التشفير.

يمكن رؤية الفيديو من الكلام بأكمله هنا, ، ويمكن العثور على كتاب الطبخ مع الحل هذا الرابط.

Answer 2

هذه مشكلة صغيرة أن حل القوة الغاشمة ليس طريقة سيئة. على افتراض أن كل حرف يجب أن يمثل رقما فريدا (أي لن نسمح للحل S = 9، M = 1، * = 0) نرى هذا عدد المجموعات للمحاولة ن!, ، أين ن هو عدد الحروف الفريدة في cryptarithm. الحد الأقصى لعدد الأقصى للنظرية لتقييم 10! = 3 628 800, ، وهو رقم صغير حقا لجهاز كمبيوتر.

إذا سمحنا بعدة أحرف بتمثيل نفس العدد، فسيتم حدوث عدد مجموعات للمحاولة 10 ^ n., ، مرة أخرى أين ن هو عدد الحروف الفريدة. على افتراض خطابات رأس المال فقط لدينا عدد كبير من مجموعات من مجموعات 10^26, ، لذلك بالنسبة لتلك الحالة النظري النظري قد نحتاج إلى بعض الاستدلال. معظم التشفير العملي لديها أقل بكثير من 26 حرفا فريدا، لذلك من المحتمل أن تكون القضية العادية من المحتمل أن تكون من قبل ن أقل من 10، وهو مجددا معقول جدا لجهاز الكمبيوتر.

Answer 3

حسنا، حاول كتابة ذلك كقائمة من الوظائف:

 SEND
 MORE
----+
MONEY

إذا كنت أتذكر الرياضيات المدارس الدنيا، فيجب أن يكون هذا:

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

Answer 4

فيما يلي طريقة القوة الغاشمة الفعالة التي تتمثل في الدورات من خلال جميع الاحتمالات بشكل متكرر ولكنها تحيط علما أيضا بنية المشكلة الخاصة باختصار المشكلة.

تمثل الحجج القليلة الأولى لكل طريقة قيم التجربة لكل فرع من الفرع، والحجج V1، V2 إلخ هي القيم التي لم يتم تخصيصها وما بعدها ويمكن تمريرها بأي ترتيب. الطريقة فعالة لأنه يحتوي على حلول محاكمة محتملة بحد أقصى 8 × 7 × 7 بدلا من الحلول 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;
        }
    }
}

Answer 5

هذه قد يكون من بعض المساعدة

تحرير: الإجابة على رابط Wiki الذي نشرته هو أيضا مفيد!