From: tjl@cbnews.cb.att.com (timothy.j.lipetz)
Subject: Program for Four Ns (four 2s) puzzle
Organization: AT&T
Date: Thu, 10 Sep 1992 19:52:10 GMT


 
As promissed earlier, here is a program to solve the
four Ns (2,4,9s) puzzle.  It does take a while to run
and I have posted my results in rec.puzzles.
  
Timothy Lipetz
tjl@cbzoo.att.com
   

------------------------------------------------------
To use, set defines for TWOS,FOURS,or NINES and compile
as indicated.
--- cut here ------------------------------------------------------


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

char* copyright = "Copyright 1992, Timothy J. Lipetz";
char* release   = "Program may by copied or modified for non-commercial \
  uses as long as copyright and release are preserved.";

/* To compile ... */
/*	cc fourNs.c -lm -o four2s   (or four4s, etc. depending on defines) */

/* This program looks for solutions to the four 4s (or four 2s or four 9s) */
/* puzzle.  It does this by trying legal combinations and seeing if they */
/* are whole numbers.  Technically, the complete search space is  */
/* infinite (2!!!!!...), however certain assumptions can limit the */
/* space.  Also, the expression is evaluated as it is built up so */
/* whole subtrees of the search can be eliminated early. */
/* Even so, as written this runs about 15 cpu hours on a Sparc. */

/* A good first guess at the total search space is... */
/* 	5 * S^4 * B^3 * U^7 */
/* where S is number of ways to use a single N (e.g. 2 -2 .2 _2(2/9)) */
/* and B is number of binary operators */
/* and U is the number of combinations of ADJACENT unary operators */
/* 		(such as sqrt(N), sqrt(N)!!, etc.) */
/* (note: formats with 22, .22, etc do not add much to the space) */

/* Because, the search space is so dependent on U, I do not use */
/* a general unary negation.  I actually did try a version of this */
/* program with it, but after running a week and still being less */
/* than 10% done, I killed it.  Interestingly, in that whole time */
/* it did not find a single solution that this version had not */
/* found. */

/* To see the assumptions made here, look at... */
/* 1) The tokenlists for singles, doubles, triples (for example the only */
/* 		place unary negation is tried is (-2) ) */
/* 2) The tokenlists for unary and binary operators (for example, no */
/* 		more than two ! or R(sqrt) in adjacent ops, and no */
/* 		sqrts of factorials) */
/* 3) Calls to return in evalnext (for example, divide by 0) */
/* 4) Returns of BAD from sroot, factorial (for example, sqrt of a neg. */
/* 		or 2 ! or (>12)! since 13! is over 6 billion ) */

/* I use double precision and test for "close enough" to integer */
/* results.  This was easier than writing my own rational arithmetic */
/* package (that could handle roots!).  However, some "false positive" */
/* results are possible, where a truly non-integer expression happens */
/* to be within my tolerance test.  The only case of this I have seen */
/* involved a sqrt of a sqrt. */

/* Finally, since it is much easier to do the calculations in */
/* postfix, I choose the easy route and print out the results in */
/* postfix.  Anyone who wants infix output can find the conversion */
/* algorithm in many computer science textbooks. */

/* You can run sort -n on the output (after it is done) for a more useful */
/* ordering. */

/* Timothy J. Lipetz */
/* August 1992 */


/* DEFINE ONLY ONE OF THESE THREE */
#define TWOS
/* #define FOURS */
/* #define NINES */

/* LIMITS ON PRINT OUT */
#define NUMSOLUTIONS 1	/* How many solutions of each number */
#define MININTEREST 1
#define MAXINTEREST 1001

/* #define DEBUG1 */
/* #define DEBUG2 */

#define GOOD 0
#define BAD 1

/* How close does floating pt number have to be to integer */
#define SMALL 0.0000001

struct Stack
{
    double nums[5];     /* never have more than 4 operands */
    int top;  		/* index of last used space */
};

/* this is for a specific token - see 'format' below for token types */
struct Token
{
    int type;
    double num;  /* if type is NUM */
};

struct Expr
{
    char* formatstr;
    struct Stack stack;  	/* for unevaluated NUMs */
    struct Token tokens[15];	/* for specific token list */
    int nexttoken;		/* index of last evaluated */
				/*       token or format char */
};

