diff options
| -rw-r--r-- | challenge-124/duncan-c-white/README | 74 | ||||
| -rwxr-xr-x | challenge-124/duncan-c-white/perl/ch-1.pl | 49 | ||||
| -rwxr-xr-x | challenge-124/duncan-c-white/perl/ch-2.pl | 89 |
3 files changed, 176 insertions, 36 deletions
diff --git a/challenge-124/duncan-c-white/README b/challenge-124/duncan-c-white/README index b7d8d96453..ab825e9e01 100644 --- a/challenge-124/duncan-c-white/README +++ b/challenge-124/duncan-c-white/README @@ -1,47 +1,49 @@ -Task 1: "Ugly Numbers - -You are given an integer $n >= 1. - -Write a script to find the $nth element of Ugly Numbers. - -Ugly numbers are those number whose prime factors are 2, 3 or 5. -For example, the first 10 Ugly Numbers are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12. - -Example - - Input: $n = 7 - Output: 8 - - Input: $n = 10 - Output: 12 +Task 1: "Write a script to print the Venus Symbol, international gender +symbol for women. Please feel free to use any character. + + ^^^^^ + ^ ^ + ^ ^ + ^ ^ + ^ ^ + ^ ^ + ^ ^ + ^ ^ + ^ ^ + ^ ^ + ^^^^^ + ^ + ^ + ^ + ^^^^^ + ^ + ^ " -My notes: sounds quite simple. I thought of digging out primes and -factors code from previous PWCs, but the only primes we care about are -2, 3 and 5. +My notes: sounds like a print statement to reproduce the given input. -Task 2: "Square Points +Task 2: "Tug of War -You are given coordinates of four points -i.e. (x1, y1), (x2, y2), (x3, y3) and (x4, y4). +You are given a set of $n integers (n1, n2, n3, ...). -Write a script to find out if the given four points form a square. +Write a script to divide the set in two subsets of n/2 sizes each so +that the difference of the sum of two subsets is the least. If $n is +even then each subset must be of size $n/2 each. In case $n is odd then +one subset must be ($n-1)/2 and other must be ($n+1)/2. Example - Input: x1 = 10, y1 = 20 - x2 = 20, y2 = 20 - x3 = 20, y3 = 10 - x4 = 10, y4 = 10 - Output: 1 as the given coordinates form a square. - - Input: x1 = 12, y1 = 24 - x2 = 16, y2 = 10 - x3 = 20, y3 = 12 - x4 = 18, y4 = 16 - Output: 0 as the given coordinates doesn't form a square. + Input: Set = (10, 20, 30, 40, 50, 60, 70, 80, 90, 100) + Output: Subset 1 = (30, 40, 60, 70, 80) + Subset 2 = (10, 20, 50, 90, 100) + + Input: Set = (10, -15, 20, 30, -25, 0, 5, 40, -5) + Subset 1 = (30, 0, 5, -5) + Subset 2 = (10, -15, 20, -25, 40) " -My notes: sounds surprisingly easy for a task 2. I guess the points -can be in any order. +My notes: sounds like a "generate and test" problem. Easy to do inefficiently, + challenging to try to make efficient. + Let's start by counting from 0 to 2^n-1 and using the bits + to select which subset to put each value into. diff --git a/challenge-124/duncan-c-white/perl/ch-1.pl b/challenge-124/duncan-c-white/perl/ch-1.pl new file mode 100755 index 0000000000..bda30a247a --- /dev/null +++ b/challenge-124/duncan-c-white/perl/ch-1.pl @@ -0,0 +1,49 @@ +#!/usr/bin/perl +# +# Task 1: "Write a script to print the Venus Symbol, international gender +# symbol for women. Please feel free to use any character. +# +# ^^^^^ +# ^ ^ +# ^ ^ +# ^ ^ +# ^ ^ +# ^ ^ +# ^ ^ +# ^ ^ +# ^ ^ +# ^ ^ +# ^^^^^ +# ^ +# ^ +# ^ +# ^^^^^ +# ^ +# ^ +# " +# +# My notes: sounds like a print statement to reproduce the given input. +# + +use strict; +use warnings; +#use Data::Dumper; + +print " ^^^^^ + ^ ^ + ^ ^ + ^ ^ + ^ ^ + ^ ^ + ^ ^ + ^ ^ + ^ ^ + ^ ^ + ^^^^^ + ^ + ^ + ^ + ^^^^^ + ^ + ^ +"; diff --git a/challenge-124/duncan-c-white/perl/ch-2.pl b/challenge-124/duncan-c-white/perl/ch-2.pl new file mode 100755 index 0000000000..936ff3cf41 --- /dev/null +++ b/challenge-124/duncan-c-white/perl/ch-2.pl @@ -0,0 +1,89 @@ +#!/usr/bin/perl +# +# Task 2: "Tug of War +# +# You are given a set of $n integers (n1, n2, n3, ...). +# +# Write a script to divide the set in two subsets of n/2 sizes each so +# that the difference of the sum of two subsets is the least. If $n is +# even then each subset must be of size $n/2 each. In case $n is odd then +# one subset must be ($n-1)/2 and other must be ($n+1)/2. +# +# Example +# +# Input: Set = (10, 20, 30, 40, 50, 60, 70, 80, 90, 100) +# Output: Subset 1 = (30, 40, 60, 70, 80) +# Subset 2 = (10, 20, 50, 90, 100) +# +# Input: Set = (10, -15, 20, 30, -25, 0, 5, 40, -5) +# Subset 1 = (30, 0, 5, -5) +# Subset 2 = (10, -15, 20, -25, 40) +# " +# +# My notes: sounds like a "generate and test" problem. Easy to do +# inefficiently, challenging to try to make efficient. +# Let's start by counting from 0 to 2^n-1 and using the bits +# to select which subset to put each value into. +# + +use strict; +use warnings; +use feature 'say'; +use Function::Parameters; +use List::Util qw(sum); +use Data::Dumper; + +die "Usage: tug-of-war N1 N2...\n" unless @ARGV>1; +my @n = @ARGV; + +my $two2n = 2**scalar(@n); + + +# +# partition( $partno, $ss1, $ss2, @n ); +# Partition @n into @$ss1 and @$ss2 based on the partition no $partno. +# +fun partition( $partno, $ss1, $ss2, @n ) +{ + @$ss1 = @$ss2 = (); + for( my $i=0; $i<@n; $i++ ) + { + my $bit = ($partno % 2); + $partno /= 2; + my $aref = $bit ? $ss1 : $ss2; + push @$aref, $n[$i]; + } +} + + +my $debug = 0; + +my $minsumdiff = sum(@n); +my @bests1 = @n; +my @bests2 = (); + +my $halfn = int(@n / 2); + +for( my $i=0; $i<$two2n; $i++ ) +{ + my( @s1, @s2 ); + partition( $i, \@s1, \@s2, @n ); + next unless @s1 == $halfn; + + my $sum1 = sum(@s1); + my $sum2 = sum(@s2); + my $diff = abs($sum1-$sum2); + + say "partition $i has s1=". join(',',@s1). ", s2==". join(',',@s2). ", diff=$diff" if $debug; + + if( $diff < $minsumdiff ) + { + $minsumdiff = $diff; + @bests1 = @s1; + @bests2 = @s2; + } +} + +say "Subset 1 = ". join(',',@bests1); +say "Subset 2 = ". join(',',@bests2); +say "Difference = $minsumdiff"; |