Merge pull request #8008 from dcw803/master

belatedly completed the C translation of task 2 (challenge 214)

6 files changed, 170 insertions, 11 deletions

diff --git a/challenge-214/duncan-c-white/C/.cbuild b/challenge-214/duncan-c-white/C/.cbuild
index 835981f6f1..c168e34403 100644
--- a/challenge-214/duncan-c-white/C/.cbuild
+++ b/challenge-214/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-214/duncan-c-white/C/Makefile b/challenge-214/duncan-c-white/C/Makefile
index 3a6ebb224c..6ac7c0c23c 100644
--- a/challenge-214/duncan-c-white/C/Makefile
+++ b/challenge-214/duncan-c-white/C/Makefile
@@ -1,7 +1,7 @@
 # Makefile rules generated by CB
 CC	= gcc
 CFLAGS	= -Wall -g
-BUILD	= ch-1
+BUILD	= ch-1 ch-2
 
 all:	$(BUILD)
 
@@ -11,6 +11,8 @@ clean:
 args.o:	args.c
 ch-1:	ch-1.o args.o parseints.o printarray.o rank.o
 ch-1.o:	ch-1.c args.h parseints.h printarray.h rank.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
 rank.o:	rank.c rank.h
diff --git a/challenge-214/duncan-c-white/C/README b/challenge-214/duncan-c-white/C/README
index ba67141dfe..70410cd471 100644
--- a/challenge-214/duncan-c-white/C/README
+++ b/challenge-214/duncan-c-white/C/README
@@ -1,4 +1,4 @@
-Thought I'd also have a go at translating ch-1.pl and ch-2.pl (coming soon) into C..
+Thought I'd also have a go at translating ch-1.pl and ch-2.pl into C..
 
 Both C versions produce very similar (non-debugging and debugging)
 output to the Perl originals.
