Article 4818 of comp.programming:
Path: news.u.washington.edu!netnews.nwnet.net!ogicse!decwrl!concert!news-feed-1.peachnet.edu!darwin.sura.net!cs.ucf.edu!schnitzi
From: schnitzi@cs.ucf.edu (Mark Schnitzius)
Newsgroups: comp.lang.c,comp.programming,rec.puzzles
Subject: CONCISENESS CONTEST ROUND 2 -- first runner up
Message-ID: <schnitzi.737039339@eola.cs.ucf.edu>
Date: 10 May 93 13:08:59 GMT
Article-I.D.: eola.schnitzi.737039339
Sender: news@cs.ucf.edu (News system)
Distribution: comp,rec
Organization: University of Central Florida
Lines: 220
Xref: news.u.washington.edu comp.lang.c:49006 comp.programming:4818 rec.puzzles:19260


int n, work[20], top, *ops;

/* layout of work array (where N is the number of input values; note
** that during the most of the code that follows, the variable n holds
** the value N+1):
**   0        : target value
**   1..N     : values to be used in expression
**   N+1..N+5 : stack area for evaluating expressions
**   N+6..10  : unused (this area empty for N == 5)
**   11..19   : record preorder traversal of expression tree
** top is used to index into the stack area; ops points into the
** preorder traversal.
*/

/* note that we do not include stdio.h because doing so would strap us
** with the macro version of putchar, and that would preclude the
** conciseness optimization we made in printexp() below, which hides
** the right paren for putchar within another macro.  This way,
** putchar is implicitly declared as an extern function, so the
** library version gets called.
*/
/* #include <stdio.h> */


#define SCANF scanf("%d",

main()
{
  /* the following loop is very convoluted by the drive to conserve
  ** tokens.  The outer while loop stops when scanf fails to read an
  ** integer from stdin.  When it succeeds, the value goes into top,
  ** (though it will eventually be transferred into n (sort of)).  If
  ** not for conciseness, the value would go directly into n, where it
  ** belongs.  Instead, n ends up with the value 1 (value of the true
  ** boolean expression).
  */
  while (n = SCANF &top) == 1)
    /* Here's the inner loop.  For now, concentrate on the first and
    ** last lines... ignoring what comes after "||", the while loop
    ** repeats top (which should be n) times, and each time it reads a
    ** new integer from stdin.  The values are stored in the work
    ** array in consecutive locations, starting with 1 (if not for
    ** conciseness that would have been 0).  When all values have been
    ** read, top is -1, n is one more than the number of input values,
    ** and the input values are stored in work[1...n-1].  Then the
    ** first piece of the while condition fails, so the following
    ** alternative is executed (it would be in code following the loop
    ** if not for conciseness).
    */
    while (top-- ||
      /* This code should be thought of as following the while loop,
      ** as it only executes after the last real iteration.  On entry,
      ** we have top = -1, and n-1 input values in work[1..n-1].  We
      ** scan the target number into work[0], and then invoke testeval
      ** to search for solutions.  The first arg to testeval is a bit
      ** mask that looks like 0...01...10, with a 1 in positions
      ** 1...n-1 (counting from the right, starting with 0).  Thus
      ** there's a 1 bit corresponding to every position in the work
      ** array holding an input value.  The scanf that reads in the
      ** target value returns 1, and that's used in building the mask.
      ** The other arguments are unused, and their sole purpose is to
      ** initialize some things before testeval actually starts
      ** computing, namely: ops will point to the top end of the work
      ** array, where the successful expression, if any, will be
      ** recorded; and top is made to index the element of the work
      ** array just prior to the area that will be used as an
      ** expression evaluation stack (if not for conciseness, this
      ** stack would be its own array, and top would be set to -1).
      ** The return value of testeval is used to select a printf
      ** format string corresponding to success or failure, and in the
      ** former case, printexp is also called in the process, to print
      ** the winning expression.  Note that printf will return a
      ** nonzero value, so !printf(...) will return zero, causing the
      ** inner while loop to terminate in either case, as required.
      */
      !printf(testeval((SCANF work)<<n)-2, ops=work+19, top += n)
          ? printexp(0), "=%d\n"
 	  : "TARGET NUMBER UNREACHABLE\n", *work))
        SCANF work+n++);		/* the inner loop body */
}