/* S = single 'N', Double,Triple,BinOp,UnOp */
/*     NOOP=no operation,R=square root,F=factorial*/
typedef enum
{
    SINGLE_Np0 = 0, SINGLE_0pN, SINGLE_0PN, SINGLE_mN,
    DOUBLE_NNp0, DOUBLE_0pNN, DOUBLE_0PNN, TRIPLE,
    B_ADD, B_SUBT, B_MULT, B_DIV, B_EXPON,
    U_NOOP, U_R, U_F, U_RF, U_RR, U_FF, U_RRF, U_RRFF
};

/* ----------------------- */
/* initialize some globals */
/* ----------------------- */

/* this should be parallel to enum above */
char* outstrings[] =
{
#ifdef TWOS
    "2 ", ".2 ", "_2 ", "-2 ", "22 ", ".22 ", "_22 ", "222 ",
#endif
#ifdef FOURS
    "4 ", ".4 ", "_4 ", "-4 ", "44 ", ".44 ", "_44 ", "444 ",
#endif
#ifdef NINES
    "9 ", ".9 ", "_9 ", "-9 ", "99 ", ".99 ", "_99 ", "999 ",
#endif
    "+ ", "- ", "* ", "/ ", "^ ",
    "", "sqrt ", "! ", "sqrt ! ", "sqrt sqrt ", "! ! ",
	    "sqrt sqrt ! ", "sqrt sqrt ! ! ", "BUG IN PROGRAM "
};

struct Token binops[] =
{
    { B_ADD, 0.0 },
    { B_SUBT, 0.0 },
    { B_MULT, 0.0 },
    { B_DIV, 0.0 },
    { B_EXPON, 0.0 },
    { -1, 0.0 }		/* end marker */
};

struct Token unaryops[] =
{
    { U_NOOP, 0.0 },
    { U_R, 0.0 },
    { U_F, 0.0 },
    { U_RF, 0.0 },
    { U_RR, 0.0 },
    { U_FF, 0.0 },
    { U_RRF, 0.0 },
    { U_RRFF, 0.0 },
    { -1, 0.0 }		/* end marker */
};

#ifdef TWOS
struct Token singles[] =
{
    { SINGLE_Np0, 2.0 },		/* N */
    { SINGLE_0pN, 0.2 },		/* .N */
    { SINGLE_0PN, 2.0/9.0 },		/* _N */
    { SINGLE_mN, -2.0 },		/* -N */
    { -1, 0.0 }		/* end marker */
};
struct Token doubles[] =
{
    { DOUBLE_NNp0, 22.0 },		/* NN */
    { DOUBLE_0pNN, 0.22 },		/* .NN */
    { DOUBLE_0PNN, 22.0/99.0 },		/* _NN */
    { -1, 0.0 }		/* end marker */
};
struct Token triples[] =
{
    { TRIPLE, 222.0 },		/* NNN */
    { -1, 0.0 }		/* end marker */
};
#endif
#ifdef FOURS
struct Token singles[] =
{
    { SINGLE_Np0, 4.0 },		/* N */
    { SINGLE_0pN, 0.4 },		/* .N */
    { SINGLE_0PN, 4.0/9.0 },		/* _N */
    { SINGLE_mN, -4.0 },		/* -N */
    { -1, 0.0 }		/* end marker */
};
struct Token doubles[] =
{
    { DOUBLE_NNp0, 44.0 },		/* NN */
    { DOUBLE_0pNN, 0.44 },		/* .NN */
    { DOUBLE_0PNN, 44.0/99.0 },		/* _NN */
    { -1, 0.0 }		/* end marker */
};
struct Token triples[] =
{
    { TRIPLE, 444.0 },		/* NNN */
    { -1, 0.0 }		/* end marker */
};
#endif
#ifdef NINES
struct Token singles[] =
{
    { SINGLE_Np0, 9.0 },		/* N */
    { SINGLE_0pN, 0.9 },		/* .N */
    { SINGLE_0PN, 9.0/9.0 },		/* _N */
    { SINGLE_mN, -9.0 },		/* -N */
    { -1, 0.0 }		/* end marker */
};
struct Token doubles[] =
{
    { DOUBLE_NNp0, 99.0 },		/* NN */
    { DOUBLE_0pNN, 0.99 },		/* .NN */
    { DOUBLE_0PNN, 99.0/99.0 },		/* _NN */
    { -1, 0.0 }		/* end marker */
};
struct Token triples[] =
{
    { TRIPLE, 999.0 },		/* NNN */
    { -1, 0.0 }		/* end marker */
};
#endif

