/********************************\
* Copyright, Bill Godfrey, 1997. *
\********************************/

#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <stdlib.h>
#include <ctype.h>

#define MAX_TERMS 10
#define MAX_STEPS (MAX_TERMS-1)
#define NUM_OPS 6

#define FILE_OUT_CMD_OPTION "-f"
#define NO_SCREEN_OUT_OPTION "-q"
#define RESULT_SPEC_OPTION "-t"

#define bool int
#define false 0
#define true (!false)

#define CHECKTERMS
#define CHECKTARGET             /* #undef these to skip the range checks. */

#undef CHECKTERMS
#undef CHECKTARGET

enum
{
        OP_NONE,
                OP_ADD,
                OP_SUBTRACT,
                OP_MULTIPLY,
                OP_DIVIDE,
                OP_R_SUBTRACT,
                OP_R_DIVIDE,
                OP_END
};

typedef long Op;

typedef struct
{
        long t1,t2;
        Op oper;
        long result;
} Calc;

typedef struct th
{
        long terms[MAX_TERMS];          /* End with zero */
        long cecil;
        Calc steps[MAX_STEPS];          /* End with .oper == OP_END */
        long result;

        struct th *next;
} Thread;

typedef struct
{
        Thread underval;
        Thread overval;
        long underdist;
        long overdist;

        bool exact;             /* If true, underval is only relevant item. */

        /* Configuration. */

        FILE *outfile;          /* Pointing to an argv or NULL */
        bool quiet;


} Solutions;

long CalcNumPairs(long numterms)
{
        long n;
        long total=0;

        assert(numterms > 1);

        for (n=1; n != numterms; n++)
        {
                total += n;
        }

        assert(total != 0);

        return total;
}

void InitThread(Thread *t)
{
        long s;
        memset(t,0,sizeof(Thread));
        
        for (s=0; s<MAX_STEPS; s++)
        {
                t->steps[s].oper=OP_END;
        }
}
void InitSolutions(Solutions *s)
{
        memset(s,0,sizeof(Solutions));
}

long CountTerms(Thread *src)
{
        long n;

        assert(src != NULL);

        for (n=0; src->terms[n] != 0; n++);

        return n;
}

size_t SpaceNeededForForks(Thread *src)
{
        long numpairs; 
        long numcalcs;
        size_t spacereq;
        assert(src != NULL);

        numpairs=CalcNumPairs(CountTerms(src));
        numcalcs=numpairs*NUM_OPS;

        numcalcs++;
        numcalcs++;

        spacereq=numcalcs*sizeof(Thread);

        return spacereq;
        
}

bool DoCalc(Calc *src)
{
        if (src->oper == OP_ADD)
        {
                src->result=src->t1+src->t2;
        }
        else if (src->oper == OP_SUBTRACT)
        {
                if (src->t1 < src->t2)          /* -ve or zero? */
                {
                        src->result=0;
                        return false;
                }
                src->result=src->t1 - src->t2;
        }
        else if (src->oper == OP_MULTIPLY)
        {

                if ((src->t1 == 1) || (src->t2 == 1) || (src->t1 == 0) || (src->t2 == 0))
                {
                        return false;
                }                                       /* Multiply by zero or one? */
                
                src->result = src->t1 * src->t2;

        }
        else if (src->oper == OP_DIVIDE)
        {
                if ((src->t1 == 1) || (src->t2 == 1) || (src->t1 == 0) || (src->t2 == 0))
                {
                        return false;
                }                                       /* Divide by zero or one? */
                
                if ((src->t1 % src->t2) != 0)   /* Non-zero remainder. */
                {
                        src->result=0;
                        return false;
                }

                src->result = src->t1 / src->t2;
        }
        else if (src->oper == OP_R_SUBTRACT)
        {
                if (src->t1 > src->t2)          /* -ve or zero. */
                {
                        src->result=0;
                        return false;
                }
                src->result=src->t2 - src->t1;
        }
        else if (src->oper == OP_R_DIVIDE)
        {

                if ((src->t1 == 1) || (src->t2 == 1) || (src->t1 == 0) || (src->t2 == 0))
                {
                        return false;
                }                                       /* Divide by zero or one? */
                
                if ((src->t2 % src->t1) != 0)   /* non-zero remainder. */
                {
                        src->result=0;
                        return false;
                }

                src->result = src->t2 / src->t1;
        }
        else
        {
                return false;
        }

        return true;
}

