الصناديق المقفلة

طريقان إلى نفس الفكرة

المتطلبات قبل البداية

المفاهيم الأساسية

المسألة: عندك n صندوقًا مرقّمة من 0 إلى n-1‏. الصندوق 0 مفتوح، وكل صندوق فيه مفاتيح لصناديق أخرى. السؤال: هل تستطيع أن تفتحها كلها؟

1إعادة صياغة المسألة: هذا رسم بياني

بدّل الكلمات وتختفي المسألة: كل صندوق هو عقدة، وكل مفتاح هو سهم من الصندوق الذي فيه المفتاح إلى الصندوق الذي يفتحه. والسؤال صار: هل كل العقد قابلة للوصول من العقدة صفر؟

هذه تسمّى مسألة قابلية الوصول (reachability)، وحلّها معروف: ابدأ من نقطة البداية، وتتبّع كل سهم تستطيع عليه، وسجّل كل عقدة وصلتها، ثم قارن عدد ما وصلته بالعدد الكلي.

2لماذا نحتاج المجموعة opened‏؟

سببان، وكلٌّ منهما يكفي:

• منع الدوران اللانهائي. لو كان الصندوق 0 فيه مفتاح 2 والصندوق 2 فيه مفتاح 0، فبدون تسجيل ما فُتح ستدور بينهما إلى الأبد.
• العدّ. في النهاية نحتاج نعرف كم صندوقًا فتحنا. المجموعة تمنع العدّ المزدوج لو وصلنا نفس الصندوق من طريقين.

3المفاتيح التي بلا صناديق

النص يقول صريحًا: «قد توجد مفاتيح ليس لها صناديق». يعني ممكن يأتيك المفتاح 42 وعندك 5 صناديق فقط. لذلك الشرط 0 <= key < n ليس زينة، بدونه يظهر لك IndexError عند boxes[42]‏.

4عمقًا أولًا أم عرضًا أولًا؟

بما أن السؤال «هل نصل للكل؟» ولا يهمنا أقصر طريق، فالاثنان صحيحان. المكدّس أبسط لأنه قائمة عادية بلا استيراد. (k هو عدد المفاتيح كلها، أي مجموع أطوال القوائم الداخلية.)

5الحل الساذج ولماذا نتجنّبه

الحل الأول الذي يخطر في البال: امشِ على كل الصناديق، خذ مفاتيح المفتوح منها، وكرّر هذا حتى ما يتغيّر شيء. هذا يعطي الجواب الصحيح، لكن في أسوأ الحالات تحتاج n مسحة وكل مسحة O(n)‏، فيصير O(n²)‏. البحث بمكدّس يزور كل صندوق مرة واحدة فقط.

كيف يعمل؟

ثلاثة أشكال: مسار البحث نفسه، ثم الحالة الفاشلة من الاختبار كرسم بياني، ثم الحل الساذج لكي ترى الفرق بعينك.

شكل 3، مسار البحث: اسحب صندوقًا من المكدّس، خذ منه كل مفتاح جديد وصالح، وأضف صاحبه للمكدّس، حتى يفرغ.

شكل 4، نفس الحالة الثالثة من الاختبار كرسم بياني: الصندوقان 5 و6 (المرسومان بخط متقطع) ما يصل لهما سهم أبدًا، ومفاتيحهما لا تنفعهما لأن المفتاح داخل صندوق مقفل كأنه غير موجود.

شكل 5، الحل الساذج: مسحة كاملة على كل الصناديق في كل دورة، ويمكن تفتح صندوقًا واحدًا فقط في المسحة، فيصير العمل مضاعفًا بلا داعٍ.

الحل خطوة بخطوة

نكتب الحل، نشغّله، ثم نمشي على الحالة الفاشلة خطوة بخطوة. كل مخرج تحت حقيقي.

الخطوة 1، الحل

#!/usr/bin/python3
"""0-lockboxes"""


def canUnlockAll(boxes):
    """Return True if every box can be opened starting from box 0."""
    n = len(boxes)
    if n == 0:
        return True

    opened = {0}
    stack = [0]
    while stack:
        box = stack.pop()
        for key in boxes[box]:
            if 0 <= key < n and key not in opened:
                opened.add(key)
                stack.append(key)
    return len(opened) == n

الخطوة 2، التشغيل

$ cat main_0.py
#!/usr/bin/python3
canUnlockAll = __import__('0-lockboxes').canUnlockAll

boxes = [[1], [2], [3], [4], []]
print(canUnlockAll(boxes))
boxes = [[1, 4, 6], [2], [0, 4, 1], [5, 6, 2], [3], [4, 1], [6]]
print(canUnlockAll(boxes))
boxes = [[1, 4], [2], [0, 4, 1], [3], [], [4, 1], [5, 6]]
print(canUnlockAll(boxes))

$ ./main_0.py
True
True
False

الخطوة 3، الحدود

>>> canUnlockAll([[]])            # one box, already open
True
>>> canUnlockAll([[1], []])        # box 0 holds the key to box 1
True
>>> canUnlockAll([[], [1]])        # box 1 unreachable; its own key is useless
False
>>> canUnlockAll([[1, 9, 42], []]) # keys with no box: harmlessly ignored
True

السطر الأخير مهم: المفاتيح 9 و42 لا توجد لها صناديق، والحل يتجاهلها بهدوء بفضل شرط المدى.

الخطوة 4، امشِ على الحالة الفاشلة

اعتقاد شائع × الحقيقة

أين نستخدمه فعليًا؟

جرّب بنفسك

بطاقات مراجعة سريعة

تحقّق من فهمك