油売り算

今回のお題は油売り算。

斗桶 (a) に油が 1 斗 (10 升) ある。これを等分したい。7 升枡 (b) と 3 升枡 (c) しかない。この 2 つの枡だけで、5 升ずつ等分する方法を記述せよ。
この問題を解くにあたり、(a) に入っている油の容量を第 1 引数、(b) の容量を第 2 引数、(c) の容量を第 3 引数とするプログラムとせよ。

キミならどう書く 2.0 - 2007 - その 1

結構定番の問題だと思う。過去に何かのアルゴリズム解説書や雑誌などで見掛けたおぼえがある。そういえば洋画のダイ・ハードでもこの系統の問題を出す場面があったような気がする。
と、言うわけで、schemeで書いてみた。油を移すパターンを素で全て書いてるのが冗長に思えるのだけれど、うまく抽象化する方法が思いつかなかった。

(define (lower-bound a b)
  (let ((r (- a b)))
    (if (< r 0) 0 r)))

(define (upper-bound a b u)
  (let ((r (+ a b)))
    (if (> r u) u r)))

(define (oil-store a b c)
  (let ((hash-table (make-hash-table 'equal?)))
    (let move ((a1 a)
               (b1 0)
               (c1 0)
               (path '()))
      (if (or (= a (* 2 b1)) (= a (* 2 c1)))
	  (print (reverse path))
	  (if (hash-table-get hash-table (list a1 b1 c1) #t)
	      (begin
                (hash-table-put! hash-table (list a1 b1 c1) #f)
                (move (lower-bound a1 (- b b1))
                      (upper-bound b1 a1 b)
                      c1
                      (cons 'a->b path))
                (move (lower-bound a1 (- c c1))
                      b1
                      (upper-bound c1 a1 c)
                      (cons 'a->c path))
                (move a1
                      (lower-bound b1 (- c c1))
                      (upper-bound b1 c1 c)
                      (cons 'b->c path))
                (move a1
                      (upper-bound b1 c1 b)
                      (lower-bound c1 (- b b1))
                      (cons 'c->b path))
                (move (+ a1 b1)
                      0
                      c1
                      (cons 'b->a path))
                (move (+ a1 c1)
                      b1
                      0
                      (cons 'c->a path))
                (hash-table-delete! hash-table (list a1 b1 c1))
                )
              )))))

(oil-store 10 7 3)

Document ID: 848657f16cf8781601c4fbfaae1ae80b