[matchsticks-search.git] / main.c

/*
 * Searches for "good" ways to divide n matchsticks up and reassemble them
 * into m matchsticks.  "Good" means the smallest fragment is as big
 * as possible.
 *
 * Invoke as   ./main n m
 *
 * The arguments must be ordered so that n > m:
 *   n is the number of (more, shorter) input matches of length m
 *   m is the number of (fewer, longer) output matches of length n
 *
 * Options:
 *  -j<jobs>     run in parallel on <jobs> cores
 */

/*
 * matchsticks/main.c  Copyright 2014 Ian Jackson
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 */

#define _GNU_SOURCE

#include <publib.h>

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <unistd.h>
#include <stdbool.h>
#include <inttypes.h>
#include <math.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <sys/uio.h>
#include <sys/fcntl.h>

#include <glpk.h>

#ifndef VERSION
#define VERSION "(unknown-version)"
#endif

/*
 * Algorithm.
 *
 * Each input match contributes, or does not contribute, to each
 * output match; we do not need to consider multiple fragments
 * relating to the same input/output pair this gives an n*m adjacency
 * matrix (bitmap).  Given such an adjacency matrix, the problem of
 * finding the best sizes for the fragments can be expressed as a
 * linear programming problem.
 *
 * We search all possible adjacency matrices, and for each one we run
 * GLPK's simplex solver.  We represent the adjacency matrix as an
 * array of bitmaps: one word per input stick, with one bit per output
 * stick.
 *
 * However, there are a couple of wrinkles:
 *
 * To best represent the problem as a standard LP problem, we separate
 * out the size of each fragment into a common minimum size variable,
 * plus a fragment-specific extra size variable.  This reduces the LP
 * problem size at the cost of making the problem construction, and
 * interpretation of the results, a bit fiddly.
 *
 * Many of the adjacency matrices are equivalent.  In particular,
 * permutations of the columns, or of the rows, do not change the
 * meaning.  It is only necessasry to consider any one permutation.
 * We make use of this by considering only adjacency matrices whose
 * bitmap array contains bitmap words whose numerical values are
 * nondecreasing in array order.
 *
 * Once we have a solution, we also avoid considering any candidate
 * which involves dividing one of the input sticks into so many
 * fragment that the smallest fragment would necessarily be no bigger
 * than our best solution.  That is, we reject candidates where any of
 * the hamming weights of the adjacency bitmap words are too large.
 *
 * We further winnow the set of possible adjacency matrices, by
 * ensuring the same bit is not set in too many entries of adjmatrix
 * (ie, as above, only considering output sticks); and by ensuring
 * that it is not set in too few: each output stick must consist
 * of at least two fragments since the output sticks are longer than
 * the input ones.
 *
 * And, we want to do the search in order of increasing maximum
 * hamming weight.  This is because in practice optimal solutions tend
 * to have low hamming weight, and having found a reasonable solution
 * early allows us to eliminate a lot of candidates without doing the
 * full LP.
 */

typedef uint32_t AdjWord;
#define PRADJ "08"PRIx32

#define FOR_BITS(j,m) for (j=0, j##bit=1; j < (m); j++, j##bit<<=1)

static int n, m, maxhamweight;
static AdjWord *adjmatrix;
static AdjWord adjall;

static double best;
static glp_prob *best_prob;
static AdjWord *best_adjmatrix;

static int n_max_frags, m_max_frags;
static int *weight;

static unsigned printcounter;

static void iterate(void);
static void iterate_recurse(int i, AdjWord min);
static bool preconsider_ok(int nwords, bool doprint);
static bool maxhamweight_ok(void);
static void optimise(bool doprint);

static void progress_eol(void) {
  fprintf(stderr,"        \r");
  fflush(stderr);
}