void CopyThread(Thread *src, Thread *dst)
{
        long tnum;
        long snum;
        
        assert(src != NULL);
        assert(dst != NULL);

        for(tnum=0; tnum < MAX_TERMS; tnum++)
        {
                dst->terms[tnum] = src->terms[tnum];
        }

        for(snum=0; snum < MAX_STEPS; snum++)
        {
                dst->steps[snum].t1 = src->steps[snum].t1;
                dst->steps[snum].t2 = src->steps[snum].t2;
                dst->steps[snum].oper = src->steps[snum].oper;
                dst->steps[snum].result = src->steps[snum].result;
        }

        dst->result = src->result;
        dst->cecil = src->cecil;
}

void AddCalc(Thread *list, Calc *item, long first, long second)
{
        long n=0;
/*      long first=-1,second=-1; */
        long s,d;

        assert(list != NULL);
        assert(item != NULL);

        assert(item->t1 != 0);
        assert(item->t2 != 0);

        assert(first != second);
        assert(first >= 0);
        assert(second >= 0);

        s=CountTerms(list)-1;

        list->terms[first]=item->result;                /* New result replaces first term. */

        if (second == s)
        {
                list->terms[s]=0;       /* Lost the last one. */
        }
        else 
        {
                list->terms[second]=list->terms[s];             /* Last term replaces second */
                list->terms[s]=0;                                               /* Lose the last one, since copied. */
        }
        
        for (d=0; list->steps[d].oper != OP_END; d++);  /* d points to vacant slot. */
        
        memcpy(&list->steps[d], item, sizeof(Calc));

        list->result=item->result;
}

long ForkThreads(Thread *src, Thread **head)
{
        Thread *newhead;
        long numterms;
        long numThreads=0;
        Calc aCalc;
        long first,second;
        Op op;

        assert(head != NULL);
        assert(src != NULL);
        
        numterms=CountTerms(src);

        assert(numterms >= 2);

        for (first=0; first < (numterms-1); first++)    /* For each first term. */
        {
                for (second=(first+1); second < numterms; second++)             /* For each second term. */
                {
                        assert(first < second);
                        assert(first < numterms);
                        assert(second < numterms);

                        for (op= OP_ADD; op < OP_END; op++)             /* For each option. */
                        {
                                bool valid;

                                aCalc.oper=op;
                                aCalc.t1=src->terms[first];
                                aCalc.t2=src->terms[second];

                                valid=DoCalc(&aCalc);

                                if (valid)
                                {
                                        newhead=(Thread*)malloc(sizeof(Thread));
                                        assert(newhead != NULL);

                                        CopyThread(src,newhead);
                                        AddCalc(newhead,&aCalc,first,second);

                                        newhead->next=(*head);
                                        (*head)=newhead;

                                        numThreads++;
                                }
                        }
                }
        }

        return numThreads;
}

void DisplaySolution(Thread *src, Solutions *sols)
{
        long s;
        FILE *f;

        f=sols->outfile ? sols->outfile : stdout;

        for (s=0; src->steps[s].oper != OP_END; s++)
        {
                switch (src->steps[s].oper)
                {
                case OP_ADD:
                        fprintf(f,"%c: %d + %d = %d\n", s+'A', src->steps[s].t1, src->steps[s].t2, src->steps[s].result);
                        break;
                case OP_SUBTRACT:
                        fprintf(f,"%c: %d - %d = %d\n", s+'A', src->steps[s].t1, src->steps[s].t2, src->steps[s].result);
                        break;
                case OP_MULTIPLY:
                        fprintf(f,"%c: %d * %d = %d\n", s+'A', src->steps[s].t1, src->steps[s].t2, src->steps[s].result);
                        break;
                case OP_DIVIDE:
                        fprintf(f,"%c: %d / %d = %d\n", s+'A', src->steps[s].t1, src->steps[s].t2, src->steps[s].result);
                        break;
                case OP_R_SUBTRACT:
                        fprintf(f,"%c: %d - %d = %d\n", s+'A', src->steps[s].t2, src->steps[s].t1, src->steps[s].result);
                        break;
                case OP_R_DIVIDE:
                        fprintf(f,"%c: %d / %d = %d\n", s+'A', src->steps[s].t2, src->steps[s].t1, src->steps[s].result);
                        break;
                default:
                        assert(1==0);
                }
        }

        fprintf(f,"--END--\n");
}
                        

