Programming Challenge 1

[markiemrboo]

Bah, it's not about competition, it's about a challenge.  I thought I was "winning" til markie showed his little head, but who cares?  I loved markie's post because it made me go back through my own code and work on it more.  I just enjoy having -something- to code.  Now that I'm outta school I don't get challenged with coding projects anymore, and I miss using that part of my brain.  I can't wait til I find something else to work on

526581[/snapback]

 

Know how you feel man. I actually loved my programming Uni assignments

 

I actually think the recursive thing should be slightly faster. It looks simpler.. and it looks like mine is doing a little more work. I am convinced it's just that iostream C++ blah that's making yours slower.

 

Aside from that I managed to shave off 10 seconds from mine on 4 characters last night

[Verran]

Know how you feel man. I actually loved my programming Uni assignments

 

I actually think the recursive thing should be slightly faster. It looks simpler.. and it looks like mine is doing a little more work. I am convinced it's just that iostream C++ blah that's making yours slower.

 

Aside from that I managed to shave off 10 seconds from mine on 4 characters last night

526770[/snapback]

 

Ok, I'm back...

 

I converted the same logistics I used before to C code instead of C++. I am not nearly as good with C as I am with C++, and for that reason, you will see that I blatantly stole a few parts from markie (like the input validation loop) in the interest of time. The actual core logic is all mine though, and really doesn't differ much from its C++ counterpart.

 

After mine was running, I added the windows timing stuff to both mine and markie's and compared. I took 3 times for each program (at 4 chars) and averaged. The tests were run staggered (mine, his, mine, his, mine, his) and with nothing else running, for a fair comparison.

 

Mine:

287842997, 287822949, 287941630

 

avg 287869192 ticks

 

Markie's:

298454854, 302549901, 300309637

 

avg 300438130 ticks

 

 

The difference in averages is: 12568938 ticks

That's about 3 and a half seconds faster on my machine. (about 4.2%)

 

So mine is faster here, however.... This is with markie's code that's posted here. If he has indeed shaved 10seconds from his 4 character time since the code posted here, then he's probably got me beat all over again. Also, my compiled exe is 47.2kb and his is 18.4kb, so he's deinately still got me beat there. But my old C++ one was 466kb, so this is still a vast improvement in that category.

 

I'm pretty amazed though. The exact same logic in C is about 50% faster than in C++ (524131528 ticks) and is 10% the size (exe).

 

Here's my C code:

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <windows.h>

#define BUF_LENGTH 4

int main()
{
  int len;
  int count;
  int* dynword;
  char *buf = NULL;
  LARGE_INTEGER start, end, tps;  
  FILE *fout = NULL;
  
  void checkfunc(int*,int,int&); 
    
  /* Allocate memory for input buffer and zero it */
  buf = (char *)malloc(BUF_LENGTH * sizeof(char));
  assert(buf != NULL);
  memset(buf, 0, BUF_LENGTH * sizeof(char));
  
  do {
       fflush(stdin);
       printf("Please enter the number of letters: ");
       fgets(buf, BUF_LENGTH, stdin);
       len = atoi(buf);
  } while (len < 1 || len > 99);
  
  QueryPerformanceCounter(&start);
  
  fout = fopen("word.txt", "w");
  if (!fout) // Always test file open
       {
       printf("Error opening output file\n");
       return -1;
       }
       
  count = len - 1;          //set count to point at last slot in dyn array
   
  dynword = new int[len];
   
  for(int i=0;i<len;i++)       //Initialize "all a's" array
          dynword[i] = 33;     //
                                
  len = len - 1; // subtract 1 for working with arrays (0 -> len-1)
  
  while (count >= 0)
  {      
          for(int i=0;i<(len+1);i++)
                  fprintf(fout, "%c", dynword[i]);         
          
          if (dynword[len] == 126) 
                  checkfunc(dynword,len,count);                    
          else
                  dynword[len]++;

 fprintf(fout, "\n"); 
 } // end while
 
  fclose(fout);
  
  QueryPerformanceCounter(&end);
  QueryPerformanceFrequency(&tps);
  printf("%d ticks per second\n", tps.QuadPart);
  printf("done in %d ticks\n", (end.QuadPart - start.QuadPart));
  
  system ("pause");
  return 0;
  
}

