Merge pull request #7690 from dcw803/master

ok, a day late but I've done the C versions of both tasks in ch 206…

13 files changed, 669 insertions, 2 deletions

diff --git a/challenge-206/duncan-c-white/C/.cbuild b/challenge-206/duncan-c-white/C/.cbuild
new file mode 100644
index 0000000000..a14ec76520
--- /dev/null
+++ b/challenge-206/duncan-c-white/C/.cbuild
@@ -0,0 +1,4 @@
+BUILD = ch-1 ch-2
+CFLAGS = -Wall -g
+#LDFLAGS = -lm
+#CFLAGS = -g
diff --git a/challenge-206/duncan-c-white/C/Makefile b/challenge-206/duncan-c-white/C/Makefile
new file mode 100644
index 0000000000..34d8a4d520
--- /dev/null
+++ b/challenge-206/duncan-c-white/C/Makefile
@@ -0,0 +1,18 @@
+# Makefile rules generated by CB
+CC	= gcc
+CFLAGS	= -Wall -g
+BUILD	= ch-1 ch-2
+
+all:	$(BUILD)
+
+clean:
+	/bin/rm -f $(BUILD) *.o core a.out
+
+args.o:	args.c
+ch-1:	ch-1.o args.o
+ch-1.o:	ch-1.c args.h
+ch-2:	ch-2.o args.o parseints.o printarray.o
+ch-2.o:	ch-2.c args.h parseints.h printarray.h
+parseints.o:	parseints.c args.h parseints.h printarray.h
+printarray.o:	printarray.c
+
diff --git a/challenge-206/duncan-c-white/C/README b/challenge-206/duncan-c-white/C/README
new file mode 100644
index 0000000000..c9507cf6e0
--- /dev/null
+++ b/challenge-206/duncan-c-white/C/README
@@ -0,0 +1,14 @@
+Thought I'd also have a go at translating ch-1.pl and ch-2.pl into C..
+
+Both C versions produce near-identical (non-debugging and even debugging)
+output to the Perl originals.
+
+The C translation of ch-2.pl could have been quite tricky to write, mainly on
+storage allocation (as usual), we would have needed a dynamic array of
+solutions; but I bodged it with a static array and an assertion check
+assert( n < MAXSOLS )..
+
+These C versions use most of my regular support modules:
+- a command-line argument processing module args.[ch],
+- a csvlist-of-int parsing module parseints.[ch], and
+- an int-array printing module printarray.[ch].
diff --git a/challenge-206/duncan-c-white/C/args.c b/challenge-206/duncan-c-white/C/args.c
new file mode 100644
index 0000000000..d4a2d38b9a
--- /dev/null
+++ b/challenge-206/duncan-c-white/C/args.c
@@ -0,0 +1,207 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdbool.h>
+#include <string.h>
+#include <ctype.h>
+#include <assert.h>
+
+
+bool debug = false;
+
+
+// process_flag_noarg( name, argc, argv );
+//	Process the -d flag, and check that there are no
+//	remaining arguments.
+void process_flag_noarg( char *name, int argc, char **argv )
+{
+	int arg=1;
+	if( argc>1 && strcmp( argv[arg], "-d" ) == 0 )
+	{
+		debug = true;
+		arg++;
+	}
+
+	int left = argc-arg;
+	if( left != 0 )
+	{
+		fprintf( stderr, "Usage: %s [-d]\n", name );
+		exit(1);
+	}
+}
+
+
+// int argno = process_flag_n_args( name, argc, argv, n, argmsg );
+//	Process the -d flag, and check that there are exactly
+//	n remaining arguments, return the index position of the first
+//	argument.  If not, generate a fatal Usage error using the argmsg.
+//	
+int process_flag_n_args( char *name, int argc, char **argv, int n, char *argmsg )
+{
+	int arg=1;
+	if( argc>1 && strcmp( argv[arg], "-d" ) == 0 )
+	{
+		debug = true;
+		arg++;
+	}
+
+	int left = argc-arg;
+	if( left != n )
+	{
+		fprintf( stderr, "Usage: %s [-d] %s\n       Exactly %d "
+			"arguments needed\n", name, argmsg, n );
+		exit(1);
+	}
+	return arg;
+}
+
+
+// int argno = process_flag_n_m_args( name, argc, argv, min, max, argmsg );
+//	Process the -d flag, and check that there are between
+//	min and max remaining arguments, return the index position of the first
+//	argument.  If not, generate a fatal Usage error using the argmsg.
+//	
+int process_flag_n_m_args( char *name, int argc, char **argv, int min, int max, char *argmsg )
+{
+	int arg=1;
+	if( argc>1 && strcmp( argv[arg], "-d" ) == 0 )
+	{
+		debug = true;
+		arg++;
+	}
+
+	int left = argc-arg;
+	if( left < min || left > max )
+	{
+		fprintf( stderr, "Usage: %s [-d] %s\n       Between %d and %d "
+			"arguments needed\n", name, argmsg, min, max );
+		exit(1);
+	}
+	return arg;
+}
+
+
+// process_onenumarg_default( name, argc, argv, defvalue, &n );
+//	Process the -d flag, and check that there is a single
+//	remaining numeric argument (or no arguments, in which case
+//	we use the defvalue), putting it into n
+void process_onenumarg_default( char *name, int argc, char **argv, int defvalue, int *n )
+{
+	char argmsg[100];
+	sprintf( argmsg, "[int default %d]", defvalue );
+	int arg = process_flag_n_m_args( name, argc, argv, 0, 1, argmsg );
+
+	*n = arg == argc ? defvalue : atoi( argv[arg] );
+}
+
+
+// process_onenumarg( name, argc, argv, &n );
+//	Process the -d flag, and check that there is a single
+//	remaining numeric argument, putting it into n
+void process_onenumarg( char *name, int argc, char **argv, int *n )
+{
+	int arg = process_flag_n_args( name, argc, argv, 1, "int" );
+
+	// argument is in argv[arg]
+	*n = atoi( argv[arg] );
+}
+
+
+// process_twonumargs( name, argc, argv, &m, &n );
+//	Process the -d flag, and check that there are 2
+//	remaining numeric arguments, putting them into m and n
+void process_twonumargs( char *name, int argc, char **argv, int *m, int *n )
+{
+	int arg = process_flag_n_args( name, argc, argv, 2, "int" );
+
+	// arguments are in argv[arg] and argv[arg+1]
+	*m = atoi( argv[arg++] );
+	*n = atoi( argv[arg] );
+}
+
+
+// process_twostrargs() IS DEPRECATED: use process_flag_n_m_args() instead
+
+
+// int arr[100];
+// int nel = process_listnumargs( name, argc, argv, arr, 100 );
+//	Process the -d flag, and check that there are >= 2
+//	remaining numeric arguments, putting them into arr[0..nel-1]
+//	and returning nel.
+int process_listnumargs( char *name, int argc, char **argv, int *arr, int maxel )
+{
+	int arg=1;
+	if( argc>1 && strcmp( argv[arg], "-d" ) == 0 )
+	{
+		debug = true;
+		arg++;
+	}
+
+	int left = argc-arg;
+	if( left < 2 )
+	{
+		fprintf( stderr, "Usage: %s [-d] list_of_numeric_args\n", name );
+		exit(1);
+	}
+	if( left > maxel )
+	{
+		fprintf( stderr, "%s: more than %d args\n", name, maxel );
+		exit(1);
+	}
+
+	// elements are in argv[arg], argv[arg+1]...
+
+	if( debug )
+	{
+		printf( "debug: remaining arguments are in arg=%d, "
+		        "firstn=%s, secondn=%s..\n",
+			arg, argv[arg], argv[arg+1] );
+	}
+
+	int nel = 0;
+	for( int i=arg; i<argc; i++ )
+	{
+		arr[nel++] = atoi( argv[i] );
+	}
+	arr[nel] = -1;
+	return nel;
+}
+
+
+//
+// bool isint = check_unsigned_int( char *val, int *n );
+//	Given an string val, check that there's an unsigned integer
+//	in it (after optional whitespace).  If there is a valid
+//	unsigned integer value, store that integer value in *n and
+//	return true; otherwise return false (and don't alter *n).
+bool check_unsigned_int( char *val, int *n )
+{
+	// skip whitespace in val
+	char *p;
+	for( p=val; isspace(*p); p++ )
+	{
+		/*EMPTY*/
+	}
+	if( ! isdigit(*p) ) return false;
+	*n = atoi(p);
+	return true;
+}
+
+
+//
+// bool ok = check_unsigned_real( char *val, double *n );
+//	Given an string val, check that there's an unsigned real
+//	in it (after optional whitespace).  If there is a valid
+//	unsigned real value, store that value in *n and
+//	return true; otherwise return false (and don't alter *n).
+bool check_unsigned_real( char *val, double *n )
+{
+	// skip whitespace in val
+	char *p;
+	for( p=val; isspace(*p); p++ )
+	{
+		/*EMPTY*/
+	}
+	if( ! isdigit(*p) ) return false;
+	*n = atof(p);
+	return true;
+}
diff --git a/challenge-206/duncan-c-white/C/args.h b/challenge-206/duncan-c-white/C/args.h
new file mode 100644
index 0000000000..8844a8f9c4
--- /dev/null
+++ b/challenge-206/duncan-c-white/C/args.h
@@ -0,0 +1,11 @@
+extern bool debug;
+
+extern void process_flag_noarg( char * name, int argc, char ** argv );
+extern int process_flag_n_args( char * name, int argc, char ** argv, int n, char * argmsg );
+extern int process_flag_n_m_args( char * name, int argc, char ** argv, int min, int max, char * argmsg );
+extern void process_onenumarg_default( char * name, int argc, char ** argv, int defvalue, int * n );
+extern void process_onenumarg( char * name, int argc, char ** argv, int * n );
+extern void process_twonumargs( char * name, int argc, char ** argv, int * m, int * n );
+extern int process_listnumargs( char * name, int argc, char ** argv, int * arr, int maxel );
+extern bool check_unsigned_int( char * val, int * n );
+extern bool check_unsigned_real( char * val, double * n );
diff --git a/challenge-206/duncan-c-white/C/ch-1.c b/challenge-206/duncan-c-white/C/ch-1.c
new file mode 100644
index 0000000000..ac4a4af8a1
--- /dev/null
+++ b/challenge-206/duncan-c-white/C/ch-1.c
@@ -0,0 +1,129 @@
+//
+// Task 1: Shortest Time
+// 
+// C version.
+// 
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdbool.h>
+#include <string.h>
+#include <ctype.h>
+#include <assert.h>
+
+#include "args.h"
+
+
+//
+// int time = parsehhmm( hhmm );
+//	Parse a 24-hour hh:mm time string into the total number
+//	of minutes since 00:00, and return it.
+//
+int parsehhmm( char *hhmm )
+{
+	if( strlen(hhmm) != 5 )
+	{
+		fprintf( stderr, "parsehhmm: bad length %s\n", hhmm );
+		exit(1);
+	}
+	if( ! isdigit(hhmm[0]) || ! isdigit(hhmm[1]) || hhmm[2] != ':'
+	||  ! isdigit(hhmm[3]) || ! isdigit(hhmm[4]) )
+	{
+		fprintf( stderr, "parsehhmm: bad format %s\n", hhmm );
+		exit(1);
+	}
+	return 60*atoi(hhmm) + atoi(hhmm+3);
+}
+
+
+int intcompare( const void *ap, const void *bp )
+{
+	int a = *((int *)ap);
+	int b = *((int *)bp);
+	return a-b;
+}
+
+
+int main( int argc, char **argv )
+{
+	int argno = process_flag_n_m_args( "shortest-time", argc, argv,
+		1, 1000, "hh:mm list" );
+
+	int nel = argc-argno;
+	int time[nel+1];
+
+	if( debug )
+	{
+		printf( "debug: initial list: nel=%d, ", nel );
+		for( int i=argno; i<argc; i++ )
+		{
+			if( i>argno ) putchar(',');
+			printf( "%s", argv[i] );
+		}
+		putchar( '\n' );
+	}
+
+	for( int i=argno; i<argc; i++ )
+	{
+		time[i-argno] = parsehhmm( argv[i] );
+	}
+
+	if( debug )
+	{
+		printf( "debug: times are: " );
+		for( int i=0; i<nel; i++ )
+		{
+			if( i>0 ) putchar(',');
+			printf( "%d", time[i] );
+		}
+		putchar( '\n' );
+	}
+
+	qsort( time, nel, sizeof(int), &intcompare );
+
+	time[nel] = 1440+time[0];
+
+	if( debug )
+	{
+		printf( "debug: sorted times are: " );
+		for( int i=0; i<=nel; i++ )
+		{
+			if( i>0 ) putchar(',');
+			printf( "%d", time[i] );
+		}
+		putchar( '\n' );
+	}
+
+	int best   = 1440;
+	int bestt1 = -1;
+	int bestt2 = -1;
+
+	for( int pos=0; pos<nel; pos++ )
+	{
+		int t = time[pos+1];
+		int diff = t - time[pos];
+		if( debug )
+		{
+			printf( "debug: pos %d, diff %d\n", pos, diff );
+		}
+		if( best > diff )
+		{
+			best = diff;
+			bestt1 = time[pos];
+			bestt2 = t;
+		}
+	}
+
+	printf( "%d\n", best );
+
+	if( debug )
+	{
+		char sbestt1[10];
+		char sbestt2[10];
+		sprintf( sbestt1, "%02d:%02d", bestt1/60, bestt1%60 );
+		sprintf( sbestt2, "%02d:%02d", bestt2/60, bestt2%60 );
+		printf( "(%s..%s)\n", sbestt1, sbestt2 );
+	}
+
+	return 0;
+}
diff --git a/challenge-206/duncan-c-white/C/ch-2.c b/challenge-206/duncan-c-white/C/ch-2.c
new file mode 100644
index 0000000000..3fe9c6cfae
--- /dev/null
+++ b/challenge-206/duncan-c-white/C/ch-2.c
@@ -0,0 +1,125 @@
+//
+// Task 2: Array Pairings
+// 
+// C version.
+// 
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdbool.h>
+#include <string.h>
+#include <ctype.h>
+#include <assert.h>
+
+#include "args.h"
+#include "parseints.h"
+#include "printarray.h"
+
+
+#define MAXSOLS 128
+
+
+//
+// find_all( sum, solarray, &nsol, list, nel );
+//	Given an even-length list list[0..nel-1], a sum so far (sum),
+//	an array of solutions (solarray) and a pointer to the number of
+//	solutions (nsol), pick all possible pairs of items from list
+//	including the first item in the list, and min(that pair) to the sum,
+//	and recurse on the rest of the array.  Accumulate all solutions
+//	(the final value of sum when list is empty) in solarray[].
+//
+void find_all( int sum, int *solarray, int *nsols, int *list, int nel )
+{
+	if( nel == 0 )
+	{
+		int n = (*nsols)++;
+		assert( n < MAXSOLS );
+		solarray[n] = sum;
+		return;
+	}
+
+	// find all pairs of first item, another item in @list
+	int first = list[0];
+	for( int spos = 1; spos<nel; spos++ )
+	{
+		int second = list[spos];
+		int min = first<second ? first : second;
+		int news = sum + min;
+		if( debug )
+		{
+			printf( "debug: removed %d and %d (min %d, newsum %d) ",
+				first, second, min, news );
+		}
+
+		// now remove elements 0 and spos from a clone of list..
+		int *newl = malloc( nel * sizeof(int) );
+		assert( newl != NULL );
+		int newn = 0;
+		for( int i=1; i<nel; i++ )
+		{
+			if( i != spos ) newl[newn++] = list[i];
+		}
+		if( debug )
+		{
+			printf( "leaving " );
+			for( int i=0; i<newn; i++ )
+			{
+				if( i>0 ) putchar(',');
+				printf( "%d", newl[i] );
+			}
+			putchar( '\n' );
+		}
+		find_all( news, solarray, nsols, newl, newn );
+		free( newl );
+	}
+}
+
+
+int main( int argc, char **argv )
+{
+	int argno = process_flag_n_m_args( "array-pairings", argc, argv,
+		1, 1000, "intlist" );
+
+	int nel;
+	int *list = parse_int_args( argc, argv, argno, &nel );
+
+	if( nel % 2 == 1 )
+	{
+		fprintf( stderr, "array-pairings: need even number of integers, not %d\n", nel );
+		exit(1);
+	}
+
+	if( debug )
+	{
+		printf( "debug: initial list: " );
+		print_int_array( 60, nel, list, ',', stdout );
+		putchar( '\n' );
+	}
+
+	int solutions[MAXSOLS];	// list of all solutions, final answer is max(these)
+	int nsols = 0;
+
+	find_all( 0, solutions, &nsols, list, nel );
+
+	if( debug )
+	{
+		printf( "debug: pairing solutions: nsols=%d, ", nsols );
+		for( int i=0; i<nsols; i++ )
+		{
+			if( i>0 ) putchar( ',' );
+			printf( "%d", solutions[i] );
+		}
+		putchar( '\n' );
+	}
+
+	int max = solutions[0];
+	for( int i=1; i<nsols; i++ )
+	{
+		if( solutions[i] > max ) max = solutions[i];
+	}
+	printf( "%d\n", max );
+
+	free( list );
+
+	return 0;
+}
diff --git a/challenge-206/duncan-c-white/C/parseints.c b/challenge-206/duncan-c-white/C/parseints.c
new file mode 100644
index 0000000000..80408d3382
--- /dev/null
+++ b/challenge-206/duncan-c-white/C/parseints.c
@@ -0,0 +1,114 @@
+// 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_unsigned_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-206/duncan-c-white/C/parseints.h b/challenge-206/duncan-c-white/C/parseints.h
new file mode 100644
index 0000000000..da5e145a86
--- /dev/null
+++ b/challenge-206/duncan-c-white/C/parseints.h
@@ -0,0 +1 @@
+extern int * parse_int_args( int argc, char ** argv, int argno, int * nel );
diff --git a/challenge-206/duncan-c-white/C/printarray.c b/challenge-206/duncan-c-white/C/printarray.c
new file mode 100644
index 0000000000..ddee597df3
--- /dev/null
+++ b/challenge-206/duncan-c-white/C/printarray.c
@@ -0,0 +1,39 @@
+#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-206/duncan-c-white/C/printarray.h b/challenge-206/duncan-c-white/C/printarray.h
new file mode 100644
index 0000000000..40efb83277
--- /dev/null
+++ b/challenge-206/duncan-c-white/C/printarray.h
@@ -0,0 +1 @@
+extern void print_int_array( int maxw, int nel, int * results, char sep, FILE * out );
diff --git a/challenge-206/duncan-c-white/README b/challenge-206/duncan-c-white/README
index 3a95b6badb..7fd1e70858 100644
--- a/challenge-206/duncan-c-white/README
+++ b/challenge-206/duncan-c-white/README
@@ -26,7 +26,8 @@ into account.  Might convert each hh:mm time into a number of minutes,
 then sort the array.. then check every adjacant pair (including the
 wraparound pair, i.e the last and the first)..
 