/* testeval takes two legitimate args (y is just a local int):
** avail = mask showing which input values are still unused in the
**    current expression: bit (1 << i) on means vals[i] has not yet
**    been used and can therefore be pushed onto the stack (i ranges
**    from 1..n-1)
**  x = value currently at top of stack (or arbitrary value if stack
**    is empty)
**
** We build all possible expressions using the n input values, and
** evaluate each one to see whether it equals the target.  If so, we
** return through the recursion with the ops pointer intact.
**
** The evaluation is performed by means of a stack, which lives within
** the work array, just past the last input value.  Each operation
** either pushes a value onto the stack, or pops two values, applies a
** binary operator to them, and pushes the result.  The expression
** itself is recorded in the right portion of the work array,
** addressed via the pointer "ops".  Each operation is recorded either
** as a non-negative integer (meaning that value was pushed onto the
** stack) or a negative integer encoding a binary operation: -1 => +,
** -9 => -, -17 => *, -25 => /.  (The codes are spaced by eight in
** order to support the parenthesizing code in printexp() below.)
** Following a successful evaluation, ops points to the beginning of a
** preorder traversal of the expression tree.
**
** Note: if op codes could be 0, -8, -16, -24, we could save two
** tokens in printexp() below.  But that would mean additions and
** pushes of zeros would be indistinguishable.  The original problem
** statement was self-contradictory as to whether zero input values
** need be handled, but the contest moderator clarified in the
** affirmative.
**/

#define SETTOP , work[top] =
#define TRYLEFT testeval(avail SETTOP x
#define TRYRIGHT y, *ops-- -= 8) ||

testeval(avail,x)
{
  int y = n;
  top++;

  /* first see if there are any unused values to push */
  while (y--)
    if (avail & 1<<y && testeval(avail ^ 1<<y SETTOP *ops-- = work[y]))
      return 1;

  /* no luck pushing new values... if there are at least */
  /* two values on the stack, try reducing by applying a binary op */
  return --top > n ? y = work[--top], *ops = 7,
    TRYLEFT + TRYRIGHT TRYLEFT - TRYRIGHT TRYLEFT * TRYRIGHT
      y && x%y == 0 && TRYLEFT / TRYRIGHT
      /* following case is when all binops failed... fix the stack and fail */
      (ops++ SETTOP y, top++ SETTOP x, 0)
      /* here when the stack had less than two values.  Three cases:
      ** (1) it was empty, in which case avail != 0, and we're not
      ** interested; (2) it contains one element but there are still
      ** numbers to be pushed, in which case avail != 0 and we're not
      ** interested; (3) we bottomed out, and the sole stack element
      ** is the value of the current expression, in which case avail
      ** == 0 and we're interested
      */
      : ops++ && !avail && x == *work;
}

