Kinx アルゴリズム - 宣教師と人食い人種
はじめに
「見た目は JavaScript、頭脳(中身)は Ruby、（安定感は AC/DC）」 でお届けしているスクリプト言語 Kinx。「プログラム＝アルゴリズム＋データ構造」。アルゴリズムの実装例をご紹介。
元ネタは「C言語による（30年経っても）最新アルゴリズム事典」。今回は宣教師と人食い人種です。
- 参考
- 最初の動機 ... スクリプト言語 KINX（ご紹介）
- 個別記事へのリンクは全てここに集約してあります。
- リポジトリ ... https://github.com/Kray-G/kinx
- Pull Request 等お待ちしております。
- 最初の動機 ... スクリプト言語 KINX（ご紹介）
最新アルゴリズム事典にはこういうのも結構載ってる。パズル的な。
これは割と最近書いた。なぜって、解を表示するところが printf のフォーマット書式を駆使しててその移植が面倒な感じになっていたから。
宣教師と人食い人種
Wikipedia より
宣教師と先住民
3人の宣教師と3人の先住民が川岸にいる。川には2人まで乗れるボートが1艘ある。
ボートを漕げるのは宣教師のうちの1人と、先住民のうちの1人だけである。どちらかの岸で先住民の数が宣教師の数より多くなると、先住民は反旗を翻し宣教師に襲い掛かる。全員が無事に対岸に渡るにはどうしたらよいか?
ソースコード
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 言語では以下のように実装されている。
#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);
}
}
これはこのままでは使えないので、こう書き換えている。
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);
}
}
仕方ないよね。
では、また次回。