/*****************
dance3.c

Copyright July 2006 Wei-Hwa Huang

Swatches of code copyrighted by Donald Knuth; I stared
at his source code while typing this all out, and kept 
some of his variable names and stuff while reformatting it into
my coding style.  Sometimes (often, actually) subroutines
that I found opaque have been subdivided.

Version: 1.0

This is an enhancement of dance2.c that adds the ability to use
"negative" weights in a very special way, called "clone restriction."
The basic concept is this:

Nodes still are restricted to positive weight counts, but columns
can now have a negative weight, with the following meaning.

If a column has current weight -N-1, where N > 1, then it can
hold any number of nodes of weight N, but may not hold any
nodes of weight != N.  If a column has current weight -1, then
it can hold any number nodes of some identical weight.  (The first
weight chosen will change the column's weight to -N-1.)

Columns with negative weight necessarily have low priority.

Comments from dance2.c follow below
***************************************

Version: 2.0

(The main change for 2.0 is the addition of "minimum" requirements.)

This file isn't really C compliant, but only because I use
C++ style comments liberally.  Don had a heck of a lot of
"register" hints, which I've removed on the assumption that
the compiler is smarter than I am.

This is an implementation of an extension of Donald Knuth's
"Dancing Links" algorithm X.  The main innovation is that each node
is given a "weight"  W[n].   As a "matrix" node, the weight
represents the value in the matrix; as a "column" node, the
weight represents the maximal sum of the selected rows in
a given answer.

In Knuth's original algorithm X, the matrix only has 1s and 0s, and
the sum of the rows must be exactly 1.  With this extension, the
matrix has any weight_type value of weight, and the sum of the rows must
be exactly the weight specified.  This extension reduces to the
case of Knuth's algorithm DLX in the case where W[n] = 1 for all n.

A quick description of DLX is as follows:

0.  If the matrix is empty, we're done.  Print the "current working" solution.
1.  Choose a column, deterministically (usually the column that is
    most likely to get to a solution, such as the one with
    the fewest rows in it).
2.  Remove that column and all its rows from the matrix (so that events in
    3.2 don't affect it).
3.  For each row R that intersects the column:
3.1  "Select" row R in the "current working" solution, and adjust the matrix
     as necessary.
3.2  Recurse on what's left (go to step 0 with the existing matrix).
3.3  Revert the changes made in 2.1.

The matrix adjustment in step 3.1 bears some explanation;
since no solution has more than one element per column, adjusting
the matrix for an addition of row R goes something like:
3.1.0  For each column C that row R has an element in:
3.1.1  Look at all the rows that column C intersects with (except
   for row R). Remove all those rows from the matrix (because they
   cannot be in the solution, as we have already decided that row
   R is in the solution.

By adding weights, three main changes had to be made:

 * In step 3.1.1., the removal of rows is no longer guaranteed.
  Instead, each column keeps a tally of how much weight the "selected"
  rows account for, and a row is only removed when a selection
  renders a row impossible (such as, when adding the row would make
  the column exceed the weight).  For example:

  Suppose a column has weight 13.  In that column, there are
  rows A, B, C, D, E, which have weight 4, 10, 3, 8, 6 respectively.
  We "select" row A.  The column's "remaining weight" is decremented
  to 9.  Since Row B's weight is > 9 but <= 13, we remove row B
  from the matrix, but rows C, D, and E are still available to be
  selected.  Suppose later we "select" row C, decrementing the column
  from 9 to 6.  Then, Row D has weight > 6 but <= 9, so it is removed.

  When later we "deselect" row C, the weight goes up from 6 to 9, so
  row D comes back.. but row B, which has weight above 9, is not.

 * In step 3, we can't just do a linear iteration through all the rows,
  because more than one row may need to be selected to get the needed
  weight.  In fact, instead of a nice O(N) algorithm, we have a
  subset-sum situation.  Although the best-known solution is 
  Horowitz-Sahni's 1974 algorithm with complexity O(N 2^(N/2)), that
  would require too much overhead for small values of N (which hopefully
  is what we're dealing with due to our smart column selection process).
  So instead, we have a boring recursive O(2^N) algorithm -- select
  a row, recurse on what's left, deselect that row, recurse on what's
  left.  To make this algorithm a bit faster, when we insert nodes
  into a column, we use an insertion sort to ensure that the nodes
  appear in decreasing order (by weight).  (This makes the data
  structure very tangled, though.)

 * In step 2, the removal can't be done immediately, because it is
  possible for a selection of a row to invalidate (through a chain
  reaction) another row in that column.  Accordingly, the removal
  is postponed to step 3.1 (and rolled back in 3.3).

Knuth later added an enhancement that allowed for columns to be
"non-primary".  Non-primary columns would not necessarily need to
be satisfied.  One could think of this as meaning "the total weight
can be either 0 or 1", but this is actually misleading -- since if
a matrix had rows that only used non-primary columns, those would
never get added to the solution, even though they were legitimate
solutions.

In this version, you can specify non-primary columns as well, but
you can also specify "minimum weight" for the primary columns.
(The default value is "minimum weight" == weight.)
All solutions where that column sums to >= the minimum weight and
<= the weight will be calculated.  

Note that a primary column with minimum weight 0 is not quite the
same as a non-primary column -- it will give different results (if
there are solutions that include rows that only use non-primary
columns) and may (but not always) result in more computation.

You can make a node weight == 0, which will perform as expected
(it simply won't affect the total weight).

Other weird weights (negative, > total weight) will have weird
effects.  They might conceivably have some use.

*************************

We use a similar input format to Knuth's implementation, and
it is (mostly) backwards compatible.

The first line of input is of the form:

[n] [w] [m] [n] [w] [m] ... [n] [w] [m] | [n] [w] ... [n] [w]

[n] is a column name.  It may be up to COL_NAME_LENGTH-1 characters
long, but may *not* start with a digit.

[w] is a weight for that column.  It must be a number that fits in
weight_type (unsigned short by default).  If [w] is omitted, the
default weight of 1 is assumed.  If you attempt to have consecutive
terms starting with digits, the program will assume that the last
one is the actual weight, and the others will (effectively) be ignored.

[m] is a minimum weight for that column.  It should be a number that
is >= 0 but <= [w].  When the algorithm runs, it will make sure that
all combinations of that column that have a weight >= [m] and <= [w]
are tried.

The column names and weights after the | represent non-primary
columns.  These are similar to columns that have [m] == 0, except
that not all combinations will be tried -- the algorithm stops when
all primary columns are satisfied.  (Note that you cannot specify
a minimum weight for non-primary columns.)

The remaining lines represent the rows similarly:

[n] [w] [n] [w] ... [n] [w]

Again, the weight may be omitted (1 assumed).

Similar verbosity parameters as Knuth; prints number of solutions
and the total number of link updates, prints every nth solution
if the integer command line argument n is given, and has increased
verbosity for up to three more arguments.  The second verbose
parameter, if != 1, is treated as the maximum level that should
be printed.

The first command line argument can have special values:

If 0, then we don't bother maintaining the number of
solutions and number of updates (and don't print them, either).
This gives us a little bit extra efficiency (assuming you have
a compiler anywhere near decent) and makes it a bit
easier for external programs to use our output (assuming 
you didn't go for verbose > 1).

If negative (say -n), then we print n solutions and stop.
In addition, selection is random where possible (row node
insertion, column selection).  This
is not very useful for doing an exhaustive search, but is
rather convenient if, say, the solution space is reasonably
dense and you just want a sample of a few solutions.

*****************/

