宣教師と人食い人種の問題をGolangで再帰するクロージャ使って書いてみた。

# 1.背景

　いま、[プログラミング言語 Go](https://www.amazon.co.jp/dp/4621300253) を読んでいて、これの「5.6節 無名関数」でクロージャを
再帰させるコード例が出ていたのを見て、ふと、
「これと同じように、クロージャ使って、『宣教師と人食い人種問題』を再帰で解くのをGoで書いてみよう」
と思い立って書いてみました。
　今回書いたソースコードは、https://github.com/jun68ykt/m-and-c に上げてあります。

# 2.「宣教師と人食い人種」問題とは

### 2.1　初めて聞く人のために

「宣教師と人食い人種」問題を初めて聞く人のために説明すると、以下の(1)から(3)で設定される問題です。

　　(1) 川岸の片側に宣教師が3人と人食い人種が3人いて、2人まで乗れるボートがある。
　　

　　(2) 宣教師も人食い人種もともにボートを漕ぐことができて、何往復かすることで6人全員が
　　 　向こう岸に渡りたい。（川に入って歩いたり泳いだりして渡るのはナシで。）

　　　以下の図はこの様子を描いたもので、Mは宣教師（Missionary)、C は人食い人種（Cannibal）を表す。

<img width="775" alt="スクリーンショット 2017-12-10 23.16.18.png" src="https://qiita-image-store.s3.amazonaws.com/0/74659/47992565-1e40-0970-2328-6e990d8111cf.png">

　　　　なお上記の図で、矢印の先に「ボートを使って**何往復**かして、全員が向こう岸に行きたい。」と書いて
　　　あるけれども、「**何往復**」というのは間違いで、正しくは「ボートを使って**何回か行き来して**、全員が
　　　向こう岸に行きたい。」です。なぜなら最後に片道一回が必ずあるからです。

　　　 　以下、説明の便宜上、最初に6人がいる方の岸を、上の図にそって**左岸**といい、
　　　渡って行きたいほうの岸を**右岸**という。
　
　　(3) 何回かボートを往復（＋最後の片道一回）させて、彼らは右岸に渡ろうとするが、
　　　注意しなければならないのは、

　　  　**左岸、右岸どちらにおいても、もし、人食い人種の人数のほうが宣教師の人数よりも多くなると、
　　 　宣教師は人食い人種に食われてしまう**

　　　ということ。

　　　　例えば、上記(2)の初期状態から、宣教師2名がボートに乗って右岸に行こうとすると、
　　　左岸において、宣教師が1人、人食い人種が3人の状況になり、左岸で一人残された宣教師は
　　　人食い人種に食われてしまう。以下の図では、左岸の宣教師が、3人の人食い人種に襲われて
　　　食われてしまうことを表している。

<img width="520" alt="スクリーンショット 2017-12-10 23.28.28.png" src="https://qiita-image-store.s3.amazonaws.com/0/74659/46febdb1-bc95-c172-03ff-f6ed45b36bb0.png">

　　　もうひとつの例として、以下のような状態の場合を考える。

　　　<img width="621" alt="スクリーンショット 2017-12-10 23.34.38.png" src="https://qiita-image-store.s3.amazonaws.com/0/74659/f99abf8f-82c5-1243-137a-e907f550af3a.png">

　　　このときに、もし次に右岸から人食い人種が1人だけでボートに乗って、左岸に行ったとする。

<img width="655" alt="スクリーンショット 2017-12-10 23.37.34.png" src="https://qiita-image-store.s3.amazonaws.com/0/74659/348538f6-9b82-3729-e20e-9a6193d016fe.png">

　　　　すると、ボートが左岸に着いて、乗っていた人食い人種が岸に降りたとき、左岸では
　　　人食い人種が2人、宣教師が1人になり、人食い人種のほうが多いので宣教師が襲われる。

<img width="662" alt="スクリーンショット 2017-12-10 23.42.39.png" src="https://qiita-image-store.s3.amazonaws.com/0/74659/ba47c966-0f89-9feb-f8ec-b8dbc0ae7dd9.png">

　　　　このように、ボートに乗った宣教師も人食い人種も、川を渡りきったら、いったんは
　　　全員がボートから降りて、降りた状態での人数によって、人食い人種が宣教師を襲うか
　　　どうかを判定するものとする。（つまり、ボートに2人乗って降りるのは1人だけに
　　　しておく、ということはできない。そういうルール）

