Path: utzoo!attcan!uunet!lll-winken!lll-tis!ames!mailrus!tut.cis.ohio-state.edu!bloom-beacon!husc6!cca!g-rh From: g-rh@cca.CCA.COM (Richard Harter) Newsgroups: comp.lang.c Subject: A coding exercise Message-ID: <30563@cca.CCA.COM> Date: 8 Jul 88 04:57:30 GMT References: <2742@utastro.UUCP> <77200036@p.cs.uiuc.edu> Reply-To: g-rh@CCA.CCA.COM.UUCP (Richard Harter) Organization: Computer Corp. of America, Cambridge, MA Lines: 118 In article <77200036@p.cs.uiuc.edu> kenny@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])= 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.