#include <stdio.h>
#include <fcntl.h>
#include <errno.h>
#include <ctype.h>
#include <string.h>

#include "fdc_int.h"

// try to save on variables
static fd_int fd_const[MAX_VALUE + 1];

#define FD_CONST(n) (fd_const[n] ? fd_const[n] : (fd_const[n] = fd_new(n, n)))

//#define FD_CONST(n) fd_new(n, n)

#define NCOINS (sizeof(coins_value) / sizeof(*coins_value))

int coins_value[] = { 1, 2, 5, 10, 20, 50 };

int main(int argc, char *argv[])
{
  int solutions = 0, one_solution = 1;
  fd_int change[NCOINS], coins[NCOINS];
  fd_int ncoins, amount;
  int am = 37;
  int i;

  fd_init(&argc, &argv);

  for (i = 1; i < argc; ++i)
    if (!strcmp(argv[i], "--all"))
      one_solution = 0;
    else if (isdigit(*argv[i]))
      am = atoi(argv[i]);
    else
      _fd_error("%s: unknown argument `%s'\n", argv[0], argv[i]);

  for (i = 0; i < NCOINS; ++i)
    coins[i] = FD_CONST(coins_value[i]);

  for (i = 0; i < NCOINS; ++i)
    change[i] = fd_new(0, MAX_VALUE);

  amount = FD_CONST(am);
  fd_knapsack2(change, coins, NCOINS, amount);

  ncoins = fd_new(0, MAX_VALUE);
  fd_sum2(change, NCOINS, ncoins);

  fd_min(ncoins);

  while (fd_solve() == FD_OK)
    {
      printf("solution %d:\n", ++solutions);

      printf("coins needed: %d\n", fd_var_value(ncoins));

      for (i = 0; i < NCOINS; ++i)
	{
	  printf("%d × %d ", fd_var_value(change[i]), fd_var_value(coins[i]));

	  if (i != NCOINS - 1)
	    putchar('+'), putchar(' ');
	}
      printf(" = %d\n", fd_var_value(amount));

#if !(defined(LOCAL_SEARCH) || defined(DISTRIBUTED_SOLVER))
      if (one_solution)
#endif
	break;
    }

  if (solutions)
    printf("%d solutions found\n", solutions);
  else
    printf("inconsistent CSP\n");

  fd_end();

  return !solutions;
}