　【問題】
 　　上記 (1)〜(3) で設定された状況とルールにそって、何回かボートを行き来させれば、全員が
　無事に右岸に渡れるだろうか？渡れるならば、毎回のボートの行き来で、宣教師が何人、
　人食い人種が何人乗ればよいのかを示せ。

・・・というのが、この問題になります。


### 2.2　補足

　なお、この問題は、Wikipediaの[Missionaries_and_cannibals_problem](https://en.wikipedia.org/wiki/Missionaries_and_cannibals_problem) に、
 
> a well-known toy problem in artificial intelligence

と書いてあるとおり、人工知能の勉強をしていると、どこかしらで目にするクイズだったりします。
　かくいう私も、[第5世代コンピュータ](https://ja.wikipedia.org/wiki/%E7%AC%AC%E4%BA%94%E4%B8%96%E4%BB%A3%E3%82%B3%E3%83%B3%E3%83%94%E3%83%A5%E3%83%BC%E3%82%BF)プロジェクト [※1](https://qiita.com/jun68ykt/items/2b7d788d21a4cc5c9a56#%E8%84%9A%E6%B3%A8) の終焉期に、システム科学を専攻する学生として [Prolog](https://ja.wikipedia.org/wiki/Prolog) の勉強をしていて、それ関係の[書籍 ※2](https://qiita.com/jun68ykt/items/2b7d788d21a4cc5c9a56#%E8%84%9A%E6%B3%A8)に出ていて知りました。

# 3. Golang で解いてみます。

　それでは、Golang で解を求めるアルゴリズムを書いていきます。

### 3.1　川岸の状態を表す構造体

　宣教師の人数を `m` 、人食い人種の人数を `c` として、以下の構造体 `RiverSide`を定義します。

```Go
type RiverSide struct {
	m, c int
}
```

### 3.2　両岸の状態と、ボートがどちらにあるかを表す構造体

　全体の状況を表す構造体 `State` を以下のように定義します。

```Go
type State struct {
	left, right RiverSide
	boat string // "left" or "right"
}
```
フィールド変数が何を表すかというと、

- `left` と `right` は、それぞれ左岸、右岸を表します。
- `boat`は文字列で、ボートが左岸にあるとき `"left"` 、右岸にあるとき`"right"`になるものとします。

### 3.3　初期状態と目標状態

　上記の `State`構造体のインスタンスとして、初期状態と目標(Goal）状態を構造体リテラルで
書くと、以下のようになります。

```Go:初期状態
var initialState State = State{
	left:  RiverSide{3, 3},
	right: RiverSide{0, 0},
	boat:  "left",
}
```

```Go:目標状態
var goalState State = State{
	left:  RiverSide{0, 0},
	right: RiverSide{3, 3},
	boat:  "right",
}
```

### 3.4　オペレータ

　　この手の問題をAI分野では探索問題といい、探索問題において、ある状態から別の状態に
　変化させる手段のことをオペレータ（作用素）といいます。👉[「探索問題 オペレータ」でググる](https://www.google.co.jp/search?q=%E6%8E%A2%E7%B4%A2%E5%95%8F%E9%A1%8C+%E3%82%AA%E3%83%9A%E3%83%AC%E3%83%BC%E3%82%BF&ie=UTF-8)。
　　では、この問題においてオペレータは何かといえば、ボートによる、宣教師または人食い人種の
　一回（片道）の移動です。この一回の移動を特徴づけるのは、そこに宣教師が何人、人食い人種が
　何人乗っているのかという人数ですので、オペレータを表す構造体 `Operator` を以下のように定義
　します。

```Go:オペレータ
type Operator struct {
	m, c int
}
```

　　次に、実際に選択可能なオペレータの集合を考えます。
　　この問題では、ボートには2人までしか乗ることができず、また、誰も乗らなければ移動はできないので、
　以下のように、選択可能なオペレータの集合は5個の要素を持つことになります。

```
　選択可能なオペレータの集合　＝
　｛ 宣教師2人がボートに乗る, 
　　 宣教師1人だけでボートに乗る, 
　　 宣教師1人と人食い人種1人がボートに乗る, 
　　 人食い人種1人だけでボートに乗る,  
　　 人食い人種2人でボートに乗る }
```


　　上記の集合をどうプログラムで書くかですが、Goでは、(Pythonの`set`のような）集合を表す型が標準で
　用意されていないので、`Operator`の配列で表すことにして、以下の `Operators`を定義します。

```Go:選択可能なオペレータの配列
var Operators = [5]Operator{
	{2, 0},
	{1, 0},
	{1, 1},
	{0, 1},
	{0, 2},
}
```

### 3.5　状態が妥当であるかの検証

　「どちらの岸でも、人食い人種の人数が宣教師の人数を上回ると、人食い人種が宣教師を
　食べてしまうので、このような状態は避けなければならない」
　というルールは、状態の妥当性を検証するバリデータとして、以下のように実装しました。

```Go:状態の妥当性を検証する関数
func valid(state State) bool {
	switch {
	case state.left.m < 0 || state.left.c < 0 || state.right.m < 0 || state.right.c < 0:
		return false
	case state.left.m > 0 && state.left.c > state.left.m:
		return false
	case state.right.m > 0 && state.right.c > state.right.m:
		return false
	default:
		return true
	}
}
```
　　上記には3つの `case`がありますが、2つ目と3つ目の `case`で、
　「人食い人種が宣教師を食べてしまう状況が発生するときは、`false`を返す」
　ようにしています。
　　1つ目の`case`は、いかなる状態でも、両岸の宣教師、人食い人種を表す `m` と `c` は負数に
　なってはならないという自明な制約を表しています。

### 3.6　状態遷移関数

　下準備の最後に重要なのは、この状態遷移関数です。これによって、この問題は[有限オートマトン](https://ja.wikipedia.org/wiki/%E6%9C%89%E9%99%90%E3%82%AA%E3%83%BC%E3%83%88%E3%83%9E%E3%83%88%E3%83%B3) を
構成することになるといえます。
　ここでは、現在の状態 `currentState` とオペレータ `op` を引数として、遷移先の状態を表す `nextState`と、遷移が成功したことを示す bool値の `ok`を返す関数を、以下のように定義しました。

```Go:状態遷移関数

func stateTransition(currentState State, op Operator) (nextState State, ok bool) {

	var from, to *RiverSide

	if currentState.boat == "left" {
		from, to = &currentState.left, &currentState.right
		nextState.boat = "right"
		nextState.right = RiverSide{ to.m + op.m, to.c + op.c }
		nextState.left = RiverSide{ from.m - op.m, from.c - op.c }
	} else {
		from, to = &currentState.right, &currentState.left
		nextState.boat = "left"
		nextState.left = RiverSide{ to.m + op.m, to.c + op.c }
		nextState.right = RiverSide{ from.m - op.m, from.c - op.c }
	}

	ok = valid(nextState)

	return
}
```

### 3.7　解を得るアルゴリズムを書く

　3.6 までに書いた構造体や関数を使って、解を得るアルゴリズムを書いていきます。
なお、これから示すコードは、

```Go
func main() {

}
```
の中に書いていくものとします。
　

#### 3.7.1　得られた解を保存しておくオペレータのスライス

　以下のように、空のスライスを用意しておきます。

```Go
solution := []Operator{}
```

　
#### 3.7.2　探索時に一度たどった状態を記録しておくマップ

　`State`をキーとして `bool`を値とするマップで、一度たどった`State`を記録するものとします。

```Go
history := map[State]bool{ initialState: true }
```
　
　　Go の構造体は、そのすべてのフィールドが比較可能であれば、その構造体自体も比較可能です。これに沿えば、先に定義した`RiverSide`は比較可能であり、したがって`State`も比較可能なので、（JAVAの [equals()メソッド](https://docs.oracle.com/javase/jp/7/api/java/lang/Object.html#equals(java.lang.Object))のような同値メソッドを別途作らなくても）そのままマップのキーに使える。これはなかなかイイ。
　
#### 3.7.3　与えられた状態から目標状態に到達する解を探す関数

　これを書くのが、冒頭の [1.背景](https://qiita.com/jun68ykt/items/2b7d788d21a4cc5c9a56#1%E8%83%8C%E6%99%AF) に書いた、そもそもの動機でした。
色々な書き方があると思いますが、以下のようにしてみました。

```Go:探索関数（クロージャ）
	var solve func(currentState State) bool

	solve = func(currentState State) bool {

		// もし、currentStateが目標状態と等しいなら、trueを返す。
		if currentState == goalState {
			return true
		}

		// 深さ優先探索(Depth-first search)で目標状態に至る解を探す。
		for _, op := range Operators {
			if nextState, ok := stateTransition(currentState, op); ok {
				if !history[nextState] {
					history[nextState] = true
					solution = append(solution, op)
					if solve(nextState) {
						return true
					} else {
						solution = solution[0 : len(solution)-1]
					}
				}
			}
		}
		return false
	}
```

　　　ところで、上記の

```Go
    var solve func(currentState State) bool

    solve = func(currentState State) bool {
        // 関数本体・・・
    }
　　　　　　
```
　のところは、なんとなく冗長に思えて、一行で

```Go
    var solve = func(currentState State) bool {
        // 関数本体・・・
    }
```
　と書けたら、ちょっとうれしいのだけれど、このように書いて実行すると、

```
undefined: solve
```
　と叱られますね。


#### 3.7.4　結果の出力

　もし、`solve` が問題を解くことができたら、解となる`Operator`の列を保存してある
`solution`を表示するようにします。

```Go
	if solve(initialState) {
		fmt.Printf("%+v\n", solution)
	}
```

# 4. 実行結果と解になっていることの確認

　以下は、上記のコードをGoファイル `main.go`に保存して、実行してみたところです。

> $ go version
go version go1.9.2 darwin/amd64
> $ go run main.go
[{m:1 c:1} {m:1 c:0} {m:0 c:2} {m:0 c:1} {m:2 c:0} {m:1 c:1} {m:2 c:0} {m:0 c:1} {m:0 c:2} {m:1 c:0} {m:1 c:1}]

　解として表示された、Operator のスライス　`[{m:1 c:1} ・・・ ]`　が本当に正解になっているかは、
手作業で絵を描いていけば確認できます。
　あるいは、Wikipedia [Missionaries_and_cannibals_problem](https://en.wikipedia.org/wiki/Missionaries_and_cannibals_problem) 　のページ中ほどの右側に出ている、[解を図示したもの](https://en.wikipedia.org/wiki/Missionaries_and_cannibals_problem#Solution)と、上記の`Operator`のスライス内容とが同じになっていることでも確認できます。
 （図のキャプションには、Graphic of solution to Jealous Husbands River Crossing Problem とありますが
実質、同じことを問う問題です。）

# 5. ソースコード
　
　　今回書いたソースコードは、以下

　https://github.com/jun68ykt/m-and-c

　に上げておきましたので、この手の問題がお好きな方はご自由に手を入れて頂き、
　たとえば
　「深さ優先探索ではなく、幅優先探索にしてやんよ」
　みたいな感じで遊んでみてください。


# 脚注
[※1：第5世代コンピュータ](https://qiita.com/jun68ykt/items/2b7d788d21a4cc5c9a56#22%E8%A3%9C%E8%B6%B3) 
　このプロジェクトがどういうもので、予算規模はどのくらいで、結果としてどういう経緯をたどったのかについては、池田信夫氏のブログエントリ「[第5世代コンピュータ](http://ikedanobuo.livedoor.biz/archives/51292517.html)」の解説が分かりやすい。

[※2：それ関係の書籍](https://qiita.com/jun68ykt/items/2b7d788d21a4cc5c9a56#22%E8%A3%9C%E8%B6%B3)
　うろ覚えだが、その本は[DEC-10 Prologの開発者R・コワルスキ](https://ja.wikipedia.org/wiki/Prolog#%E3%82%B3%E3%83%AF%E3%83%AB%E3%82%B9%E3%82%AD%E3%81%A8DEC-10Prolog)による [Logic for Problem Solving](https://www.researchgate.net/publication/277669992_Logic_for_Problem_Solving)の訳本[「論理による問題の解法」培風館(1987/3/1)](https://www.amazon.co.jp/dp/4563007889) だった気がする。あ、いや。違うかもしれない。この本に出ていたのは、[15パズル](https://ja.wikipedia.org/wiki/15%E3%83%91%E3%82%BA%E3%83%AB)か、あるいは[ハノイの塔](https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%8E%E3%82%A4%E3%81%AE%E5%A1%94)だったかもしれない。忘れた。なにせ、この本を修論のための副読本として読んだのは、四半世紀あまり昔の話だ。