From 56f9787695c9913d9dcaeac567c687a1c5a1484a Mon Sep 17 00:00:00 2001 From: dcw Date: Sun, 4 Dec 2022 23:48:13 +0000 Subject: added my late solutions to challenge 192 (Perl x 2 + C x 2) and my solutions to challenge 193 (Perl x 2 + C x 1) --- challenge-192/duncan-c-white/C/Makefile | 19 +++ challenge-192/duncan-c-white/C/README | 9 ++ challenge-192/duncan-c-white/C/args.c | 207 ++++++++++++++++++++++++++++ challenge-192/duncan-c-white/C/args.h | 11 ++ challenge-192/duncan-c-white/C/ch-1.c | 37 +++++ challenge-192/duncan-c-white/C/ch-2.c | 142 +++++++++++++++++++ challenge-192/duncan-c-white/C/parseints.c | 114 +++++++++++++++ challenge-192/duncan-c-white/C/parseints.h | 1 + challenge-192/duncan-c-white/C/printarray.c | 39 ++++++ challenge-192/duncan-c-white/C/printarray.h | 1 + challenge-192/duncan-c-white/README | 121 ++++++++-------- challenge-192/duncan-c-white/perl/ch-1.pl | 62 +++++++++ challenge-192/duncan-c-white/perl/ch-2.pl | 154 +++++++++++++++++++++ challenge-193/duncan-c-white/C/.cbuild | 2 +- challenge-193/duncan-c-white/C/Makefile | 14 ++ challenge-193/duncan-c-white/C/README | 7 + challenge-193/duncan-c-white/C/args.c | 207 ++++++++++++++++++++++++++++ challenge-193/duncan-c-white/C/args.h | 11 ++ challenge-193/duncan-c-white/C/ch-1.c | 61 ++++++++ challenge-193/duncan-c-white/README | 108 +++++++-------- challenge-193/duncan-c-white/perl/ch-1.pl | 46 +++++++ challenge-193/duncan-c-white/perl/ch-2.pl | 116 ++++++++++++++++ 22 files changed, 1371 insertions(+), 118 deletions(-) create mode 100644 challenge-192/duncan-c-white/C/Makefile create mode 100644 challenge-192/duncan-c-white/C/README create mode 100644 challenge-192/duncan-c-white/C/args.c create mode 100644 challenge-192/duncan-c-white/C/args.h create mode 100644 challenge-192/duncan-c-white/C/ch-1.c create mode 100644 challenge-192/duncan-c-white/C/ch-2.c create mode 100644 challenge-192/duncan-c-white/C/parseints.c create mode 100644 challenge-192/duncan-c-white/C/parseints.h create mode 100644 challenge-192/duncan-c-white/C/printarray.c create mode 100644 challenge-192/duncan-c-white/C/printarray.h create mode 100755 challenge-192/duncan-c-white/perl/ch-1.pl create mode 100755 challenge-192/duncan-c-white/perl/ch-2.pl create mode 100644 challenge-193/duncan-c-white/C/Makefile create mode 100644 challenge-193/duncan-c-white/C/README create mode 100644 challenge-193/duncan-c-white/C/args.c create mode 100644 challenge-193/duncan-c-white/C/args.h create mode 100644 challenge-193/duncan-c-white/C/ch-1.c create mode 100755 challenge-193/duncan-c-white/perl/ch-1.pl create mode 100755 challenge-193/duncan-c-white/perl/ch-2.pl diff --git a/challenge-192/duncan-c-white/C/Makefile b/challenge-192/duncan-c-white/C/Makefile new file mode 100644 index 0000000000..0e674ee7dd --- /dev/null +++ b/challenge-192/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 +ch-1.o: ch-1.c args.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-192/duncan-c-white/C/README b/challenge-192/duncan-c-white/C/README new file mode 100644 index 0000000000..31e5ebdb28 --- /dev/null +++ b/challenge-192/duncan-c-white/C/README @@ -0,0 +1,9 @@ +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]. diff --git a/challenge-192/duncan-c-white/C/args.c b/challenge-192/duncan-c-white/C/args.c new file mode 100644 index 0000000000..d4a2d38b9a --- /dev/null +++ b/challenge-192/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" + + +int main( int argc, char **argv ) +{ + int n; + process_onenumarg_default( "binary-flip", argc, argv, 100, &n ); + + if( debug ) + { + printf( "debug: n=%d\n", n ); + } + + int p = 1; + while( p < n ) + { + p *= 2; + } + + n = (~ n) & (p-1); + printf( "%d\n", n ); + + return 0; +} diff --git a/challenge-192/duncan-c-white/C/ch-2.c b/challenge-192/duncan-c-white/C/ch-2.c new file mode 100644 index 0000000000..0b604739e1 --- /dev/null +++ b/challenge-192/duncan-c-white/C/ch-2.c @@ -0,0 +1,142 @@ +// +// Task 2: Equal Distribution +// +// C version. +// + +#include +#include +#include +#include +#include +#include + +#include "args.h" +#include "parseints.h" +#include "printarray.h" + + +// +// int pos = find_pair_diff_gt_1(nel, list[]); +// Find the position pos of the first element of the first pair in list +// where the absolute difference between list[pos] and list[pos+1] is > 1. +// Return -1 if none. +// +int find_pair_diff_gt_1( int nel, int *list ) +{ + for( int pos=0; pos 1 ) return pos; + } + return -1; +} + + +// +// int pos = find_pair_f_lt_s(nel, list[]); +// Find the position pos of the first element of a pair in @list +// where list[$pos] < list[pos+1]. Return -1 if none. +// +int find_pair_f_lt_s( int nel, int *list ) +{ + for( int pos=0; pos 1 elements\n" ); + exit(1); + } + + if( debug ) + { + printf( "debug: initial list: " ); + print_int_array( 60, nel, list, ',', stdout ); + putchar( '\n' ); + } + + int nmoves = 0; + + if( debug ) + { + printf( "starting first pass\n" ); + } + + // first pass: repeatedly find two adjacent cells whose absolute + // difference > 1 and transfer one from the bigger to the smaller. + int pos; + while( (pos = find_pair_diff_gt_1(nel, list)) != -1 ) + { + if( debug ) + { + printf( "debug: found pos %d, list=", pos ); + print_int_array( 60, nel, list, ',', stdout ); + putchar( '\n' ); + } + if( list[pos] < list[pos+1] ) + { + list[pos]++; + list[pos+1]--; + } else + { + list[pos]--; + list[pos+1]++; + } + nmoves++; + } + + if( debug ) + { + printf( "starting second pass\n" ); + } + + // second pass: repeatedly find 2 adjacent cells where + // firstvalue < secondvalue and transfer one from secondvalue + // to firstvalue + while( (pos = find_pair_f_lt_s(nel, list)) != -1 ) + { + if( debug ) + { + printf( "debug: found pos %d, list=", pos ); + print_int_array( 60, nel, list, ',', stdout ); + putchar( '\n' ); + } + list[pos]++; + list[pos+1]--; + nmoves++; + } + + int firstel = list[0]; + int nsame = 0; + for( pos=0; pos +#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-192/duncan-c-white/C/printarray.h b/challenge-192/duncan-c-white/C/printarray.h new file mode 100644 index 0000000000..40efb83277 --- /dev/null +++ b/challenge-192/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-192/duncan-c-white/README b/challenge-192/duncan-c-white/README index d51cea2c1e..4b7a727129 100644 --- a/challenge-192/duncan-c-white/README +++ b/challenge-192/duncan-c-white/README @@ -1,89 +1,98 @@ -Task 1: Task 1: Twice Largest +Task 1: Binary Flip -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. +You are given a positive integer, $n. +Write a script to find the binary flip. Example 1 -Input: @list = (1,2,3,4) -Output: -1 +Input: $n = 5 +Output: 2 -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 +First find the binary equivalent of the given integer, 101. +Then flip the binary digits 0 -> 1 and 1 -> 0 and we get 010. +So Binary 010 => Decimal 2. Example 2 -Input: @list = (1,2,0,5) -Output: 1 +Input: $n = 4 +Output: 3 -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 +Decimal 4 = Binary 100 +Flip 0 -> 1 and 1 -> 0, we get 011. +Binary 011 = Decimal 3 Example 3 -Input: @list = (2,6,3,1) +Input: $n = 6 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 +Decimal 6 = Binary 110 +Flip 0 -> 1 and 1 -> 0, we get 001. +Binary 001 = Decimal 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"... +MY NOTES: very easy. That's ones complement with a bit of range-fixing! 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: Cute List +Task 2: Equal Distribution + +You are given a list of integers greater than or equal to zero, @list. + +Write a script to distribute the number so that each members are same. If you succeed then print the total moves otherwise print -1. + +Please follow the rules (as suggested by Neils van Dijke [2022-11-21 13:00] + +1) You can only move a value of '1' per move +2) You are only allowed to move a value of '1' to a direct neighbor/adjacent cell -You are given an integer, 0 < $n <= 15. -Write a script to find the number of orderings of numbers that form a cute list. +Example 1: + +Input: @list = (1, 0, 5) +Output: 4 + +Move #1: 1, 1, 4 +(2nd cell gets 1 from the 3rd cell) + +Move #2: 1, 2, 3 +(2nd cell gets 1 from the 3rd cell) + +Move #3: 2, 1, 3 +(1st cell get 1 from the 2nd cell) + +Move #4: 2, 2, 2 +(2nd cell gets 1 from the 3rd cell) + +Example 2: + +Input: @list = (0, 2, 0) +Output: -1 + +It is not possible to make each same. -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 +Example 3: -1) $list[$i] is evenly divisible by $i -or -2) $i is evenly divisible by $list[$i] +Input: @list = (0, 3, 0) +Output: 2 -Example +Move #1: 1, 2, 0 +(1st cell gets 1 from the 2nd cell) -Input: $n = 2 -Ouput: 2 +Move #2: 1, 1, 1 +(3rd cell gets 1 from the 2nd cell) -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.. If I'm understanding that right, it's two passes: +1. repeatedly find two adjacent cells whose absolute difference > 1 +and transfer one from the bigger cell to the smaller cell. +2. repeatedly find 2 adjacent cells where firstvalue < secondvalue +and transfer one from secondvalue to firstvalue -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. +Note also that I'm pretty sure that all lists whose sum is divisible +by 3 can be balanced, and no list whose sum is NOT divisible by 3 can be. 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-192/duncan-c-white/perl/ch-1.pl b/challenge-192/duncan-c-white/perl/ch-1.pl new file mode 100755 index 0000000000..c7a408b460 --- /dev/null +++ b/challenge-192/duncan-c-white/perl/ch-1.pl @@ -0,0 +1,62 @@ +#!/usr/bin/perl +# +# Task 1: Binary Flip +# +# You are given a positive integer, $n. +# +# Write a script to find the binary flip. +# +# Example 1 +# +# Input: $n = 5 +# Output: 2 +# +# First find the binary equivalent of the given integer, 101. +# Then flip the binary digits 0 -> 1 and 1 -> 0 and we get 010. +# So Binary 010 => Decimal 2. +# +# Example 2 +# +# Input: $n = 4 +# Output: 3 +# +# Decimal 4 = Binary 100 +# Flip 0 -> 1 and 1 -> 0, we get 011. +# Binary 011 = Decimal 3 +# +# Example 3 +# +# Input: $n = 6 +# Output: 1 +# +# Decimal 6 = Binary 110 +# Flip 0 -> 1 and 1 -> 0, we get 001. +# Binary 001 = Decimal 1 +# +# MY NOTES: very easy. That's ones complement with a bit of range-fixing! +# +# 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: binary-flip [--debug] N\n" + unless GetOptions( "debug"=>\$debug ) && @ARGV==1; + +my $n = shift; +$n += 0; + +my $p = 1; +while( $p < $n ) +{ + $p *= 2; +} + +$n = (~ $n) & ($p-1); +say "$n"; diff --git a/challenge-192/duncan-c-white/perl/ch-2.pl b/challenge-192/duncan-c-white/perl/ch-2.pl new file mode 100755 index 0000000000..0d2a76c5fb --- /dev/null +++ b/challenge-192/duncan-c-white/perl/ch-2.pl @@ -0,0 +1,154 @@ +#!/usr/bin/perl +# +# Task 2: Equal Distribution +# +# You are given a list of integers greater than or equal to zero, @list. +# +# Write a script to distribute the number so that each members are +# same. If you succeed then print the total moves otherwise print -1. +# +# Please follow the rules (as suggested by Neils van Dijke [2022-11-21 13:00] +# +# 1) You can only move a value of '1' per move +# 2) You are only allowed to move a value of '1' to a direct neighbor/adjacent cell +# +# Example 1: +# +# Input: @list = (1, 0, 5) +# Output: 4 +# +# Move #1: 1, 1, 4 +# (2nd cell gets 1 from the 3rd cell) +# +# Move #2: 1, 2, 3 +# (2nd cell gets 1 from the 3rd cell) +# +# Move #3: 2, 1, 3 +# (1st cell get 1 from the 2nd cell) +# +# Move #4: 2, 2, 2 +# (2nd cell gets 1 from the 3rd cell) +# +# Example 2: +# +# Input: @list = (0, 2, 0) +# Output: -1 +# +# It is not possible to make each same. +# +# Example 3: +# +# Input: @list = (0, 3, 0) +# Output: 2 +# +# Move #1: 1, 2, 0 +# (1st cell gets 1 from the 2nd cell) +# +# Move #2: 1, 1, 1 +# (3rd cell gets 1 from the 2nd cell) +# +# MY NOTES: Hmm.. If I'm understanding that right, it's two passes: +# 1. repeatedly find two adjacent cells whose absolute difference > 1 +# and transfer one from the bigger cell to the smaller cell. +# 2. repeatedly find 2 adjacent cells where firstvalue < secondvalue +# and transfer one from secondvalue to firstvalue +# +# 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: same-list [--debug] intlist\n" + unless GetOptions( "debug"=>\$debug ) && @ARGV>0; + +my @list = split(/,/, join( ',', @ARGV )); + +die "same-list: need a list of > 1 elements\n" if @list<2; + + +=pod + +=head2 my $pos = find_pair_diff_gt_1(@list); + +Find the position $pos of the first element of the first pair in @list +where the absolute difference between list[$pos] and list[pos+1] is > 1. +Return -1 if none. + +=cut +fun find_pair_diff_gt_1( @list ) +{ + for( my $pos=0; $pos<@list-1; $pos++ ) + { + return $pos if abs( $list[$pos] - $list[$pos+1] ) > 1; + } + return -1; +} + + + +=pod + +=head2 my $pos = find_pair_f_lt_s(@list); + +Find the position $pos of the first element of a pair in @list +where list[$pos] < list[pos+1]. Return -1 if none. + +=cut +fun find_pair_f_lt_s( @list ) +{ + for( my $pos=0; $pos<@list-1; $pos++ ) + { + return $pos if $list[$pos] < $list[$pos+1]; + } + return -1; +} + + +my $nmoves = 0; + +say "starting first pass" if $debug; + +# first pass: repeatedly find two adjacent cells whose absolute difference > 1 +# and transfer one from the bigger cell to the smaller cell. +while( (my $pos = find_pair_diff_gt_1(@list)) != -1 ) +{ + say "debug: found pos $pos, list=", join(',',@list) if $debug; + if( $list[$pos] < $list[$pos+1] ) + { + $list[$pos]++; + $list[$pos+1]--; + } else + { + $list[$pos]--; + $list[$pos+1]++; + } + $nmoves++; +} + + +say "starting second pass" if $debug; + +# second pass: repeatedly find 2 adjacent cells where firstvalue < secondvalue +# and transfer one from secondvalue to firstvalue +while( (my $pos = find_pair_f_lt_s(@list)) != -1 ) +{ + say "debug: found pos $pos, list=", join(',',@list) if $debug; + $list[$pos]++; + $list[$pos+1]--; + $nmoves++; +} + +my $firstel = $list[0]; +my $nsame = grep { $_ == $firstel } @list; +my $success = $nsame == @list ? 1 : 0; + +say "debug: after $nmoves moves, nsame=$nsame, success=$success, final list=", join(',',@list) if $debug; +say $success ? $nmoves : -1; diff --git a/challenge-193/duncan-c-white/C/.cbuild b/challenge-193/duncan-c-white/C/.cbuild index a14ec76520..624a95ebfb 100644 --- a/challenge-193/duncan-c-white/C/.cbuild +++ b/challenge-193/duncan-c-white/C/.cbuild @@ -1,4 +1,4 @@ -BUILD = ch-1 ch-2 +BUILD = ch-1 CFLAGS = -Wall -g #LDFLAGS = -lm #CFLAGS = -g diff --git a/challenge-193/duncan-c-white/C/Makefile b/challenge-193/duncan-c-white/C/Makefile new file mode 100644 index 0000000000..e9ebaeaa96 --- /dev/null +++ b/challenge-193/duncan-c-white/C/Makefile @@ -0,0 +1,14 @@ +# Makefile rules generated by CB +CC = gcc +CFLAGS = -Wall -g +BUILD = ch-1 + +all: $(BUILD) + +clean: + /bin/rm -f $(BUILD) *.o core a.out + +args.o: args.c +ch-1: ch-1.o args.o +ch-1.o: ch-1.c args.h + diff --git a/challenge-193/duncan-c-white/C/README b/challenge-193/duncan-c-white/C/README new file mode 100644 index 0000000000..6664968152 --- /dev/null +++ b/challenge-193/duncan-c-white/C/README @@ -0,0 +1,7 @@ +Thought I'd also have a go at translating ch-1.pl into C.. + +It produces near-identical (non-debugging and even debugging) output to the +Perl original. + +It uses one of my regular support modules: +- a command-line argument processing module args.[ch] diff --git a/challenge-193/duncan-c-white/C/args.c b/challenge-193/duncan-c-white/C/args.c new file mode 100644 index 0000000000..d4a2d38b9a --- /dev/null +++ b/challenge-193/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" + + +// +// print_binary( x, nbits ); +// Print x out as an unsigned $nbits binary value. +// +void print_binary( int x, int nbits ) +{ + int mask = 1<<(nbits-1); + for( int i=0; i>= 1; + } +} + + +int main( int argc, char **argv ) +{ + int n; + process_onenumarg_default( "binary-strings", argc, argv, 100, &n ); + + if( debug ) + { + printf( "debug: n=%d\n", n ); + } + + int max = 1< 0. +Write a script to find all possible binary numbers of size $n bits. 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 +Input: $n = 2 +Output: 00, 11, 01, 10 Example 2 -Input: @list = (1,2,0,5) -Output: 1 +Input: $n = 3 +Output: 000, 001, 010, 100, 111, 110, 101, 011 -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 +MY NOTES: very easy -Example 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) -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 +Task 2: Odd String -Example 4 +You are given a list of strings of same length, @s. -Input: @list = (4,5,2,3) -Output: -1 +Write a script to find the odd string in the given list. Use positional +value of alphabet starting with 0, i.e. a = 0, b = 1, ... z = 25. -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 +Find the difference array for each string as shown in the example. Then +pick the odd one out. -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"... +Example 1: -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) +Input: @s = ("adc", "wzy", "abc") +Output: "abc" +Difference array for "adc" => [ d - a, c - d ] + => [ 3 - 0, 2 - 3 ] + => [ 3, -1 ] -Task 2: Cute List +Difference array for "wzy" => [ z - w, y - z ] + => [ 25 - 22, 24 - 25 ] + => [ 3, -1 ] -You are given an integer, 0 < $n <= 15. +Difference array for "abc" => [ b - a, c - b ] + => [ 1 - 0, 2 - 1 ] + => [ 1, 1 ] -Write a script to find the number of orderings of numbers that form a cute list. +The difference array for "abc" is the odd one. -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 +Example 2: -1) $list[$i] is evenly divisible by $i -or -2) $i is evenly divisible by $list[$i] +Input: @s = ("aaa", "bob", "ccc", "ddd") +Output: "bob" -Example +Difference array for "aaa" => [ a - a, a - a ] + => [ 0 - 0, 0 - 0 ] + => [ 0, 0 ] -Input: $n = 2 -Ouput: 2 +Difference array for "bob" => [ o - b, b - o ] + => [ 14 - 1, 1 - 14 ] + => [ 13, -13 ] -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). +Difference array for "ccc" => [ c - c, c - c ] + => [ 2 - 2, 2 - 2 ] + => [ 0, 0 ] -@list = (1,2) is cute since $list[1] = 1 is divisible by 1 and $list[2] -= 2 is divisible by 2. +Difference array for "ddd" => [ d - d, d - d ] + => [ 3 - 3, 3 - 3 ] + => [ 0, 0 ] -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. +The difference array for "bob" is the odd one. -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) +MY NOTES: Hmm.. not always a single odd one out. What are we supposed +to do if there is no odd one out? diff --git a/challenge-193/duncan-c-white/perl/ch-1.pl b/challenge-193/duncan-c-white/perl/ch-1.pl new file mode 100755 index 0000000000..bdb3fd1dfd --- /dev/null +++ b/challenge-193/duncan-c-white/perl/ch-1.pl @@ -0,0 +1,46 @@ +#!/usr/bin/perl +# +# Task 1: Binary String +# +# You are given an integer, $n > 0. +# Write a script to find all possible binary numbers of size $n bits. +# +# Example 1 +# +# Input: $n = 2 +# Output: 00, 11, 01, 10 +# +# Example 2 +# +# Input: $n = 3 +# Output: 000, 001, 010, 100, 111, 110, 101, 011 +# +# 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) +# + +use strict; +use warnings; +use feature 'say'; +use Getopt::Long; +use Data::Dumper; + +my $debug=0; +die "Usage: binary-strings [--debug] N\n" + unless GetOptions( "debug"=>\$debug ) && @ARGV==1; + +my $n = shift; +$n += 0; + +my $max = 2 ** $n; +#say $max; + +my @result; +for( my $i=0; $i<$max; $i++ ) +{ + my $bitstring = sprintf( "%0".$n."b", $i ); + push @result, $bitstring; +} +say join(', ', @result ); diff --git a/challenge-193/duncan-c-white/perl/ch-2.pl b/challenge-193/duncan-c-white/perl/ch-2.pl new file mode 100755 index 0000000000..988f4819cf --- /dev/null +++ b/challenge-193/duncan-c-white/perl/ch-2.pl @@ -0,0 +1,116 @@ +#!/usr/bin/perl +# +# Task 2: Odd String +# +# You are given a list of strings of same length, @s. +# +# Write a script to find the odd string in the given list. Use positional +# value of alphabet starting with 0, i.e. a = 0, b = 1, ... z = 25. +# +# Find the difference array for each string as shown in the example. Then +# pick the odd one out. +# +# Example 1: +# +# Input: @s = ("adc", "wzy", "abc") +# Output: "abc" +# +# Difference array for "adc" => [ d - a, c - d ] +# => [ 3 - 0, 2 - 3 ] +# => [ 3, -1 ] +# +# Difference array for "wzy" => [ z - w, y - z ] +# => [ 25 - 22, 24 - 25 ] +# => [ 3, -1 ] +# +# Difference array for "abc" => [ b - a, c - b ] +# => [ 1 - 0, 2 - 1 ] +# => [ 1, 1 ] +# +# The difference array for "abc" is the odd one. +# +# Example 2: +# +# Input: @s = ("aaa", "bob", "ccc", "ddd") +# Output: "bob" +# +# Difference array for "aaa" => [ a - a, a - a ] +# => [ 0 - 0, 0 - 0 ] +# => [ 0, 0 ] +# +# Difference array for "bob" => [ o - b, b - o ] +# => [ 14 - 1, 1 - 14 ] +# => [ 13, -13 ] +# +# Difference array for "ccc" => [ c - c, c - c ] +# => [ 2 - 2, 2 - 2 ] +# => [ 0, 0 ] +# +# Difference array for "ddd" => [ d - d, d - d ] +# => [ 3 - 3, 3 - 3 ] +# => [ 0, 0 ] +# +# The difference array for "bob" is the odd one. +# +# MY NOTES: Hmm.. not always a single odd one out. What are we supposed +# to do if there is no odd one out? +# + +use strict; +use warnings; +use feature 'say'; +use Getopt::Long; +use Function::Parameters; +use Data::Dumper; + + +my $debug=0; +die "Usage: odd-string [--debug] stringlist\n" + unless GetOptions( "debug"=>\$debug ) && @ARGV>0; + +=pod + +=head2 my $diffsig = diffsig($str); + +Given an alphabetic string $str, form the difference signature. + +=cut +fun diffsig( $str ) +{ + my @x = split( //, $str ); + my @diff; + foreach my $pos (0..$#x-1) + { + push @diff, ord($x[$pos+1])-ord($x[$pos]); + } + return join( ',', @diff ); +} + + +my @list = @ARGV; + +my @diffsig = map { diffsig($_) } @list; + +my %d2l; # diffsig -> list of all strings with that diffsig +foreach my $pos (0..$#list) +{ + my $ref = ($d2l{ $diffsig[$pos] } //= []); + push @$ref, $list[$pos]; +} + +#say for @diffsig; +#say Dumper(\%d2l); + +my %freq; +map { $freq{$_}++ } @diffsig; + +foreach my $k (keys %freq) +{ + delete $freq{$k} if $freq{$k}>1; +} + +foreach my $k (keys %freq) +{ + my $ref = $d2l{$k}; + say join(',', @$ref); +} -- cgit