/* Implementation of the Ferry Loading Problem using a hash table */
/* Reference: http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0101-74382015000200423 */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define ENDOFREC -1
#define P1 3
#define P2 5
#define P3 7
#define NOT_FOUND 0
#define FOUND 1

typedef struct _node {
   int k;
   int u;
   int v;
   struct _node *next;
} node;

typedef node **htbl;

int *genlen ( int n )
{
   int *A, i;

   printf("    ");
   A = (int *)malloc(n * sizeof(int));
   for (i=0; i<n; ++i) {
      A[i] = 1 + rand() % 9;
      printf("%d ", A[i]);
   }
   printf("\n");
   return A;
}

/* Recursive function:
   B[] stores the best solution found so far
   C[] stores the current path */
int esearchrec ( int L, int *A, int n, int k, int u, int v, char *B, char *C )
{
   int k1, k2, kmax, i;

   if (k == n) {
      kmax = k;
   } else {
      k1 = k2 = ENDOFREC;
      /* Make a random decision which deck to explore first */
      if (rand() % 2) { /* Explore the left deck first */
         if (u+A[k] <= L) {
            C[k] = 'L';
            k1 = esearchrec(L,A,n,k+1,u+A[k],v,B,C);
         }
         if (v+A[k] <= L) {
            C[k] = 'R';
            k2 = esearchrec(L,A,n,k+1,u,v+A[k],B,C);
         }
      } else {          /* Explore the right deck first */
         if (v+A[k] <= L) {
            C[k] = 'R';
            k2 = esearchrec(L,A,n,k+1,u,v+A[k],B,C);
         }
         if (u+A[k] <= L) {
            C[k] = 'L';
            k1 = esearchrec(L,A,n,k+1,u+A[k],v,B,C);
         }
      }
      if ((k1 == ENDOFREC) && (k2 == ENDOFREC)) kmax = k;
      else kmax = (k1 >= k2) ? k1 : k2;
   }
   if ((kmax == k) && (kmax > B[n])) {     /* Better leaf found */
      for (i=0; i<kmax; ++i) B[i] = C[i];
      B[n] = kmax;
   }
   return kmax;
}

/* Wrapper function */
int exhsearch ( int L, int *A, int n, char *B )
{
   char *C;
   int k;

   C = (char *)malloc(n*sizeof(char));
   k = esearchrec(L,A,n,0,0,0,B,C);
   free(C);
   return k;
}

int H ( int k, int u, int v, int s )
{
   return (P3 * k + P1 * u + P2 * v) % s;
}

htbl init ( int s )
{
   htbl T;

   T = (node **)malloc(s * sizeof(node));
   while (--s >= 0) T[s] = NULL;
   return T;
}

int search ( htbl T, int s, int k, int u, int v, int USE_SYMMETRY )
{
   int h;
   node *p;

   h = H(k,u,v,s);
   p = T[h];
   if (USE_SYMMETRY) {
      while (p) {
         /* Because of symmetry in the two decks (i,u,v) and (i,v,u) are
            essentially the same configuration */
         if ((p -> k == k) && ((p -> u == u) || (p -> v == u))) return FOUND;
         p = p -> next;
      }
   } else {
      while (p) {
         /* i and u fix v, so there is no need to check for v */
         if ((p -> k == k) && (p -> u == u)) return FOUND;
         p = p -> next;
      }
   }
   return NOT_FOUND;
}

void insert ( htbl T, int s, int k, int u, int v, int USE_SYMMETRY )
{
   int h;
   node *p;

   h = H(k,u,v,s);

   /* Search */
   p = T[h];
   if (USE_SYMMETRY) {
      while (p) {
         if ((p -> k == k) && ((p -> u == u) || (p -> v == u))) return;
         p = p -> next;
      }
   } else {
      while (p) {
         if ((p -> k == k) && (p -> u == u)) return;
         p = p -> next;
      }
   }

   /* If search is unsuccessful */
   p = (node *)malloc(sizeof(node));
   p -> k = k; p -> u = u; p -> v = v;
   p -> next = T[h]; T[h] = p;
}

void freetbl ( htbl T, int s )
{
   node *p, *q;

   while (--s >= 0) {
      p = T[s];
      while (p) {
         q = p;
         p = p -> next;
         free(q);
      }
   }
   free(T);
}

/* Recursive function:
   B[] stores the best solution found so far
   C[] stores the current path */
