5
\$\begingroup\$

I first saw this challenge when a user posted it to SO about two years ago without a shred of code.
The post's plea, "How do I get started?" meant the user's post didn't survive long on that site.

This is, it seems, a well-known challenge, with lots of Google-able demonstrations of solutions.

Spoiler Alert: DO NOT go looking for those solutions before considering your interest developing your own version.
The same caution applies to reading/reviewing the working code below.
Once one has "seen it done one way", it's hard to forget and find the joy of one's own achievement.


The challenge

Scene: 8 people are standing together on a river bank; 2 parents, 2 daughters, 2 sons, 1 cop and 1 criminal. The challenge is to orchestrate them all crossing the river using one small boat capable of carrying only two individuals, maximum.

Goal: all 8 are on the opposite river bank at the end.

Constraints:

  • The criminal cannot be in the company of any family member unless the cop is present.
  • The mother cannot be in the company of either son unless dad is present.
  • The dad cannot be in the company of either daughter unless mom is present.
  • Only the cop, mom and dad are able to row the boat (no kid, no criminal).

Find the most efficient solution(s) so that all 8 are able to continue their journey having crossed the river.


One programmatic solution

This is yet another Windows Console App with a focus on coding an efficient algorithmic solution, and minimal attention given to "looking nice."

This is a 'single source' app that uses a few file scope variables to cut-down on passing parameters to functions.

#include <stdio.h>
#include <stdint.h>
#include <stdarg.h>

int trace = 0; // threshold 0-7 for reporting something
void Trace( int lvl, char *fmt, ... ) {
    if( lvl > trace ) return;
    va_list ap;
    va_start(ap, fmt);
    vfprintf( stderr, fmt, ap );
    va_end( ap );
}

enum { // the cast of 2 daughters, 2 sons, 1 bad guy, 1 good guy, and 2 parents (each a bit)
    eD1=1, eD2=2, eS1=4, eS2=8, eBG=16, eGG=32, eMo=64, eDa=128,
    eDD = eD1 | eD2, // 2 daughters
    eSS = eS1 | eS2, // 2 sons
    eMD = eMo | eDa, // parents
    eFM = eDD | eSS |eMo | eDa // family
};

// give 'em names
char *who[] = { "Dot", "Dee", "Sam", "Sem", "Crm", "Cop", "Mum", "Dad" };

// Show a single "population" as names. Could be those in the boat.
void showPop( char *ttl, uint8_t sel ) {
    printf( ttl );
    for( uint8_t msk = 0x80, i = 7; msk; msk >>= 1, i-- )
        printf( "%-4s", ( sel & msk ) ? who[i] : "" );
}

// Show populations on both banks
void showState( uint8_t b0, uint8_t b1 ) {
    showPop( "State:  ", b0 );
    showPop( "  ====  ", b1 );
    putchar( '\n' );
}

uint32_t bitpop[ 8 ]; // 8 bits on one bank => 256 populations; most are invalid.
uint16_t pops[ 100 ]; // permitted populations empirically found to be 70, in fact!
int nPops;
uint16_t bhb4[ 100 ]; // "Been Here BeFore" to prevent infinite cycles

// precalculate bit patterns of permitted populations
bool BADq( uint8_t b ) { return (b & eDD) && (b & eSS)  && !(b & eMD); } // No kids w/o at least one parent
bool BADx( uint8_t b ) { return (b & eBG) && !(b & eGG) && (b & eFM); } // no thief w/o policeman if family present
bool BADy( uint8_t b ) { return (b & eDa) && !(b & eMo) && (b & eDD); } // no dad w/o mom with a daughter
bool BADz( uint8_t b ) { return (b & eMo) && !(b & eDa) && (b & eSS); } // no mom w/o dad with a son
void mkPops() {
    for( int i = 0; i <= 0xFF; i++ ) {
        uint8_t l = (uint8_t)~i; // left...
        uint8_t r = (uint8_t)~l; // right river bank

        if( BADq( l ) || BADq( r ) // reject those that are bad
        ||  BADx( l ) || BADx( r )
        ||  BADy( l ) || BADy( r )
        ||  BADz( l ) || BADz( r ) )
            continue;

        pops[ nPops++ ] = (uint16_t)(l<<8 | r); // record good pops for both sides as 16 bits
        bitpop[ (i >> 5) & 7 ] |= ( 1 << ( i & 0x1F ) );
    }
}

