#include <stdio.h>

#define NO_DEBUG

#ifdef DEBUG
#define DEBUG_P1(S,A) printf(S,A)
#define DEBUG_P2(S,A,B) printf(S,A,B)
#define DEBUG_P3(S,A,B,C) printf(S,A,B,C)
#define DEBUG_P4(S,A,B,C,D) printf(S,A,B,C,D)
#define DEBUG_P6(S,A,B,C,D,E,F) printf(S,A,B,C,D,E,F)
#else
#define DEBUG_P1(S,A)
#define DEBUG_P2(S,A,B)
#define DEBUG_P3(S,A,B,C)
#define DEBUG_P4(S,A,B,C,D)
#define DEBUG_P6(S,A,B,C,D,E,F)
#endif


/* Finding minimal rulers. We would like to construct a
   set {p_1, p_2, ... p_k} such that
   { p_j - p_i | 0 <= i < j <= k } subset {1, 2, .. n}
*/
/* typing of search method: */

#define NO_L_LIM         /* Limit l = p_k */
#define K_LIM            /* Limit k */
#define ONLY_FIRST       /* how many solutions should be printed */

/* maximum values for n, k, and l */

#define MAX_N  100
#define MAX_K  MAX_N
#define MAX_L  (MAX_N+2)

int g_n,
    g_k,
    g_l;    /* = p_k */
int opt_print_sol;
int nr_to_check;

int ruler[MAX_N];
int found[MAX_L];
int found_at[MAX_K][MAX_L];

int sol_found;
int count[MAX_L][MAX_K];

void check_solution(int k, int l)
{   int i;
    
    if (opt_print_sol == 2)
    {   int j;

#ifdef L_LIM
        printf("found k=%d: ", k + 2));
#else
        printf("found k=%d: ", k + 1);
#endif
        for (j = 0; j <= k; j++)
            printf("%d ", ruler[j]);
#ifdef L_LIM
        printf("%d ", g_l);
#endif
        printf(" | ");
        for (j = 1; j <= g_n; j++)
            printf(" %d", found[j]);
        /* printf("\n"); */
    }
    if (found[g_n+1] > 0)
    {   if (opt_print_sol == 2)
            printf(" NOT TRUE\n");
        return; /* not a true sparse ruler for n */
    }

    /* Check if minimal */
    for (i = 0; i <= k; i++)
    {   int j, nn = 1;

        for (j = 1; j <= g_k && nn; j++)
            nn = found_at[i][j] < found[j]; 

        if (nn)
        {   if (opt_print_sol == 2)
                printf(" NOT MINIMAL FOR %d\n", i);
            return;
        }
    }
#ifdef L_LIM
    {   int j, nn = 1;

        for (j = 1; j <= g_k && nn; j++)
            nn = found_at[g_l][j] < found[j]; 

        if (nn)
        {   if (opt_print_sol == 2)
                printf(" NOT MINIMAL FOR %d\n", k+1);
            return;
        }
    }
#endif
    if (opt_print_sol == 2)
        printf(" TRUE, MINIMAL\n");
    if (opt_print_sol == 1)
    {   int j;

#ifdef L_LIM
        /* printf("found k=%d: ", k + 2); */
#else
        /* printf("found k=%d: ", k + 1); */
#endif
        for (j = 0; j <= k; j++)
            printf("%d ", ruler[j]);
#ifdef L_LIM
        printf("%d ", g_l);
#endif
        /* printf(" | ");
           for (j = 1; j <= g_n; j++)
               printf(" %d", found[j]); */
        printf("\n"); 
    }

    sol_found++;
#ifdef L_LIM
    count[g_l][k + 2]++;
#else
    count[l][k + 1]++;
#endif
}