#define COL_NAME_LENGTH 8
#define MAX_LEVEL 1000
#define MAX_DEGREE 5000 
#define MAX_COLS 7000
#define MAX_NODES 100000
#define BUF_SIZE ((COL_NAME_LENGTH+4)*MAX_COLS+3)
#define DIE(m) {fprintf(stderr,"%s!\n%s",m,buf);exit(-1);}

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>  // for the RNG

typedef short weight_type;

typedef struct node_struct {
  struct node_struct *left;
  struct node_struct *right;
  struct node_struct *up;
  struct node_struct *down;
  weight_type weight;  // for matrix nodes, this will be a constant value.
                       // for column nodes, this will decrease as rows
                       // are selected.
  struct col_struct *col;
} node;

typedef struct col_struct {
  node head;
  int sel;  // number of selected nodes in column.
  int len;  // number of (visible) nodes in column.  Used for optimizing.
  int tot_weight;  // total weight of all remaining
                   // nodes in column.  Used for optimizing.
  weight_type wsb;  // short for "weight satisfaction boundary".
                    // as the weight decreases, the column is only satisfied
                    // if the weight is <= wsb.  Another way to think
                    // of this is that the minimum sum of this column
                    // in any solution is initial weight value - wsb.
  char name[COL_NAME_LENGTH];
  struct col_struct *prev;
  struct col_struct *next;
} column;

