/*****************
dance2-fast.c

Copyright July 2006 Wei-Hwa Huang

Same as dance2, but all debug messages have been removed.
Hopefully this runs faster.

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

#define COL_NAME_LENGTH 7
#define MAX_LEVEL 1000
#define MAX_DEGREE 200 
#define MAX_COLS 2000
#define MAX_NODES 20000
#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 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 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.

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 num_rows_in_solution = 0;

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);
  cur_node = cur_node->right;
  while (cur_node != row_start) {
    printf(" %s", cur_node->col->name);
    cur_node = cur_node->right;
  }

  // which row is this?
  row_num = 1;
  for (cur_node = row_start->col->head.down; 
       cur_node != row_start; cur_node = cur_node->down) {
    if (cur_node == &(row_start->col->head)) {
      // we've come in a cycle; this isn't one of the rows with a number.
      printf("\n"); return;
    }
    row_num++;
  }

  if (spacing != 0) {
    printf(" (%d of %d)", row_num, row_start->col->len);
  }
  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;
  n->col->len--;
}

// Reappears a node.
void reappear(node* 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) {
  node* it;
  for (it = n->right; it != n; it = it->right) {
    disappear(it);
  }
}

// Unignores a row.
void unignore(node* 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);
  }
}

// Ignores with a check.
// For most cases, a row should not be ignored if that node's
// weight is higher than the column's remaining weight
// because (presumably) it has been ignored alredy.
void ignore_if_safe(node* n) {
  if (n->weight > n->col->head.weight) return;
  ignore(n);
}

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

// 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;

  hide(c);

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

// Uncovers a column.
void uncover(column* c) {
  node* row_start;
  // 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);
}

// 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 (n->col->head.weight == n->weight) {
    cover(n->col);
  } else {
    for (temp = n->col->head.down; temp != &(n->col->head);
         temp = temp->down) {
      if (temp->weight > n->col->head.weight - n->weight) 
        ignore_if_safe(temp);
    }
  }

  n->col->head.weight -= n->weight;
  n->col->tot_weight -= n->weight;
}

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

  n->col->tot_weight += n->weight;
  n->col->head.weight += n->weight;

  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 (temp->weight > n->col->head.weight - n->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;

  n->col->head.weight -= n->weight;

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

// undoes a decrement_row.
void increment_row(node* n) {
  node* temp;
  for (temp = n->left; temp != n; temp = temp->left) {
    increment(temp);
  }
  n->col->head.weight += n->weight;
}

///////////////////////////////////////
///  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));
    }
  }

  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]);

  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++;
    }
    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 (cur_col->head.weight == 0) DIE("Weight is zero");
        rwa = 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;
    }
  }
  attach_column(cur_col, root);

  end_col = cur_col+1;
}

// 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"  
  if (randomness >= 0) {
    while ((ibm != &(c->head)) && (ibm->weight > n->weight)) {
      ibm = ibm->down;
    }
    node* it = ibm;  // short for "iterator"
    int nswsw = 0;  // short for "nodes seen with same weight"
    while ((it != &(c->head)) && (it->weight == n->weight)) {
      nswsw++;
      it = it->down;
      if (rand_int(nswsw+1) == 0) ibm = it;
    }
  } else {
    while ((ibm != &(c->head)) && (ibm->weight >= n->weight)) {
      ibm = ibm->down;
    }
  }
  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;
  char temp[COL_NAME_LENGTH];
  
  while (fgets(buf, BUF_SIZE, stdin)) {
    column* cur_col;
    node* row_start = NULL;
    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);
      } else {
        insert_into_column(cur_node);
        cur_node++;
        write_name(&p, temp);
        cur_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->col = cur_col;
        cur_node->weight = 1;
      }
    }
    if (row_start == NULL) DIE("Empty row");
    attach_horizontal(cur_node, row_start);
  } 
  insert_into_column(cur_node);

  end_node = cur_node+1;
}

// 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.

short better(column* newguy, column* baseline) {
  if (newguy->len < baseline->len) return 1;
  if (newguy->len > baseline->len) 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();
  return &chosen->head;
}

void add_row_to_solution(node* n) {
  choice[num_rows_in_solution] = n;
  decrement_row(n);
}

void remove_row_from_solution(node* n) {
  increment_row(n);
}

// returns 1 if the node can be selected (weight fits in column).
bool node_fits_in_column(node* n) {
  return (n->weight <= n->col->head.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.
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) {
    if (spacing == 0 || solution_count % spacing == 0) {
      if (spacing != 0) printf("%d:", solution_count);
      printf("\n");
      for (i = 0; i < num_rows_in_solution; 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) {
  return (terms_left * max_weight_per_term >= weight_needed);
}

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

// the actual algorithm.


void execute_algorithm(node* n) {
  if (num_rows_in_solution > MAX_LEVEL) DIE("Too many levels deep");

  if (all_rows_done(n)) {
    if (!column_satisfied(n)) 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(chosen->down);
      unhide(chosen->col);
    }
  
    return;

  } else if (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)) {
      add_row_to_solution(n);
      num_rows_in_solution++;
      execute_algorithm(n->down);
      num_rows_in_solution--;
      remove_row_from_solution(n);
    }

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

    execute_algorithm(n->down);

    unignore(n);


  }
}

void show_final_stats() {
  printf("Altogether %d solutions.\n", solution_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();
  execute_algorithm(&(root->head));
  if (spacing != 0) {
    show_final_stats(); 
  }
  exit(0);
}