#! /usr/bin/gawk -f
# Last edited on 2008-07-26 17:03:00 by stolfi

BEGIN {
  PROG = "guess-cuts-in-budget"
  USAGE = ( PROG " -v sum={SUM} < INFILE.pairs > OUTFILE.subs" );

  # Reads from stdin a list of pairs "{VALUE} {ITEM}".
  # Prints all subsets of this list whose {VALUE}s add to the 
  # specified {SUM}.

  abort = -1;
  if (sum == "") { arg_error(("must define (sum}")); }

  nread = 0;       # Number of value-name pairs read.
  split("", v);    # {v[0..nread-1]} are the item values read.
  split("", item); # {item[0..nread-1]} are the item names.
}

(abort >= 0) { exit(abort); }

// { 
  # Remove '#"-comments:
  gsub(/[\#].*$/, "", $0);
}

/^[ ]*([\#]|$)/ { 
  # Blank line, ignore: 
  next;
}

(NF == 2) {
  v[nread] = $1;
  item[nread] = $2;
  if (v[nread] + 0.0 <= 0.0)
    { data_error(("bad value = «" $1 "»")); }
  nread++;
  next;
}

// {
  data_error(("bad format  NF = " NF "")); 
}

END {
  split("", ix); # {ix[0.. ]} are th eindices of the items in the current subset.
  enum_combs(0, nread, sum+0);
}

function enum_combs(m,k,s,   i,t)
{
  # Enumerates al subsets of {v[0..k-1]} that add to {s}.
  # For each such subset, prints {v[ix[0..m-1]], item[ix[0..m-1]]}.
  # Assumes that {v[0..k-1]} are all positive.
  if (s < 0)
    { # No combination will do:
      return;
    }
  else if (s == 0)
    { # We found a combination, print it.
      t = 0;
      printf "\n";
      for (i = 0; i < m; i++) 
        { printf "%10s %s\n", v[ix[i]], item[ix[i]]; t += v[ix[i]]; }
      printf "%10s %s\n", "---------", "--------------------";
      printf "%10s %s\n", t, "TOTAL";
      if (t != sum+0) { prog_error("beh?"); }
      # No use recursing further: 
      return;
    }
  else if (k == 0)
    { # No more items to consider:
      return;
    }
  else
    { # Try without item {k-1}:
      enum_combs(m, k-1, s);
      # Try with item {k-1}:
      ix[m] = k-1;
      enum_combs(m+1, k-1, s-v[k-1]);
    }
}
        

function arg_error(msg)
{ printf "%s: **%s\n", PROG, msg > "/dev/stderr";
  printf "usage: %s\n", USAGE;
  abort = 1;
  exit(abort);
}

function data_error(msg)
{ printf "%s:%s: **%s\n", FILENAME, FNR, msg > "/dev/stderr";
  abort = 1;
  exit(abort);
}

function prog_error(msg)
{ printf "%s:%s: ** PROGRAM ERROR - %s\n", FILENAME, FNR, msg > "/dev/stderr";
  abort = 1;
  exit(abort);
}