كيف يمكنني حل تمرين "كيكر سرداب" المقترح في "تحديات البرمجة (دليل تدريب مسابقة البرمجة)"؟

Question

"تحديات البرمجة (دليل تدريب مسابقة البرمجة)" ربما يكون أحد أجمل كتاب التدريبات على الخوارزميات. لقد قمت بحل أول 11 تمرينًا ، لكنني الآن عالق في مشكلة "Crypt Kicker":

كيكر سرداب
تتمثل الطريقة الشائعة ولكن غير الآمنة لتشفير النص في تمييز حروف الأبجدية. بمعنى آخر ، يتم استبدال كل حرف من الحروف الأبجدية باستمرار في النص بواسطة حرف آخر. للتأكد من أن التشفير قابل للعكس ، لا يتم استبدال حرفين بنفس الحرف.

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

مدخل
يتكون المدخلات من خط يحتوي على عدد صحيح N ، يليه كلمات صغيرة ، واحدة لكل سطر ، بالترتيب الأبجدي. هذه الكلمات n تشكل قاموس الكلمات التي قد تظهر في النص فك التشفير.
بعد القاموس توجد عدة أسطر من المدخلات. يتم تشفير كل سطر كما هو موضح أعلاه.

لا يوجد أكثر من 1000 كلمة في القاموس. لا توجد كلمة تتجاوز 16 رسالة. تحتوي الخطوط المشفرة على أحرف ومسافات أقل فقط ولا تتجاوز 80 حرفًا.

انتاج |
فك تشفير كل سطر وطباعته إلى الإخراج القياسي. إذا كانت هناك حلول متعددة ، فسيقوم أي شخص بذلك.
إذا لم يكن هناك حل ، استبدل كل حرف من الأبجدية بواسطة علامة نجمية.

عينة المدخلات 6
و
ديك
جين
نفخة
بقعة
yertle

BJVG XSB HXSN XSB QYMM XSB RQAT XSB PNETFN
xxxx yyy zzzz www yyyy aaa bbbb ccc dddddd

عينة الإخراج
ديك وجين والنفخ والبقعة و yertle ...

ماذا إستراتيجية هل يجب أن آخذ من أجل حل هذا التمرين؟ كنت أفكر في حل التراجع الكلاسيكي والوحشي ، لكنني أحاول تجنب ذلك حتى أجد شيئًا أكثر ذكاءً.

ملاحظة: هذا لا يتعلق بالواجب المنزلي ، فأنا أحاول فقط تحسين مهاراتي العامة.

Answer 1

سوف Keyarray عقد جدول الاستبدال.

• ابدأ بمفاتيح فارغة ، هذا الإصدار 0

• تطابق أطول كلمة مشفرة مع أطول كلمة قاموس وإضافة إلى Keyarray (إذا كان هناك اثنين من الأطول ، اختر أي) ، هذا هو الإصدار 1.

• فك تشفير بعض رسائل الأطول الأطول.

• تحقق مما إذا كانت الرسائل التي تم فك تشفيرها تتطابق مع الحرف في نفس الموضع في أي كلمة من نفس القاموس من نفس الطول.
• إذا لم يتطابق أي منها ، عد إلى الإصدار 0 وجرب كلمة أخرى.

• إذا تطابق بعض الرسائل ، فأضف بقية الحروف إلى Keyarray ، فهذا الإصدار 2.

• فك تشفير بعض رسائل الأطول الأطول.

• تحقق مما إذا كانت الرسائل التي تم فك تشفيرها تتطابق مع الرسالة في نفس الموقف في أي كلمة قاموس.
• إذا لم يتطابق أي منها ، عد إلى الإصدار 1 وجرب كلمة أخرى
• إذا تطابق بعض الرسائل ، فأضف بقية الحروف إلى Keyarray ، فهذا الإصدار 3.

كرر حتى يتم فك تشفير جميع الكلمات.

إذا كان في الإصدار 0 لا شيء من أطول الكلمات يخلق فك تشفير جزئي بكلمات أقصر ، فربما لا يوجد حل.

Answer 2

يمكن إجراء تحسين بسيط عن طريق تعداد الاحتمالات قبل تشغيل التراجع. في بيثون:

