Project Euler مسائل ١١-١٥: الشبكات، القواسم وعلم التراكيب

ملخص

تقدم المشكلات من 11 إلى 15 معالجة الشبكات (المشكلة 11)، وعد القواسم (المشكلة 12)، وتحليل وتقطيع النصوص (المشكلة 13)، والمتتاليات التكرارية (المشكلة 14)، والتحليل التوافيقي عبر البرمجة الديناميكية (المشكلة 15). تسلط الحلول الضوء على قوة المذكرة (memoization)، والتكرار الفعال، والتعرف على الأنماط الهيكلية في البيانات.

تمثل مشكلات Project Euler من 11 إلى 15 قفزة كبيرة في الصعوبة المفاهيمية. لم تعد تعمل مع حسابيات بسيطة فحسب — بل أصبحت الآن تعالج شبكات ثنائية الأبعاد، وتعد القواسم بكفاءة، وتحلل أرقاماً ضخمة، وتحسب قيماً توافيقية هائلة. تعلم هذه المشكلات أنماطاً خوارزمية أساسية: اجتياز الشبكة، المذكرة (memoization)، تعداد القواسم، والبرمجة الديناميكية.

المشكلة 11: أكبر حاصل ضرب في شبكة

المشكلة: بمعلومية شبكة أرقام بحجم 20×20، أوجد الأرقام الأربعة المتجاورة (أفقياً، رأسياً، أو قطرياً) التي يكون حاصل ضربها هو الأكبر.

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

إعداد المشكلة:

grid_str = """08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 95 65 53 87 06 16 91 19 35 68 76 74 20 73 02 29 23
...
"""

grid = []
for line in grid_str.strip().split('\n'):
    grid.append([int(x) for x in line.split()])

print(f"Grid dimensions: {len(grid)} rows × {len(grid[0])} columns")

حل القوة الغاشمة (Brute Force):

def largest_product_in_grid_bruteforce(grid: list[list[int]]) -> int:
    """O(n²): check all positions, all directions."""
    rows, cols = len(grid), len(grid[0])
    max_product = 0

    directions = [
        (0, 1),   # Right
        (1, 0),   # Down
        (1, 1),   # Diagonal down-right
        (1, -1),  # Diagonal down-left
    ]

    for r in range(rows):
        for c in range(cols):
            for dr, dc in directions:
                # Check if 4 elements fit in this direction
                r_end, c_end = r + 3 * dr, c + 3 * dc
                if 0 <= r_end < rows and 0 <= c_end < cols:
                    product = 1
                    for i in range(4):
                        product *= grid[r + i * dr][c + i * dc]
                    max_product = max(max_product, product)

    return max_product

الوقت: O(rows × cols × 4 directions × 4 elements) = O(n²)، حيث n=20. المساحة: O(1).

الحل المحسن (نفس التعقيد، ثوابت أفضل):

التعقيد مثالي بالفعل (يجب فحص جميع المواضع). يكمن التحسين في العوامل الثابتة: تجنب الضرب الزائد، واستخدام حلقات تكرار فعالة.

def largest_product_in_grid_optimized(grid: list[list[int]]) -> int:
    """O(n²): optimized grid scan."""
    rows, cols = len(grid), len(grid[0])
    max_product = 0

    # Right
    for r in range(rows):
        for c in range(cols - 3):
            product = grid[r][c] * grid[r][c+1] * grid[r][c+2] * grid[r][c+3]
            max_product = max(max_product, product)

    # Down
    for r in range(rows - 3):
        for c in range(cols):
            product = grid[r][c] * grid[r+1][c] * grid[r+2][c] * grid[r+3][c]
            max_product = max(max_product, product)

    # Diagonal down-right
    for r in range(rows - 3):
        for c in range(cols - 3):
            product = grid[r][c] * grid[r+1][c+1] * grid[r+2][c+2] * grid[r+3][c+3]
            max_product = max(max_product, product)

    # Diagonal down-left
    for r in range(rows - 3):
        for c in range(3, cols):
            product = grid[r][c] * grid[r+1][c-1] * grid[r+2][c-2] * grid[r+3][c-3]
            max_product = max(max_product, product)

    return max_product