int hsearchrec ( int L, int *A, int n, int k, int u, int v, htbl T, int s, char *B, char *C, int USE_SYMMETRY )
{
   int k1, k2, kmax, i;

   insert(T,s,k,u,v,USE_SYMMETRY);
   if (k == n) {
      kmax = k;
   } else {
      k1 = k2 = ENDOFREC;
      /* Make a random decision which deck to explore first */
      if (rand() % 2) { /* Explore the left deck first */
         if ((u+A[k] <= L) && (search(T,s,k+1,u+A[k],v,USE_SYMMETRY) == NOT_FOUND)) {
            C[k] = 'L';
            k1 = hsearchrec(L,A,n,k+1,u+A[k],v,T,s,B,C,USE_SYMMETRY);
         }
         if ((v+A[k] <= L) && (search(T,s,k+1,v,v+A[k],USE_SYMMETRY) == NOT_FOUND)) {
            C[k] = 'R';
            k2 = hsearchrec(L,A,n,k+1,u,v+A[k],T,s,B,C,USE_SYMMETRY);
         }
      } else {          /* Explore the right deck first */
         if ((v+A[k] <= L) && (search(T,s,k+1,v,v+A[k],USE_SYMMETRY) == NOT_FOUND)) {
            C[k] = 'R';
            k2 = hsearchrec(L,A,n,k+1,u,v+A[k],T,s,B,C,USE_SYMMETRY);
         }
         if ((u+A[k] <= L) && (search(T,s,k+1,u+A[k],v,USE_SYMMETRY) == NOT_FOUND)) {
            C[k] = 'L';
            k1 = hsearchrec(L,A,n,k+1,u+A[k],v,T,s,B,C,USE_SYMMETRY);
         }
      }
      if ((k1 == ENDOFREC) && (k2 == ENDOFREC)) kmax = k;
      else kmax = (k1 >= k2) ? k1 : k2;
   }
   if ((kmax == k) && (kmax > B[n])) {     /* Better leaf found */
      for (i=0; i<kmax; ++i) B[i] = C[i];
      B[n] = kmax;
   }
   return kmax;
}

/* Wrapper function */
int hashsearch ( int L, int *A, int n, char *B, int USE_SYMMETRY )
{
   htbl T;
   int kmax, s;
   char *C;

   s = n * L;
   T = init(s);
   printf("    Hash table of size %d initialized\n", s);
   C = (char *)malloc(n*sizeof(char));
   kmax = hsearchrec(L,A,n,0,0,0,T,s,B,C,USE_SYMMETRY);
   freetbl(T,s);
   free(C);
   return kmax;
}

void printsol ( int *A, int n, char *B, int k )
{
   int s1, s2, i;

   s1 = 0;
   printf("    Deck 1: ");
   for (i=0; i<k; ++i) if (B[i] == 'L') {
      printf("%c%d", (s1) ? ',' : '[', A[i]);
      s1 += A[i];
   }
   printf("] Length used = %d\n", s1);

   s2 = 0;
   printf("    Deck 2: ");
   for (i=0; i<k; ++i) if (B[i] == 'R') {
      printf("%c%d", (s2) ? ',' : '[', A[i]);
      s2 += A[i];
   }
   printf("] Length used = %d\n", s2);
}

int main ( int argc, char *argv[] )
{
   int n, L, *A, k;
   char *B;
   clock_t c1, c2;

   if (argc > 1) L = atoi(argv[1]); else scanf("%d", &L);
   if (argc > 2) n = atoi(argv[2]); else scanf("%d", &n);
   printf("    %d %d\n", L, n);
   srand((unsigned int)time(NULL));

   A = genlen(n);
   B = (char *)malloc((n+1)*sizeof(char));

   printf("\n+++ Exhaustive search\n"); B[n] = 0;
   c1 = clock(); k = exhsearch(L,A,n,B); c2 = clock();
   printf("    k = %d\n", k);
   printsol(A,n,B,k);
   printf("    Search time = %lf sec\n", (double)(c2-c1)/(double)CLOCKS_PER_SEC);

   printf("\n+++ Hash-based search\n"); B[n] = 0;
   c1 = clock(); k = hashsearch(L,A,n,B,0); c2 = clock();
   printf("    k = %d\n", k);
   printsol(A,n,B,k);
   printf("    Search time = %lf sec\n", (double)(c2-c1)/(double)CLOCKS_PER_SEC);

   printf("\n+++ Hash-based search using symmetry\n"); B[n] = 0;
   c1 = clock(); k = hashsearch(L,A,n,B,1); c2 = clock();
   printf("    k = %d\n", k);
   printsol(A,n,B,k);
   printf("    Search time = %lf sec\n", (double)(c2-c1)/(double)CLOCKS_PER_SEC);

   free(A); free(B);

   exit(0);
}