/* S = single 'N', Double,Triple,BinOp,UnOp */
char* formats[] =
{
    "SUSUSUSUBUBUBU",
    "SUSUSUBUSUBUBU",
    "SUSUBUSUSUBUBU",
    "SUSUSUBUBUSUBU",
    "SUSUBUSUBUSUBU",
    "SUSUDUBUBU",
    "SUDUSUBUBU",
    "DUSUSUBUBU",
    "SUSUBUDUBU",
    "SUDUBUSUBU",
    "DUSUBUSUBU",
    "DUDUBU",
    "SUTUBU",
    "TUSUBU",
    0
};

int foundlist[MAXINTEREST];

void addtoken();
void printexpression();
int factorial();
void evalnext();
int sroot();
int factorial();

main()
{
    char** format;
    struct Expr expr;
    int i;

    for(i=0;i<MAXINTEREST;i++)
    {
	foundlist[i] = 0;
    }

    for(format=formats; *format; format++)
    {
#ifdef DEBUG1
	fprintf(stderr,"Doing format `%s'\n", *format);
#endif
	expr.formatstr = *format;
	expr.nexttoken = 0;
	expr.stack.top = -1;
	addtoken(expr);
    }
}

/* The work is done by two routines - addtoken, which understands syntax */
/* of valid postscript expressions, and evalnext, which understands */
/* arithmetic on those expressions.  They are mutually recursive and */
/* pass a structure (not ptr) containing the expression, so they can */
/* use the C stack to traverse the tree of possible expressions. */
/* Early pruning of the tree is done by evalnext as a performance */
/* enhancement. */

void
addtoken(expr)
    struct Expr expr;  /* struct is passed, NOT a pointer */
{
    int next;
    struct Token* availtoklist;
    double temp;
    int itemp;

    next = expr.nexttoken;
    switch(expr.formatstr[next])
    {
    case 'S':
	availtoklist = singles;
	break;
    case 'D':
	availtoklist = doubles;
	break;
    case 'T':
	availtoklist = triples;
	break;
    case 'B':
	availtoklist = binops;
	break;
    case 'U':
	availtoklist = unaryops;
	break;
    case '\0':
	if(expr.stack.top != 0)
	{
	    fprintf(stderr, "Addtoken: extra left in stack on %s\n",
					expr.formatstr);
	    exit(1);
	}
	temp = rint(expr.stack.nums[0]);
	if(fabs(expr.stack.nums[0] - temp) > SMALL)  /* not whole number */
	    return;
	itemp = (int)temp;
	if(itemp < MININTEREST)
	    return;
	if(itemp > MAXINTEREST)
	    return;
	if(foundlist[itemp] >= NUMSOLUTIONS)
	    return;
	foundlist[itemp]++;
	printf(" %d = ", itemp);
	printexpression(&expr);
	fflush(stdout);
	return;
	break;
    default:
	fprintf(stderr,"Addtoken: Bad format char #%d in `%s'\n",
				next, expr.formatstr);
	exit(1);
	break;
    }

    for( ; availtoklist->type >= 0; availtoklist++)
    {
	/* structure assignment */
	expr.tokens[next] = *availtoklist;
#ifdef DEBUG2
	printexpression(&expr);
#endif
	evalnext(expr, availtoklist->type); /* this can recurse back */
    }
}