static void set_best(double new_best) {
  best = new_best;
  /*
   * When computing n_max_frags, we want to set a value that will skip
   * anything that won't provide strictly better solutions.  So we
   * want
   *             frags <      n / best
   *                        _          _
   *   <=>       frags <   |  n / best  |
   *                        _          _
   *   <=>       frags <=  |  n / best  | - 1
   *
   * But best values from glpk are slightly approximate, so we
   * subtract a fudge factor from our target.
   */
  double near_best = best * 0.98 - 0.02;
  n_max_frags = ceil(n / near_best) - 1;
  m_max_frags = ceil(m / near_best) - 1;
}

/*----- multicore support -----*/

/*
 * Multicore protocol
 *
 * We fork into:
 *   - master (parent)
 *   - generator
 *   - ncpu workers
 *
 * ipc facilities:
 *   - one pipe ("work") from generator to workers
 *   - ever-extending file ("bus") containing new "best" values
 *   - one file for each worker giving maxhamweight and adjmatrix for best
 *
 * generator runs iterate_recurse to a certain depth and writes the
 * candidates to a pipe
 *
 * workers read candidates from the pipe and resume iterate_recurse
 * halfway through the recursion
 *
 * whenever a worker does a doprint, it checks the bus for new best
 * value; actual best values are appended
 *
 * master waits for generator and all workers to finish and then
 * runs optimise() for each worker's best, then prints
 */ 

static int ncpus = 0, multicore_iteration_boundary = INT_MAX;

static int mc_bus, mc_work[2];
static off_t mc_bus_read;

typedef struct {
  int w;
  FILE *results;
  pid_t pid;
} Worker;
static Worker *mc_us;
static bool mc_am_generator;

static void multicore_check_for_new_best(void);

#define MAX_NIOVS 4
static AdjWord mc_iter_min;
static int mc_niovs;
static size_t mc_iovlen;
static struct iovec mc_iov[MAX_NIOVS];

#define IOV0 (mc_niovs = mc_iovlen = 0)

#define IOV(obj, count) ({                              \
    assert(mc_niovs < MAX_NIOVS);                       \
    mc_iov[mc_niovs].iov_base = &(obj);                 \
    mc_iov[mc_niovs].iov_len = sizeof(obj) * (count);   \
    mc_iovlen += mc_iov[mc_niovs].iov_len;              \
    mc_niovs++;                                         \
  })

static void mc_rwvsetup_outer(void) {
  IOV0;
  IOV(maxhamweight, 1);
  IOV(mc_iter_min, 1);
  IOV(*adjmatrix, multicore_iteration_boundary);
  IOV(*weight, m);
}

static void mc_rwvsetup_full(void) {
  IOV0;
  IOV(*adjmatrix, n);
}

static void vlprintf(const char *fmt, va_list al) {
  vfprintf(stderr,fmt,al);
  progress_eol();
}

static void LPRINTF(const char *fmt, ...) {
  va_list al;
  va_start(al,fmt);
  vlprintf(fmt,al);
  va_end(al);
}

static void mc_awaitpid(int wnum, pid_t pid) {
  LPRINTF("master awaiting %2d [%ld]",wnum,(long)pid);
  int status;
  pid_t got = waitpid(pid, &status, 0);
  assert(got == pid);
  if (status) {
    fprintf(stderr,"\nFAILED SUBPROC %2d [%ld] %d\n",
            wnum, (long)pid, status);
    exit(-1);
  }
}

static void multicore_outer_iteration(int i, AdjWord min) {
  static unsigned check_counter;

  assert(i == multicore_iteration_boundary);
  mc_iter_min = min;
  mc_rwvsetup_outer();
  ssize_t r = writev(mc_work[1], mc_iov, mc_niovs);
  assert(r == mc_iovlen);
  /* effectively, this writev arranges to transfers control
   * to some worker's instance of iterate_recurse via mc_iterate_worker */

  if (!(check_counter++ & 0xff))
    multicore_check_for_new_best();
}