/* printexp prints the expression stored in the top of the work array,
** starting at the element pointed to by ops. If the element in this
** position is the encoding of a binary operator, printexp is called
** twice recursively to print the subexpressions, with the operator
** printed between the recursive calls.  Otherwise the value in the
** ops array is printed as a decimal integer.  Each call to printexp
** leaves ops pointing just past the last element that was part of the
** expression printed by this call.
**
** Whether or not a given expression needs to be parenthesized depends
** on the opcode, that of the immediate parent expression, and whether
** this expression is the left or right child of its parent.  The
** rules can be encoded in two 4x4 tables, as shown below.  The
** operations across the top represent the parent's opcode, and those
** along the left side are the child's.
**
**   For left  child:              For right child:
**
**       +  -  *  /                    +  -  *  /
**    +  0  0  1  1     	    +  0  1  1  1
**    -  0  0  1  1     	    -  0  1  1  1
**    *  0  0  0  0     	    *  0  0  0  1
**    /  0  0  0  0     	    /  0  0  0  1
**
** In the above tables, a 0 means the child expression need not be
** parenthesized, and a 1 means parens are needed.
**
** printexp takes a single argument, of which only the low-order four
** bits are used.  Those four bits are the appropriate column from one
** of the above tables.  The parent selects the value to pass on to
** the child by shifting a 32-bit value (the concatenation of the
** columns of the appropriate table with 4-bits of filler per column)
** a number of columns equal to its (negated) opcode.  (This is why
** the opcodes values are spaced at intervals of eight. I could have
** done without the filler bits and spaced the opcodes by four, but
** then the opcodes wouldn't give me the correct shift amount for
** printing the operators themselves (see below), and since I'm going
** with 32-bit ints for that anyway, I can save myself two tokens by
** going with 32 bits here too).  The child uses its own opcode to
** select the appropriate bit from this value and prints parens if the
** bit is 1.  Noe that the top-level call to printexp provides a zero
** arg, so the outermost expression never gets parenthesized.
**
** The operator itself is printed by shifting a 32-bit value
** representing the concatenation of the four possible 8-bit character
** codes.  This saves big over the more straightforward approach of
** indexing a charstring, because the token counter will count a
** 4-char string as 6 tokens, whereas our 32-bit number is a single
** token.  This obviously won't work on 16-bit machines.
**
** The shift amounts are extracted in a rather bizarre fashion.  The
** encodings for the operators are -1, -9, -17, and -25, which we need
** to convert into shift amounts of 0, 8, 16, and 24, respectively.
** So we could negate and subtract one.  But this is identical to
** complementing the bit pattern, assuming 2's complement arithmetic,
** so that's what we do instead.
**/

#define PAREN key & 1<<~op/8 && putchar(
#define OPSHIFT >> ~op ),

printexp(key)
{
  int op = *ops++;
  op < 0 ?
    PAREN '('),
    printexp(0x03030000 OPSHIFT
    putchar(0x2f2a2d2b OPSHIFT	/* this fails with macro version of putchar */
    printexp(0x0f030300 OPSHIFT
    PAREN ')')
  : printf("%d",op);
}


Article 4819 of comp.programming:
Path: news.u.washington.edu!netnews.nwnet.net!ogicse!decwrl!concert!news-feed-1.peachnet.edu!darwin.sura.net!cs.ucf.edu!schnitzi
From: schnitzi@cs.ucf.edu (Mark Schnitzius)
Newsgroups: comp.programming,rec.puzzles
Subject: CONCISENESS CONTEST ROUND 2 -- the winner
Message-ID: <schnitzi.737039434@eola.cs.ucf.edu>
Date: 10 May 93 13:10:34 GMT
Article-I.D.: eola.schnitzi.737039434
Sender: news@cs.ucf.edu (News system)
Distribution: comp,rec
Organization: University of Central Florida
Lines: 109
Xref: news.u.washington.edu comp.programming:4819 rec.puzzles:19261


/****************************************************************************/
/*                                                                          */
/*          Entry for Internet Programming Conciseness Contest #2           */
/*          by Barry Gorman, University of Central Lancashire, UK.          */
/*            [gorman_b@p1.uclan.ac.uk OR barry@sc.lancsp.ac.uk]            */
/*                                                                          */
/*********** WARNING: VERY MACHINE DEPENDENT -- NOT FOR VAX OR PC ***********/
/*                                                                          */
/*  As submitted, this program requires an implementation of C with 32-bit, */
/*  int's, big-endian addressing and ASCII characters.  Otherwise portable. */
/*  Numerous warning messages: due to failure to declare anything properly; */
/*  but this is a competition after all! Inclusion of stdio.h would involve */
/*  the deletion of putchar, which is usually a macro, because of the split */
/*  across macro boundaries of its parameter, which upsets pre-processors.  */
/*                                                                          */
/****************************************************************************/

#define quote(tokens) #tokens                  /* ANSI 'stringise' operator */
#define left_op_right stack[stack_level]       /* counters stacked to print */
#define left          left_op_right/040        /* index to left value, 0..7 */
#define op_bits       (left_op_right & 030)    /* keep these bits unshifted */
#define right         left_op_right%010        /* use / % not >> &, save () */
#define value         stack[10+                /* array of the input values */
#define how_many      value 0xFFFFFFFFUL]      /* main put it into stack[9] */
#define PARAMS        (stack_level,flag_bits){ /* a generic function header */

int target_number, value 9]={0x25640000L, 0x3D25640AL};   /* format strings */

