digits: a C program to help you solve digits puzzles.

/*

digits by D. Constales (dcons@world.std.com).

Did you realize that 6 * 3 ^ 9 - 54 * 2187 = 0 ?

This program can help you find such interesting arithmetical
combinations which involve each of the digits 0,1,...,9 exactly once.

Compile this C program and run it e.g. by

./digits '.*.^.-...*....'

to get:

.*.^.-...*.... 6*3^9-054*2187

i.e. the equation A*B^C-DEF*GHIJ=0 has only one solution if the letters
must be the ten digits in some order.

You can use + - * / ^ ( and ) in the expressions. The digits are
represented by dots. Try out e.g. (.+..)^.-......, etc.

Warning: the answers digit provides are *suggestions* in that
integer overflow is not acted upon (to prevent speed penalties). If
a solution includes large intermediate numbers, make sure to check it
using a multi-precision tool like bc!

*/


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

static char const *prog;	/* name of this program (for error msgs) */
static char const *text;	/* text of current problem */
static char const *cur;		/* cursor into this text for scan/parse */
static jmp_buf jmpbuf;		/* jump buffer to abort parsing at errors */
static char digits[10];		/* array of chars to be permuted */

typedef unsigned char token_t;	/* type for tokens and ops */

/* ops part */
/* opcodes for the supported operations and for tokens like ( and ) */

#define ADD ((token_t)11)
#define SUB ((token_t)12)
#define MUL ((token_t)13)
#define DIV ((token_t)14)
#define POW ((token_t)15)
#define CHS ((token_t)16)
#define LPR ((token_t)17)
#define RPR ((token_t)18)

/* max number of ops allowed per problem */

#define MXOPS 100

/* the tokens of this problem (for printing out the answers) */
static token_t tks[MXOPS];
static int nxtk;

/* the ops of this problem */
static token_t ops[MXOPS];
static int nxtop;

/* add a token if therés space left */
static void
addtok (token_t const v)
{
  if (nxtk >= MXOPS)
    {
      fprintf (stderr,
	       "%s: \"%s\": error (at position %d): too many tokens.\n",
	       prog, text, cur - text);
      longjmp (jmpbuf, 1);
    }
  else
    tks[nxtk++] = v;
}

/* add an op if therés space left */
static void
addop (token_t const v)
{
  if (nxtop >= MXOPS)
    {
      fprintf (stderr,
	       "%s: \"%s\": error (at position %d): too many operations.\n",
	       prog, text, cur - text);
      longjmp (jmpbuf, 1);
    }
  else
    ops[nxtop++] = v;
}

/* integer power, ignoring overflows */
static int
mypow (int x, int y)
{
  int r = 1;
  while (y > 0)
    {
      if (y & 1)
	r *= x;
      y >>= 1;
      x *= x;
    }
  return r;
}

/* compute the value of a sequence of ops (given the current permutation
   of digits) */
static int
opexec (void)
{
  int j = 0;
  token_t *p = ops;
  int stack[MXOPS];
  int stktop = -1;

  while (1)
    {
      int w = 0;
      switch (*p++)
	{
	case 0:
	  return stack[0];

	case 10:
	  w = digits[j++];
	case 9:
	  w = 10 * w + digits[j++];
	case 8:
	  w = 10 * w + digits[j++];
	case 7:
	  w = 10 * w + digits[j++];
	case 6:
	  w = 10 * w + digits[j++];
	case 5:
	  w = 10 * w + digits[j++];
	case 4:
	  w = 10 * w + digits[j++];
	case 3:
	  w = 10 * w + digits[j++];
	case 2:
	  w = 10 * w + digits[j++];
	case 1:
	  stack[++stktop] = 10 * w + digits[j++];
	  break;

	case ADD:
	  stack[stktop - 1] += stack[stktop];
	  stktop--;
	  break;

	case SUB:
	  stack[stktop - 1] -= stack[stktop];
	  stktop--;
	  break;

	case MUL:
	  stack[stktop - 1] *= stack[stktop];
	  stktop--;
	  break;

	case DIV:
	  if (stack[stktop] == 0)
	    return -12345;
	  stack[stktop - 1] /= stack[stktop];
	  stktop--;
	  break;

	case POW:
	  stack[stktop - 1] = mypow (stack[stktop - 1],
				     stack[stktop]);
	  stktop--;
	  break;

	case CHS:
	  stack[stktop] = -stack[stktop];
	  break;

	default:;		/* cannot happen */
	}
    }
  return stack[0];
}

/* parser part */

/* current token */
static token_t tok;

/* total number of dots encountered */
static int dots;

/* scan next token from text at cur */
static void
scan (void)
{
  while (isspace (*cur))
    cur++;

  switch (*cur++)
    {
    case '\0':
      tok = 0;
      cur--;
      break;

    case '+':
      tok = ADD;
      break;

    case '-':
      tok = SUB;
      break;

    case '*':
      tok = MUL;
      break;

    case '/':
      tok = DIV;
      break;

    case '^':
      tok = POW;
      break;

    case '(':
      tok = LPR;
      break;

    case ')':
      tok = RPR;
      break;

    case '.':
      tok = 1;
      while (*cur == '.')
	{
	  cur++;
	  tok++;
	}
      dots += tok;
      if (dots > 10)
	{
	  fprintf (stderr,
		   "%s: \"%s\": error (at position %d): too many \"...\".\n",
		   prog, text, cur - text);
	  longjmp (jmpbuf, 1);
	}
      break;

    default:
      fprintf (stderr,
	  "%s: \"%s\": error (at position %d): unknown character \"%c\".\n",
	       prog, text, cur - text, cur[-1]);
      longjmp (jmpbuf, 1);
    }
  addtok (tok);
}

