From 0f83c52e064e6670b23ed4fb14c373fd935f816c Mon Sep 17 00:00:00 2001 From: dcw Date: Sun, 20 Nov 2022 20:27:44 +0000 Subject: after last week's deadline, I did a translation of task 1 into Pascal.. --- challenge-190/duncan-c-white/README | 2 + challenge-190/duncan-c-white/pascal/Makefile | 12 ++ challenge-190/duncan-c-white/pascal/ch-1.pas | 158 ++++++++++++++++++ challenge-190/duncan-c-white/pascal/ch-2.c | 133 +++++++++++++++ challenge-190/duncan-c-white/pascal/ch-2.pas | 239 +++++++++++++++++++++++++++ 5 files changed, 544 insertions(+) create mode 100644 challenge-190/duncan-c-white/pascal/Makefile create mode 100644 challenge-190/duncan-c-white/pascal/ch-1.pas create mode 100644 challenge-190/duncan-c-white/pascal/ch-2.c create mode 100644 challenge-190/duncan-c-white/pascal/ch-2.pas diff --git a/challenge-190/duncan-c-white/README b/challenge-190/duncan-c-white/README index 9edc65e930..113911c007 100644 --- a/challenge-190/duncan-c-white/README +++ b/challenge-190/duncan-c-white/README @@ -29,6 +29,8 @@ MY NOTES: very easy. GUEST LANGUAGE: As a bonus, I also had a go at translating ch-1.pl into C (look in the C directory for the translation) +After the deadline, I added a Pascal version of ch-1.pl (look in the +pascal directory for that). Task 2: Decoded List diff --git a/challenge-190/duncan-c-white/pascal/Makefile b/challenge-190/duncan-c-white/pascal/Makefile new file mode 100644 index 0000000000..109c2a6e86 --- /dev/null +++ b/challenge-190/duncan-c-white/pascal/Makefile @@ -0,0 +1,12 @@ +BUILD = ch-1 ch-2 + +all: $(BUILD) + +clean: + /bin/rm -f $(BUILD) *.o core a.out + +ch-1: ch-1.pas + fpc ch-1.pas + +ch-2: ch-2.pas + fpc ch-2.pas diff --git a/challenge-190/duncan-c-white/pascal/ch-1.pas b/challenge-190/duncan-c-white/pascal/ch-1.pas new file mode 100644 index 0000000000..91c84ba9b9 --- /dev/null +++ b/challenge-190/duncan-c-white/pascal/ch-1.pas @@ -0,0 +1,158 @@ +(* + * Task 1: Capital Detection + * + * GUEST LANGUAGE: THIS IS THE PASCAL VERSION OF ch-1.pl, suitable for + * the Free Pascal compiler. + *) + +uses sysutils; + +type strarray = array [0..100] of string; + +var debug : boolean; + + +(* process_args_exactly_n( n, str[] ); + * Process command line arguments, + * specifically process the -d flag, + * check that there are exactly n remaining arguments, + * copy remaining args to str[n], a string array + *) +procedure process_args_exactly_n( n : integer; var str : strarray ); + +(* note: paramStr(i)); for i in 1 to paramCount() *) + +var + nparams : integer; + nel : integer; + arg : integer; + i : integer; + p : string; + +begin + nparams := paramCount(); + + arg := 1; + if (nparams>0) and SameText( paramStr(arg), '-d' ) then + begin + debug := true; + arg := 2; + end; + + nel := 1+nparams-arg; + if nel <> n then + begin + writeln( stderr, + 'Usage: cap-det [-d] target string' ); + halt; + end; + + + // elements are in argv[arg..nparams], copy them to str[] + + for i := arg to nparams do + begin + p := paramStr(i); + str[i-arg] := p; + end; +end; + + +const + Upper = ['A'..'Z']; + Lower = ['a'..'z']; + + +function capdetect( str : string ) : boolean; +var + alllower, allupper : boolean; + len, i : integer; +begin + len := length(str); + if debug then + begin + writeln( 'debug: capdetect(', str, '): entry, str1=', str[1] ); + end; + if str[1] in Upper then + begin + if debug then + begin + writeln( 'debug: capdetect(', str, '): starts with upper' ); + end; + alllower := true; + allupper := true; + for i := 2 to len do + begin + if not( str[i] in Lower) then + begin + if debug then + begin + writeln( 'debug: capdetect(', str, '): found ', str[i], ' not lower case' ); + end; + alllower := false; + end; + if not( str[i] in Upper) then + begin + if debug then + begin + writeln( 'debug: capdetect(', str, '): found ', str[i], ' not upper case' ); + end; + allupper := false; + end; + end; + if alllower or allupper then exit( true ); + end else if str[1] in Lower then + begin + if debug then + begin + writeln( 'debug: capdetect(', str, '): starts with lower' ); + end; + alllower := true; + for i := 2 to len do + begin + if not( str[i] in Lower) then + begin + writeln( 'debug: capdetect(', str, '): found ', str[i], ' not lower case' ); + alllower := false; + end; + end; + if alllower then exit( true ); + end; + exit( false ); +end; + + +procedure main; + +var + strarr : strarray; + str : string; + ok : boolean; + +begin + debug := false; + + process_args_exactly_n( 1, strarr ); + str := strarr[0]; + + if debug + then begin + writeln( 'debug: str=', str ); + end; + + ok := capdetect( str ); + + if ok then + begin + writeln( 1 ); + end else + begin + writeln( 0 ); + end; + +end; + + +begin + main; +end. diff --git a/challenge-190/duncan-c-white/pascal/ch-2.c b/challenge-190/duncan-c-white/pascal/ch-2.c new file mode 100644 index 0000000000..daca37a01d --- /dev/null +++ b/challenge-190/duncan-c-white/pascal/ch-2.c @@ -0,0 +1,133 @@ +// +// Task 2: Decoded List +// +// C version. +// + +#include +#include +#include +#include +#include +#include + +#include "args.h" + + +typedef char bigstr[1024]; + + +char enc[27]; // element 0 not used + + +// +// decode_all( str, prefix, results[], &nr ); +// Decode str, taking 1 or 2 digits off the front (as long +// as the number that results is between 1..26), producing +// all the possible decodings (adding prefix to each decoding +// that we produce) +// +void decode_all( char *str, char *prefix, bigstr *results, int *nr ) +{ + if( *str == '\0' ) + { + int i = (*nr); + strcpy( results[i], prefix ); + if( debug ) + { + printf( "found solution %d = %s\n", i, prefix ); + } + (*nr)++; + return; + } + + // try taking off the first char.. + char first = *str; + char *rem = str+1; + if( debug ) + { + printf( "debug: first=%c, rem=%s\n", first, rem ); + } + if( strcmp(rem,"0") != 0 && first != '0') + { + bigstr p2; + strcpy( p2, prefix ); + char *p = p2+strlen(p2); + *p++ = enc[first-'0']; + *p++ = '\0'; + if( debug ) + { + printf( "debug: recurse with rem=%s, first=%c, prefix=%s\n", + rem, first, p2 ); + } + decode_all( rem, p2, results, nr ); + } + + if( strlen(str) > 1 ) + { + // try taking off the first two chars.. + int first = (*str-'0')*10 + (str[1]-'0'); + char *rem = str+2; + if( debug ) + { + printf( "debug: first=%d, rem=%s\n", first, rem ); + } + + if( strcmp(rem,"0") != 0 && first <= 26 ) + { + bigstr p2; + strcpy( p2, prefix ); + char *p = p2+strlen(p2); + *p++ = enc[first]; + *p++ = '\0'; + if( debug ) + { + printf( "debug: recurse with rem=%s, first=%d, prefix=%s\n", + rem, first, p2 ); + } + decode_all( rem, p2, results, nr ); + } + } +} + + +int main( int argc, char **argv ) +{ + int argno = process_flag_n_args( "decoded-list", argc, argv, + 1, "encoded string" ); + + char *str = argv[argno++]; + + if( debug ) + { + printf( "debug: str=%s\n", str ); + } + + for( char ch='A'; ch<='Z'; ch++ ) + { + enc[ch-'@'] = ch; + if( debug ) + { + printf( "debug: enc[%d] = %c\n", ch-'@', ch ); + } + } + + + bigstr results[1024]; + int nr = 0; + decode_all( str, "", results, &nr ); + + bool first = true; + for( int i=0; i0) and SameText( paramStr(arg), '-d' ) then + begin + debug := true; + arg := 2; + end; + + nel := 1+nparams-arg; + if nel < 2 then + begin + writeln( stderr, + 'Usage: summations [-d] list of +ve numbers' ); + halt; + end; + + if nel > maxints then + begin + writeln( stderr, + 'summations too many numbers (max ', + maxints, ')' ); + halt; + end; + + if debug then + begin + writeln( 'debug: arg', arg, ', nparams=', nparams, ', nel=', + nel ); + end; + + // elements are in argv[arg..nparams], copy them to v[] + + // check that all remaining arguments are +ve integers, + // and then copy them to v[] + for i := arg to nparams do + begin + p := paramStr(i); + if (p[1] < '0') or (p[1] > '9') then + begin + writeln( stderr, + 'summations arg ', i, + ' (', p, ') is not a +ve number' ); + halt; + end; + v[i-arg] := StrToInt( p ); + end; +end; + + +(* + * rement the frequency of el in freq (adding an element if + * it's not there yet) + *) +procedure incfreq( var freq : pairarray; var np : integer; el : integer ); + +var + i : integer; + over : boolean; + +begin + over := false; + for i:=0 to np-1 do + begin + if not over and (freq[i].el = el) + then begin + inc( freq[i].freq ); + over := true; + end; + end; + if not over then + begin; + freq[np].el := el; + freq[np].freq := 1; + inc( np ); + end; +end; + + + +(* + * int deg = degree( arr, f, t ); + * Calculate the degree (max frequency) of array[f..t]. + *) +function degree( arr : intarray; f, t : integer ) : integer; + +var + i, max : integer; + np : integer; (* number of pairs in freq *) + freq : pairarray; + +begin + np := 0; + + for i:=f to t + do begin + incfreq( freq, np, arr[i] ); + end; + + (* now find the maximum frequency in freq[] *) + max := 0; + for i:=0 to np-1 + do begin + if freq[i].freq > max + then begin + max := freq[i].freq; + end; + end; + degree := max; +end; + + +(* + * makeslicestr( arr, f, t, slicestr ); + * Build slicestr, a plain text string containing all elements + * arr[f..t], comma separated + * Sort of like slicestr = join(',', arr[f..t]); + *) +procedure makeslicestr( arr : intarray; f, t : integer; var slicestr : ansistring ); + +var + i : integer; + +begin + slicestr := ''; + for i:=f to t + do begin + if i>f + then begin + AppendStr( slicestr, ',' ); + end; + AppendStr( slicestr, IntToStr( arr[i] ) ); + end; +end; + + +procedure main; + +var + nel : integer; + ilist : intarray; + wholedeg : integer; + slicestr : ansistring; + smallarray : ansistring; + smallestarraysize : integer; + f, t : integer; + deg, size : integer; + +begin + debug := false; + + process_args( nel, ilist ); + + wholedeg := degree( ilist, 0, nel-1 ); + + makeslicestr( ilist, 0, nel-1, slicestr ); + + if debug then + begin + writeln( 'debug: wholedeg = ', wholedeg ); + end; + + smallestarraysize := nel+1; + + for f:=0 to nel-2 do + begin + for t:=f+1 to nel-1 do + begin + deg := degree( ilist, f, t ); + if deg = wholedeg then + begin + makeslicestr( ilist, f, t, slicestr ); + if debug then + begin + writeln( 'debug: found sub-array ', + slicestr, ' with degree ', deg ); + end; + + size := t+1-f; + if size < smallestarraysize then + begin + smallestarraysize := size; + smallarray := slicestr; + end; + end; + end; + end; + + writeln( smallarray ); +end; + + +begin + main; +end. -- cgit From e2232acaf7deca62a2551afe032cdef96055cae5 Mon Sep 17 00:00:00 2001 From: dcw Date: Sun, 20 Nov 2022 20:34:11 +0000 Subject: fixed 2 small typos in Pascal ch-1.pas and the Makefile --- challenge-190/duncan-c-white/pascal/Makefile | 2 +- challenge-190/duncan-c-white/pascal/ch-1.pas | 2 +- 2 files changed, 2 insertions(+), 2 deletions(-) diff --git a/challenge-190/duncan-c-white/pascal/Makefile b/challenge-190/duncan-c-white/pascal/Makefile index 109c2a6e86..ad308de958 100644 --- a/challenge-190/duncan-c-white/pascal/Makefile +++ b/challenge-190/duncan-c-white/pascal/Makefile @@ -1,4 +1,4 @@ -BUILD = ch-1 ch-2 +BUILD = ch-1 #ch-2 all: $(BUILD) diff --git a/challenge-190/duncan-c-white/pascal/ch-1.pas b/challenge-190/duncan-c-white/pascal/ch-1.pas index 91c84ba9b9..e6eb830bb6 100644 --- a/challenge-190/duncan-c-white/pascal/ch-1.pas +++ b/challenge-190/duncan-c-white/pascal/ch-1.pas @@ -43,7 +43,7 @@ begin if nel <> n then begin writeln( stderr, - 'Usage: cap-det [-d] target string' ); + 'Usage: cap-det [-d] string' ); halt; end; -- cgit From 285c81d101dfe254b96cf3bc74ce1411bb0be923 Mon Sep 17 00:00:00 2001 From: dcw Date: Sun, 20 Nov 2022 22:18:51 +0000 Subject: imported my solutions to this week's tasks in C and Perl, nice.. --- challenge-191/duncan-c-white/C/Makefile | 19 +++ challenge-191/duncan-c-white/C/README | 10 ++ challenge-191/duncan-c-white/C/args.c | 207 +++++++++++++++++++++++++++ challenge-191/duncan-c-white/C/args.h | 11 ++ challenge-191/duncan-c-white/C/ch-1.c | 66 +++++++++ challenge-191/duncan-c-white/C/ch-2.c | 90 ++++++++++++ challenge-191/duncan-c-white/C/nextintperm.c | 63 ++++++++ challenge-191/duncan-c-white/C/nextintperm.h | 1 + challenge-191/duncan-c-white/C/parseints.c | 114 +++++++++++++++ challenge-191/duncan-c-white/C/parseints.h | 1 + challenge-191/duncan-c-white/C/printarray.c | 39 +++++ challenge-191/duncan-c-white/C/printarray.h | 1 + challenge-191/duncan-c-white/README | 106 ++++++++------ challenge-191/duncan-c-white/perl/ch-1.pl | 78 ++++++++++ challenge-191/duncan-c-white/perl/ch-2.pl | 134 +++++++++++++++++ 15 files changed, 895 insertions(+), 45 deletions(-) create mode 100644 challenge-191/duncan-c-white/C/Makefile create mode 100644 challenge-191/duncan-c-white/C/README create mode 100644 challenge-191/duncan-c-white/C/args.c create mode 100644 challenge-191/duncan-c-white/C/args.h create mode 100644 challenge-191/duncan-c-white/C/ch-1.c create mode 100644 challenge-191/duncan-c-white/C/ch-2.c create mode 100644 challenge-191/duncan-c-white/C/nextintperm.c create mode 100644 challenge-191/duncan-c-white/C/nextintperm.h create mode 100644 challenge-191/duncan-c-white/C/parseints.c create mode 100644 challenge-191/duncan-c-white/C/parseints.h create mode 100644 challenge-191/duncan-c-white/C/printarray.c create mode 100644 challenge-191/duncan-c-white/C/printarray.h create mode 100755 challenge-191/duncan-c-white/perl/ch-1.pl create mode 100755 challenge-191/duncan-c-white/perl/ch-2.pl diff --git a/challenge-191/duncan-c-white/C/Makefile b/challenge-191/duncan-c-white/C/Makefile new file mode 100644 index 0000000000..4deb8e047f --- /dev/null +++ b/challenge-191/duncan-c-white/C/Makefile @@ -0,0 +1,19 @@ +# 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 nextintperm.o parseints.o printarray.o +ch-2.o: ch-2.c args.h nextintperm.h parseints.h printarray.h +nextintperm.o: nextintperm.c nextintperm.h +parseints.o: parseints.c args.h parseints.h printarray.h +printarray.o: printarray.c + diff --git a/challenge-191/duncan-c-white/C/README b/challenge-191/duncan-c-white/C/README new file mode 100644 index 0000000000..7da556012c --- /dev/null +++ b/challenge-191/duncan-c-white/C/README @@ -0,0 +1,10 @@ +Thought I'd also have a go at translating ch-1.pl and ch-2.pl into C.. + +Both produce near-identical (non-debugging and even debugging) output to my +Perl originals. + +They use several 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]. +- and newly broken out: permutation of an int-array: nextintperm.[ch]. diff --git a/challenge-191/duncan-c-white/C/args.c b/challenge-191/duncan-c-white/C/args.c new file mode 100644 index 0000000000..d4a2d38b9a --- /dev/null +++ b/challenge-191/duncan-c-white/C/args.c @@ -0,0 +1,207 @@ +#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( "twice-largest", argc, argv, + 1, 1000, "csvlist(int)" ); + int nel; + int *list = parse_int_args( argc, argv, argno, &nel ); + + if( debug ) + { + printf( "debug: nel=%d\n", nel ); + print_int_array( 70, nel, list, ',', stdout ); + putchar('\n'); + } + + int max = list[0]; + for( int i=1; i max ) max = list[i]; + } + + if( debug ) + { + printf( "debug: max el = %d\n", max ); + } + + int n = 0; + for( int i=0; i +#include +#include +#include +#include +#include + +#include "args.h" +#include "parseints.h" +#include "printarray.h" +#include "nextintperm.h" + + +// +// bool iscute = is_cute( arr, n ); +// Return true iff arr[0..n-1] is cute, as in the top spec. +// Return false otherwise. +// +bool is_cute( int *arr, int n ) +{ + for( int i0=0; i0 15 ) + { + fprintf( stderr, "cute-list: N (%d) must be in range 1..15)\n", n ); + exit(1); + } + + if( debug ) + { + printf( "debug: n=%d\n", n ); + } + + int list[16]; + for( int i=0; i +#include +#include +#include +#include +#include + + +#include "nextintperm.h" + + +// +// book exhausted = next_perm( arr, n ); +// Find and return the next permutation in lexicographic order +// of @arr[0..n-1]. Return false if @arr is the last permutation. +// 1. Find the largest index k such that a[k] < a[k + 1]. +// If no such index exists, we've found the last permutation. +// 2. Find the largest index l greater than k such that a[k] < a[l]. +// 3. Swap the value of a[k] with that of a[l]. +// 4. Reverse the sequence from a[k + 1] up to and including the final element a[n]. +// +bool next_perm( int *arr, int n ) +{ + n--; + + int k, l; + for( k=n-1; k>=0 && arr[k]>=arr[k+1]; k-- ) + { + } + if( k<0 ) return true; + for( l=n; l>k && arr[k]>=arr[l]; l-- ) + { + } + + #if 0 + printf( "next_perm: k=%d, l=%d, arr[k]=%d, arr[l]=%d\n", + k, l, arr[k], arr[l] ); + #endif + + // swap arr[k] and arr[l] + int t = arr[k]; + arr[k] = arr[l]; + arr[l] = t; + + // reverse arr[k+1]..arr[n] + if( k+1 < n ) + { + #if 0 + printf( "next_perm: reversing arr[%d..%d]\n", k+1, n ); + #endif + int x, y; + for( x=k+1, y=n; x +#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 ); + } + #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 ); + 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-191/duncan-c-white/C/printarray.h b/challenge-191/duncan-c-white/C/printarray.h new file mode 100644 index 0000000000..40efb83277 --- /dev/null +++ b/challenge-191/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-191/duncan-c-white/README b/challenge-191/duncan-c-white/README index 9edc65e930..d51cea2c1e 100644 --- a/challenge-191/duncan-c-white/README +++ b/challenge-191/duncan-c-white/README @@ -1,73 +1,89 @@ -Task 1: Capital Detection +Task 1: Task 1: Twice Largest -You are given a string with alphabetic characters only: A..Z and a..z. +You are given list of integers, @list. -Write a script to find out if the usage of Capital is appropriate if it -satisfies any of the following rules: - -1) Only first letter is capital and all others are small. -2) Every letter is small. -3) Every letter is capital. +Write a script to find out whether the largest item in the list is at +least twice as large as each of the other items. Example 1 - Input: $s = 'Perl' - Output: 1 + +Input: @list = (1,2,3,4) +Output: -1 + +The largest in the given list is 4. +However 4 is not greater than (dcw:OR EQUAL TO) twice remaining element 3: +2 x 3 > 4 Example 2 - Input: $s = 'TPF' - Output: 1 + +Input: @list = (1,2,0,5) +Output: 1 + +The largest in the given list is 5. +Also 5 is greater than (dcw:OR EQUAL TO) twice of every remaining element. +1 x 2 <= 5 +2 x 2 <= 5 +0 x 2 <= 5 Example 3 - Input: $s = 'PyThon' - Output: 0 + +Input: @list = (2,6,3,1) +Output: 1 + +The largest in the given list is 6. +Also 6 is greater than (dcw:OR EQUAL TO) twice of every remaining element. +2 x 2 <= 6 +3 x 2 <= 6 +1 x 2 <= 6 Example 4 - Input: $s = 'raku' - Output: 1 -MY NOTES: very easy. +Input: @list = (4,5,2,3) +Output: -1 + +The largest in the given list is 5. +Also 5 is not greater than (dcw:OR EQUAL TO) twice of every remaining element. +4 x 2 > 5 +2 x 2 <= 5 +3 x 2 > 5 + +MY NOTES: very easy, although there's an error in the wording of the examples +above - to get eg3 to "succeed" (have result 1) it's got to be "max element +is >= every other element * 2"... GUEST LANGUAGE: As a bonus, I also had a go at translating ch-1.pl into C (look in the C directory for the translation) -Task 2: Decoded List - -You are given an encoded string $s consisting of a sequence of numeric -characters: 0..9. +Task 2: Cute List -Write a script to find all valid different decodings in sorted order. +You are given an integer, 0 < $n <= 15. -Encoding is simply done by mapping A,B,C,D,# to 1,2,3,4,# etc. +Write a script to find the number of orderings of numbers that form a cute list. -Example 1 - Input: $s = 11 - Output: AA, K +With an input @list = (1, 2, 3, .. $n) for positive integer $n, an +ordering of @list is cute if for every entry, indexed with a base index of +1, either - 11 can be decoded as (1 1) or (11) i.e. AA or K +1) $list[$i] is evenly divisible by $i +or +2) $i is evenly divisible by $list[$i] -Example 2 - Input: $s = 1115 - Output: AAAE, AAO, AKE, KAE, KO +Example - Possible decoded data are: - (1 1 1 5) => (AAAE) - (1 1 15) => (AAO) - (1 11 5) => (AKE) - (11 1 5) => (KAE) - (11 15) => (KO) +Input: $n = 2 +Ouput: 2 -Example 3 - Input: $s = 127 - Output: ABG, LG +Since $n = 2, the list can be made up of two integers only i.e. 1 and 2. +Therefore we can have two list i.e. (1,2) and (2,1). - Possible decoded data are: - (1 2 7) => (ABG) - (12 7) => (LG) +@list = (1,2) is cute since $list[1] = 1 is divisible by 1 and $list[2] += 2 is divisible by 2. -MY NOTES: Hmm.. may be simple "take 1 or 2 chars off the front" (if that -front part is in 1..26 range), plus recursive processing of what's left, with a prefix -added to each sub-solution.. +MY NOTES: Hmm.. isn't every number divisible by 1, doesn't that mean that +the list[1] check is unnecessary? Looks weird but otherwise reasonably +straightforward. Obviously need a "next permutation of the list" iterator, +reusing the one from Challenge 134, adapted slightly. GUEST LANGUAGE: As a bonus, I also had a go at translating ch-2.pl into C (look in the C directory for the translation) diff --git a/challenge-191/duncan-c-white/perl/ch-1.pl b/challenge-191/duncan-c-white/perl/ch-1.pl new file mode 100755 index 0000000000..14a5350eaf --- /dev/null +++ b/challenge-191/duncan-c-white/perl/ch-1.pl @@ -0,0 +1,78 @@ +#!/usr/bin/perl +# +# Task 1: Twice Largest +# +# You are given list of integers, @list. +# +# Write a script to find out whether the largest item in the list is at +# least twice as large as each of the other items. +# +# Example 1 +# +# Input: @list = (1,2,3,4) +# Output: -1 +# +# The largest in the given list is 4. +# However 4 is not greater than (dcw:OR EQUAL TO) twice remaining element 3: +# 2 x 3 > 4 +# +# Example 2 +# +# Input: @list = (1,2,0,5) +# Output: 1 +# +# The largest in the given list is 5. +# Also 5 is greater than (dcw:OR EQUAL TO) twice of every remaining element. +# 1 x 2 <= 5 +# 2 x 2 <= 5 +# 0 x 2 <= 5 +# +# Example 3 +# +# Input: @list = (2,6,3,1) +# Output: 1 +# +# The largest in the given list is 6. +# Also 6 is greater than (dcw:OR EQUAL TO) twice of every remaining element. +# 2 x 2 <= 6 +# 3 x 2 <= 6 +# 1 x 2 <= 6 +# +# Example 4 +# +# Input: @list = (4,5,2,3) +# Output: -1 +# +# The largest in the given list is 5. +# Also 5 is not greater than (dcw:OR EQUAL TO) twice of every remaining element. +# 4 x 2 > 5 +# 2 x 2 <= 5 +# 3 x 2 > 5 +# +# MY NOTES: very easy, although there's an error in the wording of the examples +# above - to get eg3 to "succeed" (have result 1) it's got to be "max element +# is >= every other element * 2"... +# +# GUEST LANGUAGE: As a bonus, I also had a go at translating ch-1.pl +# into C (look in the C directory for the translation) +# + +use strict; +use warnings; +use feature 'say'; +use Getopt::Long; +use Data::Dumper; +use List::Util qw(max); + +my $debug=0; +die "Usage: twice-largest [--debug] intlist\n" + unless GetOptions( "debug"=>\$debug ) && @ARGV>0; + +my @x = split(/,/, join(',', @ARGV) ); +my $max = max(@x); +my @exceptmax = grep { $_ ne $max } @x; + +my $n = grep { $max < 2 * $_ } @exceptmax; +my $result = ($n == 0) ? 1 : -1; + +say $result; diff --git a/challenge-191/duncan-c-white/perl/ch-2.pl b/challenge-191/duncan-c-white/perl/ch-2.pl new file mode 100755 index 0000000000..05cbd36ed8 --- /dev/null +++ b/challenge-191/duncan-c-white/perl/ch-2.pl @@ -0,0 +1,134 @@ +#!/usr/bin/perl +# +# Task 2: Cute List +# +# You are given an integer, 0 < $n <= 15. +# +# Write a script to find the number of orderings of numbers that form a cute list. +# +# With an input @list = (1, 2, 3, .. $n) for positive integer $n, an +# ordering of @list is cute if for every entry, indexed with a base index of +# 1, either +# +# 1) $list[$i] is evenly divisible by $i +# or +# 2) $i is evenly divisible by $list[$i] +# +# Example +# +# Input: $n = 2 +# Ouput: 2 +# +# Since $n = 2, the list can be made up of two integers only i.e. 1 and 2. +# Therefore we can have two list i.e. (1,2) and (2,1). +# +# @list = (1,2) is cute since $list[1] = 1 is divisible by 1 and $list[2] +# = 2 is divisible by 2. +# +# MY NOTES: Hmm.. isn't every number divisible by 1, doesn't that mean that +# the list[1] check is unnecessary? Looks weird but otherwise reasonably +# straightforward. Obviously need a "next permutation of the list" iterator, +# reusing the one from Challenge 134, adapted slightly. +# +# My results: dunno if I'm doing it right, but here at my results for N=1..10: +# 1: 1 +# 2: 2 +# 3: 3 +# 4: 8 +# 5: 10 +# 6: 36 +# 7: 41 +# 8: 132 +# 9: 250 +# 10: 700 +# +# GUEST LANGUAGE: As a bonus, I also had a go at translating ch-2.pl +# into C (look in the C directory for the translation) +# + +use strict; +use warnings; +use feature 'say'; +use Getopt::Long; +use Function::Parameters; +use Data::Dumper; + + +my $debug=0; +die "Usage: cute-list [--debug] N (1..15)\n" + unless GetOptions( "debug"=>\$debug ) && @ARGV==1; + +my $n = shift; + +die "cute-list: N ($n) must be in range 1..15)\n" + unless $n>0 && $n<16; + +# +# my @next = next_perm( @a ); +# Find and return the next permutation in lexicographic order +# of @arr. Return () if $val is the last permutation (in order). +# Algorithm is as follows: +# 1. Find the largest index k such that a[k] < a[k + 1]. If no such index exists, +# the permutation is the last permutation. +# 2. Find the largest index l greater than k such that a[k] < a[l]. +# 3. Swap the value of a[k] with that of a[l]. +# 4. Reverse the sequence from a[k + 1] up to and including the final element a[n]. +# +fun next_perm( @a ) +{ + my( $k, $l ); + my $n = @a-1; + for( $k=$n-1; $k>=0 && $a[$k]>=$a[$k+1]; $k-- ) + { + } + return () if $k<0; + for( $l=$n; $l>$k && $a[$k]>=$a[$l]; $l-- ) + { + } + ( $a[$k], $a[$l] ) = ( $a[$l], $a[$k] ); + + # reverse a[k+1]..a[n] + @a[$k+1..$n] = reverse @a[$k+1..$n]; + + return @a; +} + + +=pod + +=head2 my $iscute = is_cute(@list); + +Return 1 iff @list is cute, as in the top spec. Return 0 otherwise. + +=cut +fun is_cute( @list ) +{ + foreach my $i0 (0..$#list) + { + my $index = $i0+1; # index base at 1 + my $val = $list[$i0]; + # NOT cute if both are NOT evenly disible by tother + return 0 if ( $val % $index != 0 ) && ( $index % $val != 0 ); + } + return 1; +} + + +my @list = (1..$n); +say "initial list: ", join(',',@list) if $debug; + +my $ncute = 0; + +for( my $i=1; ; $i++ ) +{ + last if @list==0; + #say "perm $i: ", join(',',@list); + if( is_cute(@list) ) + { + say "cute perm: ", join(',',@list) if $debug; + $ncute++; + } + @list = next_perm( @list ); +} + +say $ncute; -- cgit