From 6606c13eec857840fd2b569a6404d326556be686 Mon Sep 17 00:00:00 2001 From: dcw Date: Sun, 5 Mar 2023 22:34:42 +0000 Subject: catchup commit: ch205, both tasks, Perl and C, plus ch206: both tasks in Perl only --- challenge-205/duncan-c-white/C/Makefile | 18 +++ challenge-205/duncan-c-white/C/README | 14 ++ challenge-205/duncan-c-white/C/args.c | 207 ++++++++++++++++++++++++++++ challenge-205/duncan-c-white/C/args.h | 11 ++ challenge-205/duncan-c-white/C/ch-1.c | 78 +++++++++++ challenge-205/duncan-c-white/C/ch-2.c | 66 +++++++++ challenge-205/duncan-c-white/C/parseints.c | 114 +++++++++++++++ challenge-205/duncan-c-white/C/parseints.h | 1 + challenge-205/duncan-c-white/C/printarray.c | 39 ++++++ challenge-205/duncan-c-white/C/printarray.h | 1 + challenge-205/duncan-c-white/README | 71 +++++----- challenge-205/duncan-c-white/perl/ch-1.pl | 65 +++++++++ challenge-205/duncan-c-white/perl/ch-2.pl | 75 ++++++++++ challenge-206/duncan-c-white/C/.cbuild | 4 - challenge-206/duncan-c-white/README | 88 ++++++------ challenge-206/duncan-c-white/perl/ch-1.pl | 94 +++++++++++++ challenge-206/duncan-c-white/perl/ch-2.pl | 96 +++++++++++++ 17 files changed, 955 insertions(+), 87 deletions(-) create mode 100644 challenge-205/duncan-c-white/C/Makefile create mode 100644 challenge-205/duncan-c-white/C/README create mode 100644 challenge-205/duncan-c-white/C/args.c create mode 100644 challenge-205/duncan-c-white/C/args.h create mode 100644 challenge-205/duncan-c-white/C/ch-1.c create mode 100644 challenge-205/duncan-c-white/C/ch-2.c create mode 100644 challenge-205/duncan-c-white/C/parseints.c create mode 100644 challenge-205/duncan-c-white/C/parseints.h create mode 100644 challenge-205/duncan-c-white/C/printarray.c create mode 100644 challenge-205/duncan-c-white/C/printarray.h create mode 100755 challenge-205/duncan-c-white/perl/ch-1.pl create mode 100755 challenge-205/duncan-c-white/perl/ch-2.pl delete mode 100644 challenge-206/duncan-c-white/C/.cbuild create mode 100755 challenge-206/duncan-c-white/perl/ch-1.pl create mode 100755 challenge-206/duncan-c-white/perl/ch-2.pl diff --git a/challenge-205/duncan-c-white/C/Makefile b/challenge-205/duncan-c-white/C/Makefile new file mode 100644 index 0000000000..1b34ccd3b2 --- /dev/null +++ b/challenge-205/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-205/duncan-c-white/C/README b/challenge-205/duncan-c-white/C/README new file mode 100644 index 0000000000..79d015ffe4 --- /dev/null +++ b/challenge-205/duncan-c-white/C/README @@ -0,0 +1,14 @@ +Thought I'd also have a go at translating ch-1.pl and ch-2.pl into C.. + +Both C versions produce near-identical (non-debugging and even debugging) +output to the Perl originals. + +The C translation of ch-2.pl was quite tricky to write, mainly on storage +allocation (as usual), although I found a neat (slightly cheaty?) +way of doing it. specifically: I create a 1d-array of all the elements, +and then I print it out as if it were an RxC matrix.. + +These C versions use most 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-205/duncan-c-white/C/args.c b/challenge-205/duncan-c-white/C/args.c new file mode 100644 index 0000000000..d4a2d38b9a --- /dev/null +++ b/challenge-205/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 intcomparedesc( const void *ap, const void *bp ) +{ + int a = *((int *)ap); + int b = *((int *)bp); + return b-a; +} + + +int main( int argc, char **argv ) +{ + int argno = process_flag_n_m_args( "third-highest", argc, argv, + 1, 1000, "intlist" ); + + int nel; + int *list = parse_int_args( argc, argv, argno, &nel ); + + if( debug ) + { + printf( "debug: initial list: " ); + print_int_array( 60, nel, list, ',', stdout ); + putchar( '\n' ); + } + + qsort( list, nel, sizeof(int), &intcomparedesc ); + + if( debug ) + { + printf( "debug: sorted list: " ); + print_int_array( 60, nel, list, ',', stdout ); + putchar( '\n' ); + } + + // remove duplicates + for( int i=0; i 2 ) ? list[2] : list[0]; + printf( "%d\n", third ); + + free( list ); + + return 0; +} diff --git a/challenge-205/duncan-c-white/C/ch-2.c b/challenge-205/duncan-c-white/C/ch-2.c new file mode 100644 index 0000000000..3aa2d9a358 --- /dev/null +++ b/challenge-205/duncan-c-white/C/ch-2.c @@ -0,0 +1,66 @@ +// +// Task 2: Maximum XOR +// +// C version. +// + +#include +#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( "max-xor", argc, argv, + 1, 1000, "intlist" ); + + int nel; + int *list = parse_int_args( argc, argv, argno, &nel ); + + if( debug ) + { + printf( "debug: initial list: " ); + print_int_array( 60, nel, list, ',', stdout ); + putchar( '\n' ); + } + + int max = -1; + int maxa = -1; + int maxb = -1; + + for( int i=0; i max ) + { + max = xor; + maxa = a; + maxb = b; + } + } + } + + printf( "%d\n", max ); + + if( debug ) + { + printf( "The maximum result of %d xor %d = %d\n", + maxa, maxb, max ); + } + + free( list ); + + return 0; +} diff --git a/challenge-205/duncan-c-white/C/parseints.c b/challenge-205/duncan-c-white/C/parseints.c new file mode 100644 index 0000000000..0fb9985633 --- /dev/null +++ b/challenge-205/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 ); + } + #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-205/duncan-c-white/C/printarray.h b/challenge-205/duncan-c-white/C/printarray.h new file mode 100644 index 0000000000..40efb83277 --- /dev/null +++ b/challenge-205/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-205/duncan-c-white/README b/challenge-205/duncan-c-white/README index f38be3a4b5..3da46a12e7 100644 --- a/challenge-205/duncan-c-white/README +++ b/challenge-205/duncan-c-white/README @@ -1,71 +1,70 @@ -Task 1: Monotonic Array +Task 1: Third Highest You are given an array of integers. -Write a script to find out if the given array is Monotonic. Print 1 if -it is otherwise 0. - -An array is Monotonic if it is either monotone increasing or decreasing. - -Monotone increasing: for i <= j , nums[i] <= nums[j] -Monotone decreasing: for i <= j , nums[i] >= nums[j] +Write a script to find out the Third Highest if found otherwise return +the maximum. Example 1 - Input: @nums = (1,2,2,3) - Output: 1 + Input: @array = (5,3,4) + Output: 3 + + First highest is 5. + Second highest is 4. + Third highest is 3. Example 2 - Input: @nums = (1,3,2) - Output: 0 + Input: @array = (5,6) + Output: 6 + + First highest is 6. + Second highest is 5. + Third highest is missing, so maximum is returned. Example 3 - Input: @nums = (6,5,5,4) - Output: 1 + Input: @array = (5,4,4,3) + Output: 3 -MY NOTES: seems very easy. use reverse() in order not to detect -monotonically increasing and decreasing.. + First highest is 5. Second highest is 4. Third highest is 3. + +MY NOTES: seems very easy. sort, take 3rd biggest distinct element +(or biggest element if less than 3) 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: Reshape Matrix - -You are given a matrix (m x n) and two integers (r) and (c). +Task 2: Maximum XOR -Write a script to reshape the given matrix in form (r x c) with the -original value in the given matrix. If you can't reshape print 0. +You are given an array of integers. +Write a script to find the highest value obtained by XORing any two +distinct members of the array. Example 1 -Input: $matrix = [ [ 1, 2 ], [ 3, 4 ] ] - $r = 1 - $c = 4 + Input: @array = (1,2,3,4,5,6,7) + Output: 7 -Output: [ 1 2 3 4 ] + The maximum result of 1 xor 6 = 7. Example 2 -Input: $matrix = [ [ 1, 2, 3 ] , [ 4, 5, 6 ] ] - $r = 3 - $c = 2 + Input: @array = (2,4,1,3) + Output: 7 -Output: [ [ 1, 2 ], [ 3, 4 ], [ 5, 6 ] ] + The maximum result of 4 xor 3 = 7. Example 3 -Input: $matrix = [ [ 1, 2 ] ] - $r = 3 - $c = 2 + Input: @array = (10,5,7,12,8) + Output: 15 -Output: 0 + The maximum result of 10 xor 5 = 15. -MY NOTES: also quite easy, can be done if R1*C1==R2*C -(of course we have to discover R1 and C1, the dimensions o -the original matrix). Also have to read the matrix in.. +MY NOTES: also quite easy, try all combinations, pick max of all xors. 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). Needed to diff --git a/challenge-205/duncan-c-white/perl/ch-1.pl b/challenge-205/duncan-c-white/perl/ch-1.pl new file mode 100755 index 0000000000..ee3dec3163 --- /dev/null +++ b/challenge-205/duncan-c-white/perl/ch-1.pl @@ -0,0 +1,65 @@ +#!/usr/bin/perl +# +# Task 1: Third Highest +# +# You are given an array of integers. +# +# Write a script to find out the Third Highest if found otherwise return +# the maximum. +# +# Example 1 +# +# Input: @array = (5,3,4) +# Output: 3 +# +# First highest is 5. +# Second highest is 4. +# Third highest is 3. +# +# Example 2 +# +# Input: @array = (5,6) +# Output: 6 +# +# First highest is 6. +# Second highest is 5. +# Third highest is missing, so maximum is returned. +# +# Example 3 +# +# Input: @array = (5,4,4,3) +# Output: 3 +# +# First highest is 5. Second highest is 4. Third highest is 3. +# +# MY NOTES: seems very easy. sort, take 3rd biggest distinct element +# (or biggest element if less than 3) +# +# 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; + +my $debug=0; +die "Usage: third-highest [--debug] intlist\n" + unless GetOptions( "debug"=>\$debug ) && @ARGV>0; + +my @list = split( /,/, join(',',@ARGV) ); + +@list = sort { $b <=> $a } @list; + +say "sorted: ", join(',',@list) if $debug; + +# remove dups +my %seen; +@list = grep { ! $seen{$_}++ } @list; + +say "nodups: ", join(',',@list) if $debug; + +my $third = ( @list > 2 ) ? $list[2] : $list[0]; +say $third; diff --git a/challenge-205/duncan-c-white/perl/ch-2.pl b/challenge-205/duncan-c-white/perl/ch-2.pl new file mode 100755 index 0000000000..4a71341928 --- /dev/null +++ b/challenge-205/duncan-c-white/perl/ch-2.pl @@ -0,0 +1,75 @@ +#!/usr/bin/perl +# +# Task 2: Maximum XOR +# +# You are given an array of integers. +# Write a script to find the highest value obtained by XORing any two +# distinct members of the array. +# +# Example 1 +# +# Input: @array = (1,2,3,4,5,6,7) +# Output: 7 +# +# The maximum result of 1 xor 6 = 7. +# +# Example 2 +# +# Input: @array = (2,4,1,3) +# Output: 7 +# +# The maximum result of 4 xor 3 = 7. +# +# Example 3 +# +# Input: @array = (10,5,7,12,8) +# Output: 15 +# +# The maximum result of 10 xor 5 = 15. +# +# MY NOTES: also quite easy, try all combinations, pick max of all xors. +# +# 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). Needed to +# pass original sizes into C routine.. +# + +use strict; +use warnings; +use feature 'say'; +use Getopt::Long; +use Function::Parameters; +use Data::Dumper; + +my $debug=0; +die "Usage: max-xor [--debug] intlist\n" + unless GetOptions( "debug"=>\$debug ) && @ARGV > 0; + +my @list = split( /,/, join(',',@ARGV) ); + +say "list: ", join(',',@list) if $debug; + +my $max = -1; +my $maxa = -1; +my $maxb = -1; + +foreach my $i (0..$#list-1) +{ + foreach my $j ($i+1..$#list) + { + my $a = $list[$i]+0; + my $b = $list[$j]+0; + my $xor = $a^$b; + #say "debug: i=$i, j=$j, a=$a, b=$b, xor=$xor, max=$max" if $debug; + if( $xor > $max ) + { + $max = $xor; + $maxa = $a; + $maxb = $b; + } + } +} + +say "$max"; + +say "The maximum result of $maxa xor $maxb = $max" if $debug; diff --git a/challenge-206/duncan-c-white/C/.cbuild b/challenge-206/duncan-c-white/C/.cbuild deleted file mode 100644 index a14ec76520..0000000000 --- a/challenge-206/duncan-c-white/C/.cbuild +++ /dev/null @@ -1,4 +0,0 @@ -BUILD = ch-1 ch-2 -CFLAGS = -Wall -g -#LDFLAGS = -lm -#CFLAGS = -g diff --git a/challenge-206/duncan-c-white/README b/challenge-206/duncan-c-white/README index f38be3a4b5..3a95b6badb 100644 --- a/challenge-206/duncan-c-white/README +++ b/challenge-206/duncan-c-white/README @@ -1,72 +1,66 @@ -Task 1: Monotonic Array +Task 1: Shortest Time -You are given an array of integers. - -Write a script to find out if the given array is Monotonic. Print 1 if -it is otherwise 0. - -An array is Monotonic if it is either monotone increasing or decreasing. - -Monotone increasing: for i <= j , nums[i] <= nums[j] -Monotone decreasing: for i <= j , nums[i] >= nums[j] +You are given a list of time points, at least 2, in the 24-hour clock +format HH:MM. Write a script to find out the shortest time in minutes +between any two time points. Example 1 - Input: @nums = (1,2,2,3) - Output: 1 + Input: @time = ("00:00", "23:55", "20:00") + Output: 5 + + Since the difference between "00:00" and "23:55" is the shortest (5 minutes). Example 2 - Input: @nums = (1,3,2) - Output: 0 + Input: @array = ("01:01", "00:50", "00:57") + Output: 4 Example 3 - Input: @nums = (6,5,5,4) - Output: 1 - -MY NOTES: seems very easy. use reverse() in order not to detect -monotonically increasing and decreasing.. + Input: @array = ("10:10", "09:30", "09:00", "09:55") + Output: 15 -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) +MY NOTES: reasonably easy, although of course wraparound has to taken +into account. Might convert each hh:mm time into a number of minutes, +then sort the array.. then check every adjacant pair (including the +wraparound pair, i.e the last and the first).. +No C solutions today. Might do them later.. -Task 2: Reshape Matrix -You are given a matrix (m x n) and two integers (r) and (c). +Task 2: Array Pairings -Write a script to reshape the given matrix in form (r x c) with the -original value in the given matrix. If you can't reshape print 0. +You are given an array of integers having even number of elements.. +Write a script to find the maximum sum of the minimum of each pairs. Example 1 -Input: $matrix = [ [ 1, 2 ], [ 3, 4 ] ] - $r = 1 - $c = 4 + Input: @array = (1,2,3,4) + Output: 4 -Output: [ 1 2 3 4 ] + Possible Pairings are as below: + a) (1,2) and (3,4). So min(1,2) + min(3,4) => 1 + 3 => 4 + b) (1,3) and (2,4). So min(1,3) + min(2,4) => 1 + 2 => 3 + c) (1,4) and (2,3). So min(1,4) + min(2,3) => 2 + 1 => 3 -Example 2 - -Input: $matrix = [ [ 1, 2, 3 ] , [ 4, 5, 6 ] ] - $r = 3 - $c = 2 - -Output: [ [ 1, 2 ], [ 3, 4 ], [ 5, 6 ] ] + So the maxium sum is 4. -Example 3 +Example 2 -Input: $matrix = [ [ 1, 2 ] ] - $r = 3 - $c = 2 + Input: @array = (0,2,1,3) + Output: 2 -Output: 0 + Possible Pairings are as below: + a) (0,2) and (1,3). So min(0,2) + min(1,3) => 0 + 1 => 1 + b) (0,1) and (2,3). So min(0,1) + min(2,3) => 0 + 2 => 2 + c) (0,3) and (2,1). So min(0,3) + min(2,1) => 0 + 1 => 1 + + So the maximum sum is 2. -MY NOTES: also quite easy, can be done if R1*C1==R2*C -(of course we have to discover R1 and C1, the dimensions o -the original matrix). Also have to read the matrix in.. +MY NOTES: hmm. I wish one of the examples had 6 elements. It seems +to me that this sounds like a recursive solution.. Pick each possible +pair involving the first element and each of the others (in turn), +remove them, calculate and total up the minimum, then recurse. -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). Needed to -pass original sizes into C routine.. +No C solutions today. Might do them later.. diff --git a/challenge-206/duncan-c-white/perl/ch-1.pl b/challenge-206/duncan-c-white/perl/ch-1.pl new file mode 100755 index 0000000000..9a06b20182 --- /dev/null +++ b/challenge-206/duncan-c-white/perl/ch-1.pl @@ -0,0 +1,94 @@ +#!/usr/bin/perl +# +# Task 1: Shortest Time +# +# You are given a list of time points, at least 2, in the 24-hour clock +# format HH:MM. Write a script to find out the shortest time in minutes +# between any two time points. +# +# Example 1 +# +# Input: @time = ("00:00", "23:55", "20:00") +# Output: 5 +# +# Since the difference between "00:00" and "23:55" is the shortest (5 minutes). +# +# Example 2 +# +# Input: @array = ("01:01", "00:50", "00:57") +# Output: 4 +# +# Example 3 +# +# Input: @array = ("10:10", "09:30", "09:00", "09:55") +# Output: 15 +# +# MY NOTES: reasonably easy, although of course wraparound has to taken +# into account. Might convert each hh:mm time into a number of minutes, +# then sort the array.. then check every adjacant pair (including the +# wraparound pair, i.e the last and the first).. +# + +use strict; +use warnings; +use feature 'say'; +use Getopt::Long; +use Data::Dumper; + +my $debug=0; +die "Usage: shortest-time [--debug] stringlist\n" + unless GetOptions( "debug"=>\$debug ) && @ARGV>0; + +# +# my $time = parsehhmm( $hhmm ); +# Parse a 24-hour hh:mm time string into the total number +# of minutes since 00:00, and return it. +# +sub parsehhmm +{ + my( $hhmm ) = @_; + $hhmm =~ /^(\d\d):(\d\d)$/ || die "parsehhmm: bad format $hhmm\n"; + return 60*$1 + $2; +} + + + +my @list = split( /,/, join(',',@ARGV) ); + +@list = map { parsehhmm($_) } @list; + +say "parsed: ", join(',',@list) if $debug; + +@list = sort { $a <=> $b } @list; + +say "sorted: ", join(',',@list) if $debug; + +my $best = 1440; +my $bestt1 = -1; +my $bestt2 = -1; + +push @list, 1440 + $list[0]; + +say "wraparound: ", join(',',@list) if $debug; + +foreach my $pos (0..$#list-1) +{ + my $t = $list[$pos+1]; + my $diff = $t - $list[$pos]; + say "pos $pos, diff $diff" if $debug; + if( $best > $diff ) + { + $best = $diff; + $bestt1 = $list[$pos]; + $bestt2 = $t; + } +} + +say $best; + +if( $debug ) +{ + $bestt1 = sprintf( "%02d:%02d", $bestt1/60, $bestt1%60 ); + $bestt2 = sprintf( "%02d:%02d", $bestt2/60, $bestt2%60 ); + say "($bestt1..$bestt2)"; +} diff --git a/challenge-206/duncan-c-white/perl/ch-2.pl b/challenge-206/duncan-c-white/perl/ch-2.pl new file mode 100755 index 0000000000..1a1b92330a --- /dev/null +++ b/challenge-206/duncan-c-white/perl/ch-2.pl @@ -0,0 +1,96 @@ +#!/usr/bin/perl +# +# Task 2: Array Pairings +# +# You are given an array of integers having even number of elements.. +# Write a script to find the maximum sum of the minimum of each pairs. +# +# Example 1 +# +# Input: @array = (1,2,3,4) +# Output: 4 +# +# Possible Pairings are as below: +# a) (1,2) and (3,4). So min(1,2) + min(3,4) => 1 + 3 => 4 +# b) (1,3) and (2,4). So min(1,3) + min(2,4) => 1 + 2 => 3 +# c) (1,4) and (2,3). So min(1,4) + min(2,3) => 2 + 1 => 3 +# +# So the maxium sum is 4. +# +# Example 2 +# +# Input: @array = (0,2,1,3) +# Output: 2 +# +# Possible Pairings are as below: +# a) (0,2) and (1,3). So min(0,2) + min(1,3) => 0 + 1 => 1 +# b) (0,1) and (2,3). So min(0,1) + min(2,3) => 0 + 2 => 2 +# c) (0,3) and (2,1). So min(0,3) + min(2,1) => 0 + 1 => 1 +# +# So the maximum sum is 2. +# +# MY NOTES: hmm. I wish one of the examples had 6 elements. It seems +# to me that this sounds like a recursive solution.. Pick each possible +# pair involving the first element and each of the others (in turn), +# remove them, calculate and total up the minimum, then recurse. +# + +use strict; +use warnings; +use feature 'say'; +use Getopt::Long; +use Function::Parameters; +use Data::Dumper; +use List::Util qw(min max); + +my $debug=0; +die "Usage: array-pairings [--debug] even-len-intlist\n" + unless GetOptions( "debug"=>\$debug ) && @ARGV > 0; + +my @list = split( /,/, join(',',@ARGV) ); +my $nel = @list; + +die "array-pairings: need even number of integers, not $nel\n" if $nel % 2 == 1; + +say "list: ", join(',',@list) if $debug; + +=pod + +=head2 find_all( $sum, $solarrayref, @list ); + +Given an even-length list @list, a sum so far ($sum), +and a reference to an array of solutions ($solarrayref), +pick all possible pairs of items from @list including +the first item in the list, and min(that pair) to the sum, +and recurse on the rest of the array. Accumulate all +solutions (final value of $sum when @list is empty) in @$solarrayref. + +=cut +fun find_all( $sum, $solarrayref, @list ) +{ + if( @list == 0 ) + { + push @$solarrayref, $sum; + return; + } + + # find all pairs of first item, another item in @list + my $first = shift @list; + foreach my $spos (0..$#list) + { + my $second = $list[$spos]; + my $min = min($first,$second); + my @newl = ( @list[0..$spos-1], @list[$spos+1..$#list] ); + find_all( $sum+$min, $solarrayref, @newl ); + } +} + + +my @solutions; # list of all solutions, final answer is max(these) + +find_all( 0, \@solutions, @list ); + +say "pairing solutions: ", join(',',@solutions) if $debug; + +my $max = max(@solutions); +say $max; -- cgit