This is my response to The Weekly Challenge #391.
Input: @arr1 = (2), @arr2 = (4)
Output: 3.0
Merged array: (2,4)
Median: (2+4)/2 => 3
Input: @arr1 = (1,2,3), @arr2 = (7,8,9,10)
Output: 7.0
Merged array: (1,2,3,7,8,9,10)
Length of merged array is 7, the 4th element is 7.
Input: @arr1 = (), @arr2 = (10,20,30,40)
Output: 25.0
Merged array: (10,20,30,40)
Median: (20+30)/2 => 25
Input: @arr1 = (100), @arr2 = (1,2,3,4,5,6,7)
Output: 4.5
Merged array: (1,2,3,4,5,6,7,100)
Median: (4+5)/2 => 4.5
Input: @arr1 = (1,2,2), @arr2 = (2,2,3)
Output: 2.0
Merged array: (1,2,2,2,2,3)
Median: (2+2)/2 => 2
#! /usr/bin/env raku
unit sub MAIN ($arr1, $arr2, :v(:$verbose));
my @arr1 = $arr1.words>>.Numeric;
my @arr2 = $arr2.words>>.Numeric;
my @sorted = (@arr1, @arr2).flat.sort;
my $index = (@sorted.elems - 1) div 2;
if $verbose
{
say ": Merged: @sorted[]";
say ": Median index: $index";
}
say @sorted.elems % 2
?? @sorted[$index]
!! (@sorted[$index] + @sorted[$index +1]) / 2;[3] The two arrays as two space separated string of values.
[5] Split the first array string into an array, and make sure that the values are numeric. (This will abort the program on non-numeric input, and has the added benefit of making verbose mode look nicer.)
[6] The second one.
[7] Merging two arrays like this gives a new array with two elemens - the original arrays,
so we slap on a .flat to get a single array. Then we sort it.
[8] Get the index of the median (but see [16]), using integer division with
div.
See docs.raku.org/routine/div for more information about div.
[16] Do we have an odd number of elements?
[17] Yes: print the value with the given index.
[18] No: get the average of the value with the index and the next one.
Running it:
$ ./array-median "2" "4"
3
$ ./array-median "1 2 3" "7 8 9 10"
7
$ ./array-median "" "10 20 30 40"
25
$ ./array-median "100" "1 2 3 4 5 6 7"
4.5
$ ./array-median "1 2 2" "2 2 3"
2
Looking good.
With verbose mode:
$ ./array-median -v "2" "4"
: Merged: 2 4
: Median index: 0
3
$ ./array-median -v "1 2 3" "7 8 9 10"
: Merged: 1 2 3 7 8 9 10
: Median index: 3
7
$ ./array-median -v "" "10 20 30 40"
: Merged: 10 20 30 40
: Median index: 1
25
$ ./array-median -v "100" "1 2 3 4 5 6 7"
: Merged: 1 2 3 4 5 6 7 100
: Median index: 3
4.5
$ ./array-median -v "1 2 2" "2 2 3"
: Merged: 1 2 2 2 2 3
: Median index: 2
2
The two input arrays are sorted, according to the challenge text, so the intention could have been for us to merge them manually. So let us do just that:
File: array-median-manual#! /usr/bin/env raku
unit sub MAIN ($arr1, $arr2, :v(:$verbose));
my @arr1 = $arr1.words>>.Numeric;
my @arr2 = $arr2.words>>.Numeric;
my @sorted = merge-sort(@arr1, @arr2);
my $index = (@sorted.elems - 1) div 2;
my $single = @sorted.elems % 2;
if $verbose
{
say ": Merged: @sorted[]";
say ": Median index: $index" ~ ( $single ?? "" !! "+" );
}
say $single
?? @sorted[$index]
!! (@sorted[$index] + @sorted[$index +1]) / 2;
sub merge-sort (@arr1 is copy, @arr2 is copy)
{
return gather
{
while @arr1.elems || @arr2.elems
{
if @arr1.elems && @arr2.elems
{
@arr1[0] < @arr2[0]
?? take @arr1.shift
!! take @arr2.shift;
}
elsif @arr1.elems
{
take @arr1.shift;
}
else # @arr2.elems
{
take @arr2.shift;
}
}
}
}[7] Merge the two arrays, using a custom procedure.
[9] Do we have single median value, i.e. an odd number of elements?
[14] Note the added "+" when we have an even number of elements. The original program is not accurate here.
[23] Use gather to collect the sorted values for the
return statement.
See docs.raku.org/routine/gather/take for more information about gather/take.
[25] As long as at least one of the arrays is not empty.
[27] values in both? Take the lowest one.
[33] Values in the left one only? Take from that one.
[37] You get the idea...
Running it, with verbose mode:
$ ./array-median-manual -v "2" "4"
: Merged: 2 4
: Median index: 0+
3
$ ./array-median-manual -v "1 2 3" "7 8 9 10"
: Merged: 1 2 3 7 8 9 10
: Median index: 3
7
$ ./array-median-manual -v "" "10 20 30 40"
: Merged: 10 20 30 40
: Median index: 1+
25
$ ./array-median-manual -v "100" "1 2 3 4 5 6 7"
: Merged: 1 2 3 4 5 6 7 100
: Median index: 3+
4.5
$ ./array-median-manual -v "1 2 2" "2 2 3"
: Merged: 1 2 2 2 2 3
: Median index: 2+
2
Looking good.
Input: @boxes = ([1, 3], [3, 5], [6, 8], [2, 4])
Output: 4
Sort by width ascending: ([1, 3], [2, 4], [3, 5], [6, 8])
Extract heights: [3, 4, 5, 8]
[1, 3] -> [2, 4] -> [3, 5] -> [6, 8]
Input: @boxes = ([4, 5], [4, 6], [6, 7], [2, 3], [4, 3])
Output: 3
Sort by width ascending: ([2, 3], [4, 6], [4, 5], [4, 3], [6, 7])
Extract heights: (3, 6, 5, 3, 7)
[2, 3] -> [4, 5] -> [6, 7]
Input: @boxes = ([5, 5], [5, 5], [5, 5])
Output: 1
Sort by width ascending: ([5, 5], [5, 5], [5, 5])
Extract heights: (5, 5, 5)
[5, 5]
Input: @boxes = ([2, 100], [3, 200], [4, 300], [5, 50], [5, 400])
Output: 4
Sort by width ascending: ([2, 100], [3, 200], [4, 300], [5, 400], [5, 50])
Extract heights: (100, 200, 300, 400, 50)
[2, 100] -> [3, 200] -> [4, 300] -> [5, 400]
Input: @boxes = ([10, 20], [15, 10], [20, 30], [12, 18], [16, 25])
Output: 3
Sort by width ascending: ([10, 20], [12, 18], [15, 10], [16, 25], [20, 30])
Extract heights: (20, 18, 10, 25, 30)
[15, 10] -> [16, 25] -> [20, 30]
#! /usr/bin/env raku
unit sub MAIN (*@boxes, :v(:$verbose));
my @dims = @boxes>>.words>>.Numeric;
die "At least one box is required" unless @dims.elems;
die "Each box must have exactly two dimensions"
unless all(@dims>>.elems) == 2;
my @sorted = @dims.sort: { (.[0], -.[1]) };
if $verbose
{
say ": Sorted: " ~ @sorted.map({ "[$_[0], $_[1]]" }).join(", ");
say ": Heights: " ~ @sorted>>[1].join(", ")
}
my @tails;
for @sorted -> $box
{
my $lo = @tails.first({ .[*-1][1] >= $box[1] }, :k)
// @tails.elems;
@tails[$lo] = $lo > 0
?? @tails[$lo - 1].Array.append($box) !! [$box];
}
my $chain = @tails[*-1];
say ": Chain: " ~ $chain.map({ "[$_[0], $_[1]]" }).join(" -> ")
if $verbose;
say $chain.elems;[3] Specify the boxes as e.g. "1 3" "2 4".
[5] Convert the box strings into arrays, and ensure that the values are numeric.
[12] Sort the boxes by ascending width, then by descending height if the widths are the same.
[20] All the chains will end up here.
[22] Iterate over the sorted boxes.
[24] We are looking for an existing chain (from the left) where our
current box is a better fit than the last element in that chain. We get the index
with the :k adverb on first. No match means that we can add the box to
the last chain (in [25]), without replacing anything.
See docs.raku.org/routine/first for more information about first.
[27] Do we have an existing chain to add to? If so, get a copy of the chain to the left of it, add the new box, and assign to the current chain. If not, use the current box only.
[31] The longest chain is always at the end. In general, a chain at index m has the length
m+1.
[39] Print the length of the chain.
Overwriting a tails entry can happen, but that means that we found a better choice for the next value in this chain.
Running it:
$ ./arrange-box "1 3" "3 5" "6 8" "2 4"
4
$ ./arrange-box "4 5" "4 6" "6 7" "2 3" "4 3"
3
$ ./arrange-box "5 5" "5 5" "5 5"
1
$ ./arrange-box "2 100" "3 200" "4 300" "5 50" "5 400"
4
$ ./arrange-box "10 20" "15 10" "20 30" "12 18" "16 25"
3
Looking good.
With verbose mode:
$ ./arrange-box -v "1 3" "3 5" "6 8" "2 4"
: Sorted: [1, 3], [2, 4], [3, 5], [6, 8]
: Heights: 3, 4, 5, 8
: Chain: [1, 3] -> [2, 4] -> [3, 5] -> [6, 8]
4
$ ./arrange-box -v "4 5" "4 6" "6 7" "2 3" "4 3"
: Sorted: [2, 3], [4, 6], [4, 5], [4, 3], [6, 7]
: Heights: 3, 6, 5, 3, 7
: Chain: [2, 3] -> [4, 5] -> [6, 7]
3
$ ./arrange-box -v "5 5" "5 5" "5 5"
: Sorted: [5, 5], [5, 5], [5, 5]
: Heights: 5, 5, 5
: Chain: [5, 5]
1
$ ./arrange-box -v "2 100" "3 200" "4 300" "5 50" "5 400"
: Sorted: [2, 100], [3, 200], [4, 300], [5, 400], [5, 50]
: Heights: 100, 200, 300, 400, 50
: Chain: [2, 100] -> [3, 200] -> [4, 300] -> [5, 400]
4
$ ./arrange-box -v "10 20" "15 10" "20 30" "12 18" "16 25"
: Sorted: [10, 20], [12, 18], [15, 10], [16, 25], [20, 30]
: Heights: 20, 18, 10, 25, 30
: Chain: [15, 10] -> [16, 25] -> [20, 30]
3
And that's it.