void checkfunc(int* dynword, int len, int& count)
{
     int p;
           
     if (dynword[(len)] == 126)     
     {    
     dynword[len] = 33;     
     checkfunc(dynword,(len-1),count);  
     
              if (count == len)
                   count--;                                  
     }     
     else
     {
              p = ((dynword[0] - 32)*1.063829);
              dynword[(len)]++;
              if (!len)
                   printf("%d%% done.\n", p);
     }        
            
return;     
}

 

And here's the zip with the exe and source:

[markiemrboo]

I still see C++ kinda stuff in there lol

 

dynword = new int[len];

 

and the reference passing of the int, but still.. converting from the iostream C++ stuff seems to have quickened yours up quite a bit! dang! lol... you might have the better "algorithm" going for you there! *shakes your hand*

 

One of the tweaks I did to mine this morning was obviously obvious and should only apply to the iterative way. There's no need to do that loop every single time you increment the "counter"/"clock" thinger

 

If you could compare yours with http://bone.bone.servebeer.com/WordThingC.zip

 

I would be interested in the results there! Not gonna bother trying to attach that to OCC forums because, well, zips never attach properly for me.. for some reason!

[Verran]

I still see C++ kinda stuff in there lol

 

dynword = new int[len];

 

and the reference passing of the int, but still.. converting from the iostream C++ stuff seems to have quickened yours up quite a bit! dang! lol... you might have the better "algorithm" going for you there! *shakes your hand*

 

One of the tweaks I did to mine this morning was obviously obvious and should only apply to the iterative way. There's no need to do that loop every single time you increment the "counter"/"clock" thinger

 

If you could compare yours with http://bone.bone.servebeer.com/WordThingC.zip

 

I would be interested in the results there! Not gonna bother trying to attach that to OCC forums because, well, zips never attach properly for me.. for some reason!

526823[/snapback]

 

OK, yeah..... you need to post that source here.....

 

That's about THREE TIMES faster than the one you posted before. You did more than you're saying

 

I want to see that SOURCE!!!

[markiemrboo]

OK, yeah.....  you need to post that source here.....

 

That's about THREE TIMES faster than the one you posted before.  You did more than you're saying

 

I want to see that SOURCE!!! 

526826[/snapback]

 