diff --git a/challenge-214/duncan-c-white/C/ch-2.c b/challenge-214/duncan-c-white/C/ch-2.c
new file mode 100644
index 0000000000..4671058c9a
--- /dev/null
+++ b/challenge-214/duncan-c-white/C/ch-2.c
@@ -0,0 +1,159 @@
+// Task 2: Collect Points
+//
+// C translation
+
+#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"
+
+
+typedef struct { int startpos, len; } pair;
+
+
+//
+// pair moves[nel];
+// int nmoves = all_possible_first_moves( list, nel, moves );
+//	Find all possible first (immediate) moves - each move being
+//	a (startpos,len) pairs - and store them into moves[nel]
+//	and then return the number of moves found.
+//
+int all_possible_first_moves( int *list, int nel, pair *moves )
+{
+	int nmoves = 0;
+	int pos = 0;
+	pair *mp = moves;
+	do
+	{
+		int currval = list[pos];
+		int len = 0;
+		int startpos;
+		for( startpos=pos; pos < nel && list[pos]==currval; pos++ )
+		{
+			len++;
+		}
+		mp->startpos = startpos;
+		mp->len      = len;
+		nmoves++;
+		mp++;
+	} while( pos < nel );
+	return nmoves;
+}
+
+
+int bestsc;
+char bestmoves[1024];
+
+
+//
+// find_all( currsc, currmoves, list, nel );
+//	Find all possible sequences of moves removing item-sequences
+//	from list[nel], given that the current score to this point is currsc,
+//	and the current move string to this point is currmoves, and
+//	track the best (highest scoring) move sequence in bestsc & bestmoves
+//
+void find_all( int currsc, char *currmoves, int *list, int nel )
+{
+	if( nel == 0 )
+	{
+		if( debug )
+		{
+			printf( "debug: found solution, currsc=%d, bestsc=%d\n",
+				currsc, bestsc );
+		}
+		if( currsc > bestsc )
+		{
+			bestsc = currsc;
+			strcpy( bestmoves, currmoves );
+			if( debug )
+			{
+				printf( "debug: found new best, bestsc=%d, "
+					"bestmoves=%s\n", bestsc, bestmoves );
+			}
+		}
+		return;
+	}
+
+	pair moves[nel];
+	int nmoves = all_possible_first_moves( list, nel, moves );
+
+	for( int m=0; m<nmoves; m++ )
+	{
+		int startpos = moves[m].startpos;
+		int len = moves[m].len;
+
+		int val = list[startpos];
+		int newlist[nel];
+		int newnel = 0;
+
+		// newlist = list minus startpos.. startpos+len-1
+		for( int i=0; i<startpos; i++ ) newlist[i] = list[i];
+		for( int i=startpos+len; i<nel; i++ ) newlist[i-len] = list[i];
+
+		newnel = nel-len;
+		newlist[newnel] = -1;
+
+		char newmoves[1024];
+		strcpy( newmoves, currmoves );
+		if( *newmoves ) strcat( newmoves, "," );
+		char *s = newmoves+strlen(newmoves);
+		sprintf( s, "%d:%d/%d", val, startpos, len );
+		if( debug )
+		{
+			printf( "debug: list=" );
+			print_int_array( 60, nel, list, ',', stdout );
+			printf( ", currmoves=%s, removed %d:%d/%d, ",
+				currmoves, val, startpos, len );
+			printf( "newmoves=%s, made newlist[%d]: ",
+				newmoves, newnel );
+			print_int_array( 60, newnel, newlist, ',', stdout );
+			putchar( '\n' );
+
+		}
+		find_all( currsc+len*len, newmoves, newlist, newnel );
+	}
+}
+
+
+int main( int argc, char **argv )
+{
+	int argno = process_flag_n_m_args( "collect-points", argc, argv,
+		1, 1000, "intlist" );
+	int nel;
+	int *list = parse_int_args( argc, argv, argno, &nel );
+
+	if( debug )
+	{
+		printf( "debug: list: " );
+		print_int_array( 60, nel, list, ',', stdout );
+		putchar( '\n' );
+	}
+
+#if 0
+	pair moves[nel];
+	int nmoves = all_possible_first_moves( list, nel, moves );
+
+	printf( "found %d moves: ", nmoves );
+	for( int i=0; i<nmoves; i++ )
+	{
+		printf( "%d/%d ", moves[i].startpos, moves[i].len );
+	}
+	putchar( '\n' );
+#endif
+
+	bestsc = 0;
+	strcpy( bestmoves, "" );
+
+	find_all( 0, "", list, nel );
+
+	printf( "%d\n%s\n", bestsc, bestmoves );
+
+	free( list );
+	return 0;
+}
diff --git a/challenge-214/duncan-c-white/README b/challenge-214/duncan-c-white/README
index 17df43b304..ea2fd02b33 100644
--- a/challenge-214/duncan-c-white/README
+++ b/challenge-214/duncan-c-white/README
@@ -107,6 +107,5 @@ greatest score contribution, cos otherwise we'd take one of the "length 3"
 sequences and pass up the "length 6" sequence that becomes available later..
 So, yes, it's a brute force "find all" type problem..
 
-GUEST LANGUAGE: As a bonus, I will soon have a go at translating ch-2.pl
-into C, but I run out of time today.. when it's done, look in the C/
-directory for that.
+GUEST LANGUAGE: As a bonus, I had a go at translating ch-2.pl into C, a
+few days late: look in the C/ directory for that.
diff --git a/challenge-214/duncan-c-white/perl/ch-2.pl b/challenge-214/duncan-c-white/perl/ch-2.pl
index ad6d7facf5..380906e047 100755
--- a/challenge-214/duncan-c-white/perl/ch-2.pl
+++ b/challenge-214/duncan-c-white/perl/ch-2.pl
@@ -56,9 +56,8 @@
 # sequences and pass up the "length 6" sequence that becomes available later..
 # So, yes, it's a brute force "find all" type problem..
 # 
-# GUEST LANGUAGE: As a bonus, I will soon have a go at translating ch-2.pl
-# into C, but I run out of time today.. when it's done, look in the C/
-# directory for that.
+# GUEST LANGUAGE: As a bonus, I had a go at translating ch-2.pl into C, a
+# few days late: look in the C/ directory for that.
 # 
 
 use strict;
@@ -107,8 +106,8 @@ my $bestmoves;
 # find_all( $currsc, $currmoves, @list );
 #	Find all possible sequences of moves removing item-sequences
 #	from @list, given that the current score to this point is $currsc,
-#	and the current move string to this point is $currmoves,
-#	and track the best (highest scoring) move sequence in $bestsc.
+#	and the current move string to this point is $currmoves, and
+#	track the best (highest scoring) move sequence in $bestsc & $bestmoves
 #
 fun find_all( $currsc, $currmoves, @list )
 {