/****************************************************************************/
print_tree PARAMS /*stack_level,flag_bits*/    /* walks the tree and prints */
/****************************************************************************/

#define parenthesis flag_bits                  /* previous operator not a / */\
                 && op_bits<020                /* this operator either *, / */\
                  | flag_bits==030             /* previous operator was a + */\
                 || putchar(                   /* use shortcut eval for !if */

    stack_level<=how_many? printf(stack, value stack_level]):  /* if a leaf */

       (parenthesis '('),                      /* see macro for bit testing */
        print_tree(left,  op_bits|010),        /* use easy parenthesis rule */
        putchar(0x2B2D2A2FL>>op_bits),         /* stdio.h has putc as macro */
        print_tree(right, op_bits),            /* use hard parenthesis rule */
        parenthesis ')'));}                    /* test operator level above */

/****************************************************************************/
try_all PARAMS    /*stack_level,flag_bits*/    /* recurses to do each level */
/****************************************************************************/

#define evaluate_if(operator) op_bits ==       /* code: 0=/%, 1=*, 2=-, 3=+ */\
                             (025 operator 005 /* magic operator converter! */\
                              & 030) ?         /* clean-up, and test result */\
            value left] operator value right]: /* then arithmetic operation */

    left_op_right=0400;                        /* starts the packed counter */

    while(left_op_right--)                     /* test then decrement, loop */

        if (left!=right                        /* start a one-bit mask here */
            &flag_bits>>left                   /* check left operand unused */
            &flag_bits>>right                  /* do same for right operand */

            &&!(value right]                   /* skip for division by zero */
                && evaluate_if(%)              /* get remainder if division */
                !op_bits)                      /* otherwise zero=not divide */

            && (value stack_level]=            /* do the arithmetic at last */
                    evaluate_if(+)             /* if you are going to steal */
                    evaluate_if(-)             /* code, then make sure that */
                    evaluate_if(*)             /* you copy your own program */
                    evaluate_if(/) 0,          /* from the last contest :-) */

                stack_level<how_many*2?        /* alternatives for return 1 */

                    try_all(stack_level+1,     /* go up level, marks=in-use */
                        flag_bits^1<<left^1<<right^1<<stack_level): /* 0/1? */

                    value stack_level]==target_number /* print here if done */
                        && print_tree(stack_level, 030)    /* any non-zero, */
                         | printf(stack+1, target_number)  /* forces return */

                )                              /* should now have a 0/1 for */

            )                                  /* IF result, 25 lines above */

        return 1;                              /* break out of loop if done */

    return 0;}                                 /* this level failed to find */

/****************************************************************************/
main PARAMS       /*stack_level,flag_bits*/    /* read numbers, then search */
/****************************************************************************/

    while(scanf(stack, stack+10-stack_level)==1/* stop when EOF or an error */

        && (stack_level--+how_many             /* relies on init value argc */

            || (target_number=value how_many], /* can't leave this on stack */
                stack_level=                   /* resets it to 1 regardless */
                    try_all(how_many--, 0x1F>>6+stack_level)      /* search */
                    || puts(quote(TARGET NUMBER UNREACHABLE))     /* failed */
                )                              /* end of scan, value is one */

            )                                  /* effective end, scanf loop */

        );}                                    /* effective end, while loop */

/******************************** the end ***********************************/