-No C solutions today.  Might do them later..
+GUEST LANGUAGE: As a bonus (but a day after the challenge finished), I also
+had a go at translating ch-1.pl into C (look in the C directory for that)
 
 
 Task 2: Array Pairings
@@ -63,4 +64,5 @@ to me that this sounds like a recursive solution..  Pick each possible
 pair involving the first element and each of the others (in turn),
 remove them, calculate and total up the minimum, then recurse.
 
-No C solutions today.  Might do them later..
+GUEST LANGUAGE: As a bonus (but a day after the challenge finished), I also
+had a go at translating ch-2.pl into C (look in the C directory for that)
diff --git a/challenge-206/duncan-c-white/perl/ch-2.pl b/challenge-206/duncan-c-white/perl/ch-2.pl
index 1a1b92330a..d58313cd2a 100755
--- a/challenge-206/duncan-c-white/perl/ch-2.pl
+++ b/challenge-206/duncan-c-white/perl/ch-2.pl
@@ -81,6 +81,8 @@ fun find_all( $sum, $solarrayref, @list )
 		my $second = $list[$spos];
 		my $min = min($first,$second);
 		my @newl = ( @list[0..$spos-1], @list[$spos+1..$#list] );
+		say "debug: removed $first and $second (min $min), leaving ",
+			join(',',@newl) if $debug;
 		find_all( $sum+$min, $solarrayref, @newl );
 	}
 }