short verbose;      // 1, 2, 3, 4, etc.  Bigger means more debug data.
short ver_level;    // Level to print when verbose > 1
short spacing = 1;  // print out each nth solution, where this is n.
int randomness = -1;
  // if -1, behave normally.  Otherwise, create randomness as necessary
  //   (in terms of ties and the like)
  // if 0, terminate.                    
  // if n, print out n solutions, then terminate.

unsigned int updates;
unsigned int upd_prof[MAX_LEVEL]; // updates in that level.
int profile[MAX_LEVEL][MAX_DEGREE];
int max_branches_seen = 0;
short max_level_seen = 0;

char buf[BUF_SIZE];  // generic buffer for I/O.

column col_array[MAX_COLS + 2];
node node_array[MAX_NODES];
column* root = col_array;
column* fnp_col; // First non-primary column.  This doesn't
                 // have to be an actual column; we're using it
                 // for comparison purposes.
column* end_col; // position of first column space that doesn't
                 // have valid data.
node* end_node; // position of first node that doesn't
                // have valid data.

node* choice[MAX_LEVEL];  // Which node we chose going down.

int solution_count = 0;

//////////////////////////////

// Debugging routines that print out information about the current state.

// Prints a row.

void print_row(node* row_start) {
  node* cur_node = row_start;
  int row_num;

  printf("%s", cur_node->col->name);
  printf(" %d", cur_node->weight);
  cur_node = cur_node->right;
  while (cur_node != row_start) {
    printf(" %s", cur_node->col->name);
    printf(" %d", cur_node->weight);
    cur_node = cur_node->right;
  }

  printf("\n");
}

short curlevel() {
  int i;
  for (i=0; i<MAX_LEVEL; ++i) {
    if (choice[i] == NULL) return i;
  }
  return MAX_LEVEL;
}

int get_index(node* n) {
  int i;
  for (i=0; i<MAX_COLS; ++i) {
    if (n == &(col_array[i].head)) return 100 * i;
  }
  for (i=0; i<MAX_NODES; ++i) {
    if (n == &(node_array[i])) return i;
  }
  return -1;
}

void print_node_data(node *n) {
  printf("%d %d | %d %d %d %d\n",
   n->weight,
   get_index(n),
   get_index(n->left),
   get_index(n->right),
   get_index(n->up),
   get_index(n->down));
}

void print_col_data(column *c) {
  printf("%s %d %d | %d %d %d %d\n",
   c->name, c->head.weight, get_index(&(c->head)),
   get_index(&(c->prev->head)),
   get_index(&(c->next->head)),
   get_index(c->head.up),
   get_index(c->head.down));
}

void print_stack() {
  int i;
  printf("(stack: ");
  for (i=0; i<MAX_LEVEL; i++) {
    if (choice[i] == NULL) break;
    printf("%d ", get_index(choice[i]));
  }
  printf(")\n");
}

int col_size(column* c) {
  int answer = 0;
  node* n = c->head.down;
  while (n != &(c->head)) {
    answer++;
    n = n->down;
  }
  return answer;
}

void debug_data() {
  if (verbose <= 4) return;
  print_stack();
  int i;
  for (i=0; col_array + i < end_col; i++) {
    print_col_data(&(col_array[i]));
  }
  printf("---\n");
  for (i=0; node_array + i < end_node; i++) {
    print_node_data(node_array+i);
  }
  printf("-------\n");
}

/////////////////////////////////////////////

int rand_int(int max_val_plus_one) {
  return (int)(1.0 * (max_val_plus_one) * rand() / (RAND_MAX + 1.0));
}

void attach_vertical(node* upper, node* lower) {
  upper->down = lower;
  lower->up = upper;
}

void attach_horizontal(node* sinister, node* dexter) {
  sinister->right = dexter;
  dexter->left = sinister;
}

void attach_column(column* former, column* latter) {
  former->next = latter;
  latter->prev = former;
}

/////////////////////////////////////////////

// Disappears a node.  A node "disappears" by making
// it be "invisible" to the column it is in (but
// the row is still aware of its presence).
void disappear(node* n) {
  n->up->down = n->down;
  n->down->up = n->up;
  if (spacing != 0) {
    updates++;
    upd_prof[curlevel()]++;
  }
  n->col->len--;
  if (verbose > 4) {
    printf("   Disappearing %d %s collen now %d colsize now %d\n",
     get_index(n), n->col->name, n->col->len, col_size(n->col));
    assert(col_size(n->col) == n->col->len);
  }
}