التعقيد: كلاهما O(n²). الثاني أسرع في الممارسة العملية بسبب هيكل حلقة التكرار الأبسط وعدم وجود تكلفة إضافية للبحث في متجهات الاتجاه.

---

المشكلة 12: أعلى عدد مثلثي قابل للقسمة

المشكلة: العدد المثلثي هو مجموع أول n من الأعداد الطبيعية: T(n) = 1+2+...+n = n(n+1)/2. أوجد أول عدد مثلثي له أكثر من 500 قاسم.

يتطلب هذا تحسينين: (1) توليد فعال للأعداد المثلثية، (2) عد سريع للقواسم.

حل القوة الغاشمة:

def count_divisors_bruteforce(n: int) -> int:
    """O(n): count divisors by trial division."""
    count = 0
    for i in range(1, n + 1):
        if n % i == 0:
            count += 1
    return count

def triangular_number_bruteforce(divisor_target: int) -> int:
    """O(T(n) * T(n)): brute force triangular + divisor count."""
    n = 1
    while True:
        triangular = n * (n + 1) // 2
        if count_divisors_bruteforce(triangular) > divisor_target:
            return triangular
        n += 1

الوقت: بطيء جداً. بالنسبة لـ T(n) ≈ 100 مليون، فإن عد القواسم بسذاجة يستغرق √100 مليون ≈ 10 آلاف عملية لكل رقم.

الحل المحسن (عد القواسم عبر التحليل إلى عوامل أولية):

فكرة رئيسية: إذا كان n = p₁^a₁ × p₂^a₂ × ... × pₖ^aₖ، فإن عدد القواسم هو (a₁+1)(a₂+1)...(aₖ+1).

def count_divisors_optimized(n: int) -> int:
    """O(sqrt(n)): count divisors via prime factorization."""
    count = 1
    factor = 2

    while factor * factor <= n:
        exponent = 0
        while n % factor == 0:
            exponent += 1
            n //= factor
        count *= (exponent + 1)
        factor += 1

    # Remaining n (if > 1) is a prime factor
    if n > 1:
        count *= 2

    return count

def triangular_number_optimized(divisor_target: int) -> int:
    """O(sqrt(T(n))): use optimized divisor counting."""
    n = 1
    while True:
        triangular = n * (n + 1) // 2
        if count_divisors_optimized(triangular) > divisor_target:
            return triangular
        n += 1

تحسين إضافي: T(n) = n(n+1)/2. إذا كان gcd(n, n+1) = 1 (صحيح دائماً للأعداد الصحيحة المتتالية)، فإن divisor_count(T(n)) = divisor_count(n) × divisor_count(n+1).

