diff options
| -rw-r--r-- | challenge-058/duncan-c-white/README | 93 | ||||
| -rwxr-xr-x | challenge-058/duncan-c-white/perl/ch-1.pl | 156 | ||||
| -rwxr-xr-x | challenge-058/duncan-c-white/perl/ch-2.pl | 136 |
3 files changed, 344 insertions, 41 deletions
diff --git a/challenge-058/duncan-c-white/README b/challenge-058/duncan-c-white/README index 19927bb4b1..ec66b1a712 100644 --- a/challenge-058/duncan-c-white/README +++ b/challenge-058/duncan-c-white/README @@ -1,58 +1,69 @@ -Task 1: "Invert Tree +Task 1: "Compare Version -You are given a full binary tree of any height, similar to the one below: +Compare two given version number strings v1 and v2 such that: - 1 - / \ - 2 3 - / \ / \ - 4 5 6 7 + If v1 > v2 return 1 + If v1 < v2 return -1 + Otherwise, return 0 -Write a script to invert the tree, by mirroring the children of every node, from left to right. The expected output from the tree above would be: +The version numbers are non-empty strings containing only digits, the dot +('.') and underscore ('_') characters. ('_' denotes an alpha/development +version, and has a lower precedence than a dot, '.'). Here are some examples: - 1 - / \ - 3 2 - / \ / \ - 7 6 5 4 + v1 v2 Result +------ ------ ------ + 0.1 < 1.1 -1 + 2.0 > 1.2 1 + 1.2 < 1.2_5 -1 +1.2.1 > 1.2_1 1 +1.2.1 = 1.2.1 0 -The input can be any sensible machine-readable binary tree format of your choosing, and the output should be the same format. - -BONUS - -In addition to the above, you may wish to pretty-print your binary tree in a human readable text-based format similar to the above." - - -My notes: Let's reuse the same binary tree representation and input format as last time. That's the bulk of the problem. +Version numbers may also contain leading zeros. You may handle these +how you wish, as long as it's consistent. +" -The "flip-left-right" algorithm looks very simple. Not sure why "full" -is stressed, AFAIK any obvious algorithm for this would deal with any -binary tree. In Haskell, it's as simple as: +My notes: I hate it already:-) but it doesn't sound too hard. -fliplr e = e -fliplr leaf(n) = leaf(n) -fliplr node(n,l,r) = node(n, fliplr(r), fliplr(l)) -The bonus is MUCH the most difficult part, as best layout may be slightly -subjective, and it wasn't immediately clear exactly what spacing is needed -at each level. An obvious alternative would be to use GraphViz to -draw the directed graph (our tree), I did that first and it worked fine, -but in this version I attempt the fullblown ASCII art layout.. new: -decided to generalise it to deal properly with non-full binary trees too, -ie. missing elements. +Task 2: "Ordered Lineup +Write a script to arrange people in a lineup according to how many +taller people are in front of each person in line. You are given two +arrays. @H is a list of unique heights, in any order. @T is a list of +how many taller people are to be put in front of the corresponding +person in @H. The output is the final ordering of people's heights, +or an error if there is no solution. -Task 2: "Shortest Unique Prefix +Here is a small example: -Write a script to find the shortest unique prefix for each each word in the given list. The prefixes will not necessarily be of the same length. + @H = (2, 6, 4, 5, 1, 3) # Heights + @T = (1, 0, 2, 0, 1, 2) # Number of taller people wanted in front -Sample Input +The ordering of both arrays lines up, so H[i] and T[i] refer to the same +person. For example, there are 2 taller people in front of the person +with height 4, and there is 1 person in front of the person with height 1. - [ "alphabet", "book", "carpet", "cadmium", "cadeau", "alpine" ] +here is one possible solution that satisfies @H and @T: -Expected Output +(5, 1, 2, 6, 3, 4) - [ "alph", "b", "car", "cadm", "cade", "alpi" ] +Note that the leftmost element is the 'front' of the array.) " -My notes: sounds entirely straightforward. +My notes: an unfamiliar problem, sounds quite interesting. No algorithm +immediately comes to mind.. Generate-and-test was my first thought - i.e. +have a function to test "is-this-combination-a-valid-answer" and invoke it +for every possible answer. But the question also suggested that our +algorithm should be able to work at a scale of 1000 people, and the number +of combinations of 1000 people is insane (1000!). so scratch that. + +After trying a few examples manually, I realised that the first person in +the queue must be someone who wants 0 people taller than them in front of +them, and quickly generalised this into what I think it a valid and efficient +algorithm. See function "solve". + +However, it doesn't (yet) scale to the 64-person solution, much less the +1000-person one. I've tried some Perl profiling on an intermediate scale +problem, and managed to make it run 4 times faster, but it still can't +scale up to 64-person scale, would need a fundamentally faster algorithm, +which I just can't see. diff --git a/challenge-058/duncan-c-white/perl/ch-1.pl b/challenge-058/duncan-c-white/perl/ch-1.pl new file mode 100755 index 0000000000..596bb09bd0 --- /dev/null +++ b/challenge-058/duncan-c-white/perl/ch-1.pl @@ -0,0 +1,156 @@ +#!/usr/bin/perl +# +# Task 1: "Compare Version +# +# Compare two given version number strings v1 and v2 such that: +# +# If v1 > v2 return 1 +# If v1 < v2 return -1 +# Otherwise, return 0 +# +# The version numbers are non-empty strings containing only digits, the dot +# ('.') and underscore ('_') characters. ('_' denotes an alpha/development +# version, and has a lower precedence than a dot, '.'). Here are some examples: +# +# v1 v2 Result +# ------ ------ ------ +# 0.1 < 1.1 -1 +# 2.0 > 1.2 1 +# 1.2 < 1.2_5 -1 +# 1.2.1 > 1.2_1 1 +# 1.2.1 = 1.2.1 0 +# +# Version numbers may also contain leading zeros. You may handle these +# how you wish, as long as it's consistent. +# " +# +# My notes: I hate version numbers already:-) but it doesn't sound too hard. +# I am assuming there can be any number of '.'s, but one zero or one '_' +# inside each '.'-separated component. eg 1.2_2_2 isn't valid. +# + +use strict; +use warnings; +use feature 'say'; +use Function::Parameters; +use List::Util qw(max); +use Data::Dumper; + + + +die "Usage: compare-versions v1 v2\n" unless @ARGV==2; +my( $v1, $v2 ) = @ARGV; + + +# +# my $result = validate_version( $v ); +# Validate a version string $v according to +# the rules described at the top. Return 1 if $v is valid, +# -1 otherwise. +# +fun validate_version( $v ) +{ + my $origv = $v; + + $v =~ s/^0+//; # remove any leading zeroes + + while( $v ) + { + $v =~ s/^\d+// || return 0; + return 1 unless $v; + + # deal with optional underscore + if( $v =~ s/^_// ) + { + $v =~ s/^\d+// || return 0; + } + + return 1 unless $v; + + # deal with compulsory '.' + return 0 unless $v =~ s/^\.//; + } + + return 1; +} + + +# +# my $result = compare_versions( $v1, $v2 ); +# Compare two VALID version strings $v1 and $v2, according to +# the rules described at the top. Return -1 if $v1 < $v2, +# 1 if $v1 > $v2 and 0 if $v1 == $v2. Don't bother to check validity +# as you go, told both versions ARE valid. +# +fun compare_versions( $v1, $v2 ) +{ + my $origv1 = $v1; + my $origv2 = $v2; + + $v1 =~ s/^0+//; # remove any leading zeroes + $v2 =~ s/^0+//; + + while( 1 ) + { + # both must have leading digit sequence + $v1 =~ s/^(\d+)//; my $c = $1; + $v2 =~ s/^(\d+)//; my $d = $1; + + return -1 if $c < $d; # leading numeric part of v1 smaller + return 1 if $c > $d; # leading numeric part of v1 larger + + # same leading number:-) + + # deal with optional underscores + if( $v1 =~ /^_/ && $v2 =~ /^_/ ) + { + # both have _.. check and compare + $v1 =~ s/^_//; + $v2 =~ s/^_//; + + # both must have leading digit sequence: compare them + + $v1 =~ s/^(\d+)//; my $c = $1; + $v2 =~ s/^(\d+)//; my $d = $1; + + return -1 if $c < $d; # _N part of v1 smaller + return 1 if $c > $d; # _N part of v1 larger + } elsif( $v1 =~ /^_/ ) + { + return 1; + } elsif( $v2 =~ /^_/ ) + { + return -1; + } + + # might be end, or could have '.' + return 0 if $v2 eq '' && $v1 eq ''; + + # deal with optional '.' + if( $v1 =~ /^\./ && $v2 =~ /^\./ ) + { + # both have '.', check and compare + $v1 =~ s/^\.//; + $v2 =~ s/^\.//; + + # continue at top of while loop + + } elsif( $v1 =~ /^\./ ) + { + return 1; # v2 ended + } elsif( $v2 =~ /^\./ ) + { + return -1; # v1 ended + } + } + + # never reached +} + +die "v1 $v1 is invalid\n" unless validate_version($v1); +die "v2 $v2 is invalid\n" unless validate_version($v2); + +my $result = compare_versions( $v1, $v2 ); +print "$v1 is less than $v2\n" if $result == -1; +print "$v1 is greater than $v2\n" if $result == 1; +print "$v1 is same as $v2\n" if $result == 0; diff --git a/challenge-058/duncan-c-white/perl/ch-2.pl b/challenge-058/duncan-c-white/perl/ch-2.pl new file mode 100755 index 0000000000..2d3d77b742 --- /dev/null +++ b/challenge-058/duncan-c-white/perl/ch-2.pl @@ -0,0 +1,136 @@ +#!/usr/bin/perl +# +# Task 2: "Ordered Lineup +# +# Write a script to arrange people in a lineup according to how many +# taller people are in front of each person in line. You are given two +# arrays. @H is a list of unique heights, in any order. @T is a list of +# how many taller people are to be put in front of the corresponding +# person in @H. The output is the final ordering of people's heights, +# or an error if there is no solution. +# +# Here is a small example: +# +# @H = (2, 6, 4, 5, 1, 3) # Heights +# @T = (1, 0, 2, 0, 1, 2) # Number of taller people wanted in front +# +# The ordering of both arrays lines up, so H[i] and T[i] refer to the same +# person. For example, there are 2 taller people in front of the person +# with height 4, and there is 1 person in front of the person with height 1. +# +# here is one possible solution that satisfies @H and @T: +# +# (5, 1, 2, 6, 3, 4) +# +# Note that the leftmost element is the 'front' of the array.) +# " +# +# My notes: an unfamiliar problem, sounds quite interesting. No algorithm +# immediately comes to mind.. Generate-and-test was my first thought - i.e. +# have a function to test "is-this-combination-a-valid-answer" and invoke it +# for every possible answer. But the question also suggested that our +# algorithm should be able to work at a scale of 1000 people, and the number +# of combinations of 1000 people is insane (1000!). so scratch that. +# +# After trying a few examples manually, I realised that the first person in +# the queue must be someone who wants 0 people taller than them in front of +# them, and quickly generalised this into what I think it a valid and efficient +# algorithm. See function "solve". +# +# Run the program on the example as: +# ./ch-2.pl 2,6,4,5,1,3 1,0,2,0,1,2 +# bigger examples can be got (in a simple way) by adding ",MAXH+1" to the +# heights, and ",0" to the taller. eg +# ./ch-2.pl 2,6,4,5,1,3,7 1,0,2,0,1,2,0 +# ./ch-2.pl 2,6,4,5,1,3,7,8 1,0,2,0,1,2,0,0 +# ... +# ./ch-2.pl 2,6,4,5,1,3,7,8,9,10,11,12,13,14,15,16,17,18 1,0,2,0,1,2,0,0,0,0,0,0,0,0,0,0,0,0 +# + +use strict; +use warnings; +use feature 'say'; +use Function::Parameters; +#use Data::Dumper; + + +die "Usage: ordered-lineup heights nfronttaller\n" unless @ARGV==2; +my( $heightstr, $nfronttallerstr ) = @ARGV; + +my @h = split(/,/,$heightstr); +my @t = split(/,/,$nfronttallerstr); + +my $npeople = @h; +my $nt = @t; + +die "ordered-lineup: $npeople heights, $nt nfronttallers\n" unless + $npeople == $nt; + +my $nfound = 0; + + +# +# my $ng = ngreater( $x, @v ); +# Determine the number of values in @v that are greater than $x. +# Return that number. +# +fun ngreater( $x, @v ) +{ + my $ng = grep { $_ > $x } @v; + #say "there are $ng elements in ", join(',',@v), " bigger than $x"; + return $ng; +} + + +# +# solve( $hl, $pl ); +# Solve the ordered-lineup problem, given that some +# progress has already been made: we know the front scalar(@$hl) +# people of the lineup: they have people numbers @$pl and +# heights @$hl. Find all possible one-step extensions of this +# partial solution that are consistent with the rules, and +# recurse until you find all solutions. Set global $nfound to +# the number of solutions found; uses globals @h and @t for +# the data. +# +fun solve( $hl, $pl ) +{ + my %used = map { $_ => 1 } @$pl; + + #say "solving hl ", join(',',@$hl); # , " and pl ", join(',',@$pl); + + my @possp = + grep { ! $used{$_} && ngreater( $h[$_], @$hl ) == $t[$_] } + 0..$npeople-1; + unless( @possp ) + { + #say " no possible next people"; + return; + } + #say " possible next heights are ", join(',',map { $h[$_] } @possp); + + foreach my $p (@possp) + { + # found unused person p, height h[p] > t[p] + # elements in $hl. Add it to copies of hl and pl + #say "trying unused person $p, height $h[$p] as next"; + + my @p2 = @$pl; + push @p2, $p; + my @h2 = @$hl; + push @h2, $h[$p]; + if( @p2 == $npeople ) + { + say "found solution ", join(',',@h2); + $nfound++; + } else + { + solve( \@h2, \@p2 ); + } + } +} + + +$nfound = 0; + +solve( [], [] ); |