problem 79

Problem 79 - Project Euler

問題の本質は、集合の要素間の部分的な順序関係が複数与えられたときに要素全体の順序を見つける問題です。

これを解くのはトポロジカルソートです。とはいっても、この問題を解くまでトポロジカルソートについては名前と何をするものかぐらいしかしりませんでした。幸い gauche には topological-sort があることがわかりましたので、僕がするのは入力データを topological-sort の引数に与えられる形にすることだけでした。 topological-sort がなかったら、Topological sorting - Wikipedia を参考にして実装するはめになってました。

(use srfi-1)
(use util.toposort)

(define (p79)
  (call-with-input-file
    "p79_dat.txt"
    (lambda (p)
      (let loop ((nodes '()))
        (let1 line (read-line p)
              (if (not (eof-object? line))
                (let* ((nums (string->list line))
                       (key  (car nums))
                       (value (cdr nums))
                       (found (assq key nodes)))
                  (if found
                    (set-cdr! found (delete-duplicates (append found value)))  ; update
                    (set! nodes (acons key value nodes)))                      ; new
                  (loop nodes))
                (list->string (topological-sort (map cdr nodes)))))))))

(print (p79))

project euler には珍しく、この問題はプログラムを書くよりも紙と手で直接解いた方が速くすませられる問題です。実際私は初めは紙と手で解きました。