HOME SUMMARY

Problem 11

1. Problem

Largest product in a grid

In the 20×20 grid below, four numbers along a diagonal line have been marked in red.

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

The product of these numbers is 26 × 63 × 78 × 14 = 1788696.

What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20×20 grid?

方阵中的最大乘积

在如下的 20×20 方阵中,有四个呈对角线排列的数被标记为红色。

这四个数的乘积是 26×63×78×14=1788696。

在这个 20×20 方阵中,四个呈一直线(竖直、水平或对角线)相邻的数的乘积最大是多少?

2. Solution

对于这个 20×20 的矩阵,我最初的思路就是定义四个函数,它们分别是从水平,垂直,正对角线和逆对角线对整个矩阵进行遍历,然后比较这四个函数的返回值来获取最大值。现在想来,完全可以将这个大矩阵拆成多个 4×4 小矩阵,然后分别求取:

  (defun eu11-find-max4 (mat4)
    (let ((p1 [1 1 1 1])
          (p2 [1 1 1 1])
          (p3 1)
          (p4 1))
      (cl-loop for i below 4 do
               (cl-loop for j below 4 do
                        (progn
                          (aset p1 i (* (aref p1 i)
                                        (aref (aref mat4 i) j)))
                          (aset p2 j (* (aref p2 j)
                                        (aref (aref mat4 i) j)))
                          (when (= i j)
                            (setq p3 (* p3 (aref (aref mat4 i) j))))
                          (when (= i (- 3 j))
                            (setq p4 (* p4 (aref (aref mat4 i) j)))))))
      (let ((v (cl-concatenate 'vector p1 p2 `[,p3] `[,p4])))
        (aref (sort v '>) 0))))

(defvar eu10-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]]
  )

(cl-loop for i from 0 to 16
         with val = 0
         do (cl-loop for j from 0 to 16
                     do (let* ((mat `[,(cl-subseq (aref eu10-data i) j (+ j 4))
                                      ,(cl-subseq (aref eu10-data (1+ i)) j (+ j 4))
                                      ,(cl-subseq (aref eu10-data (+ i 2)) j (+ j 4))
                                      ,(cl-subseq (aref eu10-data (+ i 3)) j (+ j 4))])
                               (v (eu11-find-max4 mat)))
                          (when (> v val) (setq val v))))
         finally return val)
;; 70600674