ClojureでMissionary & Cannibal問題

「関数型オブジェクト指向AIプログラミング」からMissionaries and Cannibals問題のコーディング。

まずは状態を表すデータの定義。

[{:missionary 3 :cannibal 3} {:missionary 0 :cannibal 0} :left]

左岸にいる宣教師と食人鬼の数のマップ、右岸にいる数のマップ、ボートの現在地のキーワード、と三つの要素のvectorで表すことにする。

岸にいる人数から足したり引いたりする関数：

(defn add-movers [pos movers]
  (reduce (fn [m [key val]] 
            (update-in m [key] #(+ % val)))
        pos
        movers))

(defn subtract-movers [pos movers]
  (reduce (fn [m [key val]] 
            (update-in m [key] #(- % val)))
        pos
        movers))

ある状態から次に到達可能な状態のリストを作成する関数：

(defn next-states [[left right boat-pos]]
  (let [options (for [m (range 3)
                      c (range 3) :when (< 0 (+ m c) 3)]
                  {:missionary m :cannibal c})]
    (if (= boat-pos :left)
      (map #(identity [(subtract-movers left %) 
                       (add-movers right %) 
                       :right]) 
           options)
      (map #(identity [(add-movers left %) 
                       (subtract-movers right %) 
                       :left]) 
           options)

ただしこの関数では、ある岸にいる個体数がマイナスであっても許容される。その制約に関しては呼び出し側で修正する。

問題解決の中心となる再帰関数：

(defn solve [[history visited] current-state]
  (let [new-history (conj history current-state)
        new-visited (conj visited current-state)]
    (cond
      (= current-state end-state)
      (reduced [new-history new-visited])
    
      (let [[left right _] current-state]
        (or
          (contains? visited current-state)
          (some neg? (map second (concat left right)))
          (some
            #(and 
              (pos? (:missionary %))
              (> (:cannibal %) (:missionary %)))
            [left right])))
      [history new-visited]
      
      :else
      (let [[updated-history updated-visited]
            (reduce solve 
                    [new-history new-visited] 
                    (next-states current-state))]
        (if (= updated-history new-history)
          [history updated-visited]
          (reduced [updated-history updated-visited]))))))

reducedを使うことでreduceから条件次第で早期脱出が可能なので、正解が見つかり次第他の可能性を調べることなく答えが返ってくる。

真ん中の部分で色々な条件を記述している。具体的には、既に見たことのある状態ではいけない、どちらの岸でも人数がマイナスになってはいけない、宣教師と食人鬼両方がいる岸では「宣教師の数>=食人鬼の数」でなくてはいけない、の三点。

使い方：

(def initial-state [{:missionary 3 :cannibal 3} {:missionary 0 :cannibal 0} :left])
(def end-state [{:missionary 0 :cannibal 0} {:missionary 3 :cannibal 3} :right])

(->> (solve [[] #{}] initial-state)
     unreduced
     first
     (map println)
     do all)

結果：

[{:missionary 3, :cannibal 3} {:missionary 0, :cannibal 0} :left]
[{:missionary 3, :cannibal 1} {:missionary 0, :cannibal 2} :right]
[{:missionary 3, :cannibal 2} {:missionary 0, :cannibal 1} :left]
[{:missionary 3, :cannibal 0} {:missionary 0, :cannibal 3} :right]
[{:missionary 3, :cannibal 1} {:missionary 0, :cannibal 2} :left]
[{:missionary 1, :cannibal 1} {:missionary 2, :cannibal 2} :right]
[{:missionary 2, :cannibal 2} {:missionary 1, :cannibal 1} :left]
[{:missionary 0, :cannibal 2} {:missionary 3, :cannibal 1} :right]
[{:missionary 0, :cannibal 3} {:missionary 3, :cannibal 0} :left]
[{:missionary 0, :cannibal 1} {:missionary 3, :cannibal 2} :right]
[{:missionary 0, :cannibal 2} {:missionary 3, :cannibal 1} :left]
[{:missionary 0, :cannibal 0} {:missionary 3, :cannibal 3} :right]

ちゃんと条件を守って全員右岸に到達しているのがわかる。ただし、一番短いルートである保証はない。