Path: ...!news.nobody.at!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: DFS <nospam@dfs.com>
Newsgroups: comp.os.linux.advocacy
Subject: Re: OT programming challenge: fastest/best/shortest C program to
 jumble a sentence, then restore it
Date: Fri, 8 Mar 2024 20:53:08 -0500
Organization: A noiseless patient Spider
Lines: 280
Message-ID: <usgfe4$20gfq$2@dont-email.me>
References: <65e9cad3$0$4689$882e4bbb@reader.netnews.com>
 <l4ufsbF9kdnU4@mid.individual.net> <usf2m9$1n0jh$2@dont-email.me>
 <l518d6FmepqU1@mid.individual.net>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Sat, 9 Mar 2024 01:53:08 -0000 (UTC)
Injection-Info: dont-email.me; posting-host="bd0cd99499b1364606b6e597c9f2633e";
	logging-data="2114042"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19UaoCoDK6Hn1dtg/+K3CKd"
User-Agent: Betterbird (Windows)
Cancel-Lock: sha1:dGItwoUfsCUbRm+thOKX51qzB44=
In-Reply-To: <l518d6FmepqU1@mid.individual.net>
Content-Language: en-US
Bytes: 9131

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[i] = -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[i]]);
>      }
>      printf("\noriginal: \n");
>      for (i=0; i<slots; i++) {
>          printf("%s ", tokens[i]);
>      }
>      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[i]) && !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);
========== REMAINDER OF ARTICLE TRUNCATED ==========