static void mc_iterate_worker(void) {
  for (;;) {
    mc_rwvsetup_outer();
    ssize_t r = readv(mc_work[0], mc_iov, mc_niovs);
    if (r == 0) break;
    assert(r == mc_iovlen);
    
    bool ok = maxhamweight_ok();
    if (!ok) continue;

    ok = preconsider_ok(multicore_iteration_boundary, 1);
    progress_eol();
    if (!ok) continue;

    /* stop iterate_recurse from trying to run multicore_outer_iteration */
    int mc_org_it_bound = multicore_iteration_boundary;
    multicore_iteration_boundary = INT_MAX;
    iterate_recurse(mc_org_it_bound, mc_iter_min);
    multicore_iteration_boundary = mc_org_it_bound;
  }
  if (best_adjmatrix) {
    LPRINTF("worker %2d reporting",mc_us->w);
    adjmatrix = best_adjmatrix;
    mc_rwvsetup_full();
    ssize_t r = writev(fileno(mc_us->results), mc_iov, mc_niovs);
    assert(r == mc_iovlen);
  }
  LPRINTF("worker %2d ending",mc_us->w);
  exit(0);
}

static void multicore(void) {
  Worker *mc_workers;
  int w;
  pid_t genpid;

  multicore_iteration_boundary = n / 2;

  FILE *busf = tmpfile();  assert(busf);
  mc_bus = fileno(busf);
  int r = fcntl(mc_bus, F_GETFL);  assert(r >= 0);
  r |= O_APPEND;
  r = fcntl(mc_bus, F_SETFL, r);  assert(r >= 0);

  r = pipe(mc_work);  assert(!r);

  mc_workers = xmalloc(sizeof(*mc_workers) * ncpus);
  for (w=0; w<ncpus; w++) {
    mc_workers[w].w = w;
    mc_workers[w].results = tmpfile();  assert(mc_workers[w].results);
    mc_workers[w].pid = fork();  assert(mc_workers[w].pid >= 0);
    if (!mc_workers[w].pid) {
      mc_us = &mc_workers[w];
      close(mc_work[1]);
      LPRINTF("worker %2d running", w);
      mc_iterate_worker();
      exit(0);
    }
  }

  close(mc_work[0]);

  genpid = fork();  assert(genpid >= 0);
  if (!genpid) {
    mc_am_generator = 1;
    LPRINTF("generator running");
    iterate();
    exit(0);
  }

  close(mc_work[1]);
  mc_awaitpid(-1, genpid);
  for (w=0; w<ncpus; w++)
    mc_awaitpid(w, mc_workers[w].pid);

  for (w=0; w<ncpus; w++) {
    mc_rwvsetup_full();
    LPRINTF("reading report from %2d",w);
    ssize_t sr = preadv(fileno(mc_workers[w].results), mc_iov, mc_niovs, 0);
    if (!sr) continue;
    LPRINTF("got report from %2d",w);
    maxhamweight = 0;
    optimise(1);
  }
}

static void multicore_check_for_new_best(void) {
  if (!(mc_us || mc_am_generator))
    return;

  for (;;) {
    double msg;
    ssize_t got = pread(mc_bus, &msg, sizeof(msg), mc_bus_read);
    if (!got) break;
    assert(got == sizeof(msg));
    if (msg > best)
      set_best(msg);
    mc_bus_read += sizeof(msg);
  }
}

static void multicore_found_new_best(void) {
  if (!mc_us)
    return;

  if (mc_us /* might be master */) fprintf(stderr,"    w%-2d ",mc_us->w);
  ssize_t wrote = write(mc_bus, &best, sizeof(best));
  assert(wrote == sizeof(best));
}

/*----- end of multicore support -----*/

static AdjWord *xalloc_adjmatrix(void) {
  return xmalloc(sizeof(*adjmatrix)*n);
}