// Reappears a node.
void reappear(node* n) {
  if (verbose > 4)
    printf("   Reappearing %d\n", get_index(n));
  n->col->len++;
  n->up->down = n;
  n->down->up = n;
}

// Ignores a row.  A row is "ignored" by making all of
// the nodes in that row disappear, with the exception of
// the node passed into this function, so that we won't
// lose them of course :-) .
void ignore(node* n) {
  if (verbose > 3) {
    printf("  Ignoring %d %s : ", get_index(n), n->col->name);
    print_row(n);
  }
  node* it;
  n->col->len--;
  for (it = n->right; it != n; it = it->right) {
    disappear(it);
  }
}

// Unignores a row.
void unignore(node* n) {
  if (verbose > 3)
    printf("  UnIgnoring %d\n", get_index(n));
  node* it;
  // Okay, it doesn't *really* make a difference if we
  // go left or right, but in case a future version of
  // this program has side effects, we might as well
  // go in the opposite direction we ignored things in.
  for (it = n->left; it != n; it = it->left) {
    reappear(it);
  }
  n->col->len++;
}

// Given a column weight, and a node weight, either
// the node can be selected for a solution
// or it shouldn't.
bool can_be_selected(int column_weight, int node_weight) {
  if (column_weight >= 0) {
    return (node_weight <= column_weight);
  } else if (column_weight == -1) {
    return true;
  } else {
    return (node_weight + column_weight == -1);
  }
}

// Ignores with a check.
// Ignore rows that haven't been ignored already.
void ignore_if_safe(node* n) {
  if (can_be_selected(n->col->head.weight, n->weight)) {
    ignore(n);
  }
}

// Unignores a row.
void unignore_if_safe(node* n) {
  if (can_be_selected(n->col->head.weight, n->weight)) {
    unignore(n);
  } 
}

// We're about to (but haven't yet) add a row that will remove weight
// from this column.  All lower "safe" rows that previously
// "shouldn't be ignored" but now "should be ignored" should be ignored.
//
// "thnbisbsb" stands for "that have not been ignored but should be".
void ignore_lower_rows_thnbibsb(node* n, int weight) {
  node* temp = n->down;
  while (temp != &(n->col->head)) {
    if (!can_be_selected(temp->col->head.weight - weight, temp->weight)) {
      ignore_if_safe(temp); 
    } else if (temp->col->head.weight >= 0) {
      // if the column weight is positive, and we've gotten past all
      // the nodes that should be ignored, there's no reason to
      // continue further down because the nodes are sorted in decreasing
      // weight.
      break;
    }
    temp = temp->down;
  }
}

// Inverse of above.
void unignore_lower_rows_thnbibsb(node* n, int weight) {
  node* temp = n->down;
  while (temp != &(n->col->head)) {
    if ((temp->col->head.weight >= 0)
       && can_be_selected(temp->col->head.weight - weight, temp->weight)) {
      break;
    }
    temp = temp->down;
  }
  while (temp != n->down) {
    temp = temp->up;
    if (!can_be_selected(temp->col->head.weight - weight, temp->weight)) {
      unignore_if_safe(temp); 
    }
  }
}

// Hides a column.  A column is hidden by making the col node
// invisible from the sides.
void hide(column* c) {
  c->prev->next = c->next;
  c->next->prev = c->prev;
}

// Unhides a column.
void unhide(column* c) {
  c->next->prev = c;
  c->prev->next = c;
}

// Covers a column.  A column is covered by hiding it and making all the
// rows that it has be ignored.
void cover(column* c) {
  node* row_start;

  if (verbose > 3) printf(" Covering %d %s\n", get_index(&(c->head)), c->name);

  hide(c);

  for (row_start = c->head.down; row_start != &(c->head);
       row_start = row_start->down) {
    ignore_if_safe(row_start);
  }

  if (verbose > 3) printf(" END Covering %d\n", get_index(&(c->head)));
}

// Uncovers a column.
void uncover(column* c) {
  node* row_start;
  if (verbose > 3) printf(" UnCovering %d\n", get_index(&(c->head)));

  // See comment in unignore() above for up vs. down rationale.
  for (row_start = c->head.up; row_start != &(c->head);
       row_start = row_start->up) {
    unignore_if_safe(row_start);
  }

  unhide(c);
}

