problem 81 - mtsuyuguの日記

80*80 の行列の左上から右下まで要素を辿っていったときの経路となった要素の和が最少になるときの値はいくつかを求める問題です。

各要素の値を、ひとつ上とひとつ右の要素の値を比べて小さい方の値と自分自身の値の和に置き換える、という操作を左上から右下まで行っていけば最終的に右下の要素に求める値が入っているという仕組みです。ひとつ上やひとつ右の要素がない場合は maxnum を返しています。

(define maxnum 9999999999999)

; return vector of vectors
(define (input-file fname)
  (call-with-input-file
    fname
    (lambda (p)
      (let loop ((r '()))
        (let1 line (read-line p)
              (if (eof-object? line)
                (list->vector (reverse r))
                (loop (cons ((compose list->vector (map$ string->number))
                             (string-split line #\,))
                            r))))))))

(define (vector2d-at v i j)
  (let1 vi (vector-ref v i #f)
        (if vi (vector-ref vi j maxnum) maxnum)))

(define (vector2d-set! v i j obj)
  (let1 vi (vector-ref v i #f)
        (if vi (vector-set! vi j obj) #f)))

(define (p81)
  (let* ((h 80) (w 80) (v (input-file "p81_data.txt")))
    (let loop ((i 0) (j 1))
      (cond ((> i h)
             (vector2d-at v (- w 1) (- h 1)))
            (else
              (vector2d-set! v i j (+ (vector2d-at v i j)
                                      (min (vector2d-at v (- i 1) j)
                                           (vector2d-at v i (- j 1)))))
              (loop (if (= j (- w 1)) (+ i 1) i)
                    (if (= j (- w 1)) 0 (+ j 1))))))))

(print (p81))