/* need this declaration for mutual recursiveness */
static void readpm (void);

/* read a kernel (i.e. dots or parenthesised expression) */
static void
readk (void)
{
  switch (tok)
    {
    case LPR:
      scan ();
      readpm ();
      if (tok != RPR)
	{
	  fprintf (stderr,
		   "%s: \"%s\": error (at position %d): missing closing parenthesis.\n",
		   prog, text, cur - text);
	  longjmp (jmpbuf, 1);
	}
      scan ();
      break;
    case 1:
    case 2:
    case 3:
    case 4:
    case 5:
    case 6:
    case 7:
    case 8:
    case 9:
    case 10:
      addop (tok);
      scan ();
      break;
    default:
      fprintf (stderr,
	       "%s: \"%s\": error (at position %d): syntax error.\n",
	       prog, text, cur - text);
      longjmp (jmpbuf, 1);
    }
}

/* read a sequence of exponentials */
static void
readex (void)
{
  readk ();
  while (tok == POW)
    {
      scan ();
      readk ();
      addop (POW);
    }
}

/* read a sequence of products and quotients */
static void
readmq (void)
{
  readex ();
  while (tok == MUL || tok == DIV)
    {
      int s = tok == MUL;
      scan ();
      readex ();
      if (s == 1)
	addop (MUL);
      else
	addop (DIV);
    }
}

/* read a sequence of additions and subtractions */
static void
readpm (void)
{
  int first = 1;

  do
    {
      int s = 1;

      while (tok == ADD || tok == SUB)
	{
	  if (tok == SUB)
	    s = -s;
	  scan ();
	}

      readmq ();

      if (first)
	{
	  if (s == -1)
	    addop (CHS);
	}
      else
	{
	  if (s == -1)
	    addop (SUB);
	  else
	    addop (ADD);
	}

      first = 0;
    }
  while (tok == ADD || tok == SUB);

}

/* parse an expression */
static void
parse (void)
{
  readpm ();
  if (tok != 0)
    {
      fprintf (stderr,
	       "%s: \"%s\": error (at position %d): trailing garbage.\n",
	       prog, text, cur - text);
      longjmp (jmpbuf, 1);
    }
  if (dots < 10)
    {
      fprintf (stderr,
	       "%s: \"%s\": error (at position %d): not enough \"...\".\n",
	       prog, text, cur - text);
      longjmp (jmpbuf, 1);
    }
  addop (0);
}

/* permutation part */

/* test if a permutation satisfies the current problem
   (i.e. the ops yield 0 for it); print if found */
static void
testit (void)
{
  static int counter = 0;
  static int ival = 10000;
  static time_t start;

  if (counter == 0)
    time (&start);
  counter++;

  if (counter % ival == 0)
    {
      time_t now = time (NULL);
      double delta = difftime (now, start);

      if (delta == 0)
	delta = 1;
      fprintf (stderr, "%s: \"%s\": %7d (%5.2f%%)",
	       prog, text, counter,
	       counter * 100.0 / 3628800);

      if (delta >= 4)
	fprintf (stderr, " %7d/s %4ds left.\n",
		 (int) (counter / delta),
		 (int) ((3628800.0 / counter - 1) * delta));
      else
	fprintf (stderr, ".\n");

      if (ival < counter / delta)
	ival *= 10;
      else if (ival > 20 * counter / delta)
	ival /= 10;
    }

  if (0 == opexec ())
    {
      int i;
      int j = 0;

      printf ("%s ", text);
      for (i = 0; i < nxtk; i++)
	switch (tks[i])
	  {
	  case 0:
	    break;
	  case 10:
	    putchar (digits[j++] + '0');
	  case 9:
	    putchar (digits[j++] + '0');
	  case 8:
	    putchar (digits[j++] + '0');
	  case 7:
	    putchar (digits[j++] + '0');
	  case 6:
	    putchar (digits[j++] + '0');
	  case 5:
	    putchar (digits[j++] + '0');
	  case 4:
	    putchar (digits[j++] + '0');
	  case 3:
	    putchar (digits[j++] + '0');
	  case 2:
	    putchar (digits[j++] + '0');
	  case 1:
	    putchar (digits[j++] + '0');
	    break;

	  case ADD:
	    putchar ('+');
	    break;

	  case SUB:
	    putchar ('-');
	    break;

	  case MUL:
	    putchar ('*');
	    break;

	  case DIV:
	    putchar ('/');
	    break;

	  case POW:
	    putchar ('^');
	    break;

	  case LPR:
	    putchar ('(');
	    break;

	  case RPR:
	    putchar (')');
	    break;
	  }
      putchar ('\n');
    }
}

/* permute l chars starting at position p */
static void
doperm (char p[], int const l)
{
  int i;

  for (i = 0; i < l; i++)
    {
      char tmp;

      if (i > 0)
	{
	  tmp = p[0];
	  p[0] = p[i];
	  p[i] = tmp;
	}

      if (l > 2)
	doperm (p + 1, l - 1);
      else
	testit ();

      if (i > 0)
	{
	  p[i] = p[0];
	  p[0] = tmp;
	}
    }
}

/* solve one given problem; parse errors longjmp back into here */
static void
doit (char const s[])
{
  int i;
  for (i = 0; i < 10; i++)
    digits[i] = i;

  if (0 == setjmp (jmpbuf))
    {
      text = s;
      cur = text;
      dots = 0;
      nxtk = 0;
      nxtop = 0;

      scan ();
      parse ();

      doperm (digits, 10);
    }
}

/* solve each of the problems from the command line */
int
main (int argc, char *argv[])
{
  int i;
  prog = argv[0];
  for (i = 1; i < argc; i++)
    doit (argv[i]);

  return 0;
}