// Reduces weight of a node from the column.
void reduce(node* n) {
  n->col->sel ++;
  if (n->col->head.weight >= -1) {
    n->col->head.weight -= n->weight;
    n->col->tot_weight -= n->weight;
    if (verbose > 3) {
      printf("%d  %s weight reduced to %d from %d\n", 
        curlevel(), n->col->name, n->col->head.weight,
        n->col->head.weight + n->weight);
      debug_data();
    }
  } else {
    if (verbose > 3) {
      printf("%d  %s weight reduced to %d from %d\n", 
        curlevel(), n->col->name, n->col->head.weight,
        n->col->head.weight);
      debug_data();
    }
  } 
}

// opposite of reduce.
void unreduce(node* n) {
  n->col->sel --;
  if (n->col->head.weight >= 0 || n->col->sel == 0) {
    n->col->tot_weight += n->weight;
    n->col->head.weight += n->weight;
    if (verbose > 3) {
      printf("%d  %s weight restored to %d from %d\n", 
        curlevel(), n->col->name, n->col->head.weight,
        n->col->head.weight - n->weight);
      debug_data();
    }
  } else {
    if (verbose > 3) {
      printf("%d  %s weight restored to %d from %d\n", 
        curlevel(), n->col->name, n->col->head.weight,
        n->col->head.weight);
      debug_data();
    }
  }
}

// Decrements a column.
// In the original algorithm, when a row was selected, we just
// removed any column that intersected that row.  Now we don't
// have that luxury because those columns may still need to
// stick around.  So, we cover those that have used up
// all the weight, and just ignore those rows that have passed
// our threshhold.
void decrement(node* n) {
  node* temp;

  if (verbose > 3) {
    printf("%d  %s weight about to be reduced\n", 
           curlevel(), n->col->name);
  }

  if (n->col->head.weight == n->weight) {
    cover(n->col);
  } else {
    for (temp = n->col->head.down; temp != &(n->col->head);
         temp = temp->down) {
      if (!can_be_selected(
           (n->col->head.weight >= -1)
             ? (n->col->head.weight - n->weight)
             : (n->col->head.weight),
           temp->weight))
        ignore_if_safe(temp);
    }
  }
  
  reduce(n);
}

// Undoes a decrement.
void increment(node* n) {
  node* temp;

  unreduce(n);

  if (n->col->head.weight == n->weight) {
    uncover(n->col);
  } else {
    for (temp = n->col->head.up; temp != &(n->col->head);
         temp = temp->up) {
      if (!can_be_selected(
           (n->col->head.weight >= -1)
             ? (n->col->head.weight - n->weight)
             : (n->col->head.weight),
           temp->weight))
        unignore_if_safe(temp);
    }
  }
}

// decrements an entire row, with the exception of the node being
// passed into this function.  For that node, only the weight
// of the column is decremented.
void decrement_row(node* n) {
  node* temp;

  if (verbose > 1) {
    if (curlevel() <= ver_level) {
      printf("Lv%d: ", curlevel());
      print_row(n);
    }
  }
  if (verbose > 3) {
    printf("%d adding_row %d\n", curlevel(), get_index(n)); debug_data();
  }

  reduce(n);

  for (temp = n->right; temp != n; temp = temp->right) {
    decrement(temp);
  }
}

// undoes a decrement_row.
void increment_row(node* n) {
  node* temp;
  if (verbose > 3) {
    printf("%d removing_row %d\n", curlevel(), get_index(n)); debug_data();
  }

  for (temp = n->left; temp != n; temp = temp->left) {
    increment(temp);
  }

  unreduce(n);
}

///////////////////////////////////////
///  I/O Utilities.

char* next_nonspace(char* c) {
  while (isspace(*c)) c++;
  return c;
}

void check_name_length(char* c) {
  short length = 0;
  while (!isspace(*c)) {
    c++;
    length++;
  }
  if (length > COL_NAME_LENGTH - 1) DIE("Column name too long");
}

void write_name(char** c_from, char* c_to) {
  check_name_length(*c_from);
  while(!isspace(**c_from)) {
    *c_to = **c_from;
    c_to++;
    (*c_from)++;
  }
  *c_to = '\0';
}

int get_number(char** c_from) {
  int answer = 0;
  while(!isspace(**c_from)) {
    if (!isdigit(**c_from)) DIE("Identifier starts with digit");
    answer *= 10;
    answer += (int)((**c_from) - '0');
    (*c_from)++;
  }
  return answer;
}

////////////////////////////////////////