// precalculate permitted boat occupants
uint8_t trav[ 3 * 8 ]; // 3 rowers with 8 passengers (including self twice!)
int nTrav; // actual count without duplicates

void mkTrav() { // fill array of possible boat occupant(s)
    trav[ nTrav++ ] = eDa; // first the rowers (altogether) as solo (for return trips)
    trav[ nTrav++ ] = eMo;
    trav[ nTrav++ ] = eGG;

    for( uint8_t p0 = eDa; p0 >= eGG; p0 >>= 1 )
        for( uint8_t p1 = eDa; p1; p1 >>= 1 ) {
            if( ( p0 == p1 ) // already have solos [0], [1] and [2]
            ||  ( p0 == eDa && (p1 & eDD) ) // dad cannot cross with one daughter
            ||  ( p0 == eMo && (p1 & eSS) ) // mom cannot cross with one son
            ||  ( p1 == eBG && !(p0 &eGG) ) ) // crim can only cross with cop
                continue;
            trav[ nTrav ] = (uint8_t)(p0 | p1); // make a pair of travellers
            for( int i = 0; i < nTrav && trav[ nTrav ] != trav[ i ]; i++ ) {} // no duplicates
            nTrav += i == nTrav; // keep this pairing in array
        }

    if( trace >= 7 ) {
        printf( "\ntrav cnt %d\n", nTrav );
        for( int i = 0; i < nTrav; i++ ) {
            printf( "%2d:  ", i );
            showPop( "Boat pair: ", trav[ i ] );
            putchar( '\n' );
        }
    }
}

// recursive search for next step in sequence
int solve( int ply, uint16_t pop ) {
    int res = 0;
    bhb4[ ply-1 ] = pop;
    uint8_t from = (uint8_t)( !(ply%2) ? pop : pop>>8 );
    uint8_t dest = (uint8_t)(  (ply%2) ? pop : pop>>8 );

    Trace( 2, ">> Solve( %d ) %04X (%02X) (%02X)\n", ply, pop, from, dest );

    for( int i, tb = (ply%2) ? 3 : 0; tb < nTrav; tb++ ) {
        Trace( 5, "%2d:%2d: From %02X, Travellers %02X\n", ply, tb, from, trav[tb] );

        if( (from & trav[tb]) != trav[tb] ) {
            Trace( 6, "travellers not present\n" );
            continue;
        }

        // use temp copies to evaluate this transer of persons
        uint16_t tmpFrom = (uint16_t)(from & ~trav[tb]);
        uint16_t tmpDest = (uint16_t)(dest |  trav[tb]);
        uint16_t testPop = (uint16_t)((ply%2) ? (tmpFrom<<8) | tmpDest : tmpFrom | (tmpDest<<8) );

        if( trace >= 10 ) {
            printf( "Considering: " );
            showState( (uint8_t)(testPop>>8), (uint8_t)testPop );
            getchar();
        }

        if( ( bitpop[ ( testPop >> 5) & 7 ] & ( 1 << ( testPop & 0x1F ) ) ) == 0 ) {
            Trace( 2, "not a valid population\n" );
            continue;
        }

        for( i = 0; i < ply && ( testPop != bhb4[i] || (ply%2) != (i%2) ); i++ ) ; // loop
        if( i < ply ) {
            Trace( 2, "Been here before. Curr %d Prev %d\n", ply, i+1 );
            continue;
        }

        if( testPop == 0x00FF ) { // base case
            puts( "\n FOUND ONE \n" );

            bhb4[ ply++ ] = testPop;
            for( i = 0; i < ply; i++ )
                showState( (uint8_t)(bhb4[i]>>8), (uint8_t)bhb4[i] );
            for( int i = 0; i < ply; i++ )
                printf( "%04X ", bhb4[i] );
            getchar();
            Trace( 2, "*** BACKTRACKING ***\n" );
            ply--;
            bhb4[ ply-1 ] = 0;
            return 1;
        }

        res += solve( ply+1, testPop );
    }
    Trace( 2, "*** BACKTRACKING ***\n" );
    bhb4[ ply-1 ] = 0;
    return res;
}

