finally finished implementing challenge 216's second task in C

9 files changed, 246 insertions, 166 deletions

diff --git a/challenge-216/duncan-c-white/C/.cbuild b/challenge-216/duncan-c-white/C/.cbuild
index 835981f6f1..c168e34403 100644
--- a/challenge-216/duncan-c-white/C/.cbuild
+++ b/challenge-216/duncan-c-white/C/.cbuild
@@ -1,5 +1,5 @@
 BUILD = ch-1 ch-2
-BUILD = ch-1
+#BUILD = ch-1
 CFLAGS = -Wall -g
 #LDFLAGS = -lm
 #CFLAGS = -g
diff --git a/challenge-216/duncan-c-white/C/README b/challenge-216/duncan-c-white/C/README
index f73271428e..f65a3622f5 100644
--- a/challenge-216/duncan-c-white/C/README
+++ b/challenge-216/duncan-c-white/C/README
@@ -3,7 +3,5 @@ Thought I'd also have a go at translating ch-1.pl and (shortly) ch-2.pl into C..
 Both C versions produce very similar (non-debugging and debugging)
 output to the Perl originals.
 
-These C versions use some of my regular support modules:
-- my command-line argument processing module args.[ch],
-- my csvlist-of-int parsing module parseints.[ch], and
-- my int-array printing module printarray.[ch].
+These C versions use one of my regular support modules:
+- my command-line argument processing module args.[ch]
diff --git a/challenge-216/duncan-c-white/C/ch-1.c b/challenge-216/duncan-c-white/C/ch-1.c
index ba8185dba8..c0f4d39840 100644
--- a/challenge-216/duncan-c-white/C/ch-1.c
+++ b/challenge-216/duncan-c-white/C/ch-1.c
@@ -10,8 +10,6 @@
 #include <assert.h>
 
 #include "args.h"
-#include "parseints.h"
-#include "printarray.h"
 
 
 //
