diff options
Diffstat (limited to 'sc2001.c')
| -rw-r--r-- | sc2001.c | 340 |
1 files changed, 340 insertions, 0 deletions
diff --git a/sc2001.c b/sc2001.c new file mode 100644 index 0000000..a2781b1 --- /dev/null +++ b/sc2001.c @@ -0,0 +1,340 @@ +/* Sim Carol 2001 - By Bill Godfrey. +billg@bacchae.co.uk */ + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <limits.h> +#include <assert.h> + +typedef unsigned long term_t; /* Single term */ + +typedef enum +{ + OP_NULL, /* Terminator sentinel. */ + OP_ADD, /* max + min */ + OP_MUL, /* max * min */ + OP_SUB, /* max - min where (max!=min) */ + OP_DIV /* max / min where (max%min==0) */ +} op_t; + +#define MAX_TERMS 10 /* Yuck. */ + +typedef struct +{ + term_t t1; + term_t t2; + op_t op; +} step_t; + +typedef struct +{ + term_t unused[MAX_TERMS+1]; /* zero term array. */ + step_t steps[MAX_TERMS]; /* .op=OP_NULL term array. */ + term_t target; /* Desired target. */ + term_t result; /* Obtained target, or ULONG_MAX */ +} sol_t; + +term_t distance(term_t targ, term_t result) +{ + return (targ > result)?(targ-result):(result-targ); +} + +size_t count_unused(sol_t *s) +{ + term_t *t=s->unused; + size_t r=0; + + while (*t) + { + ++r;++t; + } + return r; +} + +size_t count_steps(sol_t *s) +{ + step_t *t=s->steps; + size_t r=0; + + while (t->op != OP_NULL) + { + ++r;++t; + } + return r; +} + +term_t do_step(step_t *s) +{ + term_t r; + + assert(s->t1 >= s->t2); + + switch (s->op) + { + case OP_ADD: + r=s->t1+s->t2; break; + case OP_MUL: + r=s->t1*s->t2; break; + case OP_SUB: + r=s->t1-s->t2; break; + case OP_DIV: + r=s->t1/s->t2; break; + default: + assert(!!"Shouldn't be here."); + } + return r; +} + +const char ops[]=" +x-/"; /* char array for operator symbols. */ + +#ifdef USE_ASCII +#define LETNUM(a) ('A'+(a)) +#else +const char letters[]="ABCDEFGHIJKLMNOPQRSTUVWXYZ"; +#define LETNUM(a) (letters[a]) +#endif + +void disp_sol(sol_t *sol) +{ + step_t *step=sol->steps; + size_t n=0; + + while (step->op != OP_NULL) + { + printf("[%c] %5lu %c %5lu = %5lu\n",LETNUM(n++),step->t1,ops[step->op],step->t2,do_step(step)); + ++step; + } + printf("-- \n"); +} + +void disp_unused(char*str1,term_t *unu,char*str2) +{ + size_t n; + + printf("%s[ ",str1); + for(n=0; unu[n]; ++n) + { + printf("%lu ",unu[n]); + } + printf("]%s",str2); +} + +void evaluate_sol(sol_t *sol, sol_t *anear) +{ + term_t newdist,olddist; + + olddist=distance(anear->target,anear->result); + newdist=distance(sol->target,sol->result); + + if ((olddist==0) && (newdist==0)) /* We have already had a winner */ + { + if (count_steps(sol) < count_steps(anear)) /* Less steps? */ + { + *anear=*sol; + printf("Improved match.\n"); + disp_sol(anear); + } + } + else if (newdist==0) /* First winner. */ + { + *anear=*sol; + printf("-- \nFirst match.\n"); + disp_sol(anear); + } + else if (newdist < olddist) /* A better nearest. */ + { + *anear=*sol; + } +} + +void update_unused(term_t *unused, size_t num_unused, term_t new, size_t t1, size_t t2) +{ + size_t lastt=num_unused-1; + + unused[t1]=new; /* Replace earlier term with new result. */ + unused[t2]=unused[lastt]; /* Move last in list over t2 */ + unused[lastt]=0; +} + +void go_calc(sol_t *start, sol_t *nearest) +{ + size_t t1,t2,maxt,mint; + term_t max,min; + op_t op; + size_t num_unused; + sol_t newsol; + step_t *newstep; + + num_unused=count_unused(start); + +#if 0 + disp_unused("Consider ",start->unused,"\n"); +#endif + + for (t1=0; t1<(num_unused-1); ++t1) + for (t2=t1+1; t2<num_unused; ++t2) + for (op=OP_ADD; op<=OP_DIV; ++op) + { + if(start->unused[t1] > start->unused[t2]) + { + maxt=t1; mint=t2; + } + else + { + maxt=t2; mint=t1; + } + + max=start->unused[maxt]; + min=start->unused[mint]; + + if ((op == OP_SUB) && (max==min)) + { + break; /* a-b produces a zero. Try next operator */ + } + if ((op == OP_DIV) && (max%min)) + { + break; /* a/b leaves a remainder. */ + } + + if ((op == OP_MUL) && (min==1)) + { + break; /* (a*1)=a wasted step. */ + } + + if ((op == OP_DIV) && (min==1)) + { + break; /* (a/1)=a wasted step. */ + } + + /* Now apply max op min to a copy of start */ + + newsol=*start; + newstep=newsol.steps + count_steps(&newsol); + assert(newstep->op == OP_NULL); + + newstep->t1=max; + newstep->t2=min; + newstep->op=op; /* Write new step in */ + + newstep[1].op=OP_NULL; /* Add sentinel */ + + newsol.result=do_step(newstep); /* Complete newstep */ + +#if 0 + disp_unused("From ",start->unused," "); + printf("(%lu%c%lu)=%lu ", + max,ops[op],min,newsol.result); +#endif + + update_unused(newsol.unused,num_unused,newsol.result,t1,t2); + +#if 0 + disp_unused("to ",newsol.unused,"\n"); +#endif + + evaluate_sol(&newsol,nearest); +#if 0 + printf("IN\n"); +#endif + go_calc(&newsol,nearest); +#if 0 + printf("OUT\n"); +#endif + } + +} + + +int main(int argc, char *argv[]) +{ + int a; + sol_t start={0}; + sol_t nearest={0}; + size_t num_unused=0; /* Number of actual terms. */ + int retval=EXIT_FAILURE; + int targetarg=0; /* Which argv[] points to the one after -t? */ + int state=0; /* 1=seen a -t */ + int toomanywarn=0; /* Has "too many" warning been delivered? */ + + fprintf(stderr,"Sim Carol 2001, By Bill Godfrey.\n"); + + for (a=1; a<argc; ++a) + { + if ((state==0) && (strcmp(argv[a],"-t")==0)) + { + state=1; /* Getting target. */ + } + else if ((state==0) && (num_unused < MAX_TERMS)) + { + term_t newterm=atol(argv[a]); + + if (newterm == 0) + { + fprintf(stderr,"Warning. \"%s\" is not a valid starting number. Ignoring.\n",argv[a]); + } + else + { + start.unused[num_unused++]=atol(argv[a]); + } + } + else if (state==1) + { + if (targetarg) + { + fprintf(stderr,"Warning. Already have a target. Ignoring \"-t\" \"%s\".\n",argv[a]); + } + else + { + start.target=atol(argv[a]); + targetarg=a; + } + state=0; + } + else if ((state==0) && (num_unused == MAX_TERMS) && (!toomanywarn)) + { + fprintf(stderr,"Warning. Too many starting numbers. Ignoring all after %s.\n",argv[a]); + toomanywarn=1; + } + } + + if (targetarg == 0) + { + fprintf(stderr,"Error. No target specified.\n"); + goto tidyup; + } + + if (start.target == 0) + { + fprintf(stderr,"Error. \"%s\" is not a valid target.\n",argv[targetarg]); + goto tidyup; + } + + if (num_unused <2) + { + fprintf(stderr,"Error. Not enough starting numbers.\n"); + goto tidyup; + } + + start.unused[num_unused]=0; /* terminate the arrays */ + start.steps[0].op=OP_NULL; + + nearest.result=ULONG_MAX; /* Our first attempt has a long way to go. */ + + go_calc(&start,&nearest); + + { + term_t dist=distance(nearest.target,nearest.result); + + if (dist) + { + printf("Nearest answer %lu from target.\n",dist); + disp_sol(&nearest); + } + } + + retval=EXIT_SUCCESS; + tidyup: + + return retval; +} |