/*
 * Ambrose Sterr
 * 04/26/06
 * Version 4.1.4
 * Formatted for emacs.
 */

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

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

int main(int argc, char* argv[])
{
    char* VERSION = "4.1.4";            /* The current version. */
    int startTime = time(NULL);
    if (argc < 3)
    /* If there aren't enough arguments, print the usage. */
    {
        printMan();
        return 0;
    }
    else if (0 == (strcmp(argv[1], "-t")))
    /* Enters test mode, preps the log, then runs the tests. */
    {
        FILE* file = fopen(argv[2], "a");
        fprintf(file, "Begin test, version %s.\n", VERSION);
        programTest(file);
        fprintf(file, "End test.\n\n");
        return 0;   /* And quits. */
    }
    else if (argc < 4)
    /* If there aren't enough arguments for normal mode, print the usage. */
    {
        printMan();
        return 1;
    }
    else
    {
        FILE* file = fopen(argv[1], "a");
        int n = atoi(argv[2]);  /* Read the list size from the arguments. */
        if (n < 4)
        /* Quits if n isn't valid. */
        {
            printf("n must be an integer greater than three.\n\n");
            fprintf(file, "ARGUMENT ERROR.\n\n");
            printMan();
            return 1;
        }
        int size = argc-3;              /* Get the size of r. */
        int* r;
        int* s;
        int i;
        time_t tTime;
        if (((r = malloc(size*sizeof(int))) == NULL)||
            ((s = malloc(size*sizeof(int))) == NULL))
        /* Get the memory for r and s, or quit. */
        {
            perror("Memory allocation error!");
            return 2;
        }
        fprintf(file, "Begin log: n=%d, r=(", n);
        for (i = 0; i < size-1; i++)
        /* Read the array r from the arguments while printing it to the log. */
        {
            fprintf(file, "%d ", r[i] = atoi(argv[i+3]));
            if (r[i] < 3)
            /* Quits if any element of r isn't valid. */
            {
                printf("Each element of r must be an integer greater than");
                printf("two.\n\n");
                fprintf(file, "ARGUMENT ERROR.\n\n");
                printMan();
                return 1;
            }
        }
        fprintf(file, "%d).\n", r[size-1] = atoi(argv[size+2]));
        fprintf(file, "Version = %s\n", VERSION);
        pSums(size, r, s);     /* To calculate a list of partial sums from r */
        if (s[size-1] >= n-1)
        {           /* Quits if the r array is too big for n. */
            printf("The sum of the elements of r must be less than n.\n\n");
            fprintf(file, "ARGUMENT ERROR.\n\n");
            printMan();
            return 1;
        }
        /* Closing and reopening file prevents the child processes
         * from also initializing the log. */
        fclose(file);
        file = fopen(argv[1], "a");
        backTrack(file, n, size, r, s);     /* Now the body of the program. */
        /* When it's all done, get and record the time. */
        tTime = time(NULL) - startTime;
        printf("Elapsed wall time:   %ds\n", tTime);
        fprintf(file, "Search took %ds.\nEnd log.\n\n", tTime);
        return fclose(file);
    }
}
void backTrack(FILE* file, int n, int size, int r[], int s[])
{
    int* used;           /* This keeps track of the numbers used. */
    int* h;              /* This keeps track of the differences encountered. */
    int i;
    int pid = 0;
    if (((used = malloc((n+1)*sizeof(int))) == NULL)||
        ((h = malloc(n*sizeof(int))) == NULL))
    /* More memory allocation and error protection. */
    {
        perror("Memory allocation error!");
        exit(2);
    }
    /* 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.*/
    for (i = 1; i <= (n+1)/2; i++)
    {
        if ((pid = fork()) < 0)
        {                       /* Fork, or quit. */
            perror("Fork failed!");
            exit(1);
        }
        if (pid == 0)
        {                       /* The children take this route. */
            int j;
            int count = 1;
            int* list;          /* This stores the list being worked on. */
            if ((list = malloc(n*sizeof(int))) == NULL)
            {
                perror("Memory allocation error!");
                exit(2);
            }
            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;
            /* This starts recursive scanning of the rest of the list.
             * Each child only runs on one fixed first element.*/
            recurse(file, n, size, r, s, used, h, list, count);
            free(list);
            exit(0);                    /* And then the child quits. */
        }
    }
    if (pid != 0)
    /* The parent takes this route. */
    {
		for (i = 1; i <= (n+1)/2; i++)
        /* And waits for all the children to complete. */
		{
			int status;
			wait(&status);
            if (status != 0)
            {
                printf("Caution! Child process terminated abnormally!\n");
            }
		}
    }   /* Then only the parent returns to main to close the log. */
}
void recurse(FILE* file, int n, int size, int r[], int s[],
             int used[], int h[], int list[], int count)
{
    if (count != n)                 /* If the list isn't filled in... */
    {
        int i;
        for (i = 1; i <= n; i++)    /* Look for the next number to add... */
        {
            if ((used[i] == 0)&&
                /* Has this number been used? */
                (h[abs(list[count-1]-i)]==0)&&
                /* Has this difference been used? */
                ((count != s[0]+1)||
                 (abs(list[s[0]]-list[0])==abs(i-list[s[0]])))&&
                /* Does it meet the extra condition for s[0]? */
                ((list[count-1]!=1)||(i==n)||
                 ((count != 1)&&(list[count-2]==n))))
                /* Are 1 and n adjacent? */
            /* If so... */
            {
                /* ...add this number... */
                list[count] = i;
                /* ...note it's been used... */
                used[i]++;
                /* ...note the new difference... */
                h[abs(list[count-1]-i)]++;
                recurse(file, n, size, r, s, used, h, list, count+1);
                /* ...then head deeper in. */
                h[abs(list[count-1]-i)]--;
                /* Before we check the next possibility, un-add this one. */
                used[i]--;
                list[count] = 0;
            }
        }
    }
    else
    /* But if the list is filled in... */
    {
        if (test(size, list, s) == 1)
        /* Then check it for the rest of the s properties. */
        {
            /* If it works, output it. */
            int i;
            /* Since this is being done simultaneously by multiple processes
             * simultaneously, the output must be regulated. I use flockfile
             * to ensure that only one process can output at a time, and
             * fseek to make sure the output is at the end of the log. */
            flockfile(file);
            fseek(file, 0, SEEK_END);
            /* Report a find! */
            fprintf(file, "g=(");
            printf("We got one: (");
            /* And print it to the screen and the log. */
            for (i = 0; i < n-1; i++)
            {
                fprintf(file, "%d ", list[i]);
                printf("%d ", list[i]);
            }
            fprintf(file, "%d) works for r=(", list[n-1]);
            printf("%d)\n", list[n-1]);         /* More info for the log. */
            for (i = 0; i < size-1; i++)
            {
                fprintf(file, "%d ", r[i]);
            }
            fprintf(file, "%d)!\n", r[size-1]);
            /* If the complement won't also be found, calculate and log it
             * as well. */
            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]);
            }
            funlockfile(file);  /* Release the lock once output is complete. */
        }
    }
}
int test (int size, int list[], int s[])  /* Checks for the extra property. */
{
    int i;
    for (i = 1; i < size; i++)
    /* Checks on the rest of s, if |s|>1.
     * (s[0] is checked during list generation.) */
    {
        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 and return 0. */
        }
    }
    return 1;            /* If it has passed all the tests, return 1. */
}
void pSums(int size, int r[], int s[])
/* Makes a partial sum list out of the first passed list,
 * and leaves it in the second 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];
    };
}
void printMan(void)
/* Prints the usage instructions. */
{
    printf("\n");
    printf(" Mathfind program.\n");
    printf(" USAGE: mathfind [-t] <outputfile> [n] [r1 r2 ...]\n");
    printf("   [-t]         - Runs tests instead of normal operation.\n");
    printf("                  Requires <outputfile>, but not [n] or\n");
    printf("                  [r1 r2 ...].  The file mathfind.garbage is\n");
    printf("                  used as scratch.\n");
    printf("   <outputfile> - A file where the output will be written.\n");
    printf("                  The data is appended to the file.\n");
    printf("   [n]          - The value of n.  Must be at least 4.\n");
    printf("   [r1 r2 ...]  - The values of r, delimited by spaces.  Each\n");
    printf("                  value must be at least 3, but the sum of all\n");
    printf("                  of them must be less than n.\n\n");
    printf("   Examples:\n");
    printf("     mathfind try.txt 11 4 5\n");
    printf("       Prints the results for n=11 and r=(4 5) to try.txt\n");
    printf("     mathfind -t test.log\n");
    printf("       Tests the program and stores the results in test.log\n\n");
}
void programTest (FILE* file)
{
    /* The number of tests: */
    int t = 5;
    /* The data for test 1: */
    int ra[] = {3, 3, 3, 3, 3};
    int sa[5];
    /* The data for test 2: */
    int rb[] = {4, 5};
    int sb[2];
    /* The data for test 3: */
    int listc[] = {4, 7, 3, 10, 5, 6, 8, 2, 11, 1, 9};
    /* The data for test 4: */
    int sd[] = {6, 12};
    int listd[] = {4, 13, 2, 16, 1, 14, 7, 10, 5, 15, 3, 11, 9, 8, 12, 6};
    /* The data for test 5: */
    int re[] = {4, 5};
    int se[] = {3, 8};
    int used[12];
    int h[11];
    int i;
    /* Where the data is written to and checked from: */
    FILE* junk = fopen("mathfind.garbage", "w");
    char readLine[50];
    int pass = 1;
    /* TEST 1: check pSums against a known result. */
    pSums(5, ra, sa);
    if ((sa[0] == 2)&&(sa[1] == 5)&&(sa[2] == 8)&&(sa[3] == 11)&&(sa[4] == 14))
    {
        printf("Test 1 of %d passed.\n", t);
        fprintf(file, "Test 1 of %d passed.\n", t);
    }
    else
    {
        printf("Test 1 of %d failed!  Check the pSums subroutine!\n", t);
        fprintf(file, "Test 1 of %d failed!  pSums produced an", t);
        fprintf(file, " incorrect result.\n", t);
    }
    /* TEST 2: check pSums against a known result. */
    pSums(2, rb, sb);
    if ((sb[0] == 3)&&(sb[1] == 8))
    {
        printf("Test 2 of %d passed.\n", t);
        fprintf(file, "Test 2 of %d passed.\n", t);
    }
    else
    {
        printf("Test 2 of %d failed!  Check the 'pSums' subroutine!\n", t);
        fprintf(file, "Test 2 of %d failed!  'pSums' produced an", t);
        fprintf(file, " incorrect result.\n", t);
    }
    /* TEST 3: tests a bad list. */
    if (test(2, listc, sb) == 1)
    {
        printf("Test 3 of %d failed!  Check the 'test' subroutine!\n", t);
        printf("Test 3 of %d failed!  'test' produced a false positive.\n", t);
    }
    else
    {
        printf("Test 3 of %d passed.\n", t);
        fprintf(file, "Test 3 of %d passed.\n", t);
    }
    /* TEST 4: checks a good list. */
    if (test(2, listd, sd) == 1)
    {
        printf("Test 4 of %d passed.\n", t);
        fprintf(file, "Test 4 of %d passed.\n", t);
    }
    else
    {
        printf("Test 4 of %d failed!  Check the 'test' subroutine!\n", t);
        fprintf(file, "Test 4 of %d failed!  'test' produced a false", t);
        fprintf(file, " negative.\n");
    }
    /* TEST 5: look for solutions starting with 4 to n=11, r=(4, 5). */
    listc[1] = 4;
    for (i = 0; i < 11; i++)
    {
        used[i+1] = 0;
        h[i] = 0;
    }
    used[4]++;
    recurse(junk, 11, 2, re, se, used, h, listc, 1);
    fclose(junk);
    /* Examine the logged results to see if they match the expected results. */
    junk = fopen("mathfind.garbage", "r");
    fgets(readLine, 49, junk);
    if(0!=strcmp(readLine, "g=(4 9 3 7 10 2 11 1 8 6 5) works for r=(4 5)!\n"))
        pass = 0;
    fgets(readLine, 49, junk);
    if(0!=strcmp(readLine, "g=(8 3 9 5 2 10 1 11 4 6 7) works for r=(4 5)!\n"))
        pass = 0;
    if (fgets(readLine, 49, junk) != NULL)
        pass = 0;
    if (pass == 1)
    {
        printf("Test 5 of %d passed.\n", t);
        fprintf(file, "Test 5 of %d passed.\n", t);
    }
    else
    {
        printf("Test 5 of %d failed!  Check the 'recurse' subroutine!\n", t);
        fprintf(file, "Test 5 of %d failed!  A run starting at 'recurse'", t);
        fprintf(file, " did not return the expected values.\n", t);
    }
    /* That's it for tests. */
}