/********************************************************************************* * * Program to solve programmer bridge problem. * * There are four programmers on one side of a bridge. They must all cross the * bridge at night, sharing one flashlight. Only two programmers may be on the * bridge at any one time. The flashlight "carry" is configurable. * * 030715 Eichhorn Initial creation * *********************************************************************************/ #include // standard C libraries #include // time libraries #include // string libraries float carry = .25; // flashlight carry (1 = entire span) #define pcnt 4 // number of programmers float ptimes[pcnt] = {1, 2, 4, 8}; // programmer times /* * possible positions for programmers and flashlight: * 0 = near side * 1 = one flashlight carry in from near side * 2 = middle * 3 = one flashlight carry in from far side * 4 = far side */ int dcnt = 0; // number of destinations float dists[5]; // distances for each destination typedef struct { // state structure int progs[pcnt]; // programmer positions int flash; // flashlight position float eltime; // elapsed time } state; #define maxstates 10 int depth = 0; // current depth state states[maxstates]; // current sequence of states int bdepth = 0; // best depth state bstates[maxstates]; // best sequence of states float beltime = 20; // best elapsed time long statecnt = 0; // total states long solcnt = 0; // solutions long dupcnt = 0; // duplicates discarded long maxdepcnt = 0; // max depth states aborted long subopcnt = 0; // suboptimal states aborted long subop2cnt = 0; // suboptimal 2 states aborted int trace = 0; // trace flag time_t disptime = 0; // last display time void next(void); // make next state(s) from current void disp(int, state*); // display state void dispall(int, state*); // display current path // distance between positions #define dist(a, b) (dists[a] < dists[b] ? dists[b] - dists[a] : dists[a] - dists[b]) /*------------------------------------------------------------------------------- * * Main line - setup initial state, loop through all possible transitions */ main ( int argc, // count of parameters char *parmv[] // parameter vector ) { printf("Programmer bridge solver starting...\n"); #ifdef _DEBUG trace = 1; #endif dists[dcnt++] = 0; // init distances if (carry > 0 && carry < .5) dists[dcnt++] = carry; else if (carry > .5 && carry < 1) dists[dcnt++] = 1 - carry; else dists[dcnt++] = .25; dists[dcnt++] = .5; if (carry > 0 && carry < .5) dists[dcnt++] = 1 - carry; else if (carry > .5 && carry < 1) dists[dcnt++] = carry; else dists[dcnt++] = .75; dists[dcnt++] = 1; /* * setup initial state */ states[0].progs[0] = states[0].progs[1] = states[0].progs[2] = states[0].progs[3] = states[0].flash = 0; // everything is on near side /* * generate new states from initial state recursively */ next(); /* * display best solution */ printf("Programmer bridge solver done!\n"); printf("\nBEST SOLUTION\n"); dispall(bdepth, bstates); getchar(); return (0); } /* * Check if state duplicates previous in this path, return true if so. */ bool inline chkdup (void) { for (int s = 0; s < depth; s++) if (!memcmp(states[depth].progs, states[s].progs, sizeof(states[s].progs))) break; if (s < depth) { dupcnt++; return true; } return false; } /*-------------------------------------------------------------------------------- * * subroutine to make new states from current state * * Each possible transition consists of one or two programmers moving from where * they are to another position. The flashlight must illuminate all movement. */ void next (void) { time_t now; state *csp = states + depth, // current state pointer *nsp = states + depth + 1; // next state pointer statecnt++; /* * Report current state (if tracing or time elapsed) */ time(&now); if (now - disptime > 10) { disptime = now; printf("... %ld ... (sol=%ld dup=%ld subop=%ld / %ld)\n", statecnt, solcnt, dupcnt, subopcnt, subop2cnt); dispall(depth + 1, states); } if (trace) disp(depth + 1, csp); /* * Check if depth exceeded, abort if so */ if (depth == maxstates - 1) { if (trace) printf("MAX DEPTH\n"); maxdepcnt++; return; } /* * Check if best elapsed time already exceeded, abort if so */ if (beltime < csp->eltime || (beltime == csp->eltime && bdepth <= depth)) { if (trace) printf("NON OPTIMAL\n"); subopcnt++; return; } /* * Check if goal state reached - if so setup this sequence as "best" so far */ for (int p = 0; p < pcnt; p++) if (csp->progs[p] != dcnt - 1) break; if (p == pcnt) { for (int di = 0; di <= depth; di++) bstates[di] = states[di]; bdepth = depth + 1; beltime = states[depth].eltime; printf("SOLUTION\n"); dispall(bdepth, bstates); solcnt++; return; } /* * As a simple optimization, find slowest programmer / destination and * verify an optimal solution is still possible. */ float seltime = 0; // init residual time for (p = 0; p < pcnt; p++) // loop through programmers if ((1 - dists[csp->progs[p]]) * ptimes[p] > seltime) seltime = (1 - dists[csp->progs[p]]) * ptimes[p]; if (csp->eltime + seltime > beltime) { // abort if can't improve on best time if (trace) printf("NON OPTIMAL (%f6.3)\n", csp->eltime + seltime); subop2cnt++; return; } /* * Consider all possible two-programmer movements. One programmer movements * fall out of this logic as "both programmers are the same". */ depth++; // nest in one state for (int p1 = 0; p1 < pcnt; p1++) // loop through first programmer for (int d1 = 0; d1 < dcnt; d1++) { // loop through first's destinations if (d1 == csp->progs[p1]) // skip if no movement continue; // time for first's movement float t1 = dist(csp->progs[p1], d1) * ptimes[p1]; for (int p2 = 0; p2 <= p1; p2++) // loop through second programmer for (int d2 = 0; d2 < dcnt; d2++) { // loop through second's destinations if (d2 == csp->progs[p2]) // skip if no movement continue; if (p1 == p2 && d1 != d2) // if progs same, dests must be same continue; // time for second's movement float t2 = dist(csp->progs[p2], d2) * ptimes[p2]; // verify not more than two on bridge int bcnt = 2 - (p1 == p2); // number moving for (int p = 0; p < pcnt; p++) { // count number not moving if (p == p1 || p == p2) continue; if (csp->progs[p] > 0 && csp->progs[p] < dcnt - 1) bcnt++; } if (bcnt > 2) continue; // first programmer carries flashlight // verify second programmer is lit if (csp->flash == csp->progs[p1] && ((csp->progs[p1] < d1 && csp->progs[p2] >= csp->progs[p1]) || (csp->progs[p1] > d1 && csp->progs[p2] <= csp->progs[p2])) && dist(csp->flash, csp->progs[p2]) <= carry && dist(d1, d2) <= carry) { *nsp = *csp; nsp->progs[p1] = nsp->flash = d1; nsp->progs[p2] = d2; if (!chkdup()) { if (t1 > t2) nsp->eltime += t1; else nsp->eltime += t2; next(); } } // second programmer carries flashlight // verify first programmer is lit if (csp->flash == csp->progs[p2] && ((csp->progs[p2] < d2 && csp->progs[p1] >= csp->progs[p2]) || (csp->progs[p2] > d2 && csp->progs[p1] <= csp->progs[p2])) && dist(csp->flash, csp->progs[p1]) <= carry && dist(d2, d1) <= carry) { *nsp = *csp; nsp->progs[p1] = d1; nsp->progs[p2] = nsp->flash = d2; if (!chkdup()) { if (t1 > t2) nsp->eltime += t1; else nsp->eltime += t2; next(); } } // neither programmer carries flashlight // verify flashlight remains manned and // verify both programmers are lit for (p = 0; p < pcnt; p++) { if (p == p1 || p == p2) continue; if (csp->flash == csp->progs[p]) break; } if (p < pcnt && ((csp->progs[p1] <= csp->flash && d1 <= csp->flash && csp->progs[p2] <= csp->flash && d2 <= csp->flash) || (csp->progs[p1] >= csp->flash && d1 >= csp->flash && csp->progs[p2] >= csp->flash && d2 >= csp->flash)) && dist(csp->flash, csp->progs[p1]) <= carry && dist(csp->flash, d1) <= carry && dist(csp->flash, csp->progs[p2]) <= carry && dist(csp->flash, d2) <= carry) { *nsp = *csp; nsp->progs[p1] = d1; nsp->progs[p2] = d2; if (!chkdup()) { if (t1 > t2) nsp->eltime += t1; else nsp->eltime += t2; next(); } } } } depth--; // nest out one state if (trace) printf("\n"); } /* * display a state */ void disp (int depth, state* csp) { printf("%d / %6.3f -", depth, csp->eltime); for (int d = 0; d < dcnt; d++) { printf(" ("); for (int p = 0; p < pcnt; p++) if (csp->progs[p] == d) printf("%d", p); if (csp->flash == d) printf("*"); printf(")"); } printf("\n"); } /* * display current path */ void dispall (int depth, state* sp) { for (int s = 0; s < depth; s++) disp(s, sp + s); printf("\n"); }