Project Euler

[ホーム](https://redmine.noppi.jp) - [[Wiki|Project Euler]]

# [[Problem 11]]

## Largest Product in a Grid

In the $20 \times 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 <span style="color:red">**26**</span> 38 40 67 59 54 70 66 18 38 64 70

67 26 20 68 02 62 12 20 95 <span style="color:red">**63**</span> 94 39 63 08 40 91 66 49 94 21

24 55 58 05 66 73 99 26 97 17 <span style="color:red">**78**</span> 78 96 83 14 88 34 89 63 72

21 36 23 09 75 00 76 44 20 45 35 <span style="color:red">**14**</span> 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 \times 63 \times 78 \times 14 = 1788696$.

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

## 格子内の最大の積

上の 20×20 の格子のうち, 斜めに並んだ4つの数字が赤くマークされている.

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 <span style="color:red">**26**</span> 38 40 67 59 54 70 66 18 38 64 70

67 26 20 68 02 62 12 20 95 <span style="color:red">**63**</span> 94 39 63 08 40 91 66 49 94 21

24 55 58 05 66 73 99 26 97 17 <span style="color:red">**78**</span> 78 96 83 14 88 34 89 63 72

21 36 23 09 75 00 76 44 20 45 35 <span style="color:red">**14**</span> 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

それらの数字の積は 26 × 63 × 78 × 14 = 1788696 となる.

上の 20×20 の格子のうち, 上下左右斜めのいずれかの方向で連続する4つの数字の積のうち最大のものはいくつか?

```scheme

#!r6rs

#!chezscheme

(import (chezscheme))

(define matrix

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

(define row-numbers

  (let* ([matrix-length (vector-length matrix)]

         [max-index-i (- matrix-length 4)])

    (fold-left

      (lambda (lis current-vector)

        (let loop ([i 0] [result lis])

          (if (< max-index-i i)

            result

            (let ([num1 (vector-ref current-vector i)]

                  [num2 (vector-ref current-vector (+ i 1))]

                  [num3 (vector-ref current-vector (+ i 2))]

                  [num4 (vector-ref current-vector (+ i 3))])

              (loop (add1 i) (cons `(,num1 ,num2, num3, num4) result)))))) 

      '()

      (vector->list matrix))))

(define column-numbers

  (let* ([matrix-length (vector-length matrix)]

         [max-index-i (- matrix-length 4)])

    (let loop1 ([i 0] [result '()])

      (if (< max-index-i i)

        result

        (let loop2 ([j 0] [result result])

          (if (<= matrix-length j)

            (loop1 (add1 i) result)

            (let ([num1 (vector-ref (vector-ref matrix i) j)]

                  [num2 (vector-ref (vector-ref matrix (+ i 1)) j)]

                  [num3 (vector-ref (vector-ref matrix (+ i 2)) j)]

                  [num4 (vector-ref (vector-ref matrix (+ i 3)) j)])

              (loop2 (add1 j) (cons `(,num1 ,num2, num3, num4) result)))))))))

;左下から右上

(define diagonal-numbers-1

  (let* ([matrix-length (vector-length matrix)]

         [max-index-j (- matrix-length 4)])

    (let loop1 ([i 3] [result '()])

      (if (<= matrix-length i)

        result

        (let loop2 ([j 0] [result result])

          (if (< max-index-j j)

            (loop1 (add1 i) result)

            (let ([num1 (vector-ref (vector-ref matrix i) j)]

                  [num2 (vector-ref (vector-ref matrix (- i 1)) (+ j 1))]

                  [num3 (vector-ref (vector-ref matrix (- i 2)) (+ j 2))]

                  [num4 (vector-ref (vector-ref matrix (- i 3)) (+ j 3))])

              (loop2 (add1 j) (cons `(,num1 ,num2 ,num3 ,num4) result)))))))))

;左上から右下

(define diagonal-numbers-2

  (let* ([matrix-length (vector-length matrix)]

         [max-index (- matrix-length 4)])

    (let loop1 ([i 0] [result '()])

      (if (< max-index i)

        result

        (let loop2 ([j 0] [result result])

          (if (< max-index j)

            (loop1 (add1 i) result)

            (let ([num1 (vector-ref (vector-ref matrix i) j)]

                  [num2 (vector-ref (vector-ref matrix (+ i 1)) (+ j 1))]

                  [num3 (vector-ref (vector-ref matrix (+ i 2)) (+ j 2))]

                  [num4 (vector-ref (vector-ref matrix (+ i 3)) (+ j 3))])

              (loop2 (add1 j) (cons `(,num1 ,num2 ,num3 ,num4) result)))))))))

(define all-number-combinations

  `( ,@row-numbers

     ,@column-numbers

     ,@diagonal-numbers-1

     ,@diagonal-numbers-2))

(define product-numbers

  (map

    (lambda (lis)

      (apply * lis))

    all-number-combinations))

(define answer-11

  (apply max product-numbers))

(printf "11: ~D~%" answer-11)

```