2001年12月

[前月][次月][一覧]:[表紙][映画][King][BBS]


12/17 (Mon) 石の花

友人に借りた坂口尚「石の花」読了。感動した。骨のあるマンガを久々に読んだ。 マンガというメディアの持つ力というのを改めて思い知らされた。

12/11 (Tue) 切符問題

今日はプログラミングの話題。

先日書いた、ひとけたの数字4つと四則演算を使って 数字を作る問題だが、早速 高林さんのところでRubyによるプログラムが、 nobsunさんのところでHaskellによるプログラムが示された。 ここはSchemeでも実装しとかないと。

というわけででっちあげたのがこれ。useformatGauche 依存だが、あとはR5RS + SRFI-11なので他のScheme処理系でも移植は簡単だろう。 重複する探索は除いてないので効率は悪い。Pentium III 450MHz で (solve 24 1 3 4 6) に1.5秒くらいかかる。 Schemeらしいところは、 ヒストリを木構造に直したのをそのまま表示すれば自然な数式になるとこくらいかな。 期せずしてpure functionalになった。 マクロはスタックマシンの見通しを良くするために使ったが、なんか別に使わないでも いいような気もしてきた。

(use srfi-11) ; let*-values

(define (solve target a b c d)
  (let-syntax ((make-op
                (syntax-rules ()
                  ((_ op avoid-zero? recur)
                   (lambda (code stack history)
                     (cond ((null? stack)       #f)
                           ((null? (cdr stack)) #f)
                           ((and avoid-zero? (zero? (cadr stack))) #f)
                           (else (recur code
                                        (cons (op (car stack) (cadr stack))
                                              (cddr stack))
                                        (cons 'op history)))))))))
    (define op+ (make-op + #f recur))
    (define op- (make-op - #f recur))
    (define op* (make-op * #f recur))
    (define op/ (make-op / #t recur))

    ;; 非決定性スタックマシンでインストラクションプールcodeを実行。
    ;; stack には現在のスタック、 history には演算のヒストリを残す。
    ;; 実行が最後まで行ったら report を呼び出す。
    (define (recur code stack history)
      (if (null? code)
          (if (null? (cdr stack))
              (report (car stack) history)
              #f)
          (for-each
           (lambda (pick)
             (let ((rest (delete-1 pick code)))
               (if (number? pick)
                   (recur rest (cons pick stack) (cons pick history))
                   (for-each (lambda (op) (op rest stack history))
                             (list op+ op- op* op/)))))
           code)))

    ;; 補助関数。listからeltだけを除く。eltが重複している場合もひとつだけ除く。
    ;; (SRFI-1のdeleteは重複しているものを全部除くので使えない)
    (define (delete-1 elt list)
      (cond ((null? list) '())
            ((eqv? (car list) elt) (cdr list))
            (else (cons (car list) (delete-1 elt (cdr list))))))

    ;; 順ポーランド記法のヒストリを中置記法の木構造に直す。
    (define (history->tree h)
      (define (rec h)
        (cond ((null? h) (values '() '()))
              ((number? (car h)) (values (car h) (cdr h)))
              (else (let*-values (((left  rest) (rec (cdr h)))
                                  ((right rest) (rec rest)))
                      (values (list left (car h) right) rest)))))
      (receive (r _) (rec h) r))

    ;; 結果がターゲットと同じならレポート。 Gaucheは一般の有理数はサポートしないので
    ;; 比較のところがちょっと汚い。
    (define (report val history)
      (if (< (abs (- val target)) 1.0e-6)
          (format #t "~s = ~a~%" (history->tree history) val)))

    ;; メインの呼び出し。
    (recur (list a b c d 'o 'o 'o) '() '())
    ))

12/07 (Fri) パズル

ランチタイムに同僚が出した数字パズル。ひとけたの数字 1, 3, 4, 6 と四則演算を使って24を作る。全ての数字は一回づつ使うこと。括弧は使って良い。 飲茶に行ったのだが、全員が考えてて黙って点心を食べ続ける様子は 端から見ていてきっと不自然だったに違いない。 私は答えに40分くらいかかった。 ちなみに同僚はプログラムを組んで解がその一つだけしかないのを確認したそうだ。

よし、今度は高林さんのとこで見た 12枚のコインのパズルでリベンジだ。

12/05 (Wed)

出がけにジョギングをする日本人をちらほら見る。そうか今週末はホノルルマラソンだ。 先週はじめに大雨があって、そのあとも天気がぐずついている。 当日は適度な天気になってくれればいいけど。せっかく遠くから来て走るんだからねえ。

ぐずついた天気にも良いことはある。ちょうど昼食時、ダウンタウンはお天気雨。 北向きのオフィスの窓からは完全なアーチ型の2重の虹が見えた。

Bram Stoker ``Dracula'' ようやく読了。 この時代の作品の登場人物の饒舌さにはなかなか慣れないが、 ラストシーンの美しさは見事だった。


[前月][次月][一覧]:[表紙][映画][King][BBS]

Shiro Kawai
shiro@lava.net