From e3f6a10328e5e9a4f32cb3da11632d845eb2bf3e Mon Sep 17 00:00:00 2001 From: dcw Date: Sun, 6 Nov 2022 20:41:12 +0000 Subject: imported my solutions to this week's tasks; done in Perl, C and Pascal this week. two nice easy questions! --- challenge-189/duncan-c-white/C/Makefile | 18 ++ challenge-189/duncan-c-white/C/README | 8 + challenge-189/duncan-c-white/C/args.c | 207 +++++++++++++++++++++++ challenge-189/duncan-c-white/C/args.h | 11 ++ challenge-189/duncan-c-white/C/ch-1.c | 52 ++++++ challenge-189/duncan-c-white/C/ch-2.c | 155 +++++++++++++++++ challenge-189/duncan-c-white/C/parseints.c | 114 +++++++++++++ challenge-189/duncan-c-white/C/parseints.h | 1 + challenge-189/duncan-c-white/C/printarray.c | 39 +++++ challenge-189/duncan-c-white/C/printarray.h | 1 + challenge-189/duncan-c-white/README | 95 ++++++----- challenge-189/duncan-c-white/pascal/Makefile | 12 ++ challenge-189/duncan-c-white/pascal/ch-1.pas | 105 ++++++++++++ challenge-189/duncan-c-white/pascal/ch-2.pas | 239 +++++++++++++++++++++++++++ challenge-189/duncan-c-white/perl/ch-1.pl | 63 +++++++ challenge-189/duncan-c-white/perl/ch-2.pl | 113 +++++++++++++ 16 files changed, 1190 insertions(+), 43 deletions(-) create mode 100644 challenge-189/duncan-c-white/C/Makefile create mode 100644 challenge-189/duncan-c-white/C/README create mode 100644 challenge-189/duncan-c-white/C/args.c create mode 100644 challenge-189/duncan-c-white/C/args.h create mode 100644 challenge-189/duncan-c-white/C/ch-1.c create mode 100644 challenge-189/duncan-c-white/C/ch-2.c create mode 100644 challenge-189/duncan-c-white/C/parseints.c create mode 100644 challenge-189/duncan-c-white/C/parseints.h create mode 100644 challenge-189/duncan-c-white/C/printarray.c create mode 100644 challenge-189/duncan-c-white/C/printarray.h create mode 100644 challenge-189/duncan-c-white/pascal/Makefile create mode 100644 challenge-189/duncan-c-white/pascal/ch-1.pas create mode 100644 challenge-189/duncan-c-white/pascal/ch-2.pas create mode 100755 challenge-189/duncan-c-white/perl/ch-1.pl create mode 100755 challenge-189/duncan-c-white/perl/ch-2.pl diff --git a/challenge-189/duncan-c-white/C/Makefile b/challenge-189/duncan-c-white/C/Makefile new file mode 100644 index 0000000000..1b34ccd3b2 --- /dev/null +++ b/challenge-189/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-189/duncan-c-white/C/README b/challenge-189/duncan-c-white/C/README new file mode 100644 index 0000000000..93788320dc --- /dev/null +++ b/challenge-189/duncan-c-white/C/README @@ -0,0 +1,8 @@ +Thought I'd also have a go at translating ch-1.pl and ch-2.pl into C.. + +Both produce near-identical (non-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]. diff --git a/challenge-189/duncan-c-white/C/args.c b/challenge-189/duncan-c-white/C/args.c new file mode 100644 index 0000000000..d4a2d38b9a --- /dev/null +++ b/challenge-189/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_args( "gt-chr", argc, argv, + 2, "target string" ); + + char *tstr = argv[argno++]; + char target = *tstr; + char *str = argv[argno++]; + + if( debug ) + { + printf( "debug: target=%c, str=%s\n", target, str ); + } + + char minchar = 127; + int len = strlen(str); + for( int i=0; i target && ch < minchar ) + { + minchar = ch; + } + } + if( minchar == 127 ) minchar = target; + printf( "%c\n", minchar ); + + return 0; +} diff --git a/challenge-189/duncan-c-white/C/ch-2.c b/challenge-189/duncan-c-white/C/ch-2.c new file mode 100644 index 0000000000..8882b18e63 --- /dev/null +++ b/challenge-189/duncan-c-white/C/ch-2.c @@ -0,0 +1,155 @@ +// +// Task 2: Array Degree +// +// C version. +// + +#include +#include +#include +#include +#include +#include + +#include "args.h" +#include "parseints.h" +#include "printarray.h" + + +typedef struct +{ + int el; // an element + int freq; // and it's associated frequency +} pair; + + +// Increment the frequency of el in freq (adding an element if +// it's not there yet) +static void incfreq( pair *freq, int *np, int el ) +{ + for( int i=0; i<*np; i++ ) + { + if( freq[i].el == el ) + { + freq[i].freq++; + return; + } + } + int pos = (*np)++; + freq[pos].el = el; + freq[pos].freq = 1; +} + + +// +// int deg = degree( array, from, to ); +// Calculate the degree (max frequency) of array[from..to]. +// +int degree( int *array, int from, int to ) +{ + pair *freq = malloc( (to+1-from) * sizeof(pair) ); + assert( freq != NULL ); + int np = 0; // number of pairs in freq + + for( int i=from; i<=to; i++ ) + { + incfreq( freq, &np, array[i] ); + } + + // now find the maximum frequency in freq[] + int max = 0; + for( int i=0; i max ) + { + max = freq[i].freq; + } + } + free( freq ); + return max; +} + + +// makeslicestr( arr, from, to, slicestr ); +// Build slicestr, a plain text string containing all elements +// arr[from..to], comma separated +// Sort of like slicestr = join(',', arr[from..to]); +// +static void makeslicestr( int *arr, int from, int to, char *slicestr ) +{ + char *s = slicestr; + *s = '\0'; + for( int i=from; i<=to; i++ ) + { + if( i>from ) + { + *s++ = ','; + } + sprintf( s, "%d", arr[i] ); + s += strlen(s); + *s = '\0'; + } +} + + +int main( int argc, char **argv ) +{ + int argno = process_flag_n_m_args( "array-degree", argc, argv, + 2, 1000, "csvlist(int)" ); + int nel; + int *ilist = parse_int_args( argc, argv, argno, &nel ); + + if( debug ) + { + printf( "debug: list=" ); + print_int_array( 70, nel, ilist, ',', stdout ); + putchar( '\n' ); + } + + int wholedeg = degree( ilist, 0, nel-1 ); + + char *slicestr = malloc( 10000 * sizeof(char) ); + assert( slicestr != NULL ); + + makeslicestr( ilist, 0, nel-1, slicestr ); + + if( debug ) + { + printf( "debug: wholedeg = %d\n", wholedeg ); + } + + char *smallarray = malloc( 10000 * sizeof(char) ); + assert( smallarray != NULL ); + + int smallestarraysize = nel+1; + + for( int from=0; from +#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-189/duncan-c-white/C/printarray.h b/challenge-189/duncan-c-white/C/printarray.h new file mode 100644 index 0000000000..40efb83277 --- /dev/null +++ b/challenge-189/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-189/duncan-c-white/README b/challenge-189/duncan-c-white/README index 2327956670..6ac1265327 100644 --- a/challenge-189/duncan-c-white/README +++ b/challenge-189/duncan-c-white/README @@ -1,87 +1,96 @@ -Task 1: Divisible Pairs +Task 1: Greater Character -You are given list of integers @list of size $n and divisor $k. +You are given an array of characters (a..z) and a target character. -Write a script to find out count of pairs in the given list that satisfies -the following rules. - -The pair (i, j) is eligible if and only if -a) 0 <= i < j < len(list) -b) list[i] + list[j] is divisible by k +Write a script to find out the smallest character in the given array +lexicographically greater than the target character. Example 1 - Input: @list = (4, 5, 1, 6), $k = 2 - Output: 2 + Input: @array = qw/e m u g/, $target = 'b' + Output: e Example 2 - Input: @list = (1, 2, 3, 4), $k = 2 - Output: 2 + Input: @array = qw/d c e f/, $target = 'a' + Output: c Example 3 - Input: @list = (1, 3, 4, 5), $k = 3 - Output: 2 + Input: @array = qw/j a r/, $target = 'o' + Output: r Example 4 - Input: @list = (5, 1, 2, 3), $k = 4 - Output: 2 + Input: @array = qw/d c a f/, $target = 'a' + Output: c Example 5 - Input: @list = (7, 2, 4, 5), $k = 4 - Output: 1 + Input: @array = qw/t g a l/, $target = 'v' + Output: v -MY NOTES: pretty easy. Generate all pairs of indices, and test each pair -for property (2). +MY NOTES: pretty easy, although example 5 seems to imply that the spec +should say, "... or the target if no character in the array is bigger +than the target". So that's the basis on which I'm proceeding: -GUEST LANGUAGE: As a bonus, I also had a go at translating ch-1.pl -into C (look in the C directory for that). +Note that "an array of characters" is awfully like "a string + split", +so let's do that. +Can do it as a one-liner: +perl -MList::Util=minstr -E '( $target, $str ) = @ARGV; $x = minstr( grep { $_ gt $target } split( //, $str ) ) // ($target); say $x' a dcef -Task 2: Total Zero +GUEST LANGUAGE: As a bonus, I also had a go at translating ch-1.pl +into C and Pascal (look in the relevant direcories for +those translations) -You are given two positive integers $x and $y. -Write a script to find out the number of operations needed to make both -ZERO. Each operation is made up either of the following: +Task 2: Array Degree -$x = $x - $y if $x >= $y +You are given an array of 2 or more non-negative integers. -or +Write a script to find out the smallest slice, i.e. contiguous subarray +of the original array, having the degree of the given array. -$y = $y - $x if $y >= $x (using the original value of $x) +The degree of an array is the maximum frequency of an element in the array. Example 1 - Input: $x = 5, $y = 4 - Output: 5 + Input: @array = (1, 3, 3, 2) + Output: (3, 3) + + The degree of the given array is 2. + The possible subarrays having the degree 2 are as below: + (3, 3) + (1, 3, 3) + (3, 3, 2) + (1, 3, 3, 2) + + And the smallest of all is (3, 3). Example 2 - Input: $x = 4, $y = 6 - Output: 3 + Input: @array = (1, 2, 1, 3) + Output: (1, 2, 1) Example 3 - Input: $x = 2, $y = 5 - Output: 4 + Input: @array = (1, 3, 2, 1, 2) + Output: (2, 1, 2) Example 4 - Input: $x = 3, $y = 1 - Output: 3 + Input: @array = (1, 1, 2, 3, 2) + Output: (1, 1) Example 5 - Input: $x = 7, $y = 4 - Output: 5 - + Input: @array = (2, 1, 2, 1, 1) + Output: (1, 2, 1, 1) -MY NOTES: Ok, sounds easy enough, especially with some debug mode code -showing how x and y change, round by round. +MY NOTES: Ok, sounds pretty easy. Finding the degree of an array range +involves building a frequency hash, the degree is max( values %freq ). +Finding the smallest subarray is easier enough, although tedious. GUEST LANGUAGE: As a bonus, I also had a go at translating ch-2.pl -into C (look in the C directory for that). +into C and Pascal (look in the relevant direcories for those translations) diff --git a/challenge-189/duncan-c-white/pascal/Makefile b/challenge-189/duncan-c-white/pascal/Makefile new file mode 100644 index 0000000000..109c2a6e86 --- /dev/null +++ b/challenge-189/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-189/duncan-c-white/pascal/ch-1.pas b/challenge-189/duncan-c-white/pascal/ch-1.pas new file mode 100644 index 0000000000..4392c54969 --- /dev/null +++ b/challenge-189/duncan-c-white/pascal/ch-1.pas @@ -0,0 +1,105 @@ +(* + * Task 1: Greater Character + * + * 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: gt-chr [-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; + + +procedure main; + +var + strarr : strarray; + str : string; + i : integer; + len : integer; + target : char; + minchar : char; + ch : char; + +begin + debug := false; + + process_args_exactly_n( 2, strarr ); + + target := strarr[0][1]; + str := strarr[1]; + + len := length(str); + if debug + then begin + writeln( 'debug: target=', target, ', str=', str ); + end; + minchar := chr(127); + for i:=1 to len do + begin + ch := str[i]; + if debug + then begin + writeln( 'debug: str[', i, '] = "', ch, '" minsofar="', minchar, '"' ); + end; + if (ch > target) and (ch < minchar) + then begin + minchar := ch; + end; + end; + if minchar = chr(127) then minchar := target; + writeln( minchar ); +end; + + +begin + main; +end. diff --git a/challenge-189/duncan-c-white/pascal/ch-2.pas b/challenge-189/duncan-c-white/pascal/ch-2.pas new file mode 100644 index 0000000000..019580cb94 --- /dev/null +++ b/challenge-189/duncan-c-white/pascal/ch-2.pas @@ -0,0 +1,239 @@ +(* + * TASK #2 - Array Degree + * + * GUEST LANGUAGE: THIS IS THE Pascal VERSION OF ch-2.{c,pl}, + * suitable for the Free Pascal compiler. + *) + +uses sysutils; + +const maxints = 256; + +type intarray = array [0..maxints-1] of integer; + +var debug : boolean; + + +type + pair = record + el : integer; (* an element *) + freq : integer; (* and it's associated frequency *) + end; + +type + pairarray = array [ 1..1000 ] of pair; + + +(* process_args( nel, v ); + * Process command line arguments, + * specifically process the -d flag, + * set nel to the number of remaining arguments, + * check that all those remaining arguments are +ve numbers, + * copy remaining args to a new integer array v. + *) +procedure process_args( var nel : integer; var v : intarray ); + +(* note: paramStr(i)); for i in 1 to paramCount() *) + +var + nparams : 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 < 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. diff --git a/challenge-189/duncan-c-white/perl/ch-1.pl b/challenge-189/duncan-c-white/perl/ch-1.pl new file mode 100755 index 0000000000..21e3d5a100 --- /dev/null +++ b/challenge-189/duncan-c-white/perl/ch-1.pl @@ -0,0 +1,63 @@ +#!/usr/bin/perl +# +# Task 1: Greater Character +# +# You are given an array of characters (a..z) and a target character. +# +# Write a script to find out the smallest character in the given array +# lexicographically greater than the target character. +# +# Example 1 +# +# Input: @array = qw/e m u g/, $target = 'b' +# Output: e +# +# Example 2 +# +# Input: @array = qw/d c e f/, $target = 'a' +# Output: c +# +# Example 3 +# +# Input: @array = qw/j a r/, $target = 'o' +# Output: r +# +# Example 4 +# +# Input: @array = qw/d c a f/, $target = 'a' +# Output: c +# +# Example 5 +# +# Input: @array = qw/t g a l/, $target = 'v' +# Output: v +# +# MY NOTES: pretty easy, although example 5 seems to imply that the spec +# should say, "... or the target if no character in the array is bigger +# than the target". So that's the basis on which I'm proceeding: +# +# Note that "an array of characters" is awfully like "a string + split", +# so let's do that. +# +# Can do it as a one-liner: +# perl -MList::Util=minstr -E '( $target, $str ) = @ARGV; $x = minstr( grep { $_ gt $target } split( //, $str ) ) // ($target); say $x' a dcef +# +# GUEST LANGUAGE: As a bonus, I also had a go at translating ch-1.pl +# into C and Pascal (look in the obvious directories for the translations). +# + +use strict; +use warnings; +use feature 'say'; +use Getopt::Long; +use List::Util qw(minstr); +use Data::Dumper; + +my $debug=0; +die "Usage: gt-chr [--debug] target string\n" + unless GetOptions( "debug"=>\$debug ) && @ARGV==2; + +my( $target, $str ) = @ARGV; +my @array = split( //, $str ); +my $x = minstr( grep { $_ gt $target } @array ) // $target; +say $x; diff --git a/challenge-189/duncan-c-white/perl/ch-2.pl b/challenge-189/duncan-c-white/perl/ch-2.pl new file mode 100755 index 0000000000..bbee0a387b --- /dev/null +++ b/challenge-189/duncan-c-white/perl/ch-2.pl @@ -0,0 +1,113 @@ +#!/usr/bin/perl +# +# Task 2: Array Degree +# +# You are given an array of 2 or more non-negative integers. +# +# Write a script to find out the smallest slice, i.e. contiguous subarray +# of the original array, having the degree of the given array. +# +# The degree of an array is the maximum frequency of an element in the array. +# +# Example 1 +# +# Input: @array = (1, 3, 3, 2) +# Output: (3, 3) +# +# The degree of the given array is 2. +# The possible subarrays having the degree 2 are as below: +# (3, 3) +# (1, 3, 3) +# (3, 3, 2) +# (1, 3, 3, 2) +# +# And the smallest of all is (3, 3). +# +# Example 2 +# +# Input: @array = (1, 2, 1, 3) +# Output: (1, 2, 1) +# +# Example 3 +# +# Input: @array = (1, 3, 2, 1, 2) +# Output: (2, 1, 2) +# +# Example 4 +# +# Input: @array = (1, 1, 2, 3, 2) +# Output: (1, 1) +# +# Example 5 +# +# Input: @array = (2, 1, 2, 1, 1) +# Output: (1, 2, 1, 1) +# +# MY NOTES: Ok, sounds pretty easy. Finding the degree of an array range +# involves building a frequency hash, the degree is max( values %freq ). +# Finding the smallest subarray is easier enough, although tedious. +# +# GUEST LANGUAGE: As a bonus, I also had a go at translating ch-2.pl +# into C and Pascal (look in the obvious directories for the translations). +# + +use strict; +use warnings; +use feature 'say'; +use Getopt::Long; +use List::Util qw(max); +use Data::Dumper; + + +my $debug=0; +die "Usage: array-degree [--debug] csvlist(int)\n" + unless GetOptions( "debug"=>\$debug ) && @ARGV>1; + +my @list = @ARGV; +@list = split( /\s*,\s*/, join(',',@list) ); +say "debug: list=", join(',',@list) if $debug; + + +=pod + +=head2 my $deg = degree( $arreyref, $from, $to ); + +Calculate the degree (max frequency) of arrayref->[from..to]. + +=cut +sub degree ($$$) +{ + my( $arrayref, $from, $to ) = @_; + my %freq; + foreach my $i ($from..$to) + { + $freq{$arrayref->[$i]}++; + } + return max( values(%freq) ); +} + + +my $wholedeg = degree( \@list, 0, $#list ); +say "debug: wholedeg=$wholedeg" if $debug; + +my $smallestarraysize = $#list+2; +my @smallarray = (); + +foreach my $from (0..$#list-1) +{ + foreach my $to ($from+1..$#list) + { + my $deg = degree( \@list, $from, $to ); + next unless $deg == $wholedeg; + my $slicestr = join(',', @list[$from..$to]); + say "debug: found sub-array $slicestr with degree $deg" + if $debug; + my $size = $to+1-$from; + if( $size < $smallestarraysize ) + { + $smallestarraysize = $size; + @smallarray = @list[$from..$to]; + } + } +} +say join(',',@smallarray); -- cgit