static void prep(void) {
  adjall = ~((~(AdjWord)0) << m);
  adjmatrix = xalloc_adjmatrix();
  glp_term_out(GLP_OFF);
  setlinebuf(stderr);
  weight = calloc(sizeof(*weight), m);  assert(weight);
  n_max_frags = INT_MAX;
  m_max_frags = INT_MAX;
}

#if 0
static AdjWord one_adj_bit(int bitnum) {
  return (AdjWord)1 << bitnum;
}
#endif

static int count_set_adj_bits(AdjWord w) {
  int j, total = 0;
  AdjWord jbit;
  FOR_BITS(j,m)
    total += !!(w & jbit);
  return total;
}

#define PRINTF(...) if (!doprint) ; else fprintf(stderr, __VA_ARGS__)

static int totalfrags;

static bool maxhamweight_ok(void) {
  return maxhamweight <= m_max_frags;
}

static bool preconsider_ok(int nwords, bool doprint) {
  int i;

  PRINTF("%2d ", maxhamweight);

  bool had_max = 0;
  for (i=0, totalfrags=0; i<nwords; i++) {
    int frags = count_set_adj_bits(adjmatrix[i]);
    PRINTF("%"PRADJ" ", adjmatrix[i]);
    if (frags > m_max_frags) {
      PRINTF(" too fine");
      goto out;
    }
    had_max += (frags >= maxhamweight);
    totalfrags += frags;
  }
  if (!had_max) {
    /* Skip this candidate as its max hamming weight is lower than
     * we're currently looking for (which means we must have done it
     * already).  (The recursive iteration ensures that none of the
     * words have more than the max hamming weight.) */
    PRINTF(" nomaxham");
    goto out;
  }
  return 1;

 out:
  return 0;
}

