Ed Markovich
```/*
*/

#include <stdio.h>
#include <string.h>

#define c2a(x) ( x-'A' )
#define a2c(x) ( 'A'+x )

#define MAX_DIM 26

char graph[MAX_DIM][MAX_DIM];

char order[8];
char best_order[8];
int order_len = 0;

int min_score = 99999;

const char* print_order(char *target) {

static char buf[30] = "";
char *x = buf;

for (int i=0; i<order_len; ++i) {
*x = a2c(*target++);
++x;
*x = ' ';
++x;
}

return buf;
}

// returns the biggest bandwidth for the current ordering. Since the objective is to find orderings
// with smallest bandwidth, if we detect an intermediate bandwidth that's large than the known min,
// stop evaluating this one , it can't be the winner.
int score2() {

// the biggest 'bandwidth' of this ordering so far.
int local_max = 0;

// I moves from the left, J moves from the right since this helps us find the 'biggest' connections
// first. we know that once distance between i and j is less than the previously discovered local_max,
// there's no point looking closer, hence j>i+local_max condition
for (int i=0; i< order_len; ++i) {
for (int j=order_len-1; j>i+local_max; --j) {

// We know I and J are more than 'local_max' appart - now check if the connection exists
if (graph[order[i]][order[j]]) {
local_max = j-i;

// We already know that this ordering is of at least local_max bandwidth. if that's larger
// than the best known min_score, it tells us this ordering is not a winner. So we just
// return the local max even though it may not be the biggest bandwidth for this ordering.
if (local_max > min_score) {
return local_max;
}
// Distance btw. I and J is getting narrower, we know we can't do better on this I
break;
}
}
}
return local_max;
}

// generate (almost) all the permutations of the nodes - ie all possible orderings.
void permute(int position) {
int i,j,x=0;

// If we're moving the left-most node around, don't bother moving it past the middle
// point, since all orderings like were already evalauted in the mirror image version.
int limit = position > 0 ? order_len : order_len/2 + 1;
bool last_one = position == order_len -1;

for (i=position ; i<limit; ++i) {

int tmp = order[i];
order[i] = order[position];
order[position] = tmp;

if (last_one) {
// Score this position....
int x = score2();

// If this is the best (least) score so far, or we've tied the best and are
// smaller alphabetically, treat the current result as the best
if (x < min_score ||
(x == min_score && memcmp(best_order, order, sizeof(order)) > 0 )) {
memcpy(best_order, order, sizeof(order));
min_score = x;
}

return;
} else {
permute(position+1);
}

order[position] = order[i];
order[i] = tmp;
}
}

// processes this input format A:FB;B:GC;D:GC;F:AGH;E:HD
// A:FB means A has edge to F and B. I call A the 'from'/node1 node and F and B are 'to'/node2 nodes
void parse_line(const char* line) {

#define add_node(node) if (!nodes_that_exist[node]) { \
nodes_that_exist[node] = 1;                   \
*x = node;                                    \
++x;                                        }

char *x = order; // used to create an initial order to permute

min_score = 999999;
memset(graph, 0, sizeof(graph)); // 26x26 matrix where graph[a][b] == 1 means there's an edge

// quick and dirty 'set' equivalent to make sure we don't add the same node into the ordering twice
char nodes_that_exist[MAX_DIM];
memset(nodes_that_exist, 0, sizeof(nodes_that_exist));

bool new_node = true;  // tells us that the next node is the 'from' node
int node1;             // the current 'from' node
while (*line != '\0') {

if (*line == ';') {
++line;
new_node = true;
}

if (new_node) {
new_node = false;
node1 = c2a(*line);
line +=2;
}

int node2 = c2a(*line);
graph[node1][node2] = graph[node2][node1] = 1;

++line;
}

order_len = x - order;
*x = -1;
}

int main() {
char val[100];

while (1) {
scanf("%s", val);
if (val[0] == '#') { return 0; }

parse_line(val);
permute(0);

printf("%s-> %d\n", print_order(best_order), min_score);
}

return 0;
}
```
page revision: 33, last edited: 05 Mar 2009 04:21