Re: OT programming challenge: fastest/best/shortest C program to jumble a sentence, then restore it

On 3/8/2024 2:48 PM, rbowman wrote:

On Fri, 8 Mar 2024 08:09:33 -0500, DFS wrote:
 

It's harder than you think to randomly shuffle the words in a shorter
sentence, so that each word ends up in a different position than it
started in.
>
Bring it!

 #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
 int main(int argc, char** argv)
{
     char* sentence = strdup("Once you try it, you'll see it doesn't need
spice.");
     char* tokens[20];
     int token_count = 0;
     int i;
     int j;
     int slots;
     int candidate;
     int* indices;
      for (tokens[token_count] = strtok(sentence, " ");
          tokens[token_count];
          tokens[token_count] = strtok(NULL, " "))
     {
         token_count++;
     }
      indices = malloc(token_count * sizeof(int));
     for (i=0; i<token_count; i++) {
         indices = -1;
     }
     srand((unsigned int) time(NULL));
     for (i=0, slots=0; slots<token_count; i++) {
         candidate = rand() % token_count;
         for (j=0; j<token_count; j++) {
             if (indices[j] == candidate) {
                  break;
             }
             else if (indices[j] == -1) {
                 indices[slots++] = candidate;
                 break;
             }
         }
     }
     printf("\nshuffled:\n");
     for (i=0; i<slots; i++) {
         printf("%s ", tokens[indices]);
     }
     printf("\noriginal: \n");
     for (i=0; i<slots; i++) {
         printf("%s ", tokens);
     }
     printf("\n");
      return 0;
}
 ./shuffle
 shuffled:
doesn't you spice. try Once it, it need see you'll
original:
Once you try it, you'll see it doesn't need spice.
 ./shuffle
 shuffled:
need it, spice. it you you'll see Once try doesn't
original:
Once you try it, you'll see it doesn't need spice.

------------------------------------------------------------
~$ ./shuffle
slot = 0, candidate = 1
slot = 1, candidate = 8
slot = 2, candidate = 2  (match)
slot = 3, candidate = 7
slot = 4, candidate = 9
slot = 5, candidate = 5  (match)
slot = 6, candidate = 4
slot = 7, candidate = 6
slot = 8, candidate = 0
slot = 9, candidate = 3
original: Once you try it, you'll see it doesn't need spice.
shuffled: you need try doesn't spice. see you'll it Once it,
------------------------------------------------------------
Some words weren't shuffled.  Your bank acct is now hacked.
When I was writing my version yesterday (see below), I found ~8% of the rands matched when the sentence was short.
Double the length of the sentence and the percent of matches falls to around 5%.

Get enough monkeys running it and the shuffled sentence may be the same as
the original.

That would = bad programming.

For production, I'd first count the tokens and allocate the tokens array
but I'm lazy. Further enhancements, allow the string to be entered on the
command line, read strings from a file and write shuffled strings to a
file, and so on.

I usually try to take command line inputs.  Makes the program easier to test and fun to use.

Of course in Python you could use split and shuffle to abstract away all
the messiness.

It amazes me how productive Python can be versus C.
my code
----------------------------------------------------------------------
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <time.h>
//usage $./prog "sentence in quotes" N-jumbles
//is dest already set in the array
int found(int dest,int rarr[], int cnt) {
int match = 0;
for (int j = 0; j < cnt; j++) {
if (dest == rarr[j]) {match = 1;break;}
}
return match;
}
int main(int argc, char *argv[]) {
int i = 0, j = 0, k = 0;
char *orig = argv[1];
int loops = atoi(argv[2]);

//count words = number of spaces + 1
int wordcnt = 1;
for (int i = 0; i < strlen(orig); i++) {
if(isspace(orig) && !isspace(orig[i+1])) {wordcnt++;}
}
//arrays to hold words and numbers
char **words  = malloc(sizeof(char*) * wordcnt);
char **temp   = malloc(sizeof(char*) * wordcnt);
int randarr[wordcnt];
for(int i = 0; i < wordcnt ; randarr[i++] = wordcnt + 1);
//split string copy on space, add words to array
char *copy = strdup(orig);
const char delimiter[] = " ";
     char *token = strtok(copy, delimiter);
     while (token != NULL) {
         words[i++] = token;
token = strtok(NULL, delimiter);
     }

//show word count
printf(" %d words\n",wordcnt);
//print original sentence
printf("---------------------------------------------------\n");
printf("    %s\n",orig);
printf("---------------------------------------------------\n");

//generate randoms until each word moves to a different position
srand(time(NULL));
int src,dest,fdest;
int totmatches = 0;
k = 1;
while (k <= loops) {

for (int src = 0; src < wordcnt; src++) {
dest = rand() % wordcnt;
//printf("src=%d,dest=%d,found=%d\n",src,dest,found(dest,randarr,wordcnt));
while (1)
{
fdest = found(dest,randarr,wordcnt);
if ((src != dest && fdest == 0) || (src == dest && src == (wordcnt-1) && fdest == 0))
{
randarr[src] = dest;
temp[dest] = words[src];
break;
}
else
{
dest = rand() % wordcnt;
//printf("src=%d,dest=%d,found=%d\n",src,dest,found(dest,randarr,wordcnt));
}
}
}

//print jumbled indices and values in arrays
//for(j = 0; j < wordcnt;  j++) {
//printf("%d %d %10s %10s\n",j,randarr[j],words[j],temp[j]);
//}
//print jumbled sentence
printf("%2d. ",k);
int matches = 0;
for(j = 0; j < wordcnt;  j++) {
printf("%s ",temp[j]);
if (temp[j] == words[j]) {matches++;totmatches++;}
}
if (matches > 0) {printf(" %d match\n",matches);} else {printf("\n");}

//reset arrays
memset(temp, 0, wordcnt * sizeof(temp));
for(int j = 0; j < wordcnt ; randarr[j++] = 999);

k++;
}
printf("---------------------------------------------------\n");
printf("Total matches = %d\n",totmatches);

free(words);
free(temp);
return(0);
}
----------------------------------------------------------------------
~$ ./jumble "Jumble this sentence then put it back in order" 10
  9 words
---------------------------------------------------
     Jumble this sentence then put it back in order
---------------------------------------------------
  1. then put Jumble sentence in this it back order  1 match
  2. order in Jumble put back sentence then it this
  3. this back in order sentence Jumble it put then
  4. put Jumble order it then this sentence back in
  5. sentence order then Jumble in this it put back
  6. back in it this Jumble sentence order then put
  7. put Jumble back it in then order this sentence
  8. it order back in this put then Jumble sentence
  9. sentence order put Jumble back this in it then
10. it sentence back put then in Jumble this order  1 match
---------------------------------------------------
Total matches = 2
You'll note in mine the match is always the last word of the input.  I'm gonna put in a little kludge to fix that: swap the last word for a randomly chosen earlier one.  That'll make for a 'perfect' jumble.
Thanks for participating.  I was about to cancel the challenge for lack of interest.  Our code isn't quite done, since one of the requirements was to concatenate the tokens, then print.  And then split the jumbled one apart and reconstitute it.  Mostly useless exercises, I now realize.
Your code is shorter than mine, but mine takes 2 command line inputs and prints more information.