dictionary = ['and', 'dick', 'jane', 'puff', 'spot', 'yertle']
line = ['bjvg', 'xsb', 'hxsn', 'xsb', 'qymm', 'xsb', 'rqat', 'xsb', 'pnetfn']

# ------------------------------------

import collections

words_of_length = collections.defaultdict(list)

for word in dictionary:
  words_of_length[len(word)].append(word)

possibilities = collections.defaultdict(set)
certainities = {}

for word in line:
    length = len(word)
    for i, letter in enumerate(word):
        if len(words_of_length[length]) == 1:
            match = words_of_length[length][0]
            certainities[letter] = match[i]
        else:
            for match in words_of_length[length]:
              possibilities[letter].add(match[i])

for letter in certainities.itervalues():
    for k in possibilities:
        possibilities[k].discard(letter)

for i, j in certainities.iteritems():
    possibilities[i] = set([j])

# ------------------------------------

import pprint
pprint.pprint(dict(possibilities))

انتاج:

{'a': set(['c', 'f', 'o']),
 'b': set(['d']),
 'e': set(['r']),
 'f': set(['l']),
 'g': set(['f', 'k']),
 'h': set(['j', 'p', 's']),
 'j': set(['i', 'p', 'u']),
 'm': set(['c', 'f', 'k', 'o']),
 'n': set(['e']),
 'p': set(['y']),
 'q': set(['i', 'j', 'p', 's', 'u']),
 'r': set(['j', 'p', 's']),
 's': set(['n']),
 't': set(['t']),
 'v': set(['c', 'f', 'o']),
 'x': set(['a']),
 'y': set(['i', 'p', 'u'])}

إذا كان لديك بعض إمكانيات العناصر الواحدة ، فيمكنك القضاء عليها من المدخلات وإعادة تشغيل الخوارزمية.

تعديل: تحول إلى تعيين بدلاً من القائمة وإضافة رمز الطباعة.

Answer 3

لقد حاولت في الواقع نهجًا مختلفًا إلى حد ما. لقد بنيت تري من كلمات القاموس. ثم أمشي عبر trie والجملة معًا بشكل متكرر (اجتياز trie في DFS).

في كل مساحة ، أتأكد من أنني ضربت نهاية كلمة في Trie وإذا كان الأمر كذلك ، فقد عدت إلى الجذر. على طول الطريق أتتبع مهام الرسالة التي قمت بها حتى الآن. إذا كان لدي أي مهمة تتناقض مع مهمة مسبقة ، فأنا أفشل وأكشف العودة إلى النقطة التي يمكنني القيام بها في الاعتراض الممكن.

يبدو الأمر صعبًا ولكن يبدو أنه يعمل بشكل جيد. ومن الصعب حقًا أن يصعب ترميزه!

Answer 4

تحسين محتمل آخر ، إذا كان لديك نص "كاف" للتعامل معه وتعرف لغة النص ، فيمكنك استخدام ترددات الحروف (انظر: http://en.wikipedia.org/wiki/Letter_frequency). هذا بالطبع نهج تقريبي للغاية عند التعامل مع 6/7 كلمات ولكن سيكون أسرع طريقة إذا كان لديك عدد قليل من الصفحات لفك التشفير.

تحرير: حول حل ماكس ، يمكنك محاولة استخراج بعض خصائص الكلمة ، مثل تكرار الحروف. من الواضح أن الإشارة إلى أن نفخة في القاموس و QYMM في النص المشفر هي الكلمات الأربعة الوحيدة التي تنتهي بحرف مزدوج تعطي إجابة مباشرة لثلاثة من الحروف. في السيناريوهات الأكثر تعقيدًا ، يجب أن تكون قادرًا على تضييق إمكانيات كل زوجين.

Answer 5

فيما يلي تطبيق Java مع المزيد من التحسينات إلى خوارزمية اقترحها carlos gutiérrez.

خوارزمية كيكر سرداب وحل ، ما الخطأ الذي حدث؟

• الصقل هو إضافة نمط كلمة لتقليل مساحة البحث للكلمات. على سبيل المثال ، الكلمات "ABC" و "Her" لها نفس النمط بينما "AAC" و "لها" لا ككل أحرف متميزة لا تتطابق مع كلمة متميزة.

• علاوة على ذلك ، يمكن تنفيذ الخوارزمية بشكل متكرر وهو أكثر سهولة وعقلانية.