Re: Challenge: Sorting Sums Of Sorted Series

[Limbic~Region]

All,
My 3 solutions are below. The first two were not created with the memory challenge in mind. In the first, I was trying to show ikegami that if you turned the problem on its side, a merge algorithm would work.

This uses the general purpose merge algorithm iterator I created at Merge Algorithm (Combining Sorted Lists). I discovered several bugs 3 years later but they are fixed in the version below.

#!/usr/bin/perl
use strict;
use warnings;
use List::Util 'first';

sub gen_merger {
    my ($list, $fetch, $compare, $finish) = @_;
    my @item = map $fetch->($_), @$list;
    
    my $done;
    return sub {
        return $finish if $done;        
        my $idx  = first {$item[$_] ne $finish} 0 .. $#item;
        my $next = $item[$idx];
        for ($idx + 1 .. $#item) {
            next if $item[$_] eq $finish;
            my $result = $compare->($next, $item[$_]);
            if ($result == 1) {
                $next = $item[$_];
                $idx = $_;
            }
        }
        $item[$idx] = $fetch->($list->[$idx]);
        $done = 1 if ! first {$_ ne $finish} @item;
        return $next;
    };
}

sub gen_sum_iter {
    my ($num, $list) = @_;
    my $idx = 0;
    return sub {
        return undef if $idx > $#$list;
        return $num + $list->[$idx++];
    };
};

my @list1 = (1 .. 5);
my @list2 = (1 .. 5);
my $finish = 'A val that is guaranteed not to be present in any list';
my @merge_list = map gen_sum_iter($_, \@list2), @list1; # Map over sma
+ller list if possible
my $fetch = sub {my $sum = $_[0]->(); return defined $sum ? $sum : $fi
+nish;};
my $compare  = sub {$_[0] <=> $_[1]};
my $next = gen_merger(\@merge_list, $fetch, $compare, $finish);
while (1) {
    my $item = $next->();
    last if defined $item && $item eq $finish;
    print "$item\n";
}

In this version, I realized that the iterators were not needed. They really didn't reduce complexity and there is obviously the performance penalty of invoking subs repeatedly.

#!/usr/bin/perl
use constant VAL => 0;
use constant IDX => 1;
use constant SUM => 2;
use strict;
use warnings;

my @list1 = (1 .. 5);
my @list2 = (1 .. 5);

my @merge_list = map {[$_, 0, $_ + $list2[0]]} @list1; # Map over smal
+ler list if known

while (@merge_list) {
    my ($min, $index) = ($merge_list[0][SUM], 0);    
    for (1 .. $#merge_list) {
        ($min, $index) = ($merge_list[$_][SUM], $_) if $merge_list[$_]
+[SUM] < $min;
    }
    print "$min\n";
    $merge_list[$index][IDX]++;
    if ($merge_list[$index][IDX] > $#list2) {
        splice(@merge_list, $index, 1);
    }
    else {
        $merge_list[$index][SUM] = $merge_list[$index][VAL] + $list2[$
+merge_list[$index][IDX]];
    }
}

This is where I realized it could be turned into a challenge since only 1 of the 3 tracking values was necessary. Caching the sum improves performance but what are a few cycles amongst friends. I also realized that keeping track of the value in @list1 was also just a caching technique. With it gone, I was left with 2N + M along with about 4 constant scalars.

#!/usr/bin/perl
use strict;
use warnings;

my @list1 = 1 .. 5;
my @list2 = 1 .. 5;

my @merge_list = ((0) x scalar @list1); # use smaller of 2 lists 

while (1) {
    my ($min, $idx);
    for (my $i = 0; $i < @merge_list; ++$i) {
        next if $merge_list[$i] > $#list2;
        my $sum = $list1[$i] + $list2[$merge_list[$i]];
        ($min, $idx) = ($sum, $i) if ! defined $min || $sum < $min;
    }
    last if ! defined $min;
    print "$min\n";
    $merge_list[$idx]++;
}