diff --git a/challenge-216/duncan-c-white/C/ch-2.c b/challenge-216/duncan-c-white/C/ch-2.c
new file mode 100644
index 0000000000..ece2a777db
--- /dev/null
+++ b/challenge-216/duncan-c-white/C/ch-2.c
@@ -0,0 +1,238 @@
+// Task 2: Word Stickers
+//
+// C translation
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdbool.h>
+#include <string.h>
+#include <ctype.h>
+#include <assert.h>
+
+#include "args.h"
+
+
+//
+// bool ismissing = lettermissing( letter, sticker[], nstickers );
+//	Return true iff letter is missing from all sticker[nstickers].
+//	Return false otherwise.
+//
+bool lettermissing( char letter, char **sticker, int nstickers )
+{
+  for( int i=0; i<nstickers; i++ ) {
+    if( strchr( sticker[i], letter ) != NULL ) return false;
+  }
+  return true;
+}
+
+
+//
+// findmissing( word, sticker[], nstickers, missing[] );
+//	Find all the letters that are in word
+//	but which are missing from all sticker[nstickers],
+//	and copy the missing letters into missing[] as a NUL-terminated
+//	C string.  missing[] is empty ("") if no letters are missing.
+//	Assume that missing[] is big enough to store (potentially) all
+//	letters in the word.
+//
+void findmissing( char *word, char **sticker, int nstickers, char *missing ) {
+  char *mp = missing;
+  *mp = '\0';
+  for( char *wp=word; *wp; wp++ ) { // foreach letter *wp in word
+    char letter = *wp;
+    if( lettermissing(letter,sticker,nstickers) )
+    {
+      *mp++ = letter;
+      *mp = '\0';
+      if( debug ) {
+        printf( "debug: found missing letter '%c'\n", letter );
+      }
+    }
+  }
+}
+
+
+//
+// lettersincommon( word, sticker, incommon );
+//	Find all the letters that word has in common with sticker
+//	(using each letter in sticker only once), and form them
+//	into a NUL-terminated C string in incommon[].
+//	Assume that incommon[] is big enough to store (potentially) all
+//	letters in the word.
+//
+void lettersincommon( char *word, char *sticker, char *incommon ) {
+  char *cp = incommon;
+  *cp = '\0';
+  int wlen = strlen(word);
+  char wcopy[wlen+1];
+  strcpy( wcopy, word );
+  for( char *s=sticker; *s; s++ ) {
+    char letter = *s;
+    char *found = strchr( wcopy, letter );
+    if( found != NULL ) {
+      memmove( found, found+1, wlen-(found-wcopy) );	// delete *found from wcopy
+      *cp++ = letter;
+      *cp = '\0';
+    }
+  }
+}
+
+
+int nstickers;		// how many stickers there are
+char **stickers;	// stickers[nstickers]: list of sticker words
+
+
+//
+// print_stickers( n, which );
+//	Print a comma-separated list of stickers given which[n],
+//	an array of sticker NUMBERS to print.
+//
+void print_stickers( int n, int *used ) {
+  for( int i=0; i<n; i++ ) {
+    if( i>0 ) putchar( ',' );
+    printf( "%s", stickers[used[i]] );
+  }
+  putchar( '\n' );
+}
+
+
+int minstickers=1000000;
+int minstickers_used[1024];
+
+
+//
+// findall( word, used );
+//	Given a word, and a numbered list of stickers already used in
+//	used[0..] (ended by a -1 sentinel),
+//	find all combinations of stickers[nstickers] that contain all letters
+//	in word, and track and store the best (minimum) number of stickers
+//	in minstickers, along with the sticker numbers themselves in
+//	minstickers_used[].
+//	How? the key insight is that each sticker can be used (or not)
+//	whenever it contains any letters in common with the word.  So try
+//	both possibilities recursively.
+//
+void findall( char *word, int *used ) {
+  // count how many stickers we've currently used
+  int nused;
+  for( nused=0; used[nused] != -1; nused++ );
+
+  if( *word == '\0' ) {
+    if( debug ) {
+      printf( "debug: found solution, used = " );
+      print_stickers( nused, used );
+    }
+    if( nused < minstickers )
+    {
+      minstickers = nused;
+      memcpy( minstickers_used, used, nused*sizeof(int) );
+      if( debug ) {
+        printf( "debug: found new best solution, min stickers = %d, used = ",
+		minstickers );
+	print_stickers( minstickers, minstickers_used );
+      }
+    }
+    return;
+  }
+
+  for( int sn=0; sn<nstickers; sn++ ) {		// foreach sticker
+    char *sticker = stickers[sn];
+
+    char incommon[52];
+    lettersincommon( word, sticker, incommon );
+    if( *incommon == '\0' ) continue;
+
+    //if( debug ) {
+    //  printf( "debug: letters in common between %s and %s are %s\n",
+    //  word, sticker, incommon );
+    //}
+
+    // there are two possibilities: use this sticker or don't;
+    // try both..
+
+    // try using the sticker
+    if( debug ) {
+      printf( "debug: USING sticker %s, against %s, letters in common %s\n",
+        sticker, word, incommon );
+    }
+    used[nused++] = sn;
+    used[nused] = -1;
+
+    char *newword = strdup(word);
+    for( char *s=incommon; *s; s++ ) {
+      // remove first instance of each incommon letter from newword
+      char *found = strchr( newword, *s );
+      assert( found != NULL );
+      int len = strlen(newword);
+      memmove( found, found+1, len-(found-newword) );
+    }
+    if( debug ) {
+      printf( "debug: after removing common letters, new word is <%s>\n",
+        newword );
+    }
+    findall( newword, used );
+    free( newword );
+
+    // now try without the sticker
+    used[--nused] = -1;
+  }
+}
+
+
+int main( int argc, char **argv )
+{
+  int argno = process_flag_n_m_args( "word-stickers", argc, argv,
+                            2, 1000, "word stickerwordlist" );
+
+  // lower case all arguments
+  for( int i=argno; i<argc; i++ ) {
+    for( char *s=argv[i]; *s; s++ ) *s = tolower(*s);
+  }
+
+  char *word = argv[argno++];
+
+  stickers = argv+argno;
+  nstickers = argc-argno;
+
+  if( debug ) {
+    printf( "debug: word: %s, list: ", word );
+    for( int i=0; i<nstickers; i++ ) {
+      if( i>0 ) putchar( ',' );
+      printf( "%s", stickers[i] );
+    }
+    putchar( '\n' );
+  }
+
+  char missingletters[512];
+  findmissing( word, stickers, nstickers, missingletters );
+  if( *missingletters != '\0' ) {
+    printf( "0\n" );
+    if( debug ) {
+      printf( "No solutions, because letters %s "
+	      "are missing from all stickers\n", missingletters );
+    }
+    exit(0);
+  }
+
+  char incommon[52];
+  lettersincommon( word, stickers[0], incommon );
+  if( debug ) {
+    printf( "debug: letters in common between %s and %s are %s\n",
+  	word, stickers[0], incommon );
+  }
+
+  minstickers=1000000;
+  minstickers_used[0] = -1;
+
+  int stickers_used[1024];
+  stickers_used[0] = -1;
+
+  findall( word, stickers_used );
+
+  printf( "%d\n", minstickers );
+  if( debug ) {
+    printf( "debug: stickers used: " );
+    print_stickers( minstickers, minstickers_used );
+  }
+  return 0;
+}
diff --git a/challenge-216/duncan-c-white/C/parseints.c b/challenge-216/duncan-c-white/C/parseints.c
deleted file mode 100644
index 3e820eb334..0000000000
--- a/challenge-216/duncan-c-white/C/parseints.c
+++ /dev/null
@@ -1,114 +0,0 @@
-// Simple routine to parse one or more arguments,
-// looking for individual ints or comma-separated
-// lists of ints.
-// 
-
-#include <stdio.h>
-#include <stdlib.h>
-#include <stdbool.h>
-#include <string.h>
-#include <ctype.h>
-#include <assert.h>
-
-#include "args.h"
-#include "printarray.h"
-#include "parseints.h"
-
-typedef struct
-{
-	int nel;	// current number of elements 
-	int maxel;	// maximum number of elements allocated
-	int *list;	// malloc()d list of integers
-} intlist;
-
-
-//
-// intlist il.. then initialize il..  then:
-// add_one( element, &il );
-//	
-static void add_one( int x, intlist *p )
-{
-	if( p->nel > p->maxel )
-	{
-		p->maxel += 128;
-		p->list = realloc( p->list, p->maxel );
-		assert( p->list != NULL );
-	}
-	#if 0
-	if( debug )
-	{
-		printf( "PIA: appending %d to result at "
-			"pos %d\n", x, p->nel );
-	}
-	#endif
-	p->list[p->nel++] = x;
-}
-
-
-//
-// intlist il.. then initialize il..  then:
-// add_one_arg( argstr, &il );
-//	
-static void add_one_arg( char *argstr, intlist *p )
-{
-	int x;
-	if( !check_int(argstr,&x) )
-	{
-		fprintf( stderr, "PIA: arg %s must be int\n", argstr );
-		exit(1);
-	}
-	add_one( x, p );
-}
-
-
-//
-// int nel;
-// int *ilist = parse_int_args( argc, argv, argno, &nel );
-//	process all arguments argv[argno..argc-1], extracting either
-//	single ints or comma-separated lists of ints from those arguments,
-//	accumulate all integers in a dynarray list, storing the total number
-//	of elements in nel.  This list must be freed by the caller.
-//	Note that the list of elements used to be terminated by a -1 value,
-//	but I've commented this out from now on.
-//
-int *parse_int_args( int argc, char **argv, int argno, int *nel )
-{
-	int *result = malloc( 128 * sizeof(int) );
-	assert( result != NULL );
-	intlist il = { 0, 128, result };
-
-	#if 0
-	if( debug )
-	{
-		printf( "PIA: parsing ints from args %d..%d\n", argno, argc-1 );
-	}
-	#endif
-	for( int i=argno; i<argc; i++ )
-	{
-		assert( strlen(argv[i]) < 1024 );
-		char copy[1024];
-		strcpy( copy, argv[i] );
-		char *com;
-		char *s;
-		for( s=copy; (com = strchr(s,',')) != NULL; s=com+1 )
-		{
-			*com = '\0';
-			add_one_arg( s, &il );
-		}
-		add_one_arg( s, &il );
-	}
-
-	//add_one( -1, &il );
-
-	#if 0
-	if( debug )
-	{
-		printf( "PIA: final list is " );
-		print_int_array( 80, il.nel, il.list, ',', stdout );
-		putchar( '\n' );
-	}
-	#endif
-
-	*nel = il.nel;
-	return il.list;
-}
diff --git a/challenge-216/duncan-c-white/C/parseints.h b/challenge-216/duncan-c-white/C/parseints.h
deleted file mode 100644
index da5e145a86..0000000000
--- a/challenge-216/duncan-c-white/C/parseints.h
+++ /dev/null
@@ -1 +0,0 @@
-extern int * parse_int_args( int argc, char ** argv, int argno, int * nel );
diff --git a/challenge-216/duncan-c-white/C/printarray.c b/challenge-216/duncan-c-white/C/printarray.c
deleted file mode 100644
index ddee597df3..0000000000
--- a/challenge-216/duncan-c-white/C/printarray.c
+++ /dev/null
@@ -1,39 +0,0 @@
-#include <stdio.h>
-#include <string.h>
-
-
-// print_int_array( maxw, nelements, results[], sep, outfile );
-//	format results[0..nelements-1] as a <sep> separated
-//      list onto outfile with lines <= maxw chars long.
-//	produces a whole number of lines of output - without the trailing '\n'
-void print_int_array( int maxw, int nel, int *results, char sep, FILE *out )
-{
-	int linelen = 0;
-	for( int i=0; i<nel; i++ )
-	{
-		char buf[100];
-		sprintf( buf, "%d", results[i] );
-		int len = strlen(buf);
-		if( linelen + len + 2 > maxw )
-		{
-			fputc( '\n', out );
-			linelen = 0;
-		} else if( i>0 )
-		{
-			fputc( ' ', out );
-			linelen++;
-		}
-
-		linelen += len;
-		fprintf( out, "%s", buf );
-		if( i<nel-1 )
-		{
-			fputc( sep, out );
-			linelen++;
-		}
-	}
-	//if( linelen>0 )
-	//{
-	//	fputc( '\n', out );
-	//}
-}
diff --git a/challenge-216/duncan-c-white/C/printarray.h b/challenge-216/duncan-c-white/C/printarray.h
deleted file mode 100644
index 40efb83277..0000000000
--- a/challenge-216/duncan-c-white/C/printarray.h
+++ /dev/null
@@ -1 +0,0 @@
-extern void print_int_array( int maxw, int nel, int * results, char sep, FILE * out );
diff --git a/challenge-216/duncan-c-white/perl/ch-2.pl b/challenge-216/duncan-c-white/perl/ch-2.pl
index ef9597efa9..b14d58a121 100755
--- a/challenge-216/duncan-c-white/perl/ch-2.pl
+++ b/challenge-216/duncan-c-white/perl/ch-2.pl
@@ -144,7 +144,7 @@ fun findall( $word, $stickersused, @allsticker )
 {
 	if( $word eq '' )
 	{
-		say "found solution, stickersused = ", join(',',@$stickersused) if $debug;
+		say "debug: found solution, stickersused = ", join(',',@$stickersused) if $debug;
 		my $nwords = @$stickersused;
 		if( $nwords < $minstickers )
 		{
@@ -160,18 +160,19 @@ fun findall( $word, $stickersused, @allsticker )
 	{
 		my $common = lettersincommon( $word, $sticker );
 		next if $common eq '';
-		say "lettersincommon( $word, sticker $sticker ) = $common" if $debug;
+		#say "debug: lettersincommon( $word, sticker $sticker ) ".
+		#    "= $common" if $debug;
 
 		# there are two possibilities: use this sticker or don't;
 		# try both..
 
 		# try using the sticker
-		say "USE sticker $sticker, against $word, letters in common $common" if $debug;
+		say "debug: USING sticker $sticker, against $word, letters in common $common" if $debug;
 		my @newsu = @$stickersused;
 		push @newsu, $sticker;
 		my $newword = $word;
 		$newword =~ s/$_// for split(//,$common);
-		say " - new word is <$newword>" if $debug;
+		say "debug: new word is <$newword>" if $debug;
 		findall( $newword, \@newsu, @allsticker );
 
 		# or try without the sticker