Kinx アルゴリズム - 宣教師と人食い人種

# Kinx アルゴリズム - 宣教師と人食い人種

## はじめに

**「見た目は JavaScript、頭脳(中身)は Ruby、（安定感は AC/DC）」** でお届けしているスクリプト言語 [Kinx](https://github.com/Kray-G/kinx)。「プログラム＝アルゴリズム＋データ構造」。アルゴリズムの実装例をご紹介。

元ネタは「C言語による（30年経っても）最新アルゴリズム事典」。今回は宣教師と人食い人種です。

* 参考
    * 最初の動機 ... [スクリプト言語 KINX（ご紹介）](https://qiita.com/Kray-G/items/ca08b6fb40d15dd0ec76)
        * 個別記事へのリンクは全てここに集約してあります。
    * リポジトリ ... [https://github.com/Kray-G/kinx](https://github.com/Kray-G/kinx)
        * Pull Request 等お待ちしております。  

最新アルゴリズム事典にはこういうのも結構載ってる。パズル的な。

これは割と最近書いた。なぜって、解を表示するところが `printf` のフォーマット書式を駆使しててその移植が面倒な感じになっていたから。

## 宣教師と人食い人種

* https://ja.wikipedia.org/wiki/%E5%B7%9D%E6%B8%A1%E3%82%8A%E5%95%8F%E9%A1%8C

Wikipedia より
> **宣教師と先住民**
> 3人の宣教師と3人の先住民が川岸にいる。川には2人まで乗れるボートが1艘ある。
> ボートを漕げるのは宣教師のうちの1人と、先住民のうちの1人だけである。どちらかの岸で先住民の数が宣教師の数より多くなると、先住民は反旗を翻し宣教師に襲い掛かる。全員が無事に対岸に渡るにはどうしたらよいか?


## ソースコード

```javascript
const M = 3;
const C = 3;
const B = 2;

var np, solution;
var mb = [], cb = [],
    mh = [], ch = [], flag = [];
var i = 0;
var mmm = "MMMMMMMMMM", ccc = "CCCCCCCCCC";

function found(n)  /* Display a solution */
{
    var i;

    System.println("Solution %d" % ++solution);
    for (i = 0; i <= n; i++) {
        var m1 = mmm.subString(0, mh[i]);
        var m2 = mmm.subString(0, M-mh[i]);
        var c1 = ccc.subString(0, ch[i]);
        var c2 = ccc.subString(0, C-ch[i]);
        System.println(("%4d  %-%{M}s %-%{C}s  /  %-%{M}s %-%{C}s") % i % m1 % c1 % m2 % c2);
    }
}

function tryit()  /* Try it recursve */
{
    var j, m, c;

    i++;
    for (j = 1; j < np; j++) {
        if (i & 1) {  /* Go there in odd number. */
            m = mh[i - 1] - mb[j];  c = ch[i - 1] - cb[j];
        } else {      /* Come here in even number. */
            m = mh[i - 1] + mb[j];  c = ch[i - 1] + cb[j];
        }
        if (m < 0 || c < 0 || m > M || c > C ||
                (flag[m][c] & (1 << (i & 1)))) continue;
        mh[i] = m;  ch[i] = c;
        if (m == 0 && c == 0) found(i);
        else {
            flag[m][c] |= 1 << (i & 1);  tryit();
            flag[m][c] ^= 1 << (i & 1);
        }
    }
    i--;
}

var m, c;

np = 0;
for (m = 0; m <= B; m++) for (c = 0; c <= B - m; c++)
    if (m == 0 || m >= c) {
        mb[np] = m;  cb[np] = c;  np++;
    }
for (m = 0; m <= M; m++) for (c = 0; c <= C; c++)
    if ((m > 0 && m < c) || (m < M && M - m < C - c))
        flag[m][c] |= 1 | 2;
mh[0] = M;  ch[0] = C;  flag[M][C] |= 1;
solution = 0;  tryit();
if (solution == 0) System.println("No solutions.");
```

## 結果

```
Solution 1
   0  MMM CCC  /
   1  MMM C    /      CC
   2  MMM CC   /      C
   3  MMM      /      CCC
   4  MMM C    /      CC
   5  M   C    /  MM  CC
   6  MM  CC   /  M   C
   7      CC   /  MMM C
   8      CCC  /  MMM
   9      C    /  MMM CC
  10      CC   /  MMM C
  11           /  MMM CCC
Solution 2
   0  MMM CCC  /
   1  MMM C    /      CC
   2  MMM CC   /      C
   3  MMM      /      CCC
   4  MMM C    /      CC
   5  M   C    /  MM  CC
   6  MM  CC   /  M   C
   7      CC   /  MMM C
   8      CCC  /  MMM
   9      C    /  MMM CC
  10  M   C    /  MM  CC
  11           /  MMM CCC
Solution 3
   0  MMM CCC  /
   1  MM  CC   /  M   C
   2  MMM CC   /      C
   3  MMM      /      CCC
   4  MMM C    /      CC
   5  M   C    /  MM  CC
   6  MM  CC   /  M   C
   7      CC   /  MMM C
   8      CCC  /  MMM
   9      C    /  MMM CC
  10      CC   /  MMM C
  11           /  MMM CCC
Solution 4
   0  MMM CCC  /
   1  MM  CC   /  M   C
   2  MMM CC   /      C
   3  MMM      /      CCC
   4  MMM C    /      CC
   5  M   C    /  MM  CC
   6  MM  CC   /  M   C
   7      CC   /  MMM C
   8      CCC  /  MMM
   9      C    /  MMM CC
  10  M   C    /  MM  CC
  11           /  MMM CCC
```

## おわりに

解の表示以外はほぼ C 言語版と同じ。解の表示のところはマルっと書き換えている。元々がどうなっていたかここに示しておこう。元々の C 言語では以下のように実装されている。

```c
#define M  3  /* 宣教師の数 */
#define C  3  /* 人食い人の数 */

void found(int n)  /* 解の表示 */
{
    int i;
    static char mmm[] = "MMMMMMMMMM", ccc[] = "CCCCCCCCCC";

    printf("解 %d\n", ++solution);
    for (i = 0; i <= n; i++) {
        printf("%4d  %-*.*s %-*.*s  /  %-*.*s %-*.*s\n",
            i, M, mh[i], mmm, C, ch[i], ccc,
               M, M - mh[i], mmm, C, C - ch[i], ccc);
    }
}
```

これはこのままでは使えないので、こう書き換えている。

```javascript
const M = 3;
const C = 3;

function found(n)  /* Display a solution */
{
    var i;

    System.println("Solution %d" % ++solution);
    for (i = 0; i <= n; i++) {
        var m1 = mmm.subString(0, mh[i]);
        var m2 = mmm.subString(0, M-mh[i]);
        var c1 = ccc.subString(0, ch[i]);
        var c2 = ccc.subString(0, C-ch[i]);
        System.println(("%4d  %-%{M}s %-%{C}s  /  %-%{M}s %-%{C}s") % i % m1 % c1 % m2 % c2);
    }
}
```

仕方ないよね。

では、また次回。