A coding exercise

[Richard Harter]

In article <77200036 at p.cs.uiuc.edu> kenny at p.cs.uiuc.edu writes:

	In a previous Kenny considered the problem of printing
all of the node indices of a hypercube where the number of dimensions
is not fixed in advance.  He started with a recursive formulation
and went through a number of transformations.  He presents the
following as a penultimate form (always leaving room for an
ultimate form).

>		PROGRAM 7A.
>[main program still hasn't changed]
>grdgen (df, nlev)
>     register int df;		/*  no. of degrees of freedom */
>     register int nlev;		/*  no. of levels each df */
>{
>  register int i;
>  register int j;
>  register int totaldfm1 = df - 1;
>  static int value [MAXDF];	/* to hold current values of all df's */
>
>  for (;;) {
>    while (df >= 0)		/* Set up initial values */
>      value [df--] = 0;
>
>    for (j = 0; j < totaldfm1; ++j)	/* Print a node */
>      printf ("%d ", value [j]);
>    printf ("%d\n", value [j]);
>
>    do {			/* Develop another node */
>      if (df >= totaldfm1) return;
>      i = value [++df] + 1;
>    } while (i >= nlev);
>    value [df--] = i;
>  }
>}

I must admit that I perused the original long article but did not
follow it in detail.  The problem piqued my interest, so I set down
to solve it de novo.  My first thought was not, how can I set this up
as a simple recursion, but rather what is this problem like?  And the
answer immediately sprang to mind -- this is like an odometer turning
over the miles.  With this in mind I wrote the following in about 5
minutes:

doohickey(n,m)
  int n;                           /* No of dimensions              */
  int m;                           /* Max range on each dimension   */
{
  int i;                           /* Loop index                    */
  int w;                           /* Index being altered           */
  int *v;                          /* Array of indices              */
  int *vp;                         /* Ptr for print loop            */
  char *malloc();                  /* Old faithful storage allocator*/

  v = (int *)malloc(n*sizeof int); /* Get space for indices array   */
  for (i=n,vp=v;i>0;i--) *vp++ = 0;/* Initialize indices to zero    */

  for (;;) {                       /* Loop until all done           */
    for (i=n-1,vp=v;i>0;i--) printf("%d ",*vp++) /* Print n-1 v's   */
    printf("%d\n",*vp);            /* Print last with line feed     */
    w = n-1;                       /* Point to last index           */
    v[w]++;                        /* Advance last index            */
    while (v[w]>=m) {              /* Rollover loop                 */
      v[w] = 0;                    /* Roll current index over to 0  */
      w--;                         /* Next lower index              */
      if (w<0) break;              /* Indices exhausted, all done   */
      v[w]++;                      /* Advance current index         */
      }                            /* End rollover loop             */
    if (w<0) break;                /* Escape outer loop if done     */
    }                              /* End of do-all loop            */
  }                                /* End of procedure doohickey    */

Initial comments:  This is, I submit, clearer than Kenny's 7A.  There
is an immediate intuitive model of what is happening and why.  In fact,
I do not find 7A clear at all -- a quick reading says that you reset
the value array back to zero each time, and that there is no escape 
from the outer loop.  On a more careful reading you see that a return
is used as an escape (one if in the above can be avoided by using a
return as a multilevel break), and that the variable df bounces around.
I don't much like this -- I like my variables to have well defined
unique meanings, specified in the documentation, and there is no
such specification in 7A.  More to the point, it is in no way clear
to me that 7A is correct!  I assume that it is, since it was produced
by a series of transformations from an originally correct program.  But
if I saw it as original code I would have to work throught it very
carefully to have confidence in it.

On using procedures:  Both the above and 7A use a procedure.  For this
limited problem, that is fine.  However this is a general problem --
provide a coding technique for handling indexed loops with a variable
number of dimensions, with an inner core of action.  One does better,
I think, in working out this kind of problem by not gratuituously
assuming that you can put it in a procedure.

Radical simplification:  When I wrote down the above, I was not much
satisfied with it, because there are several duplications in it.  I
suspected there must be a simpler way.  One way to look for such things
is to translate all the logic into goto's, simplify, and translate back
into structured code.  Another few minutes produced, for the loop logic,

next:                                 /* Loop point for next case      */
  ... action to be performed ...
  w = n-1;                            /* Start with last index         */
rollover:                             /* Loop point for index push     */
  if ((++v[w])<m) goto next;          /* Advance value, check range    */
  v[w--] = 0;                         /* Reset current index           */
  if (w >= 0) goto rollover;          /* Next lower index is legit     */
                                      /* This is fallthru when done    */

Now this is quite pretty in its way -- the logic is clear and the number
of statements is a minimum.  Perhaps Mr. Rubin will want to use this as
an example in his campaign on behalf of the goto :-)!  I will leave the
translation of this code back into goto-less C as an exercise for the 
reader.
-- 

In the fields of Hell where the grass grows high
Are the graves of dreams allowed to die.
	Richard Harter, SMDS  Inc.