static void optimise(bool doprint) {
  /* Consider the best answer (if any) for a given adjacency matrix */
  glp_prob *prob = 0;
  int i, j;
  AdjWord jbit;

  /*
   * Up to a certain point, optimise() can be restarted.  We use this
   * to go back and print the debugging output if it turns out that we
   * have an interesting case.  The HAVE_PRINTED macro does this: its
   * semantics are to go back in time and make sure that we have
   * printed the description of the search case.
   */
#define HAVE_PRINTED ({                                         \
      if (!doprint) { doprint = 1; goto retry_with_print; }     \
    })
 retry_with_print:
  if (prob) {
    glp_delete_prob(prob);
    prob = 0;
  }

  bool ok = preconsider_ok(n, doprint);
  if (!ok)
    goto out;

  /*
   * We formulate our problem as an LP problem as follows.
   * In this file "n" and "m" are the matchstick numbers.
   *
   * Each set bit in the adjacency matrix corresponds to taking a
   * fragment from old match i and making it part of new match j.
   *
   * The structural variables (columns) are:
   *   x_minimum        minimum size of any fragment (bounded below by 0)
   *   x_morefrag_i_j   the amount by which the size of the fragment
   *                     i,j exceeds the minimum size (bounded below by 0)
   *
   * The auxiliary variables (rows) are:
   *   x_total_i       total length for each input match (fixed variable)
   *   x_total_j       total length for each output match (fixed variable)
   *
   * The objective function is simply
   *   maximise x_minimum
   *
   * We use X_ and Y_ to refer to GLPK's (1-based) column and row indices.
   * ME_ refers to entries in the list of constraint matrix elements
   * which we build up as we go.
   */

  prob = glp_create_prob();

  int Y_totals_i = glp_add_rows(prob, n);
  int Y_totals_j = glp_add_rows(prob, m);
  int X_minimum = glp_add_cols(prob, 1);

  {
  int next_matrix_entry = 1; /* wtf GLPK! */
  int matrix_entries_size = next_matrix_entry + n + m + totalfrags*2;
  double matrix_entries[matrix_entries_size];
  int matrix_entries_XY[2][matrix_entries_size];

#define ADD_MATRIX_ENTRY(Y,X) ({                        \
      assert(next_matrix_entry < matrix_entries_size);  \
      matrix_entries_XY[0][next_matrix_entry] = (X);    \
      matrix_entries_XY[1][next_matrix_entry] = (Y);    \
      matrix_entries[next_matrix_entry] = 0;            \
      next_matrix_entry++;                              \
    })

  int ME_totals_i__minimum = next_matrix_entry;
  for (i=0; i<n; i++) ADD_MATRIX_ENTRY(Y_totals_i+i, X_minimum);

  int ME_totals_j__minimum = next_matrix_entry;
  for (j=0; j<m; j++) ADD_MATRIX_ENTRY(Y_totals_j+j, X_minimum);

  /* \forall_i x_total_i = m */
  /* \forall_i x_total_j = n */
  for (i=0; i<n; i++) glp_set_row_bnds(prob, Y_totals_i+i, GLP_FX, m,m);
  for (j=0; j<m; j++) glp_set_row_bnds(prob, Y_totals_j+j, GLP_FX, n,n);

  /* x_minimum >= 0 */
  glp_set_col_bnds(prob, X_minimum, GLP_LO, 0, 0);
  glp_set_col_name(prob, X_minimum, "minimum");

  /* objective is maximising x_minimum */
  glp_set_obj_dir(prob, GLP_MAX);
  glp_set_obj_coef(prob, X_minimum, 1);

  for (i=0; i<n; i++) {
    FOR_BITS(j,m) {
      if (!(adjmatrix[i] & jbit))
        continue;
      /* x_total_i += x_minimum */
      /* x_total_j += x_minimum */
      matrix_entries[ ME_totals_i__minimum + i ] ++;
      matrix_entries[ ME_totals_j__minimum + j ] ++;

      /* x_morefrag_i_j >= 0 */
      int X_morefrag_i_j = glp_add_cols(prob, 1);
      glp_set_col_bnds(prob, X_morefrag_i_j, GLP_LO, 0, 0);
      if (doprint) {
        char buf[255];
        snprintf(buf,sizeof(buf),"mf %d,%d",i,j);
        glp_set_col_name(prob, X_morefrag_i_j, buf);
      }

      /* x_total_i += x_morefrag_i_j */
      /* x_total_j += x_morefrag_i_j */
      int ME_totals_i__mf_i_j = ADD_MATRIX_ENTRY(Y_totals_i+i, X_morefrag_i_j);
      int ME_totals_j__mf_i_j = ADD_MATRIX_ENTRY(Y_totals_j+j, X_morefrag_i_j);
      matrix_entries[ME_totals_i__mf_i_j] = 1;
      matrix_entries[ME_totals_j__mf_i_j] = 1;
    }
  }

  assert(next_matrix_entry == matrix_entries_size);

  glp_load_matrix(prob, matrix_entries_size-1,
                  matrix_entries_XY[1], matrix_entries_XY[0],
                  matrix_entries);

  int r = glp_simplex(prob, NULL);
  PRINTF(" glp=%d", r);

#define OKERR(e) \
  case e: PRINTF(" " #e ); goto out;
#define BADERR(e) \
  case e: HAVE_PRINTED; printf(" " #e " CRASHING\n"); exit(-1);
#define DEFAULT \
  default: HAVE_PRINTED; printf(" ! CRASHING\n"); exit(-1);

  switch (r) {
  OKERR(GLP_ESING);
  OKERR(GLP_ECOND);
  OKERR(GLP_EBOUND);
  OKERR(GLP_EFAIL);
  OKERR(GLP_ENOPFS);
  OKERR(GLP_ENODFS);
  BADERR(GLP_EBADB);
  BADERR(GLP_EOBJLL);
  BADERR(GLP_EOBJUL);
  BADERR(GLP_EITLIM);
  BADERR(GLP_ETMLIM);
  BADERR(GLP_EINSTAB);
  BADERR(GLP_ENOCVG);
  case 0: break;
  DEFAULT;
  }

  r = glp_get_status(prob);
  PRINTF(" status=%d", r);

  switch (r) {
  OKERR(GLP_NOFEAS);
  OKERR(GLP_UNDEF);
  BADERR(GLP_FEAS);
  BADERR(GLP_INFEAS);
  BADERR(GLP_UNBND);
  case GLP_OPT: break;
  DEFAULT;
  }

  double got = glp_get_obj_val(prob);
  PRINTF("  %g", got);
  if (got <= best)
    goto out;

  HAVE_PRINTED;

  set_best(got);
  multicore_found_new_best();

  if (best_prob) glp_delete_prob(best_prob);
  best_prob = prob;

  free(best_adjmatrix);
  best_adjmatrix = xalloc_adjmatrix();
  memcpy(best_adjmatrix, adjmatrix, sizeof(*adjmatrix)*n);

  PRINTF(" BEST        \n");
  return;

  }
 out:
  if (prob)
    glp_delete_prob(prob);
  if (doprint) progress_eol();
  if (doprint) multicore_check_for_new_best();
}

