aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authordcw <d.white@imperial.ac.uk>2022-11-06 20:41:12 +0000
committerdcw <d.white@imperial.ac.uk>2022-11-06 20:41:12 +0000
commite3f6a10328e5e9a4f32cb3da11632d845eb2bf3e (patch)
treefaafe8dd628c66f76d4c00520204cdf6fc40a714
parentf9e6c54d3113cbe89568cc4c3b851081af55eafc (diff)
downloadperlweeklychallenge-club-e3f6a10328e5e9a4f32cb3da11632d845eb2bf3e.tar.gz
perlweeklychallenge-club-e3f6a10328e5e9a4f32cb3da11632d845eb2bf3e.tar.bz2
perlweeklychallenge-club-e3f6a10328e5e9a4f32cb3da11632d845eb2bf3e.zip
imported my solutions to this week's tasks; done in Perl, C and Pascal this week. two nice easy questions!
-rw-r--r--challenge-189/duncan-c-white/C/Makefile18
-rw-r--r--challenge-189/duncan-c-white/C/README8
-rw-r--r--challenge-189/duncan-c-white/C/args.c207
-rw-r--r--challenge-189/duncan-c-white/C/args.h11
-rw-r--r--challenge-189/duncan-c-white/C/ch-1.c52
-rw-r--r--challenge-189/duncan-c-white/C/ch-2.c155
-rw-r--r--challenge-189/duncan-c-white/C/parseints.c114
-rw-r--r--challenge-189/duncan-c-white/C/parseints.h1
-rw-r--r--challenge-189/duncan-c-white/C/printarray.c39
-rw-r--r--challenge-189/duncan-c-white/C/printarray.h1
-rw-r--r--challenge-189/duncan-c-white/README95
-rw-r--r--challenge-189/duncan-c-white/pascal/Makefile12
-rw-r--r--challenge-189/duncan-c-white/pascal/ch-1.pas105
-rw-r--r--challenge-189/duncan-c-white/pascal/ch-2.pas239
-rwxr-xr-xchallenge-189/duncan-c-white/perl/ch-1.pl63
-rwxr-xr-xchallenge-189/duncan-c-white/perl/ch-2.pl113
16 files changed, 1190 insertions, 43 deletions
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 <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-189/duncan-c-white/C/args.h b/challenge-189/duncan-c-white/C/args.h
new file mode 100644
index 0000000000..8844a8f9c4
--- /dev/null
+++ b/challenge-189/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-189/duncan-c-white/C/ch-1.c b/challenge-189/duncan-c-white/C/ch-1.c
new file mode 100644
index 0000000000..fc14b97dde
--- /dev/null
+++ b/challenge-189/duncan-c-white/C/ch-1.c
@@ -0,0 +1,52 @@
+//
+// Task 1: Greater Character
+//
+// 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"
+
+
+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<len; i++ )
+ {
+ char ch = str[i];
+ if( debug )
+ {
+ printf( "debug: str[%d] = '%c' minsofar='%c'\n",
+ i, ch, minchar );
+ }
+ if( ch > 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 <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 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<np; i++ )
+ {
+ if( freq[i].freq > 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<nel-1; from++ )
+ {
+ for( int to=from+1; to<nel; to++ )
+ {
+ int deg = degree( ilist, from, to );
+ if( deg != wholedeg ) continue;
+
+ makeslicestr( ilist, from, to, slicestr );
+ if( debug )
+ {
+ printf( "debug: found sub-array %s with degree %d\n", slicestr, deg );
+ }
+
+ int size = to+1-from;
+ if( size < smallestarraysize )
+ {
+ smallestarraysize = size;
+ strcpy( smallarray, slicestr );
+ }
+ }
+ }
+
+ printf( "%s\n", smallarray );
+
+ free( smallarray );
+ free( slicestr );
+ free( ilist );
+
+ return 0;
+}
diff --git a/challenge-189/duncan-c-white/C/parseints.c b/challenge-189/duncan-c-white/C/parseints.c
new file mode 100644
index 0000000000..0fb9985633
--- /dev/null
+++ b/challenge-189/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 );
+ }
+ #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<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-189/duncan-c-white/C/parseints.h b/challenge-189/duncan-c-white/C/parseints.h
new file mode 100644
index 0000000000..da5e145a86
--- /dev/null
+++ b/challenge-189/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-189/duncan-c-white/C/printarray.c b/challenge-189/duncan-c-white/C/printarray.c
new file mode 100644
index 0000000000..ddee597df3
--- /dev/null
+++ b/challenge-189/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-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