פרויקט אוילר הוא אוסף של בעיות תכנות חמודות איתן אפשר לתרגל שפות תכנות שונות, או יכולות חדשות של שפות תכנות שאולי ביום יום לא כל כך יוצא לגעת בהן. יש שם אינסוף בעיות ואפשר למצוא את כולן באתר הפרויקט:

https://projecteuler.net/archives

בתרגיל 11 יש מטריצה של מספרים:

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 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

ואנחנו צריכים למצוא את רביעיית המספרים הצמודים (באותה שורה, טור או אלכסון) שמכפלתם הגדולה ביותר.

1. פיתרון הבעיה

בגלל ש-1 לא משפיע על מכפלות, הדרך הכי קלה (עבורי) לגשת לבעיה כזאת היתה להכניס את כל המספרים ל defaultdict שערך ברירת המחדל שלו הוא 1. בצורה כזאת לא צריך לבדוק אם אנחנו בגבולות של המטריצה - פשוט כל דבר שמחוץ למטריצה יהיה 1 ולא ישפיע על המכפלה.

זה הקוד שקורא את המטריצה למבנה נתונים מתאים בפייתון:

Index = tuple[int, int]
Matrix = dict[Index, int]
data: Matrix = defaultdict(lambda: 1)

for line_number, line in enumerate(StringIO(input_data)):
  for column_number, column_value in enumerate(line.split()):
    data[(line_number, column_number)] = int(column_value)

עכשיו שיש לנו את ה defaultdict אפשר לדבר על חישובי המכפלות. בשביל לחשב מכפלה של מספר אינדקסים במילון כתבתי את הפונקציה mul:

def mul(arr: Matrix, indices: Iterable[Index]) -> int:
  return reduce(operator.mul,
                [arr[index] for index in indices],
                1)

ובשביל לגלות איזה אינדקסים אני צריך להעביר לפונקציה כתבתי פונקציה נוספת בשם move:

def move(start_index: Index, step: Callable[[Index], Index], count: int = 4):
  index = start_index
  for i in range(count):
    yield index
    index = step(index)

הפונקציה move פשוט לוקחת אינדקס התחלה, פונקציה לצעד הבא ומספר צעדים ומחזירה Generator שכל next שלו מחזיר את האינדקס הבא.

לסיום נשאר רק לקחת את כל המטריצה ולהפוך אותה למערך של מכפלות כך שכל תא במערך יכיל את 8 המכפלות שסביבו:

products = [
  [
    mul(data, move((row, col), lambda t: (t[0] + 1, t[1]))),
    mul(data, move((row, col), lambda t: (t[0] - 1, t[1]))),
    mul(data, move((row, col), lambda t: (t[0], t[1] + 1))),
    mul(data, move((row, col), lambda t: (t[0], t[1] - 1))),
    mul(data, move((row, col), lambda t: (t[0] + 1, t[1] + 1))),
    mul(data, move((row, col), lambda t: (t[0] - 1, t[1] - 1))),
    mul(data, move((row, col), lambda t: (t[0] + 1, t[1] - 1))),
    mul(data, move((row, col), lambda t: (t[0] - 1, t[1] + 1))),
  ]
  for row in range(20)
  for col in range(20)
]

ולהדפיס את המכפלה הגדולה ביותר שמצאנו:

def flatten(matrix):
  return list(chain.from_iterable(matrix))

print(max(flatten(products)))

סך הכל הפיתרון המלא הוא:

from typing import Sequence, Callable, Iterable
from io import StringIO
import operator
from functools import reduce
from itertools import chain
from collections import defaultdict


input_data = """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 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48"""
Index = tuple[int, int]
Matrix = dict[Index, int]
data: Matrix = defaultdict(lambda: 1)

for line_number, line in enumerate(StringIO(input_data)):
  for column_number, column_value in enumerate(line.split()):
    data[(line_number, column_number)] = int(column_value)


def mul(arr: Matrix, indices: Iterable[Index]) -> int:
  return reduce(operator.mul,
                [arr[index] for index in indices],
                1)

def move(start_index: Index, step: Callable[[Index], Index], count: int = 4):
  index = start_index
  for i in range(count):
    yield index
    index = step(index)


products = [
  [
    mul(data, move((row, col), lambda t: (t[0] + 1, t[1]))),
    mul(data, move((row, col), lambda t: (t[0] - 1, t[1]))),
    mul(data, move((row, col), lambda t: (t[0], t[1] + 1))),
    mul(data, move((row, col), lambda t: (t[0], t[1] - 1))),
    mul(data, move((row, col), lambda t: (t[0] + 1, t[1] + 1))),
    mul(data, move((row, col), lambda t: (t[0] - 1, t[1] - 1))),
    mul(data, move((row, col), lambda t: (t[0] + 1, t[1] - 1))),
    mul(data, move((row, col), lambda t: (t[0] - 1, t[1] + 1))),
  ]
  for row in range(20)
  for col in range(20)
]

def flatten(matrix):
  return list(chain.from_iterable(matrix))

print(max(flatten(products)))

יש לכם כיוונים אחרים איך לפתור את זה? רוצים לשתף פיתרון בשפה אחרת? בדיוק בשביל זה יש מקום לתגובות פה למטה.