Project Euler

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

# [[Problem 28]]

## Number Spiral Diagonals

Starting with the number $1$ and moving to the right in a clockwise direction a $5$ by $5$ spiral is formed as follows:

|  |  |  |  |  |

|--|--|--|--|--|

| <span style="color:red"> **21** </span> | 22 | 23 | 24 | <span style="color:red"> **25** </span> |

| 20 | <span style="color:red"> **7** </span> | 8 | <span style="color:red"> **9** </span> | 10 |

| 19 | 6 | <span style="color:red"> **1** </span> | 2 | 11 |

| 18 | <span style="color:red"> **5** </span> | 4 | <span style="color:red"> **3** </span> | 12 |

| <span style="color:red"> **17** </span> | 16 | 15 | 14 | <span style="color:red"> **13** </span> |

It can be verified that the sum of the numbers on the diagonals is $101$.

What is the sum of the numbers on the diagonals in a $1001$ by $1001$ spiral formed in the same way?

## 螺旋状に並んだ数の対角線

1から初めて右方向に進み時計回りに数字を増やしていき, 5×5の螺旋が以下のように生成される:

|  |  |  |  |  |

|--|--|--|--|--|

| <span style="color:red"> **21** </span> | 22 | 23 | 24 | <span style="color:red"> **25** </span> |

| 20 | <span style="color:red"> **7** </span> | 8 | <span style="color:red"> **9** </span> | 10 |

| 19 | 6 | <span style="color:red"> **1** </span> | 2 | 11 |

| 18 | <span style="color:red"> **5** </span> | 4 | <span style="color:red"> **3** </span> | 12 |

| <span style="color:red"> **17** </span> | 16 | 15 | 14 | <span style="color:red"> **13** </span> |

両対角線上の数字の合計は101であることが確かめられる.

1001×1001の螺旋を同じ方法で生成したとき, 対角線上の数字の和はいくつか?

```scheme

(import (scheme base)

        (gauche base)

        (gauche array))

(define (diagonal-positions xynums)

  (assume (exact-integer? xynums))

  (assume (positive? xynums))

  (let* (; 左上→右下

         [diagonal-pos1 (fold-right

                          (^[n lis] (cons `(,n . ,n) lis))

                          '()

                          (iota xynums))]

         ; 右上→左下

         [diagonal-pos2 (fold-right

                          (^[n lis] (cons `(,n . ,(- xynums 1 n)) lis))

                          '()

                          (iota xynums))]

         [diagonal-pos (append diagonal-pos1 diagonal-pos2)])

    (if (odd? xynums)

      ; 奇数方陣の時は中央が重複して列挙されるので1つを外して返す

      (cons `(,(div xynums 2) . ,(div xynums 2))

            (remove (^c (= (car c) (cdr c) (div xynums 2)))

                    diagonal-pos))

      diagonal-pos)))

(define (diagonal-nums xynums)

  (assume (exact-integer? xynums))

  (assume (positive? xynums))

  (let ([table (make-table xynums)])

    (map (^c (array-ref table (car c) (cdr c)))

         (diagonal-positions xynums))))

(define (make-table xynums)

  (assume (exact-integer? xynums))

  (assume (positive? xynums))

  (letrec ([walk-right! (^[n y x table]

                          (cond

                            [(and (< (+ x 1) xynums)

                                  (not (array-ref table y (+ x 1))))

                             (array-set! table y (+ x 1) n)

                             (walk-down! (+ n 1) y (+ x 1) table)]

                            [(and (<= 0 (- y 1))

                                  (not (array-ref table (- y 1) x)))

                             (array-set! table (- y 1) x n)

                             (walk-right! (+ n 1) (- y 1) x table)]

                            [else table]))]

           [walk-down! (^[n y x table]

                         (cond

                           [(and (< (+ y 1) xynums)

                                 (not (array-ref table (+ y 1) x)))

                            (array-set! table (+ y 1) x n)

                            (walk-left! (+ n 1) (+ y 1) x table)]

                           [(and (< (+ x 1) xynums)

                                 (not (array-ref table y (+ x 1))))

                            (array-set! table y (+ x 1) n)

                            (walk-down! (+ n 1) y (+ x 1) table)]

                           [else table]))]

           [walk-left! (^[n y x table]

                         (cond

                           [(and (<= 0 (- x 1))

                                 (not (array-ref table y (- x 1))))

                            (array-set! table y (- x 1) n)

                            (walk-up! (+ n 1) y (- x 1) table)]

                           [(and (< (+ y 1) xynums)

                                 (not (array-ref table (+ y 1) x)))

                            (array-set! table (+ y 1) x n)

                            (walk-left! (+ n 1) (+ y 1) x table)]

                           [else table]))]

           [walk-up! (^[n y x table]

                       (cond

                         [(and (<= 0 (- y 1))

                               (not (array-ref table (- y 1) x)))

                          (array-set! table (- y 1) x n)

                          (walk-right! (+ n 1) (- y 1) x table)]

                         [(and (<= 0 (- x 1))

                               (not (array-ref table y (- x 1))))

                          (array-set! table y (- x 1) n)

                          (walk-up! (+ n 1) y (- x 1) table)]

                         [else table]))])

    (let ([table (make-array (shape 0 xynums 0 xynums) #f)])

      (array-set! table (div xynums 2) (div xynums 2) 1)

      (walk-right! 2 (div xynums 2) (div xynums 2) table))))

(define answer-28

  (apply + (diagonal-nums 1001)))

(format #t "28: ~d~%" answer-28)

```