ホーム - 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:

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の螺旋が以下のように生成される:

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

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

;;;
;;; 未完成！！！
;;;

(import (scheme base)
        (gauche base)
        (gauche array))

(define (make-table xynums)
  (let ([table (make-array (shape 0 xynums 0 xynums) #f)])
    (letrec ([walk-right (^[n y x]
                           (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))]
                             [(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)]
                             [else table]))]
             [walk-down (^[n y x]
                          (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)]
                            [(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))]
                            [else table]))]
             [walk-left (^[n y x]
                          (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))]
                            [(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)]
                            [else table]))]
             [walk-up (^[n y x]
                        (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)]
                          [(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))]
                          [else table]))])
      (array-set! table (div xynums 2) (div xynums 2) 1)
      (walk-right 2 (div xynums 2) (div xynums 2)))))

;(define answer-28

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