Contribution
for Puzzlet #98From:
Kirk
Bresniker <kirkb@rose.hp.comDave, 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. |

Site design/maintenance: Dave EllisE-mail me!

Last Updated: September 5th, 2004.