I did another tweak related to writing to the file, which should speed yours up back to .. faster than mine, probably Not using functions in my main loop also took off a little bit of time (but I won't post it like that cause of the messyness..)

 

Oh and changed the stopping condition of the loop.. but I don't expect that sped things up too much.

 

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <windows.h>

/* xx\n\0 */
#define BUF_LENGTH 4
#define LETTERS 93
#define START_CHAR 33

void inline WriteIt(FILE *, int *, int);
int inline Add(int *, int);

/*
* Write out character(s) and calculate (very rough) percentage done.
*/
void inline WriteIt(FILE *fp, int *offsets, int len) {
   int i = 0;
   static int prevOffset = 0;
   char str[len + 1];
   str[len] = '\0';

   /* write out characters, using offsets from START_CHAR (ASCII 33), to file */
   for (i = 0; i < len; i++) {
       str[i] = START_CHAR + offsets[i];
   }
   fprintf(fp, "%s\n", str);

   /*
    * if current percentage is bigger than previous, print out new percentage
    * to the screen!
    */

   if (offsets[0] > prevOffset) {
       printf("%d%% done\n", (int)(((double)offsets[0] / LETTERS) * 100));
       prevOffset = offsets[0];
   }
}

/*
* Increment letter and do all the rollover array stuff
* Example: For 2 characters the offset array would be from
* (0, 0) -> (LETTERS, LETTERS)
*
* A bit like a clock, when the minutes reach 60 the hour gets incremented and
* the minutes get set back to zero.
*/
int inline Add(int *offsets, int len) {
   int i = 0, total = 0;

   /* increment last slot in array */
   offsets[len - 1]++;

   /*
    * Work *backwards* through array checking when to roll over in to the
    * previous slot.
    */
   if (offsets[len - 1] >= LETTERS) {
       for (i = (len - 1); i >= 0; i--) {
           /*
            * An array element needs "rolling over" when the offset in that array
            * is bigger than LETTERS. Since we're working backwards we'll need to
            * check to see if we're already on the first element or not too!
           */
           if (offsets[i] > LETTERS) {
               offsets[i] = 0;
               if (i > 0) offsets[i - 1]++; else offsets[i]++;
           }

           total += offsets[i];
       }
   }

   return total;
}

int main(void) {
   int numLetters = 0, i = 0, totalDone = 0, total = 0;
   char *buf = NULL;
   int *offsets;
   FILE *fp = NULL;
   LARGE_INTEGER start, end, tps;

   /* Allocate memory for input buffer and zero it */
   buf = (char *)malloc(BUF_LENGTH * sizeof(char));
   assert(buf != NULL);
   memset(buf, 0, BUF_LENGTH * sizeof(char));

   printf("Welcome the markiemrboo's word thingy generator\n\n");

   /* Ask how many letters, convert string to int, check if range is valid */
   do {
       /* Clear anything from stdin (keyboard input please!) left over */
       fflush(stdin);
       printf("Please enter the number of letters: ");
       fgets(buf, BUF_LENGTH, stdin);
       numLetters = atoi(buf);
   } while (numLetters < 1 || numLetters > 99);

   /* free input buffer */
   free(buf);
   buf = NULL;

   QueryPerformanceCounter(&start);

   /*
    * Allocate memory for offset array, 1 slot for each character, and zero it
    */
   offsets = (int *)malloc(numLetters * sizeof(int));
   assert(offsets != NULL);
   memset(offsets, 0, numLetters * sizeof(int));

   /* Open file to write output to */
   fp = fopen("worddump.txt", "w");
   if (!fp) {
       perror("fopen");
       exit(1);
   }

   /*
    * Work out stopping condition for loop
    */
   total = (LETTERS * numLetters);

   /*
    * My crappy coding skills mean I have to write out either the first or
    * last series of letters outside of the loop.
    *
    * Example: 2 characters would be from 0,0 to LETTERS,LETTERS. If I didn't
    * have the WriteIt() outside of the loop here it would actually end up
    * writing out the characters from 0,1 to LETTERS,LETTERS because of the
    * Add() inside the loop. Get it?!
    */
   WriteIt(fp, offsets, numLetters);
   do {
       totalDone = Add(offsets, numLetters);
       WriteIt(fp, offsets, numLetters);
   } while (totalDone < total);
   printf("\n");

   /* free offsets array */
   free(offsets);
   offsets = NULL;

   /* We're done with the file so.. close that now! */
   fclose(fp);

   QueryPerformanceCounter(&end);
   QueryPerformanceFrequency(&tps);

   printf("%d ticks per second\n", tps.QuadPart);
   printf("done in %d ticks\n", (end.QuadPart - start.QuadPart));
   
   system("pause");

   return 0;
}

[Verran]

I did another tweak related to writing to the file, which should speed yours up back to .. faster than mine, probably

526827[/snapback]

 

Good god. I see exactly what you did, and that helps a TON. It's so simple, yet to brilliant

 

Having said that, I've got mine going about THREE TIMES faster than even your most recent one (I have been able to advance mine ONLY through the help you've given me, don't think I don't know that, hehe)

 

So first, I built mine just like yours. I cached all the chars into a string that was, for example, {'a','a','a','a','/0'} and then wrote each string to the file. For those following at home, this severely cuts the amount of file writes the program does, which really speeds it up. This is the "faster2" folder in my attached zip file.

 

Then, I figured "Why not take markie's caching idea even further?" So now, I have a huge cache string. By the time it's written it contains, for example:

 

aaaa/naaab/naaac/n .... aaay/naaaz/n/0

 