def triangular_number_highly_optimized(divisor_target: int) -> int:
    """O(sqrt(n)): use multiplicative property of T(n)."""
    n = 1
    div_n = count_divisors_optimized(1)  # divisors of 1

    while True:
        # T(n+1) = (n+1)(n+2)/2, but more efficiently:
        # divisors(T(n)) = divisors(n) * divisors(n+1) when gcd(n,n+1)=1
        n += 1
        if n % 2 == 0:
            div_n_plus_1 = count_divisors_optimized(n + 1)
            div_next = (count_divisors_optimized(n // 2) * div_n_plus_1)
        else:
            div_n_plus_1 = count_divisors_optimized((n + 1) // 2)
            div_next = (count_divisors_optimized(n) * div_n_plus_1)

        if div_next > divisor_target:
            triangular = n * (n + 1) // 2
            return triangular
        div_n = div_n_plus_1

التعقيد: الحل المحسن هو O(√T(n) × √n) ≈ O(n) بالمتوسط. القوة الغاشمة هي O(T(n) × √T(n)) ≈ O(n²). بالنسبة للهدف 500، يجد الحل المحسن الإجابة في ثانية واحدة تقريباً؛ بينما تستغرق القوة الغاشمة ساعات.

---

المشكلة 13: مجموع كبير

المشكلة: أُعطيت 100 رقم، كل منها يتكون من خمسين خانة. أوجد أول 10 خانات من مجموعها.

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

الحل:

def large_sum_first_digits() -> str:
    """Compute sum of 100 50-digit numbers, return first 10 digits."""
    numbers = [
        37107287533902102798797998220837590246910760607252868541
        ...  # 99 more lines
    ]

    total = sum(numbers)
    return str(total)[:10]

# Or, if reading from a file/string:
def large_sum_from_string(numbers_str: str) -> str:
    """Parse numbers and return first 10 digits of sum."""
    numbers = [int(line.strip()) for line in numbers_str.strip().split('\n')]
    total = sum(numbers)
    return str(total)[:10]

العقبة: في اللغات التي لا تدعم الأعداد الصحيحة ذات الدقة التعسفية (مثل C++ و Java)، ستحتاج إلى تنفيذ جمع الأعداد الكبيرة بنفسك أو استخدام مكتبة مخصصة. تبسط Python هذه المشكلة — لكن الدرس مهم: اعرف قدرات لغتك.

التعقيد: O(n × k) حيث n=100 و k=50 (خانة). الجمع هو O(k)، وجمع 100 رقم هو O(n). الإجمالي: O(nk) = O(5000)، وهو ضئيل.

---

المشكلة 14: أطول متتالية كولاتز

المشكلة: تنص حدسية كولاتز على أنه لأي عدد صحيح موجب، يؤدي تطبيق هذه القواعد بشكل متكرر إلى الوصول لـ 1 في النهاية:

• إذا كان n زوجياً: n → n/2
• إذا كان n فردياً: n → 3n+1

أوجد أي رقم بداية تحت المليون ينتج أطول متتالية (طول السلسلة).

حل القوة الغاشمة:

def collatz_length_bruteforce(n: int) -> int:
    """O(unknown): compute chain length for a given n."""
    length = 1
    while n != 1:
        if n % 2 == 0:
            n //= 2
        else:
            n = 3 * n + 1
        length += 1
    return length

def longest_collatz_bruteforce(limit: int) -> int:
    """O(limit × chain_length): check all starts."""
    max_length = 0
    longest_start = 0

    for start in range(1, limit):
        length = collatz_length_bruteforce(start)
        if length > max_length:
            max_length = length
            longest_start = start

    return longest_start

الوقت: O(limit × avg_chain_length). بالنسبة لـ limit=1M، هذا بطيء (حوالي عشرات الملايين من التكرارات).

الحل المحسن (المذكرة - Memoization):

فكرة رئيسية: إذا كنا قد حسبنا طول السلسلة لرقم ما بالفعل، فأعد استخدامه. على سبيل المثال، السلسلة من 10 هي 10→5→16→8→4→2→1. عند حساب السلسلة من 5، يمكننا التوقف مبكراً وإضافة الباقي المعروف.

from functools import lru_cache

@lru_cache(maxsize=None)
def collatz_length_memoized(n: int) -> int:
    """O(log n) with memoization."""
    if n == 1:
        return 1
    if n % 2 == 0:
        return 1 + collatz_length_memoized(n // 2)
    else:
        return 1 + collatz_length_memoized(3 * n + 1)

def longest_collatz_optimized(limit: int) -> int:
    """O(limit) with memoization."""
    max_length = 0
    longest_start = 0

    for start in range(1, limit):
        length = collatz_length_memoized(start)
        if length > max_length:
            max_length = length
            longest_start = start

    return longest_start

التعقيد: مع المذكرة، يتم حساب نفس السلسلة مرة واحدة وإعادة استخدامها لجميع أرقام البداية التي تشترك في جزء من السلسلة. التعقيد هو O(limit) بالمتوسط، مقارنة بـ O(limit × chain_length) في القوة الغاشمة. تسريع بمقدار 5-10 مرات.

---

المشكلة 15: مسارات الشبكة

المشكلة: في شبكة 20×20، تبدأ من أعلى اليسار ويمكنك التحرك فقط لليمين أو للأسفل. كم عدد المسارات المتميزة للوصول إلى أسفل اليمين؟

هذه مشكلة توافيقية كلاسيكية: تحتاج إلى القيام بـ 20 حركة لليمين و 20 حركة للأسفل (40 حركة إجمالاً)، مع اختيار أي 20 منها لليمين (والباقي للأسفل). هذا هو C(40, 20) = 40! / (20! × 20!).

حل القوة الغاشمة (التكرار):

def lattice_paths_bruteforce(x: int, y: int) -> int:
    """O(2^(x+y)): recursive enumeration of all paths."""
    if x == 0 or y == 0:
        return 1  # Only one path: straight line
    return lattice_paths_bruteforce(x-1, y) + lattice_paths_bruteforce(x, y-1)

result = lattice_paths_bruteforce(20, 20)
# Extremely slow: 2^40 ≈ 1 trillion recursive calls

الوقت: O(2^n)، أسي. بالنسبة لـ n=20، هذا يعني تريليون استدعاء — وهو أمر غير عملي.

الحل المحسن 1 (البرمجة الديناميكية):

استخدم جدولاً ثنائي الأبعاد لتخزين أعداد المسارات. dp[i][j] = عدد المسارات إلى الموضع (i,j).

def lattice_paths_dp(x: int, y: int) -> int:
    """O(xy): bottom-up DP."""
    dp = [[1] * (y + 1) for _ in range(x + 1)]

    for i in range(1, x + 1):
        for j in range(1, y + 1):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]

    return dp[x][y]

result = lattice_paths_dp(20, 20)
print(result)  # 137846528820

الوقت: O(xy)، المساحة: O(xy). بالنسبة لـ x=y=20، هذا يعني 400 عملية و 400 خلية ذاكرة — وهو أمر ضئيل.

الحل المحسن 2 (التحليل التوافيقي):

احسب C(40, 20) مباشرة:

from math import comb

def lattice_paths_combinatorial(x: int, y: int) -> int:
    """O(min(x,y)): use combinatorial formula."""
    return comb(x + y, x)

result = lattice_paths_combinatorial(20, 20)
print(result)  # 137846528820

الوقت: O(1) باستخدام مكتبة الرياضيات المدمجة، أو O(min(x, y)) إذا كنت تنفذ المضروب (factorial) يدوياً. المساحة: O(1).

الحل المحسن 3 (برمجة ديناميكية موفرة للمساحة):

إذا لم تكن بحاجة إلى الجدول الكامل، استخدم صفاً واحداً يتم تحديثه في مكانه:

def lattice_paths_dp_optimized(x: int, y: int) -> int:
    """O(x*y) time, O(min(x,y)) space."""
    row = [1] * (y + 1)
    for _ in range(1, x + 1):
        for j in range(1, y + 1):
            row[j] += row[j - 1]
    return row[y]

result = lattice_paths_dp_optimized(20, 20)
print(result)  # 137846528820

الوقت: O(xy)، المساحة: O(y) بدلاً من O(xy). بالنسبة للشبكات الكبيرة، الذاكرة هي عنق الزجاجة.

مقارنة التعقيد:

• القوة الغاشمة: O(2^(x+y)) = O(2^40) ≈ 1 تريليون استدعاء. لا تستخدمها.
• البرمجة الديناميكية (جدول 2D): وقت O(xy)، مساحة O(xy). واضحة ومباشرة.
• التحليل التوافيقي: وقت O(1) أو O(min(x,y))، مساحة O(1). الأكثر أناقة.
• البرمجة الديناميكية (جدول 1D): وقت O(xy)، مساحة O(min(x,y)). أفضل توازن للشبكات الكبيرة.

---

ما ستتعلمه

1. اجتياز الشبكة (المشكلة 11): التكرار البسيط هو الأمثل؛ ركز على كود نظيف وتجنب أخطاء "الزيادة بواحد" (off-by-one).
2. عد القواسم (المشكلة 12): التحليل إلى عوامل أولية يتفوق على القسمة التجريبية. الخصائص الضربية تفتح الباب لمزيد من التسريع.
3. الأعداد الكبيرة (المشكلة 13): اعرف لغتك. دقة Python التعسفية