static void iterate_recurse(int i, AdjWord min) {
  int j;
  AdjWord jbit;

  if (i >= n) {
    for (j=0; j<m; j++)
      if (weight[j] < 2)
        return;

    printcounter++;
    optimise(!(printcounter & 0xfff));
    return;
  }
  if (i >= multicore_iteration_boundary) {
    multicore_outer_iteration(i, min);
    return;
  }
  for (adjmatrix[i] = min;
       ;
       adjmatrix[i]++) {
    if (count_set_adj_bits(adjmatrix[i]) > maxhamweight)
      goto again;
    if (i == 0 && (adjmatrix[i] & (1+adjmatrix[i])))
      goto again;

    FOR_BITS(j,m)
      if (adjmatrix[i] & jbit)
        weight[j]++;
    for (int j = 0; j < m; j++)
      if (weight[j] >= n_max_frags)
        goto takeout;

    iterate_recurse(i+1, adjmatrix[i]);

  takeout:
    FOR_BITS(j,m)
      if (adjmatrix[i] & jbit)
        weight[j]--;

  again:
    if (adjmatrix[i] == adjall)
      return;
  }
}

static void iterate(void) {
  for (maxhamweight=1; maxhamweight<=m; maxhamweight++) {
    if (!maxhamweight_ok())
      continue;

    iterate_recurse(0, 1);
  }
}

static void report(void) {
  fprintf(stderr, "\n");
  if (best_prob) {
    double min = glp_get_obj_val(best_prob);
    double a[n][m];
    int i, j, cols;
    for (i = 0; i < n; i++)
      for (j = 0; j < m; j++)
        a[i][j] = 0;
    cols = glp_get_num_cols(best_prob);
    for (i = 1; i <= cols; i++) {
      int x, y;
      if (2 != sscanf(glp_get_col_name(best_prob, i), "mf %d,%d", &x, &y))
        continue;
      a[x][y] = min + glp_get_col_prim(best_prob, i);
    }
    printf("%d into %d: min fragment %g   [%s]\n", n, m, min, VERSION);
    for (i = 0; i < n; i++) {
      for (j = 0; j < m; j++) {
        if (a[i][j])
          printf(" %9.3f", a[i][j]);
        else
          printf("          ");
      }
      printf("\n");
    }
  }
  if (ferror(stdout) || fclose(stdout)) { perror("stdout"); exit(-1); }
}
 
int main(int argc, char **argv) {
  int opt;
  while ((opt = getopt(argc,argv,"j:")) >= 0) {
    switch (opt) {
    case 'j': ncpus = atoi(optarg); break;
    case '+': assert(!"bad option");
    default: abort();
    }
  }
  argc -= optind-1;
  argv += optind-1;
  assert(argc==3);
  n = atoi(argv[1]);
  m = atoi(argv[2]);
  assert(n > m);

  prep();

  if (ncpus) multicore();
  else iterate();

  report();
  return 0;
}