Cobtribution #098

Contribution for Puzzlet #98

From: Kirk Bresniker <kirkb@rose.hp.com

Dave,

I've been working backwards through your puzzlets pages, and I notice on your solution that you say your code runs very slowly. I'm guessing that a big part of this is the fact that you run through all the numbers from123456 to 987654, and then proceed to check and toss out 864198 of the numbers! There are much better and faster ways to generate these combinations. Now I generally program these exercises on my Unix workstation in C with awk or other small programs to do some of the data reduction,so I don't know if IBasic supports recursion, but that's really fast wayto generate all these cases. Here's a program that I wrote to generate M unique digits in N length sequences:

#include <stdio.h>
#define N 2
#define M 10
int n=N;
int m=M;
int *f;
int *d;
void play(depth)
int depth;
{
   int i;
   if(depth==n) {
    for(i=0;i<n;i++) printf("%d ",d[i]); printf("\n");
   }
   else {
    for(i=0;i<m;i++) {
     if(!f[i]) {
      f[i]=1;
      d[depth]=i;
      play(depth+1);
      f[i]=0;
      }
    }
   }
}

main(argc,argv)
int argc;
char **argv;
{
   if(argc>1) n=atoi(argv[1]);
   if(argc>2) m=atoi(argv[2]);
   d=(int *)malloc(sizeof(int)*n);
   f=(int *)malloc(sizeof(int)*m);
   memset(d,0,n); memset(f,0,m);
   play(0);
   free(d); free(f);
}

The recursive algorithm is to:
1. Check to see if you've picked N numbers, if so then print the result.
2. Otherwise, run through the digits 0 .. M, if M hasn't been used, set a flag and call the routine to pick the next digit then clear the flag.

This routine generates only good values, which I then pipe through thefollowing awk script to weed out the right values:

./varfor4 6 10 | awk '
{a=$1;b=$2;c=$3;d=$4;e=$5;f=$6; r= a*(b^c) + d*(e^f);
if((r>999)&&(r<10000)) {y=sprintf("%d",r);
if(((substr(y,1,1)==substr(y,2,1))) && ((substr(y,2,1)==substr(y,3,1)))

&& ((substr(y,3,1)==substr(y,4,1)))) print $0,y;}}'

This takes 7.3s on my 10 year old 280MHz PA-RISC HP-UX box, of which one 1s is taken up generating all the 151200 valid combinations.

KMB

Kirk, thanks for the idea and the code. I should have thought of recursion for this, but I guess was lazy. I hadn't tried it IBasic before, but I've now developed my own routines which are published in place of the original solution. The program runs 500% faster. It's still slowed down by the need to process each integer to apply the formular, but the actual number-generation is now fast.

Dave.