int main( void ) {
    mkPops();
    mkTrav();

    int nSol = solve( 1, 0xFF00 ); // Everyone on the first bank
    printf( "%d solutions found\n", nSol );
    for( int i = 0; i < nPops; i++ ) {
        printf( "%2d: %04X\t", i, pops[i] );
        showState( (uint8_t)(pops[i]>>8), (uint8_t)pops[i] );
    }
    for( i = 0; i < 8; i++ ) printf( "%08X\n", bitpop[i] );

    return 0;
}

Output of one solution

 FOUND ONE

State:  Dad Mum Cop Crm Sem Sam Dee Dot   ====
State:  Dad Mum         Sem Sam Dee Dot   ====          Cop Crm
State:  Dad Mum Cop     Sem Sam Dee Dot   ====              Crm
State:  Dad Mum             Sam Dee Dot   ====          Cop Crm Sem
State:  Dad Mum Cop Crm     Sam Dee Dot   ====                  Sem
State:      Mum Cop Crm         Dee Dot   ====  Dad             Sem Sam
State:  Dad Mum Cop Crm         Dee Dot   ====                  Sem Sam
State:          Cop Crm         Dee Dot   ====  Dad Mum         Sem Sam
State:      Mum Cop Crm         Dee Dot   ====  Dad             Sem Sam
State:      Mum                 Dee Dot   ====  Dad     Cop Crm Sem Sam
State:  Dad Mum                 Dee Dot   ====          Cop Crm Sem Sam
State:                          Dee Dot   ====  Dad Mum Cop Crm Sem Sam
State:      Mum                 Dee Dot   ====  Dad     Cop Crm Sem Sam
State:                              Dot   ====  Dad Mum Cop Crm Sem Sam Dee
State:          Cop Crm             Dot   ====  Dad Mum         Sem Sam Dee
State:              Crm                   ====  Dad Mum Cop     Sem Sam Dee Dot
State:          Cop Crm                   ====  Dad Mum         Sem Sam Dee Dot
State:                                    ====  Dad Mum Cop Crm Sem Sam Dee Dot
FF00 CF30 EF10 C738 F708 738C F30C 33CC 738C 43BC C33C 03FC 43BC 01FE 31CE 10EF 30CF 00FF

"Tower of Hanoi" with additional complications to make it interesting.
How many different solutions can you find?


Review objectives:

Any/all comments on my code solution (esp. on the theme of recursion) are welcome.


EDIT:

@TobySpeight correctly points out, below, that the code presented in this question does not "pass muster" when presented to a modern C compiler. Mea culpa. I do NOT wish to invalidate that answer.

Readers interested in this coding challenge and one solution, can find, here at godbolt.org, the code rectified to compile cleanly with gcc 14.1.

Dusting it off (it's been a couple of years) and looking at it again after seeing to its deficiencies, a few more minimal changes have been made to improve its output, and to touch-up a few operations. "Differencing" the two versions may be interesting to readers.

In a large codebase maintained by several coders, engaging all available "proofreading review" options of a modern compiler is certainly a recommended practise. Thank you @Toby.

\$\endgroup\$
8
  • 2
    \$\begingroup\$ You describe the code as a "Windows Console App", but I don't see anything platform-specific in the code (the compilation error should be present on Windows too, AFAICT). \$\endgroup\$ Commented Jun 17 at 11:46
  • 1
    \$\begingroup\$ @Harith Yes... I only noticed that Oops when I actually did "diff" the two versions after posting my EDIT here... Oops... Yes, turning up the compiler's detection of "Oopsies" and treating those as errors does lead to improved code. I'm content with having corrected the business with the int i variables, and include <stdbool.h> to shift from C++ to C... In this instance, if there's no "I" in "team", then the "team" has 0 members... Makes "going out for a beer after work kinda difficult." :-) Point noted, thank you... Cheers! :-) \$\endgroup\$
    – Fe2O3
    Commented Jun 18 at 2:31
  • 1
    \$\begingroup\$ @Fe2O3 Compile with std=c23 and you get bool, true, and false for free. ;) \$\endgroup\$
    – Harith
    Commented Jun 18 at 2:40
  • \$\begingroup\$ @Harith When the world "out there" is always changing, there are, for some, three "phases of accepting changes" that one goes through in life, with the ranges being (roughly) birth-25, 25-45, and 45+. Youth: "that's normal", Middle: "that's novel!", Senior: "that's new-fangled!!". Guess which one has the most difficulty accepting change... Guess where I find myself... :-) \$\endgroup\$
    – Fe2O3
    Commented Jun 18 at 2:50
  • 1
    \$\begingroup\$ @Fe2O3 Definitely not the middle. :) \$\endgroup\$
    – Harith
    Commented Jun 18 at 3:25