So I write aaaa to aaaz in one shot at the disk. Whoa! I didn't think this would actually work, but I got it running on the first try, which amazed me. (This is the faster3 directory in the zip file) The write speed sometimes even slows down a bit around 6% done where it seems to have trouble writing that fast, like it has to expand the file size before it writes or something. I figured this into my averaging below....

 

So here's some speeds:

 

markies latest iterative:

97085158 ticks

 

Verran's faster2:

92356227 ticks

 

Verran's faster3:

37978394 ticks (this is a run where it DID bog down on file write)

 

So once again, thanks to markie's kindness in sharing code, I'm going faster again I think the recursive stuff is actually faster, but as you can see (between markie's and faster2), it's not that much faster.

 

Here's my latest C/C++ blend code:

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <windows.h>

#define BUF_LENGTH 4

int main()
{
  int len;
  int count;
  int j=0;
  int* dynword;
  char *buf = NULL;
  LARGE_INTEGER start, end, tps;  
  FILE *fout = NULL;

  void checkfunc(int*,int,int&); 
    
  /* Allocate memory for input buffer and zero it */
  buf = (char *)malloc(BUF_LENGTH * sizeof(char));
  assert(buf != NULL);
  memset(buf, 0, BUF_LENGTH * sizeof(char));
  
  do {
       fflush(stdin);
       printf("Please enter the number of letters: ");
       fgets(buf, BUF_LENGTH, stdin);
       len = atoi(buf);
  } while (len < 1 || len > 99);
  
  char str[(((len + 1)*94)+1)];
  //str[len] = '\0';
  
  QueryPerformanceCounter(&start);
  
  fout = fopen("word.txt", "w");
  if (!fout) // Always test file open
       {
       printf("Error opening output file\n");
       return -1;
       }
       
  count = len - 1;          //set count to point at last slot in dyn array
   
  dynword = new int[len];
   
  for(int i=0;i<len;i++)       //Initialize "all a's" array
          dynword[i] = 33;     //
                                
  len = len - 1; // subtract 1 for working with arrays (0 -> len-1)
  
  while (count >= 0)
  {      
          for(int i=0;i<(len+1);i++)
          {
                  str[j] = char(dynword[i]);
                  j++;
          }
          
          str[j] = '\n';
          j++;
                          
          if (dynword[len] == 126)
          { 
                  str[j] = '\0';
                  fprintf(fout, "%s\n", str);
                  checkfunc(dynword,len,count); 
                  j = 0; 
          }                  
          else
                  dynword[len]++;

 } // end while
 
  fclose(fout);
  
  QueryPerformanceCounter(&end);
  QueryPerformanceFrequency(&tps);
  printf("%d ticks per second\n", tps.QuadPart);
  printf("done in %d ticks\n", (end.QuadPart - start.QuadPart));
  
  system ("pause");
  return 0;
  
}

void checkfunc(int* dynword, int len, int& count)
{
     int p;
           
     if (dynword[(len)] == 126)     
     {    
     dynword[len] = 33;     
     checkfunc(dynword,(len-1),count);  
     
              if (count == len)
                   count--;                                  
     }     
     else
     {
              p = int((dynword[0] - 32)*1.063829);
              dynword[(len)]++;
              if (!len)
                   printf("%d%% done.\n", p);
     }        
            
return;     
}

 

And here's the zip as promised

[markiemrboo]

Good god.  I see exactly what you did, and that helps a TON.  It's so simple, yet to brilliant

 

Having said that, I've got mine going about THREE TIMES faster than even your most recent one   (I have been able to advance mine ONLY through the help you've given me, don't think I don't know that, hehe)

 

So first, I built mine just like yours.  I cached all the chars into a string that was, for example, {'a','a','a','a','/0'} and then wrote each string to the file.  For those following at home, this severely cuts the amount of file writes the program does, which really speeds it up.  This is the "faster2" folder in my attached zip file.

 

Then, I figured "Why not take markie's caching idea even further?"  So now, I have a huge cache string.  By the time it's written it contains, for example:

 

aaaa/naaab/naaac/n ....  aaay/naaaz/n/0

 

