操作
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:
21 | 22 | 23 | 24 | 25 |
20 | 7 | 8 | 9 | 10 |
19 | 6 | 1 | 2 | 11 |
18 | 5 | 4 | 3 | 12 |
17 | 16 | 15 | 14 | 13 |
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の螺旋が以下のように生成される:
21 | 22 | 23 | 24 | 25 |
20 | 7 | 8 | 9 | 10 |
19 | 6 | 1 | 2 | 11 |
18 | 5 | 4 | 3 | 12 |
17 | 16 | 15 | 14 | 13 |
両対角線上の数字の合計は101であることが確かめられる.
1001×1001の螺旋を同じ方法で生成したとき, 対角線上の数字の和はいくつか?
(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)
Noppi が2024/01/12に更新 · 3件の履歴