2 Answers 2

3
\$\begingroup\$

Fix errors

Presumably nTrav += i == nTrav is intended to refer to the i that's just gone out of scope from the preceding for loop? We'll need to enlarge its scope:

            int i;
            for(i = 0; i < nTrav && trav[ nTrav ] != trav[ i ]; i++ ) {} // no duplicates
            nTrav += i == nTrav; // keep this pairing in array

And the undeclared i in main() can easily be declared:

    for(int i = 0; i < 8; i++ ) printf( "%08X\n", bitpop[i] );

Make string-literal usage const-correct

It's not hard to use const to fix these warnings exposed by gcc -Wwrite-strings:

292618.c:23:17: warning: initialization discards ‘const’ qualifier from pointer target type [-Wdiscarded-qualifiers]
   23 | char *who[] = { "Dot", "Dee", "Sam", "Sem", "Crm", "Cop", "Mum", "Dad" };
      |                 ^~~~~
292618.c:23:24: warning: initialization discards ‘const’ qualifier from pointer target type [-Wdiscarded-qualifiers]
   23 | char *who[] = { "Dot", "Dee", "Sam", "Sem", "Crm", "Cop", "Mum", "Dad" };
      |                        ^~~~~
292618.c:23:31: warning: initialization discards ‘const’ qualifier from pointer target type [-Wdiscarded-qualifiers]
   23 | char *who[] = { "Dot", "Dee", "Sam", "Sem", "Crm", "Cop", "Mum", "Dad" };
      |                               ^~~~~
292618.c:23:38: warning: initialization discards ‘const’ qualifier from pointer target type [-Wdiscarded-qualifiers]
   23 | char *who[] = { "Dot", "Dee", "Sam", "Sem", "Crm", "Cop", "Mum", "Dad" };
      |                                      ^~~~~
292618.c:23:45: warning: initialization discards ‘const’ qualifier from pointer target type [-Wdiscarded-qualifiers]
   23 | char *who[] = { "Dot", "Dee", "Sam", "Sem", "Crm", "Cop", "Mum", "Dad" };
      |                                             ^~~~~
292618.c:23:52: warning: initialization discards ‘const’ qualifier from pointer target type [-Wdiscarded-qualifiers]
   23 | char *who[] = { "Dot", "Dee", "Sam", "Sem", "Crm", "Cop", "Mum", "Dad" };
      |                                                    ^~~~~
292618.c:23:59: warning: initialization discards ‘const’ qualifier from pointer target type [-Wdiscarded-qualifiers]
   23 | char *who[] = { "Dot", "Dee", "Sam", "Sem", "Crm", "Cop", "Mum", "Dad" };
      |                                                           ^~~~~
292618.c:23:66: warning: initialization discards ‘const’ qualifier from pointer target type [-Wdiscarded-qualifiers]
   23 | char *who[] = { "Dot", "Dee", "Sam", "Sem", "Crm", "Cop", "Mum", "Dad" };
      |                                                                  ^~~~~
292618.c: In function ‘showState’:
292618.c:34:14: warning: passing argument 1 of ‘showPop’ discards ‘const’ qualifier from pointer target type [-Wdiscarded-qualifiers]
   34 |     showPop( "State:  ", b0 );
      |              ^~~~~~~~~~
