From 016a442062080d3f5281c389883b48ac114dda66 Mon Sep 17 00:00:00 2001 From: dcw Date: Mon, 17 Apr 2023 17:52:19 +0100 Subject: imported my C solutions to challenge 212 a day late and tweaked some comments in README files and ch-2.pl --- challenge-212/duncan-c-white/C/.cbuild | 1 - challenge-212/duncan-c-white/C/Makefile | 18 ++ challenge-212/duncan-c-white/C/README | 25 +++ challenge-212/duncan-c-white/C/args.c | 234 ++++++++++++++++++++++++++ challenge-212/duncan-c-white/C/args.h | 12 ++ challenge-212/duncan-c-white/C/ch-1.c | 79 +++++++++ challenge-212/duncan-c-white/C/ch-2.c | 245 ++++++++++++++++++++++++++++ challenge-212/duncan-c-white/C/parseints.c | 114 +++++++++++++ challenge-212/duncan-c-white/C/parseints.h | 1 + challenge-212/duncan-c-white/C/printarray.c | 39 +++++ challenge-212/duncan-c-white/C/printarray.h | 1 + challenge-212/duncan-c-white/README | 8 +- challenge-212/duncan-c-white/perl/ch-2.pl | 59 +++++-- 13 files changed, 814 insertions(+), 22 deletions(-) create mode 100644 challenge-212/duncan-c-white/C/Makefile create mode 100644 challenge-212/duncan-c-white/C/README create mode 100644 challenge-212/duncan-c-white/C/args.c create mode 100644 challenge-212/duncan-c-white/C/args.h create mode 100644 challenge-212/duncan-c-white/C/ch-1.c create mode 100644 challenge-212/duncan-c-white/C/ch-2.c create mode 100644 challenge-212/duncan-c-white/C/parseints.c create mode 100644 challenge-212/duncan-c-white/C/parseints.h create mode 100644 challenge-212/duncan-c-white/C/printarray.c create mode 100644 challenge-212/duncan-c-white/C/printarray.h diff --git a/challenge-212/duncan-c-white/C/.cbuild b/challenge-212/duncan-c-white/C/.cbuild index 835981f6f1..a14ec76520 100644 --- a/challenge-212/duncan-c-white/C/.cbuild +++ b/challenge-212/duncan-c-white/C/.cbuild @@ -1,5 +1,4 @@ BUILD = ch-1 ch-2 -BUILD = ch-1 CFLAGS = -Wall -g #LDFLAGS = -lm #CFLAGS = -g diff --git a/challenge-212/duncan-c-white/C/Makefile b/challenge-212/duncan-c-white/C/Makefile new file mode 100644 index 0000000000..1b34ccd3b2 --- /dev/null +++ b/challenge-212/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 parseints.o printarray.o +ch-1.o: ch-1.c args.h parseints.h printarray.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-212/duncan-c-white/C/README b/challenge-212/duncan-c-white/C/README new file mode 100644 index 0000000000..49cf0e852c --- /dev/null +++ b/challenge-212/duncan-c-white/C/README @@ -0,0 +1,25 @@ +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. + +However, ch-2.c is a complete rethink, as usual I solved ch-2.pl in a Perlish +idiomatic way using (for example) a hashset for distinct values and an +array of arrays for the output. Storage management in C is much harder, so +I decided to store the output sequences in the (reordered) list[nel] array, +i.e. an inplace solution because we already had the right amount of +storage allocated, storing size elements per sequence. This led me to +construct the desired output on the fly at the end. + +In addition, to make things simpler to reason about I decided to start by +sorting the entire list[nel] array via qsort - so from then I passed the +"sorted list[ nel]" array around instead. To check whether an element was +present in a sorted subarray, I used a simple "posisin( v, arr, s, f )" +function to check whether v is in arr[s..f], returning the position >= 0 +if found, or -1 if not found. This implemented distinct-ness and +set membership. + +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]. diff --git a/challenge-212/duncan-c-white/C/args.c b/challenge-212/duncan-c-white/C/args.c new file mode 100644 index 0000000000..20c21e6c30 --- /dev/null +++ b/challenge-212/duncan-c-white/C/args.c @@ -0,0 +1,234 @@ +#include +#include +#include +#include +#include +#include + + +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 +#include +#include +#include +#include +#include + +#include "args.h" +#include "parseints.h" +#include "printarray.h" + + +int main( int argc, char **argv ) +{ + int argno = process_flag_n_m_args( "jumping-letters", argc, argv, + 2, 1000, "word intlist" ); + char *word = argv[argno++]; + int nel; + int *list = parse_int_args( argc, argv, argno, &nel ); + + if( debug ) + { + printf( "debug: word = %s, list: ", word ); + print_int_array( 60, nel, list, ',', stdout ); + putchar( '\n' ); + } + + int len = strlen(word); + + if( len != nel ) + { + fprintf( stderr, "jumping-letters: word (len %d) must be " + "same length as list (len %d)\n", len, nel ); + exit(1); + } + + for( int pos=0; pos < len; pos++ ) + { + char letter = word[pos]; + int offset = list[pos]; + if( debug ) + { + printf( "debug: pos: %d, letter: %c, offset: %d\n", + pos, letter, offset ); + } + int base = 0; + if( islower(letter) ) + { + base = 'a'; + } else if( isupper(letter) ) + { + base = 'A'; + } else + { + continue; + } + int lpos = letter-base; + offset = (offset + lpos) % 26; + if( debug ) + { + printf( "debug: letter=%c, base=%c, lpos=%d, " + "offset=%d\n", letter, base, lpos, offset ); + } + letter = offset+base; + word[pos] = letter; + if( debug ) + { + printf( "debug: newletter=%c\n", letter ); + } + } + + printf( "%s\n", word ); + free( list ); + return 0; +} diff --git a/challenge-212/duncan-c-white/C/ch-2.c b/challenge-212/duncan-c-white/C/ch-2.c new file mode 100644 index 0000000000..d718969906 --- /dev/null +++ b/challenge-212/duncan-c-white/C/ch-2.c @@ -0,0 +1,245 @@ +// +// Task 2: Rearrange Groups (into sequences) +// +// C version. +// + +#include +#include +#include +#include +#include + +#include "args.h" +#include "parseints.h" +#include "printarray.h" + + +// qsort comparator for int elements +int intcompare( const void *a, const void *b ) +{ + int *ai = (int *)a; + int *bi = (int *)b; + return *ai - *bi; +} + + +// +// int p = posisin( v, slist, spos, epos ); +// Attempt to find (the first instance of) v in slist[spos..epos]. If +// we find it, return the position of the first v. If not, return -1. +// +int posisin( int v, int *slist, int spos, int epos ) +{ + for( int i=spos; i<=epos; i++ ) + { + if( slist[i] == v ) return i; + } + return -1; +} + + +// +// bool found = find_seq_at( nel, slist[], spos, size, pos[] ); +// Find a single size-element sequence X, X+1, X+2.. X+size-1 starting +// at spos. If such a sequence can be found, store the slist[i] index +// positions in pos[size] and return true, otherwise return false. +// +bool find_seq_at( int nel, int *slist, int spos, int size, int *pos ) +{ + pos[0] = spos; + int wantval = slist[spos]; + for( int i=1; i0 && posisin( slist[i], slist, 0, i-1 ) >= 0 ) + { + continue; + } + // x-1 must not be present + if( i>0 && posisin( slist[i]-1, slist, 0, i-1 ) >= 0 ) + { + continue; + } + #if 0 + if( debug ) + { + printf( "debug: found distinct value %d at pos %d\n", + slist[i], i ); + } + #endif + if( find_seq_at( nel, slist, i, size, pos ) ) + { + return true; + } + } + return false; +} + + + +// +// reorder( nel, slist, size, pos ); +// Given slist[0..nel-1] and a sequence found at pos[0..size-1], +// reorder the slist so that the sequence is at the front. +// +void reorder( int nel, int *slist, int size, int *pos ) +{ + for( int i=0; i=i; j-- ) + { + slist[j+1] = slist[j]; + } + slist[i] = v; + } + } +} + + +// +// bool done = find_all_sequences( slist, nel, size ); +// Attempt to find all sequences (each of length size and +// comprising X, X+1, X+2..X+size-1) from sorted slist[nel], +// modifying slist[] so that the sequences are stored at the +// front of slist[], +// ie the first size-elements in slist[] will be the first +// sequence, etc. +// Return true if this can be successfully done, or false if it can't. +// +bool find_all_sequences( int *slist, int nel, int size ) +{ + if( nel % size != 0 ) return false; + + int nseqs = nel / size; + + for( int seqno=1; seqno <= nseqs; seqno++ ) + { + if( debug ) + { + printf( "debug: seq pass %d, slist is ", seqno ); + print_int_array( 60, nel, slist, ',', stdout ); + putchar( '\n' ); + } + int pos[size]; // positions of sequence elements + bool found = find_isolated_seq_posns( size, slist, nel, pos ); + if( ! found ) + { + if( debug ) + { + printf( "debug: failed to find a sequence\n" ); + } + return false; + } + if( debug ) + { + printf( "debug: found seq " ); + for( int i=0; i0 ) putchar( ',' ); + printf( "%d", slist[pos[i]] ); + } + printf( " at posns " ); + for( int i=0; i0 ) putchar( ',' ); + printf( "%d", pos[i] ); + } + putchar( '\n' ); + } + reorder( nel, slist, size, pos ); + if( debug ) + { + printf( "debug: have reordered slist " ); + print_int_array( 60, nel, slist, ',', stdout ); + putchar( '\n' ); + } + // move array ptr over the new sequence + nel -= size; + slist += size; + } + return true; +} + + +int main( int argc, char **argv ) +{ + int argno = process_flag_n_m_args( "rearrange-groups", argc, argv, + 2, 1000, "groupsize intlist" ); + int size = atoi(argv[argno++]); + + int nel; + int *list = parse_int_args( argc, argv, argno, &nel ); + + if( debug ) + { + printf( "debug: size=%d, list: ", size ); + print_int_array( 60, nel, list, ',', stdout ); + putchar( '\n' ); + } + + qsort( list, nel, sizeof(int), &intcompare ); + + if( debug ) + { + printf( "debug: sorted list: " ); + print_int_array( 60, nel, list, ',', stdout ); + putchar( '\n' ); + } + + bool done = find_all_sequences( list, nel, size ); + + if( done ) + { + int *lp = list; + for( int i=0; i0 ) fputs( ", ", stdout ); + putchar( '(' ); + for( int j=0; j0 ) putchar( ',' ); + printf( "%d", *lp++ ); + } + putchar( ')' ); + } + putchar( '\n' ); + } else + { + printf( "-1\n" ); + } + + free( list ); + + return 0; +} diff --git a/challenge-212/duncan-c-white/C/parseints.c b/challenge-212/duncan-c-white/C/parseints.c new file mode 100644 index 0000000000..3e820eb334 --- /dev/null +++ b/challenge-212/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 +#include +#include +#include +#include +#include + +#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 +#include + + +// print_int_array( maxw, nelements, results[], sep, outfile ); +// format results[0..nelements-1] as a 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 maxw ) + { + fputc( '\n', out ); + linelen = 0; + } else if( i>0 ) + { + fputc( ' ', out ); + linelen++; + } + + linelen += len; + fprintf( out, "%s", buf ); + if( i0 ) + //{ + // fputc( '\n', out ); + //} +} diff --git a/challenge-212/duncan-c-white/C/printarray.h b/challenge-212/duncan-c-white/C/printarray.h new file mode 100644 index 0000000000..40efb83277 --- /dev/null +++ b/challenge-212/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-212/duncan-c-white/README b/challenge-212/duncan-c-white/README index 89f2c82665..cbd23d4076 100644 --- a/challenge-212/duncan-c-white/README +++ b/challenge-212/duncan-c-white/README @@ -25,8 +25,8 @@ Example 2 MY NOTES: sounds very easy. Essentially ROT(n) for a different value of n for each letter. -GUEST LANGUAGE: As a bonus, I will have a go at translating ch-1.pl into C -but I'll do that tomorrow. +GUEST LANGUAGE: As a bonus, I've had a go at translating ch-2.pl into C, +look in the C/ directory for that. Task 2: Rearrange Groups @@ -65,5 +65,5 @@ consecutive-numbers isolated at the start, ie. where first(run)-1 is not present in the input? Then we should be able to: repeatedly pick any one run, add it to solution, remove it from input, repeat until input is empty. -GUEST LANGUAGE: As a bonus, I will have a go at translating ch-2.pl into C -but I'll do that tomorrow. +GUEST LANGUAGE: As a bonus, I've had a go at translating ch-2.pl into C, +look in the C/ directory for that. diff --git a/challenge-212/duncan-c-white/perl/ch-2.pl b/challenge-212/duncan-c-white/perl/ch-2.pl index 4cc4a901ee..68d1046a07 100755 --- a/challenge-212/duncan-c-white/perl/ch-2.pl +++ b/challenge-212/duncan-c-white/perl/ch-2.pl @@ -1,6 +1,6 @@ #!/usr/bin/perl # -# Task 2: Rearrange Groups +# Task 2: Rearrange Groups (into sequences) # # You are given a list of integers and group size greater than zero. # @@ -118,28 +118,53 @@ fun find_isolated_seq( $size, @list ) -my @output; # array of size-tuples - -my $changed; -do +# +# my $done = find_all_sequences( \@list, $size, \@output ); +# Attempt to extract all sequences (each of length $size and +# comprising X, X+1, X+2..X+size-1) from @list, modifying it, +# and building @output - a list of size-tuples. Return true +# if it can be successfully done (leaving @list empty and the +# sequences in @output), false if it can't be done. +# +sub find_all_sequences ($$$) { - my @seq = find_isolated_seq( $size, @list ); - say "debug: list=", join(',',@list), ", found seq=", join(',',@seq) - if $debug; - $changed = @seq ? 1 : 0; - if( $changed ) + my( $listref, $size, $outputref ) = @_; + + if( @$listref % $size != 0 ) + { + return 0; + } + + my $nseqs = @$listref / $size; + + foreach my $seqno (1..$nseqs) { - push @output, \@seq; - @list = remove_one_of_seq( \@seq, @list ); + my @seq = find_isolated_seq( $size, @$listref ); + say "debug: list=", join(',',@$listref), ", found seq=", + join(',',@seq) + if $debug; + if( @seq == 0 ) + { + say( "debug: failed to find a sequence, leftover list". + " is: ", join(',',@$listref) ) if $debug; + return 0; + } + push @$outputref, \@seq; + @$listref = remove_one_of_seq( \@seq, @$listref ); + say( "debug: output: ", join(', ', + map { '('. join(',',@$_). ')' } @$outputref + ), ", list=",join(',',@$listref) ) + if $debug; } - say( "debug: output: ", join(', ', map { '('. join(',',@$_). ')' } @output), ", list=",join(',',@list) ) - if $debug; + return 1; +} + -} while( $changed && @list ); +my @output; # array of size-tuples -say( "debug: leftover list is: ", join(',',@list) ) if $debug; +my $done = find_all_sequences( \@list, $size, \@output ); -if( @list == 0 ) +if( $done ) { say join(', ', map { '('. join(',',@$_). ')' } @output); } else -- cgit