مسائل Project Euler من ١١ إلى ١٥: الشبكات، القواسم وعلم التوافيق

ملخص

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

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

المشكلة 11: Largest Product in a Grid

المشكلة: بالنظر إلى شبكة أرقام بحجم 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)

    # 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)

    # 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)

    # Diagonal down-left
    for r in range(rows - 3):
        for c in range(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)

    return max_product

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

الإجابة المتوقعة: 70600674.

---

المشكلة 12: Highest Divisible Triangular Number

المشكلة: الرقم المثلثي هو مجموع أول 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+ 1):
        if n % i == 0:
            count += 1
    return count

def triangular_number_bruteforce(divisor_target: int) -> int:
    """Brute force: trial division per triangular number."""
    n = 1
    while True:
        triangular = n * (n + 1) // 2
        if count_divisors_bruteforce(triangular) > divisor_target:
            return triangular
        n += 1

الوقت: بطيء جداً. count_divisors_bruteforce هو O(T(n)) — التكرار حتى T(n) لكل مرشح. بالنسبة للهدف 500، يصل T(n) إلى حوالي 76 مليون، لذا فإن كل عملية عد للقواسم وحدها تستغرق عشرات الملايين من العمليات.

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

فكرة أساسية: إذا كان 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:
    """Use the multiplicative property of T(n) = n(n+1)/2."""
    n = 1
    while True:
        # divisors(T(n)) = divisors(a) * divisors(b)
        # where {a, b} = {n/2, n+1} if n is even, else {n, (n+1)/2}.
        # Both a and b are coprime, so divisor_count is multiplicative.
        n += 1
        if n % 2 == 0:
            div_count = count_divisors_optimized(n // 2) * count_divisors_optimized(n + 1)
        else:
            div_count = count_divisors_optimized(n) * count_divisors_optimized((n + 1) // 2)

        if div_count > divisor_target:
            return n * (n + 1) // 2

التعقيد: تستدعي كل عملية تكرار count_divisors_optimized (O(√n)) مرتين، لذا فإن البحث المحسن هو تقريباً O(answer × √n). تهيمن عملية عد القواسم الداخلية على القوة الغاشمة: O(answer × T(answer)). على كمبيوتر محمول عادي، ينتهي الإصدار المحسن في أقل من ثانية؛ بينما يستغرق الإصدار البدائي وقتاً أطول بكثير (أبطأ بمراحل في الممارسة العملية).

الإجابة المتوقعة: 76576500 (وهي T(12375)).

---

المشكلة 13: Large Sum

المشكلة: أُعطيت 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(linestrip()) for line in numbers_strstrip()split('\n')]
    total = sum(numbers)
    return str(total)[:10]

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

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

الإجابة المتوقعة: 5537376230.

---

المشكلة 14: Longest Collatz Sequence

المشكلة: تنص حدسية Collatz على أنه بالنسبة لأي عدد صحيح موجب، فإن تطبيق هذه القواعد بشكل متكرر يؤدي في النهاية إلى الوصول لـ 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):
        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، يمكننا التوقف مبكراً وإضافة الباقي المعروف.

import sys
from functools import lru_cache

# Collatz chains can recurse deeply for some seeds; bump the limit.
syssetrecursionlimit(10_000)

@lru_cache(maxsize=None)
def collatz_length_memoized(n: int) -> int:
    """Cached chain length. First evaluation is O(chain_length)
    for the new value; subsequent lookups are O(1)."""
    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:
    """Each chain step is computed at most once across all starts."""
    max_length = 0
    longest_start = 0

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

    return longest_start

التعقيد: مع التخزين المؤقت، يتم حساب كل قيمة وسيطة متميزة مرة واحدة على الأكثر. يتناسب إجمالي العمل تقريباً مع اتحاد جميع قيم السلسلة التي تم لمسها، بدلاً من مجموع أطوال السلاسل. ينتهي كلا الإصدارين في أقل من دقيقة على الأجهزة الحديثة لـ limit=1_000_000؛ الإصدار المخزن مؤقتاً أسرع بشكل ملحوظ، لكن النسبة الدقيقة تعتمد على إصدار Python، وعبء التكرار مقابل التكرار الحلقي، وحجم ذاكرة التخزين المؤقت.

الإجابة المتوقعة: 837799.

---

المشكلة 15: Lattice Paths

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

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

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

def lattice_paths_bruteforce(x: int: 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) + lattice_paths_bruteforce(x-1)

result = lattice_paths_bruteforce(2020)
# 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: int) -> int:
    """O(xy): bottom-up DP."""
    dp = [[1] * (y + 1) for _ in range(x + 1)]

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

    return dp[x][y]

result = lattice_paths_dp(2020)
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: int) -> int:
    """O(min(x,y)): use combinatorial formula."""
    return comb(x + y)

result = lattice_paths_combinatorial(2020)
print(result)  # 137846528820

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

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

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

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

result = lattice_paths_dp_optimized(2020)
print(result)  # 137846528820

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

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

• القوة الغاشمة: O(2^(x+

  الخلاصة

  مشاكل Project Euler من 11 إلى 15 هي المكان الذي تبدأ فيه المشاكل "الصعبة". التعامل مع الشبكات (Grid manipulation)، وحصر القواسم، والـ memoization، والبرمجة الديناميكية (dynamic programming) هي أدوات ستستخدمها لعقود. فهم لماذا 2^40 غير مجدٍ بينما C(40,20) تافه - هذا هو التحول في التفكير الذي تنميه هذه المشاكل. اعمل عليها، واشعر ببطء القوة الغاشمة (brute force)، وقدر أناقة الحلول المحسنة.