path: root/sc2001.c

/* 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;
}