// gets the column data.
void get_columns(int argc, char* argv[]) {
  column* cur_col;
  char* p;
  bool rwa = false;  // short for "read weight already"

  // initialize root.
  attach_vertical(&root->head, &root->head);
  attach_horizontal(&root->head, &root->head);
  root->head.col = root;
  root->head.weight = 0;

  verbose = argc-1;
  if (verbose) {
    sscanf(argv[1], "%d", &spacing);
    if (spacing < 0) {
      randomness = -spacing;
      spacing = 0;
      srand(time(NULL));
    }
    if (verbose > 1) {
      sscanf(argv[2], "%d", &ver_level);
      if (ver_level < 2) ver_level == MAX_LEVEL;
    }
  }

  cur_col = &col_array[0];
  fgets(buf, BUF_SIZE, stdin);
  if (buf[strlen(buf)-1]!='\n') DIE("Input line too long!");

  fnp_col = &(col_array[MAX_COLS]);

  bool next_neg = false;

  for (p = buf; *p != 0; p++) {
    if (cur_col >= &col_array[MAX_COLS]) DIE("Too many columns");
    p = next_nonspace(p);
    if (*p == 0 || p == NULL) break;
    if (*p == '|') {
      fnp_col = cur_col+1;
      // wrap-up the end
      attach_column(cur_col, root);
      p++;
    }
    if (*p == '-') {
      next_neg = true;
    }
    p = next_nonspace(p);
    if (*p == 0 || p == NULL) break;
    if (isdigit(*p)) {
      if (rwa) {
        int min_val = get_number(&p);
        cur_col->wsb = cur_col->head.weight - min_val;
      } else {
        cur_col->head.weight = get_number(&p);
        cur_col->wsb = (cur_col < fnp_col) ? 0 : cur_col->head.weight;
        if (next_neg) cur_col->head.weight = -(cur_col->head.weight);
        cur_col->sel = 0;
        rwa = true;
      }
    } else if (*p == '-') {
      next_neg = true;
    } else {
      cur_col++;
      rwa = false;
      write_name(&p, cur_col->name);
      attach_vertical(&cur_col->head, &cur_col->head);
      attach_horizontal(&cur_col->head, &cur_col->head);
      if (cur_col >= fnp_col)
        attach_column(cur_col, cur_col);
      else
        attach_column(cur_col-1, cur_col);
      cur_col->len = 0;
      cur_col->head.col = cur_col;
      cur_col->head.weight = 1;  // assume 1 unless told otherwise.
      cur_col->wsb = (cur_col < fnp_col) ? 0 : 1;
      cur_col->sel = 0;
      next_neg = false;
    }
  }
  attach_column(cur_col, root);

  end_col = cur_col+1;
  if (verbose > 3) printf("Columns read.\n");
}

// inserts the node into the correct position in
// its column, which is done so that the weights
// are in decreasing order.
void insert_into_column(node* n) {
  if (n == node_array - 1) return;
  column* c = n->col;
  node* ibm = c->head.down;  // short for "insert before me"  
  while ((ibm != &(c->head)) && (ibm->weight > n->weight)) {
    ibm = ibm->down;
  }
  if (randomness >= 0) {
    node* it = ibm;  // short for "iterator"
    int nswsw = 1;  // short for "nodes seen with same weight"
    while ((it != &(c->head)) && (it->weight == n->weight)) {
      it = it->down;
      nswsw++;
      if (rand_int(nswsw) == 0)
        ibm = it;
    }
  }
  attach_vertical(ibm->up, n);
  attach_vertical(n, ibm);
  c->len++; 
  c->tot_weight += n->weight;
}

// finds the column with the given name.
column* find_col(char* name) {
  column* c = col_array;
  while (c != end_col && strcmp(c->name, name)) c++;
  if (c == end_col) {
    printf("'%s'", name);
    DIE(" is unknown column name");
  }
  return c;
}

// gets the rows.
void get_rows() {
  node* cur_node = node_array - 1;
  char* p;
  int steps;
  bool fits = true;
  char temp[COL_NAME_LENGTH];
  
  while (fgets(buf, BUF_SIZE, stdin)) {
    node* row_start = NULL;
    fits = true;
    if (buf[strlen(buf)-1]!='\n') DIE("Input line too long");
    for (p = buf; *p != 0; p++) {
      p = next_nonspace(p);
      if (*p == 0 || p == NULL) break;

      if (isdigit(*p)) {
        cur_node->weight = get_number(&p);
        if ((cur_node->col->head.weight >= 0)
             && (cur_node->weight > cur_node->col->head.weight)) {
          fits = false;
        }
      } else {
        cur_node++;
        write_name(&p, temp);
        cur_node->col = find_col(temp);
        if (cur_node >= &node_array[MAX_NODES]) DIE("Too many nodes");
  
        if (row_start == NULL) {
          row_start = cur_node;
        } else {
          attach_horizontal(cur_node-1, cur_node);
        }
        cur_node->weight = 1;
        if (cur_node->col->head.weight == 0) {
          fits = false;
        }
      }
    }
    if (row_start == NULL) DIE("Empty row");
    attach_horizontal(cur_node, row_start);

    if (fits) {
      node* temp = row_start;
      do {
        insert_into_column(temp);
        temp = temp->right;
      } while (temp != row_start);
    } else {
      if (verbose > 1) {
        printf("Warning: row weight too high, not inserted: ");
        print_row(row_start);
      }
    }
  } 
  end_node = cur_node+1;

  if (verbose > 3) printf("Rows read.\n");
}

