** "Looks like JavaScript, brain (contents) is Ruby, (stability is AC / DC)" ** Scripting language Kinx ). "Program = algorithm + data structure". Introducing an implementation example of the algorithm.
The original story is "The latest algorithm encyclopedia in C language (even after 30 years)". This time we are missionaries and cannibals.
There are quite a few such things in the latest algorithm encyclopedia. It's like a puzzle.
I wrote this relatively recently. The reason is that the place where the solution is displayed makes full use of the format of printf, and the porting becomes troublesome.
From Wikipedia
** Missionaries and Indigenous People ** There are three missionaries and three indigenous people on the riverbank. There is one boat on the river that can accommodate up to two people. Only one of the missionaries and one of the indigenous people can row a boat. When the number of indigenous peoples exceeds the number of missionaries on either bank, the indigenous peoples rebel and attack the missionaries. How can everyone safely cross the opposite bank?
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
It is almost the same as the C language version except for the display of the solution. The display of the solution is completely rewritten. Here's what happened originally. In the original C language, it is implemented as follows.
#define M 3 /*Number of missionaries*/
#define C 3 /*Number of cannibals*/
void found(int n) /*Display of solution*/
{
int i;
static char mmm[] = "MMMMMMMMMM", ccc[] = "CCCCCCCCCC";
printf("Solution%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);
}
}
This cannot be used as it is, so it is rewritten as follows.
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);
}
}
It can't be helped.
See you next time.
Recommended Posts