diff options
| -rw-r--r-- | challenge-217/duncan-c-white/README | 90 | ||||
| -rwxr-xr-x | challenge-217/duncan-c-white/perl/ch-1.pl | 72 | ||||
| -rwxr-xr-x | challenge-217/duncan-c-white/perl/ch-2.pl | 146 |
3 files changed, 260 insertions, 48 deletions
diff --git a/challenge-217/duncan-c-white/README b/challenge-217/duncan-c-white/README index a64621c29b..8cb1e349ee 100644 --- a/challenge-217/duncan-c-white/README +++ b/challenge-217/duncan-c-white/README @@ -1,82 +1,76 @@ -Task 1: Registration Number +Task 1: Sorted Matrix -You are given a list of words and a random registration number. -Write a script to find all the words in the given list that has every -letter in the given registration number. +You are given a n x n matrix where n >= 2. +Write a script to find 3rd smallest element in the sorted matrix. Example 1 - Input: @words = ('abc', 'abcd', 'bcd'), $reg = 'AB1 2CD' - Output: ('abcd') + Input: @matrix = [3, 1, 2], [5, 2, 4], [0, 1, 3] + Output: 1 - The only word that matches every alphabets in the given registration number is 'abcd'. + The sorted list of the given matrix: 0, 1, 1, 2, 2, 3, 3, 4, 5. + The 3rd smallest of the sorted list is 1. Example 2 - Input: @words = ('job', 'james', 'bjorg'), $reg = '007 JB' - Output: ('job', 'bjorg') + Input: @matrix = ([2, 1], [4, 5]) + Output: 4 + + The sorted list of the given matrix: 1, 2, 4, 5. + The 3rd smallest of the sorted list is 4. Example 3 - Input: @words = ('crack', 'road', 'rac'), $reg = 'C7 RA2' - Output: ('crack', 'rac') + Input: @matrix = ([1, 0, 3], [0, 0, 0], [1, 2, 1]) + Output: 0 -MY NOTES: I think the meaning is: form a set of all letters from the -registration. Select all words that contain every member of the set. -That's easy. + The sorted list of the given matrix: 0, 0, 0, 0, 1, 1, 1, 2, 3. + The 3rd smallest of the sorted list is 0. + +MY NOTES: So basically flatten the matrix onto an array, sort it, +pick out element 2.. easy. BTW, why does the matrix have to be square, +any matrix could be flattened and sorted. GUEST LANGUAGE: As a bonus, I've had a go at translating ch-1.pl into C, look in the C/ directory for that. -Task 2: Word Stickers +Task 2: Max Number -You are given a list of word stickers and a target word. -Write a script to find out how many word stickers is needed to make up -the given target word. +You are given a list of positive integers. +Write a script to concatenate the integers to form the highest possible value. Example 1: - Input: @stickers = ('perl','raku','python'), $word = 'peon' - Output: 2 - - We just need 2 stickers i.e. 'perl' and 'python'. - 'pe' from 'perl' and - 'on' from 'python' to get the target word. + Input: @list = (1, 23) + Output: 231 Example 2: - Input: @stickers = ('love','hate','angry'), $word = 'goat' - Output: 3 - - We need 3 stickers i.e. 'angry', 'love' and 'hate'. - 'g' from 'angry' - 'o' from 'love' and - 'at' from 'hate' to get the target word. + Input: @list = (10, 3, 2) + Output: 3210 Example 3: - Input: @stickers = ('come','nation','delta'), $word = 'accommodation' - Output: 4 - - We just need 2 stickers of 'come' and one each of 'nation' & 'delta'. - 'a' from 'delta' - 'ccommo' from 2 stickers 'come' - 'd' from the same sticker 'delta' and - 'ation' from 'nation' to get the target word. + Input: @list = (31, 2, 4, 10) + Output: 431210 Example 4: - Input: @stickers = ('come','country','delta'), $word = 'accommodation' - Output: 0 + Input: @list = (5, 11, 4, 1, 2) + Output: 542111 -as there's no "i" in the inputs. +Example 5: + Input: @list = (1, 10) + Output: 110 -MY NOTES: ok, so the only tricky part is that each sticker may be used any -number of times (if any of it's letters remain in the word). It will be -worth checking that every letter in the word is present in one or more stickers -before starting the main search process. +MY NOTES: First thought: try all combinations. Second thought: hang on, +don't we always pick the number with the biggest initial digit, and if +there's a tie, pick from the numbers with the biggest initial digit the +one with the biggest prefix? For example, if we vary example 4 to be: +Input: @list = (5, 12, 4, 1, 2), the output would be 542121, ie. 5-4-2-12-1. +Third thought: do I just mean "sort the numbers alphabetically"? -GUEST LANGUAGE: I will have a go at translating ch-2.pl into C tomorrow; -look in the C/ directory when that's done. +GUEST LANGUAGE: As a bonus, I had a go at translating ch-2.pl into C, +look in the C/ directory for that. diff --git a/challenge-217/duncan-c-white/perl/ch-1.pl b/challenge-217/duncan-c-white/perl/ch-1.pl new file mode 100755 index 0000000000..c0399bca26 --- /dev/null +++ b/challenge-217/duncan-c-white/perl/ch-1.pl @@ -0,0 +1,72 @@ +#!/usr/bin/perl +# +# Task 1: Sorted Matrix +# +# You are given a n x n matrix where n >= 2. +# Write a script to find 3rd smallest element in the sorted matrix. +# +# Example 1 +# +# Input: @matrix = [3, 1, 2], [5, 2, 4], [0, 1, 3] +# Output: 1 +# +# The sorted list of the given matrix: 0, 1, 1, 2, 2, 3, 3, 4, 5. +# The 3rd smallest of the sorted list is 1. +# +# Example 2 +# +# Input: @matrix = ([2, 1], [4, 5]) +# Output: 4 +# +# The sorted list of the given matrix: 1, 2, 4, 5. +# The 3rd smallest of the sorted list is 4. +# +# Example 3 +# +# Input: @matrix = ([1, 0, 3], [0, 0, 0], [1, 2, 1]) +# Output: 0 +# +# The sorted list of the given matrix: 0, 0, 0, 0, 1, 1, 1, 2, 3. +# The 3rd smallest of the sorted list is 0. +# +# MY NOTES: So basically flatten the matrix onto an array, sort it, +# pick out element 2.. easy. BTW, why does the matrix have to be square, +# any matrix could be flattened and sorted. +# +# GUEST LANGUAGE: As a bonus, I also had a go at translating ch-1.pl into C +# (look in the C directory for that). +# + +use strict; +use warnings; +use feature 'say'; +use Getopt::Long; +use Data::Dumper; +use List::Util qw(any); + +my $debug=0; +die "Usage: third-from-sorted-matrix [--debug] list-of-rows-in-csv\n" + unless GetOptions( "debug"=>\$debug ) && @ARGV>0; + +my @m = map { [ split( /,/, $_ ) ] } @ARGV; + +my $cols = @{$m[0]}; +my $rows = @m; + +say "m: ", Dumper(\@m) if $debug; + +die "sorted-matrix: all rows must be $cols columns\n" if any { @$_ != $cols } @m; +die "sorted-matrix: need at least 3 elements\n" if $rows * $cols < 3; + +# flatten +my @arr; +foreach my $row (@m) +{ + push @arr, @$row; +} + +# sort +@arr = sort @arr; + +# pick third +say $arr[2]; diff --git a/challenge-217/duncan-c-white/perl/ch-2.pl b/challenge-217/duncan-c-white/perl/ch-2.pl new file mode 100755 index 0000000000..fa53d87164 --- /dev/null +++ b/challenge-217/duncan-c-white/perl/ch-2.pl @@ -0,0 +1,146 @@ +#!/usr/bin/perl +# +# Task 2: Max Number +# +# You are given a list of positive integers. +# Write a script to concatenate the integers to form the highest possible value. +# +# Example 1: +# +# Input: @list = (1, 23) +# Output: 231 +# +# Example 2: +# +# Input: @list = (10, 3, 2) +# Output: 3210 +# +# Example 3: +# +# Input: @list = (31, 2, 4, 10) +# Output: 431210 +# +# Example 4: +# +# Input: @list = (5, 11, 4, 1, 2) +# Output: 542111 +# +# Example 5: +# +# Input: @list = (1, 10) +# Output: 110 +# +# MY NOTES: First thought: try all combinations. Second thought: hang on, +# don't we always pick the number with the biggest initial digit, and if +# there's a tie, pick (from the numbers with the biggest initial digit) the +# one with the biggest prefix? For example, if we vary example 4 to be: +# Input: @list = (5, 12, 4, 1, 2), the output would be 542121, ie. 5-4-2-12-1. +# Third thought: do I just mean "sort the numbers alphabetically"? +# Fourth thought: damn, not quite. "1-10" beats "10-1". Blast. Can we +# specify a variant comparator that compares strings favouring shorter ones? +# Fifth thought: forget sorting. Back to second thought:-) +# +# GUEST LANGUAGE: As a bonus, I had a go at translating ch-2.pl into C, +# look in the C/ directory for that. +# + +use strict; +use warnings; +use feature 'say'; +use Getopt::Long; +use Data::Dumper; +use List::Util qw(max); +use Function::Parameters; + +my $debug=0; +die "Usage: max-concat-number [--debug] intlist\n" + unless GetOptions( "debug"=>\$debug ) && @ARGV > 0; + +my @list = split( /,/, join(',',@ARGV) ); + +say "debug: list: ", join(',',@list) if $debug; + +#say join('', reverse sort { $a cmp $b } @list); + + +# +# my @l = delete_first( $v, @list ); +# Delete the first occurrence of $v from @list, +# returning what's left. +# +fun delete_first( $v, @list ) +{ + my $delete = 1; + @list = grep { $_ != $v || ($delete-- <= 0) } @list; + return @list; +} + + +# +# my $big = complex( $listref, @x ); +# Given @$listref, a list of numbers, and @x, a list of all the values +# in @$listref that start with the biggest first digit, try playing +# each of @x first, removing it from @$listref and finding the biggest +# of what's left, then finding and returning the maximum of all those +# possibilities. +# +fun complex( $listref, @x ) +{ + # try each of these @x's plus all the rest, picking the biggest + my $max = -1; + foreach my $v (@x) + { + my $result = $v; + my @newl = delete_first( $v, @$listref ); + say "debug: trying result $v, newl=". join(',',@newl) + if $debug; + $result .= find_biggest( @newl ); + say "debug: after trying $v + finding biggest, result=$result" + if $debug; + if( $result > $max ) + { + $max = $result; + say "debug: after trying $v, max=$max" if $debug; + } + } + return $max; + +} + + +# +# my $big = find_biggest( @list ); +# Given a list of numbers, try all concatenations +# and find and return the biggest. +# +fun find_biggest( @list ) +{ + my $result = ""; + + while( @list ) + { + # find max first digit + my $maxdig = max( map { /^(.)/ && $1 } @list ); + my @x = grep { /^$maxdig/ } @list; + say "debug: result=$result, list=". join(',',@list). ", maxdig=$maxdig, x=". join(',',@x) + if $debug; + + if( @x == 1 ) + { + $result .= $x[0]; + @list = delete_first( $x[0], @list ); + say "debug: 1 x: result=$result, new list=". join(',',@list). " after deleting $x[0]" + if $debug; + } else + { + say "debug: >1 x" if $debug; + $result .= complex( \@list, @x ); + return $result; + } + } + return $result; +} + + +my $big = find_biggest( @list ); +say $big; |