// returns 1 if newguy is clearly better than baseline, as
// far as choosing which column to do next is concerned.
// In the original Knuth, this was easy -- whichever had
// fewer items was the best candidate.  In this version,
// we optimize a bit more by the weights -- whichever has
// a higher ratio of total_weight to weight is best.
//
// With the addition of negative weights, this is just messy
// and more optimization could probably be used.

short better(column* newguy, column* baseline) {
  if (newguy->len < baseline->len) return 1;
  if (newguy->len > baseline->len) return 0;
  if (newguy->head.weight <= -1
      && baseline->head.weight >= 0)
    return 0;
  if (newguy->head.weight >= 0
      && baseline->head.weight <= -1)
    return 1;
  if (baseline->head.weight <= -1
      && newguy->head.weight < baseline->head.weight)
    return 1;
  if (newguy->head.weight <= -1
      && newguy->head.weight > baseline->head.weight)
    return 0;
  if (newguy->tot_weight * baseline->head.weight
    > baseline->tot_weight * newguy->head.weight)
    return 1;
  return 0;
}


// finds the best column to do next.
column* find_best_col() {
  column* temp;
  column* answer = root->next;
  short ties = 0;
  for (temp = answer->next; temp != root; temp = temp->next) {

    if (verbose > 2)
      printf(" %s(%d,%d)", temp->name, temp->len, temp->tot_weight);

    if (better(temp, answer)) {
      answer = temp;
      ties = 1;
    } else if (randomness >= 0) {
      if (better(answer, temp)) {
        // yeah, clearly better, don't do anything
      } else {
        // temp is just as good.  Maybe we should select it.
        ties++;
        if (rand_int(ties+1) == 0) {
          answer = temp;
        }
      }
    }
  }
  return answer;
}

// chooses a column and covers it, returning its column node.
node* select_new_column() {
  column* chosen = find_best_col();

  if (verbose > 0) {
    int minlen = chosen->len;
    if (minlen > max_branches_seen) {
      if (minlen > MAX_DEGREE) DIE("Too many branches");
      max_branches_seen = minlen;
    }
    profile[curlevel()][minlen]++;
    if (verbose > 2)
      printf(" branching on %s(%d)\n", chosen->name, minlen);
  }

  if (verbose > 3) {
    printf("%d Colselect %s %d\n", curlevel(),
        chosen->name, get_index(&chosen->head)); debug_data();
  }

  return &chosen->head;
}

void add_row_to_solution(int level, node* n) {
  choice[level] = n;
  decrement_row(n);
}

void remove_row_from_solution(int level, node* n) {
  increment_row(n);
  choice[level] = NULL; 
}

// returns 1 if the node can be selected (weight fits in column).
bool node_fits_in_column(node* n) {
  return can_be_selected(n->col->head.weight, n->weight);
}

// returns 1 if the row can be selected (all weights fit in column).
bool row_fits_in_column(node* n) {
  node* temp = n;
  do {
    if (!node_fits_in_column(temp)) return false;
    temp = temp->right;
  } while (temp != n);
  return true;
}

// returns 1 if the column isn't happy.
// In other words, we haven't removed enough rows to hit the wsb.
// Note that a column with negative weight is always satisfied, because
// the wsb is artificially positive.
bool column_satisfied(node* n) {
  if (n->col >= fnp_col) return true;
  if (n->col->head.weight <= n->col->wsb) return true;
  return false;
}

// returns 1 if we've tried all rows for the current column.
bool all_rows_done(node* n) {
  return (n == &(n->col->head));
}

// returns 1 if we're at a solution (the matrix is reduced to nothing).
bool solution_found() {
  return (root->next == root);
}