So I write aaaa to aaaz in one shot at the disk.  Whoa!  I didn't think this would actually work, but I got it running on the first try, which amazed me.  (This is the faster3 directory in the zip file)  The write speed sometimes even slows down a bit around 6% done where it seems to have trouble writing that fast, like it has to expand the file size before it writes or something.  I figured this into my averaging below....

 

So here's some speeds:

 

markies latest iterative:

97085158 ticks

 

Verran's faster2:

92356227 ticks

 

Verran's faster3:

37978394  ticks (this is a run where it DID bog down on file write)

 

So once again, thanks to markie's kindness in sharing code, I'm going faster again   I think the recursive stuff is actually faster, but as you can see (between markie's and faster2), it's not that much faster.

526851[/snapback]

 

yeah, I was gonna do the big cache thing like you've done there but.. it was too early/late or something. Couldn't be arsed

 

dang my kindnessness (eh?! lol) I'd be winning if I wasn't so nice sharing my code

[Verran]

yeah, I was gonna do the big cache thing like you've done there but.. it was too early/late or something. Couldn't be arsed

 

dang my kindnessness (eh?! lol) I'd be winning if I wasn't so nice sharing my code

526852[/snapback]

 

I figured you'd've thought of that, I just wanted to beat you to it.

 

Seriously though, thanks for all the ideas. This has been a lot of fun working with, and I've actually learned a lot!

 

BTW, I edited in my code and zip since you read it

[markiemrboo]

I figured you'd've thought of that, I just wanted to beat you to it. 

 

Seriously though, thanks for all the ideas.  This has been a lot of fun working with, and I've actually learned a lot!

 

BTW, I edited in my code and zip since you read it

526855[/snapback]

 

Quite alright!

 

I think I will resign and wait for "Programming Challenge 2" ( and eat my curry ). It was fun!!

[Archerzz]

we need to have the regular Programming Challenge and at the same time the n00b's Programming Challenge with easier programs for us n00blits

[markiemrboo]

we need to have the regular Programming Challenge and at the same time the n00b's Programming Challenge with easier programs for us n00blits

529829[/snapback]

 

Yeah, that'd be kinda cool maybe I think I have one for n00bs! It was in my Uni exam in the first year I think.

[lt_navvara]

here's my submission less than five minutes. the coments took a while longer as english is my second language

 

#include "iostream.h"//these are the include files, here we have all the functions and datatipes used

#include "fstream.h"//functions like cout and cin are defined in iostream.h. open and fstream are defined in fstream.h

 

fstream out;

char *words;//char is a standard datatipe, it needs no header file, it stands for character,

// the little star means tht words is a pointer. i used this so that words's size can be adjusted according to var

int var;//this is a int or integer also a standard datatipe. it stands for a number. in this program

//it represents the number of letter generated

void execute(int level)//execute is not a standard function so it is defined here. it uses a standard backtracking algorithm if you have any questions about backtracking pm me

{if(level<var)//this checks if level has excedeed var (lenght of string to be generated)

for(int i=97;i<=122;i++)//this code generates all the possible combinations

{words[level]=i;//stores them into words

execute(level+1);}//and calls itself again to generate the next character in the string

else// if level has exceeded var

{out.write(words,var);//words is writen into the file

out.write(" ",1);}//and a blank space is added, to make the file readable

 

}

void main()//this is the main function, it is the first fundtion to be executed. all functions are called from here

{out.open("words.out",ios::trunc);//here we open the file, in this case words.out

if(!out)//if words can't be opened then a message is generated

{cout<<"no way dude, can't open file";

cin>>var;}//this waits for a key imput so that you can see the error message and the program doesn't terminate immediately

else

{cin>>var;//if everything went fine we now read the string lenght

words=new char[var];//allocate space for words as it is dinamicaly generated

execute(0);//and call execute

}

}

/*that's it 22 lines (not counting comments.

some might argue that i need to close the stream but that isn't realy necessary, all streams are closed

when the program terminates*/

 

btw how can i include the exe file? i can't just paste it here.

anyway the code was writen in VC++ 6, so if you compile it use that