void fill (int k, int at, int till, int nr_to_find)
{   int i,j, v, new_nr_to_find;

    DEBUG_P6("%*sfill (%d, %d, %d, %d)\n", 
             k, " ", k, at, till, nr_to_find);

    k++;
    till++;

    DEBUG_P3("%*snow k=%d: ", k, " ", k + 1);
    for (j = 0; j < k; j++)
        DEBUG_P1("%d ", ruler[j]);
#ifdef L_LIM
        DEBUG_P1("%d", g_l);
#endif
    DEBUG_P4("\n%*snr_to_find: %d, nr_to_check %d\n", 
             k, " ", nr_to_find, nr_to_check);

    for (i = at; i < till && i <= at + g_n; i++)
    {   ruler[k] = i;
        new_nr_to_find = nr_to_find;
        for (j = 0; j < k; j++)
        {   v = i - ruler[j];
            if (v <= g_n)
            {   found_at[k][v]++;
                found_at[j][v]++;
                if (found[v]++ == 0)
                    new_nr_to_find--;
            }
            else if (v == g_n + 1)
                found[v]++;
        }
        nr_to_check -= k;
#ifdef L_LIM
        {   v = g_l - i;
            if (v <= g_n)
            {   found_at[k][v]++;
                found_at[g_l][v]++;
                if (found[v]++ == 0)
                    new_nr_to_find--;
            else if (v == g_n + 1)
                found[v]++;
            }
            nr_to_check--;
        }
#endif
        DEBUG_P3("%*sseek k=%d: ", k, " ", k + 1);
        for (j = 0; j <= k; j++)
            DEBUG_P1("%k ", ruler[j]);
#ifdef L_LIM
        DEBUG_P1("%d", g_l);
#endif
        DEBUG_P4("\n%*snr_to_find: %d, nr_to_check %d\n", 
                 k, " ", new_nr_to_find, nr_to_check);
        if (new_nr_to_find == 0)
            check_solution(k, i);
        else if (   found[g_n + 1] == 0
#ifdef K_LIM
                 && new_nr_to_find <= nr_to_check
#else
                 && new_nr_to_find < nr_to_find
#endif
                )
            fill(k, i+1, till, new_nr_to_find);
#ifdef ONLY_FIRST
        if (sol_found > 0)
            return;
#endif
        for (j = 0; j < k; j++)
        {   v = i - ruler[j];
            if (v <= g_n)
            {   found_at[k][v]--;
                found_at[j][v]--;
                found[v]--;
            }
            else if (v == g_n + 1)
                found[v]--;
        }
        nr_to_check += k;
#ifdef L_LIM
        {   v = g_l - i;
            if (v <= g_n)
            {   found_at[k][v]--;
                found_at[g_l][v]--;
                found[v]--;
            }
            else if (v == g_n + 1)
                found[v]--;
            nr_to_check++;
        }
#endif
    }
}

void solutions(int n, int k, int l, int table_form)
{   int i, j, nr_to_find, min_k;
    int not_found = 1;

    if (opt_print_sol)
        printf("finding solutions for k = %d and l = %d\n", k, l);
    ruler[0] = 0;
    ruler[k] = l;

    sol_found = 0;

    for (i = 0; i < MAX_L; i++)
        for (j = 0; j < MAX_K; j++)
        {   count[i][j] = 0;
            found_at[j][i] = 0;
        }

    for (i = 0; i <= n; i++)
        found[i] = 0;

    nr_to_check = (k * (k - 1))/2;
    nr_to_find = n;

#ifdef L_LIM
    {   if (l <= n)
        {   found[n]++;
            found_at[0][n]++;
            found_at[l][n]++;
            nr_to_find--;
        }
        nr_to_check--;
    }
#endif

    g_n = n;
    g_k = n;
    g_l = l;

#ifdef L_LIM
    fill(0, 1, l - k + 2, nr_to_find);
#else
    fill(0, 1, l - k + 1, nr_to_find);
#endif

    if (sol_found == 0)
        return;

    min_k = 2; 
    while ((min_k*(min_k-1))/2 < n)
        min_k++;

    for (j = min_k; j < MAX_K; j++)
    {   int found = 0;
        int im;

        for (im = MAX_L - 1; im >= n; im--)
            if (count[im][j] != 0L)
            {   found = 1;
                break;
            }

        if (table_form && not_found && !found)
            printf("%3d |\n", j);
        if (found)
        {  not_found = 0;
           if (table_form)
              printf("%3d |", j);
           else
#ifdef K_LIM
              printf("%3d %3d k |", n, j);
#else
              printf("%3d %3d   |", n, j);
#endif
           for (i = n; i <= im; i++)
               printf(table_form ? " %3d" : " %d", count[i][j]);
           printf("\n");
        }
    }
}

void print_table(int n)
{   int k, i;

    opt_print_sol = 1;

    printf("<H2> Number of true, minimal sparse rulers for length %d </H2>"
           "\n\n<PRE>\n    |", n);
    for (i = n; i < n + 10; i++)
        printf(" %3d", i);
    printf("\n----+");
    for (i = n; i < n + 10; i++)
        printf("----");
    printf("\n");
   
    k = 2; 
    while ((k*(k-1))/2 < n)
        k++;

    /* solutions(n, k, MAX_L, 1); */
    solutions(n, k, MAX_L, 1);
/*    if (sol_found == 0) 
    {   k++;
        solutions(n, k, MAX_L, 1);
    } */
/*
    while (sol_found != 0)
    {   k++;
        solutions(n, k, MAX_L, 1);
    }
*/
    printf("</PRE>\n\n");
}        
 
    
   
void main()
{   int n = 20;
    int k = 2;

    opt_print_sol = 1;

    print_table(37);

#ifdef COMMENT
    for (n = 5; n < 6; n++)
    {
        while ((k*(k-1))/2 < n)
            k++;
        DEBUG_P4("n = %d, k = %d (%d), l = %d\n", n, k, (k*(k-1))/2, n);
    
        solutions(n, k, n, 1, 1); 
        solutions(n, k+1, n, 1, 1); /* Does not work correct */
        solutions(n, k, MAX_L, 0, 1);
        /* if (sol_found == 0) solutions(n, k+1, MAX_L, 0, 1); */
        /* solutions(n, k, MAX_L, 0, 0); */
    }
#endif
}