// does what's necessary when a solution is found.
void handle_solution() {
  int i;
  solution_count++;
  if (verbose > 0) {
    profile[curlevel()+1][0]++;
    if (spacing == 0 || solution_count % spacing == 0) {
      if (spacing != 0) printf("%d:", solution_count);
      printf("\n");
      for (i = 0; choice[i] != NULL; i++) print_row(choice[i]);
    }
  }
  if ((randomness >= 0) && (solution_count >= randomness)) {
    exit(0);  // not graceful, but what the hell.
  }
}

// returns 1 if there is enough weight left for further selection
// to be meaningful
bool enough_weight(int weight_needed, int terms_left,
                   int max_weight_per_term) {
  if (verbose > 3) {
    printf(" %d terms left at max %d per for %d total weight\n",
           terms_left, max_weight_per_term, weight_needed);
  }
  return (terms_left * max_weight_per_term >= weight_needed);
}

//////////////////////////////////////////////////

// the actual algorithm.

void execute_algorithm(int mylevel, node* n) {
  if (mylevel > MAX_LEVEL) DIE("Too many levels deep");
  if (verbose > 0) {
    if (mylevel > max_level_seen) {
      max_level_seen = mylevel;
    }
    if (verbose > 3) {
      printf("%d execute %d\n", mylevel, get_index(n));
    }
  }

  if (all_rows_done(n)) {
    if (!column_satisfied(n)) {
      if (verbose > 1) {
        if (curlevel() <= ver_level) {
          printf("Lu%d: ", curlevel());
          print_col_data(n->col);
        }
      }
      return;
    }

    if (solution_found()) {
      handle_solution();
    } else {

      node* chosen = select_new_column();
      // hide the column so that we don't get selected again.
      hide(chosen->col);
      execute_algorithm(mylevel, chosen->down);
      unhide(chosen->col);
    }
  
    return;

  } else if (!node_fits_in_column(n)) {

    // this row is already ignored; must skip it.

    if (verbose > 3) {
      printf("%d row already ignored, skipping %d\n", curlevel(), get_index(n));
      debug_data();
    }
    execute_algorithm(mylevel, n->down);
    if (verbose > 3) {
      printf("%d row popback, skipping %d\n", curlevel(), get_index(n));
      debug_data();
    }
    

  } else if (n->col->head.weight < 0 ||
             enough_weight(n->col->head.weight - n->col->wsb,
                           n->col->len,
                           n->weight)) {

    // rows are not all done, so consider adding the current row.

    ignore(n);

    if (node_fits_in_column(n)) {
      ignore_lower_rows_thnbibsb(n, n->weight);
      add_row_to_solution(mylevel, n);
      execute_algorithm(mylevel+1, n->down);
      remove_row_from_solution(mylevel, n);
      unignore_lower_rows_thnbibsb(n, n->weight);
    }

    // And what happens if we don't add the current row?

    if (verbose > 3) {
      printf("%d not adding_row %d\n", curlevel(), get_index(n)); debug_data();
    }
    execute_algorithm(mylevel, n->down);
    if (verbose > 3) {
      printf("%d done not adding_row %d\n", curlevel(), get_index(n));
      debug_data();
    }

    unignore(n);


  }
}

  
void show_final_stats() {
  column* temp;
  int lv, width, level_sum, grand_count;

  if (verbose > 3) {
    printf("Final column stats");
    for (temp = root->next; temp != root; temp = temp->next) {
      printf(" %s(%d,%d)", temp->name, temp->len, temp->tot_weight);
    }
    printf("\n");
  }

  printf("Altogether %d solutions, after %u updates.\n",
         solution_count, updates);

  if (verbose > 0) {
    grand_count = 0;
    for (lv = 1; lv < max_level_seen+1; lv++) {
      level_sum = 0;
      for (width = 0; width <= max_branches_seen; width++) {
        printf("%6d", profile[lv][width]);
        level_sum += profile[lv][width]; 
      }
      printf("%8d nodes, %u updates\n", level_sum, upd_prof[lv-1]);
      grand_count += level_sum;
    }
    printf("Total %d nodes.\n", grand_count);
  }
}

////////////////////////////////

// Main program (duh)
int main(int argc, char* argv[]) {
  int i; 
  for (i=0; i<MAX_LEVEL; ++i) {
    choice[i] = NULL;
  }

  get_columns(argc, argv);
  get_rows();
  if (verbose > 3) debug_data();
  execute_algorithm(0, &(root->head));
  if (spacing != 0) {
    show_final_stats(); 
  }
  exit(0);
}