292618.c:26:21: note: expected ‘char *’ but argument is of type ‘const char *’
   26 | void showPop( char *ttl, uint8_t sel ) {
      |               ~~~~~~^~~
292618.c:35:14: warning: passing argument 1 of ‘showPop’ discards ‘const’ qualifier from pointer target type [-Wdiscarded-qualifiers]
   35 |     showPop( "  ====  ", b1 );
      |              ^~~~~~~~~~
292618.c:26:21: note: expected ‘char *’ but argument is of type ‘const char *’
   26 | void showPop( char *ttl, uint8_t sel ) {
      |               ~~~~~~^~~
292618.c: In function ‘mkTrav’:
292618.c:91:22: warning: passing argument 1 of ‘showPop’ discards ‘const’ qualifier from pointer target type [-Wdiscarded-qualifiers]
   91 |             showPop( "Boat pair: ", trav[ i ] );
      |                      ^~~~~~~~~~~~~
292618.c:26:21: note: expected ‘char *’ but argument is of type ‘const char *’
   26 | void showPop( char *ttl, uint8_t sel ) {
      |               ~~~~~~^~~
292618.c: In function ‘solve’:
292618.c:104:15: warning: passing argument 2 of ‘Trace’ discards ‘const’ qualifier from pointer target type [-Wdiscarded-qualifiers]
  104 |     Trace( 2, ">> Solve( %d ) %04X (%02X) (%02X)\n", ply, pop, from, dest );
      |               ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
292618.c:6:28: note: expected ‘char *’ but argument is of type ‘const char *’
    6 | void Trace( int lvl, char *fmt, ... ) {
      |                      ~~~~~~^~~
292618.c:107:19: warning: passing argument 2 of ‘Trace’ discards ‘const’ qualifier from pointer target type [-Wdiscarded-qualifiers]
  107 |         Trace( 5, "%2d:%2d: From %02X, Travellers %02X\n", ply, tb, from, trav[tb] );
      |                   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
292618.c:6:28: note: expected ‘char *’ but argument is of type ‘const char *’
    6 | void Trace( int lvl, char *fmt, ... ) {
      |                      ~~~~~~^~~
292618.c:110:23: warning: passing argument 2 of ‘Trace’ discards ‘const’ qualifier from pointer target type [-Wdiscarded-qualifiers]
  110 |             Trace( 6, "travellers not present\n" );
      |                       ^~~~~~~~~~~~~~~~~~~~~~~~~~
292618.c:6:28: note: expected ‘char *’ but argument is of type ‘const char *’
    6 | void Trace( int lvl, char *fmt, ... ) {
      |                      ~~~~~~^~~
292618.c:126:23: warning: passing argument 2 of ‘Trace’ discards ‘const’ qualifier from pointer target type [-Wdiscarded-qualifiers]
  126 |             Trace( 2, "not a valid population\n" );
      |                       ^~~~~~~~~~~~~~~~~~~~~~~~~~
292618.c:6:28: note: expected ‘char *’ but argument is of type ‘const char *’
    6 | void Trace( int lvl, char *fmt, ... ) {
      |                      ~~~~~~^~~
292618.c:132:23: warning: passing argument 2 of ‘Trace’ discards ‘const’ qualifier from pointer target type [-Wdiscarded-qualifiers]
  132 |             Trace( 2, "Been here before. Curr %d Prev %d\n", ply, i+1 );
      |                       ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
292618.c:6:28: note: expected ‘char *’ but argument is of type ‘const char *’
    6 | void Trace( int lvl, char *fmt, ... ) {
      |                      ~~~~~~^~~
292618.c:145:23: warning: passing argument 2 of ‘Trace’ discards ‘const’ qualifier from pointer target type [-Wdiscarded-qualifiers]
  145 |             Trace( 2, "*** BACKTRACKING ***\n" );
      |                       ^~~~~~~~~~~~~~~~~~~~~~~~
292618.c:6:28: note: expected ‘char *’ but argument is of type ‘const char *’
    6 | void Trace( int lvl, char *fmt, ... ) {
      |                      ~~~~~~^~~
292618.c:153:15: warning: passing argument 2 of ‘Trace’ discards ‘const’ qualifier from pointer target type [-Wdiscarded-qualifiers]
  153 |     Trace( 2, "*** BACKTRACKING ***\n" );
      |               ^~~~~~~~~~~~~~~~~~~~~~~~
292618.c:6:28: note: expected ‘char *’ but argument is of type ‘const char *’
    6 | void Trace( int lvl, char *fmt, ... ) {
      |                      ~~~~~~^~~

Fixing these is the first step toward making your code more maintainable:

void Trace( int lvl, const char *fmt, ... ) {
char const *who[] = { "Dot", "Dee", "Sam", "Sem", "Crm", "Cop", "Mum", "Dad" };
void showPop(const char *ttl, uint8_t sel ) {
\$\endgroup\$
4
  • \$\begingroup\$ How does "Dot" decay to const char * instead of char * when the type of a string literal in C is char [] (char array), unlike C++ where it has type const char []? Though the pointers should still be declared with the const qualifiers, as string literals are modifiable. \$\endgroup\$
    – Harith
    Commented Jun 17 at 13:50
  • 1
    \$\begingroup\$ String literals in C have type char* but are not modifiable (for historical reasons: early C didn't have const). That's why representing them as char const* is the way to avoid accidental attempts to modify the character data. T*T const* is a safe implicit conversion in both languages, for any type T. \$\endgroup\$ Commented Jun 17 at 14:41
  • 1
    \$\begingroup\$ Indeed, but the compiler warnings are wrong, or misleading at best, because the types are still char *, and there no discarded qualifiers in any of the mentioned assignments. Probably the compiler being overly-pedantic. \$\endgroup\$
    – Harith
    Commented Jun 17 at 14:56
  • 1
    \$\begingroup\$ I wouldn't say over-pedantic, when I've asked for this level of checking with -Wwrite-strings option (which I should have mentioned in the review - fixing now). \$\endgroup\$ Commented Jun 17 at 16:05
2
\$\begingroup\$

Review

After some minor teething problems were resolved (compiler versions and flags), the OP's code does what it needs to do.

Noteworthy points:

  • "Tracing" operation (print debugging) seems to be residual from developing the code, and the 'thresholds' used seem sporadic. These portions should have been removed once the code has been tested and its output verified.
  • The code 'pre-calculates' lists of valid populations and boat travellers that are later used to prune the search space. This is good. However, when forming singles or couples of passengers, the outer loop relies on all 4 adults being contiguous bit values. This is not robust. Reassigning the bit representations would mysteriously break this code.
  • There is no constraint stating "4 kids and 0 adults is not permitted". This is a derived heuristic and should be noted as such with an explanatory comment.
  • Detecting and preventing "infinite loops" is good, but, as will be shown, has required unnecessary attention and coding.

By focussing on "valid populations" on both river banks, the OP has neglected the real locus of the solutions: the occupants of the boat at each stage. Sometimes a problem's "background" (or "fringe") can provide a better solution that the details of the foreground.


Plan ahead; don't rush into coding

I came to hear of this challenge, as explained above, and saw the question "How do I get started?" That post suggested the challenge was to be met with a "recursive solution".

"Fools rush in..."

Experience teaches that it is better to invest time in scoping and planning, rather than rushing to simply "type up" the solution. This challenge is one instance of that general case.

Analysis of the challenge leads to the conclusion that there are, in fact, only 2 junctures where progress toward solving the problem diverges along separate paths. Of the many stages to pass through, most have only ONE valid step to make progress.

The first two steps are "forced"; there is only one valid choice for boat passengers. At that point, the only "choice" is which of the 4 kids is to be the first to cross the river (with the cop.) Then, subsequent steps are also "forced", until a second "choice" branches when selecting which of the remaining 2 kids crosses first, and which crosses later.

As such, all 8 solutions are tractable and can be represented compactly in code that merely manipulates symbols and outputs each of the few solutions. Below is one version of such an implementation (without recursion).

Noting the duplication of "travellers" across each row of the sequence of trips, it is tempting to use a switch( i ) where each case: provides the passenger list appropriate to this step in the sequence. Left as an exercise.

#include <stdio.h>

typedef unsigned char BB; // Bank or Boat population

// cast: 2 girls, 2 boys, 1 bad guy, 1 good guy, and 2 parents
// each a single bit in a byte
// not used. for documentation purposes, only
enum {
    eD1 = 1<<0, eD2 = 1<<1, eS1 = 1<<2, eS2 = 1<<3,
    eBG = 1<<4, eGG = 1<<5, eMo = 1<<6, eDa = 1<<7
};

void showPop( char *pre, BB sel ) { // show who is on 1 bank
    char *who[] = { "Dot", "Dee", "Sam", "Sem", "Crm", "Cop", "Mum", "Dad" };

    printf( pre );
    for( BB msk = 0x80, i = 7; msk; msk >>= 1, i-- )
        printf( "%-4s", ( sel & msk ) ? who[i] : "" );
}

void showState( BB lft, BB rgt, BB boat ) { // show names on 2 banks
    printf( "%02X-%02X:  ", lft, rgt ); // preamble 2 banks as hex
    showPop( "", lft );
    showPop( " ====  ", rgt );
    printf( "  boat %02X\n", boat );
}

void solve( int t ) { // output stages of sequence 't'
    BB trav[][8] = { // "col major" sequences of boat travellers
        { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, },
        { 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, },
        { 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, },
        { 0x28, 0x28, 0x24, 0x24, 0x22, 0x22, 0x21, 0x21, },
        { 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, },
        { 0x84, 0x84, 0x88, 0x88, 0x41, 0x41, 0x42, 0x42, },
        { 0x80, 0x80, 0x80, 0x80, 0x40, 0x40, 0x40, 0x40, },
        { 0xC0, 0xC0, 0xC0, 0xC0, 0xC0, 0xC0, 0xC0, 0xC0, },
        { 0x40, 0x40, 0x40, 0x40, 0x80, 0x80, 0x80, 0x80, },
        { 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, },
        { 0x80, 0x80, 0x80, 0x80, 0x40, 0x40, 0x40, 0x40, },
        { 0xC0, 0xC0, 0xC0, 0xC0, 0xC0, 0xC0, 0xC0, 0xC0, },
        { 0x40, 0x40, 0x40, 0x40, 0x80, 0x80, 0x80, 0x80, },
        { 0x42, 0x41, 0x42, 0x41, 0x88, 0x84, 0x88, 0x84, },
        { 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, },
        { 0x21, 0x22, 0x21, 0x22, 0x24, 0x28, 0x24, 0x28, },
        { 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, },
        { 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, },
    };

    BB bs[] = { 0xFF, 0 }; // Everyone on the first bank

    int i = 0, from = 0;

    printf( "Solution #%d\n", t + 1 );
    showState( bs[0], bs[1], trav[ i ][ t ] ); // initial state

    for( i = 1; bs[0]; i++ ) {
        bs[  from ] &= (~trav[ i ][ t ]); // embark
        bs[ !from ] |= ( trav[ i ][ t ]); // disembark
        from = !from; // alternate
        showState( bs[0], bs[1], trav[ i ][ t ] );
    }
getchar(); // optional
}

int main( void ) {
    for( int t = 0; t < 8; t++ ) solve( t );
    return 0;
}

Armed with a thorough analysis and understanding of a problem, coding a solution can be completed quickly, and the result is usually more correct in the first instance.

With this done, it would be light work to rewrite this iterative solution, still table-driven or with a switch(), to make it recursive if required for the assignment.

This code and its output is available here on godbolt.org for any who might want to add compiler flags and the qualifiers modern compilers recommend.

\$\endgroup\$
1
  • \$\begingroup\$ Fellow golfers might be interested in another version with a few 'tweaks' to increase inscrutability and rigidity, and to lay bare the redundancy of some "solution paths". \$\endgroup\$
    – Fe2O3
    Commented Jun 20 at 3:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.