void FreeThreadList(Thread *head)
{
        Thread *curr=head;
        Thread *next;

        while (curr != NULL)
        {
                next=curr->next;
                free(curr);
                curr=next;
        }
}

void Go(Thread *t,Solutions *sols)
{
        Thread *head, *curr;
        long numthreads;

        if (CountTerms(t) < 2)
        {
                return;         /* Out of terms. */
        }


        head=NULL;
        numthreads=ForkThreads(t,&head);

        curr=head; 
        while (curr != NULL)
        {
                if (curr->result == curr->cecil)
                {
                        DisplaySolution(curr,sols);
                }

                curr=curr->next;
        }

        for (curr=head; curr != NULL; curr=curr->next)
        {
                if (curr->result != curr->cecil)
                {
                        Go(curr,sols);
                }
        }

        FreeThreadList(head);
}


int main(int argc, char **argv)
{
        Thread root;
        Solutions sols;
        long n;
        int arg;
        long numterms=0;

        InitThread(&root);
        InitSolutions(&sols);

/*      printf("Enter six numbers:");
        scanf("%d%d%d%d%d%d",&root.terms[0],&root.terms[1],&root.terms[2],&root.terms[3],&root.terms[4],&root.terms[5]);
*/

        if (argc == 1)
        {
                /* Syntax text. */
                return 1;
        }

        for (arg=1; arg <argc; arg++)
        {
                if (strcmp(argv[arg], "-f") == 0)
                {
                        arg++;
                        if (arg == argc)
                        {
                                fprintf(stderr,"Error. No file specified.\n");
                                return 1;
                        }
                        sols.outfile=fopen(argv[arg],"w");
                        if (sols.outfile == NULL)
                        {
                                fprintf(stderr,"Error. Cannot open. \"%s\".\n",argv[arg]);
                                return 1;
                        }
                }
                else if (strcmp(argv[arg], "-q") == 0)
                {
                        sols.quiet=true;
                }
                else if (strcmp(argv[arg], "-t") == 0)
                {
                        arg++;
                        if (arg == argc)
                        {
                                fprintf(stderr,"Error. No target specified.\n");
                                if (sols.outfile != NULL)
                                        fclose(sols.outfile);
                                return 1;
                        }
                        root.cecil=atol(argv[arg]);
                }
                else if (isdigit(*(argv[arg])))
                {
                        root.terms[numterms]=atol(argv[arg]);

                        if (root.terms[numterms] != 0)
                        {
                                numterms++;
                        }

                        if (numterms == (MAX_TERMS-1))
                        {
                                fprintf(stderr,"Error. Too many starting terms.\n");
                                if (sols.outfile != NULL)
                                        fclose(sols.outfile);
                                return 1;
                        }
                }
        }

        if (numterms == 0)
        {
                fprintf(stderr,"Error. No starting terms.\n");
                if (sols.outfile != NULL)
                        fclose(sols.outfile);
                return 1;
        }


#ifdef CHECKTERMS
        for (n=0; n < numterms; n++)
        {
                if ((root.terms[n] <= 0) || (root.terms[n] >= 100))
                {
                        fprintf(stderr,"Error. Starting term #%d out of range.\n", n+1);
                        if (sols.outfile != NULL)
                                fclose(sols.outfile);
                        return 1;
                }
        }

#endif

/*      printf("Enter target:");
        scanf("%d",&root.cecil);
*/

#ifdef CHECKTARGET

        if ((root.cecil <= 99) || (root.cecil >= 1000))
        {
                fprintf(stderr,"Error. Bad target.\n");
                if (sols.outfile != NULL)
                        fclose(sols.outfile);
                return 1;
        }
#endif

        Go(&root,&sols);

        printf("Done.\n");

        if (sols.outfile != NULL)
                fclose(sols.outfile);

        return 0;
}