/*
    Ambrose Sterr
    04/05/06
    Version 3.5.0 RC4
    This version reports only the first of each solution pair, but records both to the log.
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main (int, char *[]);
void backTrack();
void recurse(int);
int test ();
void pSums();

int n;
FILE* file;
int *r;
int *s;
int size;
int *list;               /* This stores the list being worked on. */
int *used;                   /* Setup and intialization of the arrays to keep track of the numbers used and their differences. */
int *h;                      /* The difference array. */

int main(int argc, char * argv[])
{
    int i;
    clock_t t;
    char* VERSION = "3.5.0 RC4";
    file = fopen(argv[1], "a");
    n = atoi(argv[2]);          /* Read the size from the arguments */
    size = argc-3;
    if (((r = malloc(size*sizeof(int))) == NULL)||((s = malloc(size*sizeof(int))) == NULL))
    {
        exit(EXIT_FAILURE);
    }
    fprintf(file, "Begin log: n=%d, r=(", n);
    for (i = 0; i < size-1; i++)
    {
        fprintf(file, "%d ", r[i] = atoi(argv[i+3]));     /* Read the array r from the arguments while printing it to the log. */
    }
    fprintf(file, "%d).\nVersion = %s\n", r[size-1] = atoi(argv[size+2]), VERSION);
/*
    int i;
    printf("%d\n", abs(5-9));
*/
    pSums();              /* To calculate a list of partial sums from r */
/*
    for (i = 0; i < 2; i++) { printf("%d:",s[i]); }
    if (s[1] == 9)
    {
        printf("ok.\n");
    }
*/
    backTrack();                /* Gets the program going */
    t = clock();
    printf("Elapsed CPU time:   %f\n", (float) t/CLOCKS_PER_SEC);
    fprintf(file, "Search took %.3fs.\nEnd log.\n\n", (float) t/CLOCKS_PER_SEC);
    return fclose(file);
}
void backTrack()
{
    int i;
    if (((used = malloc((n+1)*sizeof(int))) == NULL)||((h = malloc(n*sizeof(int))) == NULL))
    {
        exit(EXIT_FAILURE);
    }
    for (i = 1; i <= (n+1)/2; i++)  /* The iteration of first numbers.  These lists come in pairs.  If g is one, then so is (n,..,n)-g,
                                                                                                so I only scan the first half of the permutations.*/
    {
        int j;
        int count = 1;
        if ((list = malloc(n*sizeof(int))) == NULL)
        {
            exit(EXIT_FAILURE);
        }
        for (j = 0; j < n; j++)     /* The arrays are initialized to 0 before each run. */
        {
            used[j] = 0;
            list[j] = 0;
            h[j] = 0;
        }
        used[n] = 0;
        used[i]++;                  /* The first number is used. */
        list[0] = i;
        recurse(count);    /* This starts recursive scanning of the rest of the list. */
        free(list);
    }
}
void recurse(int count)
{
/*
    printf("\nrecursing..");
*/
    if (count != n)                 /* If the list isn't filled in... */
    {
        int i;
/*
        int j;
    for (j = 0; j < n; j++)
    {
        printf("%d ", list[j]);
    }
*/
        for (i = 1; i <= n; i++)    /* Look for the next number to add... */
        {
            if (((used[i] == 0)&&(h[abs(list[count-1]-i)]==0))&&((count != s[0]+1)||(abs(list[s[0]]-list[0])==abs(i-list[s[0]]))))   /* ...make sure it's a good one... */
            {
                list[count] = i;
                used[i]++;
                h[abs(list[count-1]-i)]++;
                recurse(count+1);    /* ...then head deeper in. */
                h[abs(list[count-1]-i)]--;
                used[i]--;
                list[count] = 0;
            }
        }
    }
    else                            /* But if the list is filled in... */
    {
        if (test() == 1)       /* Then check it for the second property. */
        {
            int i;
            fprintf(file, "g=(");
            printf("We got one: (");        /* Report a find! */
            for (i = 0; i < n-1; i++)         /* And print it. */
            {
                fprintf(file, "%d ", list[i]);
                printf("%d ", list[i]);
            }
            fprintf(file, "%d) works for r=(", list[n-1]);
            printf("%d)\n", list[n-1]);
            for (i = 0; i < size-1; i++)
            {
                fprintf(file, "%d ", r[i]);
            }
            fprintf(file, "%d)!\n", r[size-1]);
            if (list[0]*2 != n + 1)
            {
                fprintf(file, "g=(");
                for (i = 0; i < n-1; i++)
                {
                    fprintf(file, "%d ", n+1-list[i]);
                }
                fprintf(file, "%d) works for r=(", n+1-list[n-1]);
                for (i = 0; i < size-1; i++)
                {
                    fprintf(file, "%d ", r[i]);
                }
                fprintf(file, "%d)!\n", r[size-1]);
            }
        }
    }
}
int test ()      /* Checks for the extra property. */
{
    int i;
/*
    if (list[0] == 4)
    {
    printf("\ntesting.. ");
    for (i = 0; i < n; i++)
    {
        printf("%d ", list[i]);
    }
    }
*/
//    if (abs(list[s[0]]-list[0])!=abs(list[s[0]+1]-list[s[0]]))
//    {                               /* Checks the base condition for s[0] */
/*
        printf("\nPassed one...");
        printf("\ntesting.. ");
        for (i = 0; i < 11; i++)
        {
            printf("%d ", list[i]);
        }
*/
//        return 0;                   /* If it fails, quit the test. */
//    }
    for (i = 1; i < size; i++)
    {                               /* Checks on the rest of s, if |s|>1 */
        if (abs(list[s[i]]-list[s[i-1]+1])!=abs(list[s[i]+1]-list[s[i]]))
        {
            return 0;               /* If any of them fail, quit the test. */
        }
    }
    return 1;                       /* If it has passed all the tests, return 1. */
}
void pSums()      /* Makes a partial sum list out of the passed list. */
{
    int i;
    s[0] = r[0]-1;                  /* The -1 here corrects for array indexes starting at 0. */
    for (i = 1; i < size; i++)
    {
        s[i] = s[i-1] + r[i];
    };
}