6
\$\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, 2024 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\$ Commented Jun 18, 2024 at 2:31
  • 1
    \$\begingroup\$ @Fe2O3 Compile with std=c23 and you get bool, true, and false for free. ;) \$\endgroup\$ Commented Jun 18, 2024 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\$ Commented Jun 18, 2024 at 2:50
  • 1
    \$\begingroup\$ @Fe2O3 Definitely not the middle. :) \$\endgroup\$ Commented Jun 18, 2024 at 3:25

2 Answers 2

Reset to default
4
\$\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\$ Commented Jun 17, 2024 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, 2024 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\$ Commented Jun 17, 2024 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, 2024 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\$ Commented Jun 20, 2024 at 3:23

You must log in to answer this question.