diff options
| -rw-r--r-- | challenge-051/duncan-c-white/README | 56 | ||||
| -rwxr-xr-x | challenge-051/duncan-c-white/perl/ch-1.pl | 47 | ||||
| -rwxr-xr-x | challenge-051/duncan-c-white/perl/ch-2.pl | 62 |
3 files changed, 126 insertions, 39 deletions
diff --git a/challenge-051/duncan-c-white/README b/challenge-051/duncan-c-white/README index 3d714d2e48..1c6e36e8ae 100644 --- a/challenge-051/duncan-c-white/README +++ b/challenge-051/duncan-c-white/README @@ -1,52 +1,30 @@ -Task 1: "Merge Intervals +Task 1: "3 Sum -Write a script to merge the given intervals whereever possible. +Given an array @L of integers, and a target T. Write a script to find +all unique triplets such that a + b + c is same as the target T. Also +make sure a <= b <= c. - [2,7], [3,9], [10,12], [15,19], [18,22] +Example: -The script should merge [2, 7] and [3, 9] together to return [2, 9]. + @L = (-25, -10, -7, -3, 2, 4, 8, 10); -Similarly it should also merge [15, 19] and [18, 22] together to return [15, 22]. - -The final result should be something like below: - -[2, 9], [10, 12], [15, 22] +One such triplet for target 0 i.e. -10 + 2 + 8 = 0. " -My notes: Fine, but why wouldn't we also merge [2,9] and [10,12] to give -[2,12]? I think we would. The immediate thought to implement this is -to collapse all ranges to an integer set, and then reconstruct the minimal -sequence of ranges direct from the set. - +My notes: Fine. -Task #2: "Noble Integer -You are given a list, @L, of three or more random integers between 1 and -50. A Noble Integer is an integer N in @L, such that there are exactly -N integers greater than N in @L. Output any Noble Integer found in @L, -or an empty list if none were found. +Task #2: "Colourful Number -An interesting question is whether or not there can be multiple Noble -Integers in a list. +Write a script to display all Colorful Number with 3 digits. -For example, + A Colorful Number is an integer where all the products of consecutive + subsets of digit are different. -Suppose we have list of 4 integers [2, 6, 1, 3]. - -Here we have 2 in the above list, known as Noble Integer, since there -are exactly 2 integers in the list greater than 2: 3 and 6. - -Therefore the script would print 2. +For example, 263 is a Colorful Number since 2, 6, 3, 2x6, 6x3, 2x6x3 are unique. " -My notes: Interesting, especially the question about "whether or not there -can be multiple Noble Integers in a list": If repeated numbers are allowed, -you can definitely have multiple (identical) noble numbers eg 2 1 1 1 1... -(each 1 is noble because there's exactly one number >1 (the 2)). So disallow that. -Now, given distinct numbers, I don't think multiple noble numbers are possible -in one list. "find a list with 2 numbers greater than 2 and 3 numbers greater -than 3" is not possible, because every number greater than 3 is ALSO greater -than 2, so there are at least as many numbers greater than 2 as there are -numbers greater than 3, i.e. at least 3 numbers in the list are greater than 2, -which contradicts the specification that only (exactly) 2 numbers in the list are -greater than 2. +My notes: Interesting. + +Having written this, assuming that it's correct, I find 328 Colourful 3-digit +numbers. diff --git a/challenge-051/duncan-c-white/perl/ch-1.pl b/challenge-051/duncan-c-white/perl/ch-1.pl new file mode 100755 index 0000000000..590b4f1288 --- /dev/null +++ b/challenge-051/duncan-c-white/perl/ch-1.pl @@ -0,0 +1,47 @@ +#!/usr/bin/perl +# +# Task 1: "3 Sum +# +# Given an array @L of integers, and a target T. Write a script to find +# all unique triplets such that a + b + c is same as the target T. Also +# make sure a <= b <= c. +# +# Example: +# +# @L = (-25, -10, -7, -3, 2, 4, 8, 10); +# +# One such triplet for target 0 i.e. -10 + 2 + 8 = 0. +# " +# +# My notes: Fine. The obvious way of achieving a<=b<=c in all +# answers is to sort @L. +# + +use feature 'say'; +use strict; +use warnings; +#use Function::Parameters; +#use Data::Dumper; + +die "Usage: 3-sum T LIST\n" if @ARGV < 4; +my $t = shift; +my @l = @ARGV; + +@l = sort @l; +my $n = @l; +my %v2p = map { $l[$_] => $_ } 0..$n-1; + +foreach my $i (0..$n-3) +{ + my $a = $l[$i]; + foreach my $j ($i+1..$n-2) + { + my $b = $l[$j]; + my $sum2 = $a+$b; + my $left = $t - $sum2; + if( defined $v2p{$left} ) + { + say "found a=$a, b=$b, c=$left (target=$t)"; + } + } +} diff --git a/challenge-051/duncan-c-white/perl/ch-2.pl b/challenge-051/duncan-c-white/perl/ch-2.pl new file mode 100755 index 0000000000..fe3e3cfe3b --- /dev/null +++ b/challenge-051/duncan-c-white/perl/ch-2.pl @@ -0,0 +1,62 @@ +#!/usr/bin/perl +# +# Task #2: "Colourful Number +# +# Write a script to display all Colorful Number with 3 digits. +# +# A Colorful Number is an integer where all the products of consecutive +# subsets of digit are different. +# +# For example, 263 is a Colorful Number since 2, 6, 3, 2x6, 6x3, 2x6x3 are unique. +# " +# +# My notes: Interesting. Having written this, assuming that it's correct, I +# find 328 Colourful 3-digit numbers. +# + +use strict; +use warnings; +use feature 'say'; +use Function::Parameters; +#use Data::Dumper; + +# for every 3 digit number $i +foreach my $i (100..999) +#my $i = 263; +{ + say "$i is colourful" if colourful($i); +} + + +# +# my $iscol = colourful( $x ); +# Function to determine whether or not $x is a colourful number, +# i.e. an integer where all the products of consecutive subsequences +# of digits are different. Return 1 iff it is; otherwise 0. +# +# For example, 263 is a Colorful Number since 2, 6, 3, 2x6, 6x3, 2x6x3 are unique. +# +fun colourful( $x ) +{ + my @dig = split( //, $x ); # find all digits. + my $n = @dig; + my %seen; # combinations already seen. + #say "x=$x"; + foreach my $startpos (0..$n-1) + { + foreach my $endpos ($startpos..$n-1) + { + #say "startpos: $startpos, endpos: $endpos"; + my $prod = 1; + foreach my $p ($startpos..$endpos) + { + $prod *= $dig[$p]; + } + #say "prod=$prod"; + return 0 if $seen{$prod}++; + } + } + return 1; +} + + |