[Java] Kinx algorithm-missionaries and cannibals

4 minute read

Kinx Algorithm-Missionaries and Cannibals

Introduction

The script language Kinxdeliveredby”“ItlookslikeJavaScript,thebrain(contents)isRuby,(stabilityisAC/DC)”). “Program = algorithm + data structure”. Introducing an example implementation 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.

The latest algorithm encyclopedia also has quite a few of these. Like a puzzle.

I wrote this relatively recently. The reason is that the place where the solution is displayed makes full use of the printf format format, and the porting becomes awkward.

Missionaries and cannibals

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

From Wikipedia

** Missionaries and Indigenous People ** Three missionaries and three indigenous people are 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. When the number of indigenous people exceeds the number of missionaries on either shore, the indigenous people rebel and attack missionaries. How can everyone safely cross the shore?

Source code

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.");

result

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

in conclusion

Almost the same as the C language version except for the display of the solution. The solution display has been completely rewritten. Here’s what it was like originally. The original C language implementation is as follows.

# define M 3 /* Number of missionaries */
# define C 3 /* Number of cannibals */

void found(int n) /* Display 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 I rewrite it 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.