/* NOTE - the expression is evaluated as it is built up.  That way */
/* we can prune out whole trees of expressions with nosensical (eg .2 ! ) */
/* or nonproductive (eg 2 ! ) components.  A return here , stops  */
/* evaluation of all expressions beginning with the tokens defined */
/* so far.  A call to addtoken continues with next token. */
void
evalnext(expr, type)
    struct Expr expr;
    int type;
{
    int tp;
    struct Stack* s;
    double* nm;
    double temp1, temp2, temp3, temp4;

    s = &expr.stack;
    tp = s->top;
    nm = s->nums;
    switch(type)
    {
    case SINGLE_Np0:
    case SINGLE_0pN:
    case SINGLE_0PN:
    case SINGLE_mN:
    case DOUBLE_NNp0:
    case DOUBLE_0pNN:
    case DOUBLE_0PNN:
    case TRIPLE:
	s->top++;
	tp = s->top;
	s->nums[tp] = expr.tokens[expr.nexttoken].num;
	break;
    case B_ADD:
	temp1 = nm[tp-1] + nm[tp];
	s->top--;
	tp = s->top;
	nm[tp] = temp1;
	break;
    case B_SUBT:
	temp1 = nm[tp-1] - nm[tp];
	s->top--;
	tp = s->top;
	nm[tp] = temp1;
	break;
    case B_MULT:
	temp1 = nm[tp-1] * nm[tp];
	s->top--;
	tp = s->top;
	nm[tp] = temp1;
	break;
    case B_DIV:
	if(nm[tp] == 0.0)
	    return;
	temp1 = nm[tp-1] / nm[tp];
	s->top--;
	tp = s->top;
	nm[tp] = temp1;
	break;
    case B_EXPON:
	if(nm[tp-1] <= 0.0)  /* X^Y and X<=0 */
	    return;
	if(nm[tp] == 1.0)  /* X^1 and (redundant with X*1) */
	    return;
	temp1 = pow(nm[tp-1], nm[tp]);
	s->top--;
	tp = s->top;
	nm[tp] = temp1;
	break;
    case U_NOOP:
	/* no-op */
	break;
    case U_R:
	if(sroot(nm[tp], &temp1) == BAD)
	    return;
	nm[tp] = temp1;
	break;
    case U_F:
	if(factorial(nm[tp], &temp1) == BAD)
	    return;
	nm[tp] = temp1;
	break;
    case U_RF:
	if(sroot(nm[tp], &temp1) == BAD)
	    return;
	if(factorial(temp1, &temp2) == BAD)
	    return;
	nm[tp] = temp2;
	break;
    case U_RR:
	if(sroot(nm[tp], &temp1) == BAD)
	    return;
	if(sroot(temp1, &temp2) == BAD)
	    return;
	nm[tp] = temp2;
	break;
    case U_FF:
	if(factorial(nm[tp], &temp1) == BAD)
	    return;
	if(factorial(temp1, &temp2) == BAD)
	    return;
	nm[tp] = temp2;
	break;
    case U_RRF:
	if(sroot(nm[tp], &temp1) == BAD)
	    return;
	if(sroot(temp1, &temp2) == BAD)
	    return;
	if(factorial(temp2, &temp3) == BAD)
	    return;
	nm[tp] = temp3;
	break;
    case U_RRFF:
	if(sroot(nm[tp], &temp1) == BAD)
	    return;
	if(sroot(temp1, &temp2) == BAD)
	    return;
	if(factorial(temp2, &temp3) == BAD)
	    return;
	if(factorial(temp3, &temp4) == BAD)
	    return;
	nm[tp] = temp4;
	break;
    default:
	fprintf(stderr,"Evalnext: Bad type %d in `%s'\n",
				type, expr.formatstr);
	exit(1);
	break;
    }

    expr.nexttoken++;
    addtoken(expr);  	/* recurse (indirectly) on next token */
}

int
sroot(d, sr)
    double d;
    double* sr;
{
    if(d <= 0.0)  /* X^(1/2) and X<=0 */
	return(BAD);
    if(d == 1.0)  /*  sqrt is noop */
	return(BAD);
    *sr = sqrt(d);
    return(GOOD);
}

int
factorial(d, f)
    double d;
    double* f;
{
    double temp1;
    int itemp1, itemp2;

    temp1 = floor(d);
    if(fabs(d - temp1) > SMALL)  /* not whole number */
	return(BAD);
    itemp1 = (int)temp1;
    if(itemp1 <= 2)  /* X! and X<=0  (or 1,2 which are noops) */
	return(BAD);
    if(itemp1 > 12)  /* too big to compute */
	return(BAD);
    for(itemp2=1; itemp1>0; itemp1--)
	itemp2 *= itemp1;
    *f = itemp2;
    return(GOOD);
}

void
printexpression(e)
    struct Expr* e;
{
    /* print out postfix for now - maybe do infix conversion later */
    int i;
    for(i=0; i<e->nexttoken; i++)
    {
	printf("%s", outstrings[e->tokens[i].type]);
    }
    printf("\n");
}