in reply to Challenge: Sorting Sums Of Sorted Series
You can always save space by never storing anything  just recompute a sum every time you need it.. Here's a solution that uses constant space:
sub print_sums {
my ($listA, $listB) = @_;
my $min = $listA>[0] + $listB>[0]  1;
while ($min < $listA>[1] + $listB>[1]) {
my $nextmin = undef;
my $multiplicity = 0;
for my $i (0 .. $#$listA) {
for my $j (0 .. $#$listB) {
my $sum = $listA>[$i] + $listB>[$j];
if ($sum > $min and ($sum < $nextmin or not defined $nextm
+in)) {
($nextmin, $multiplicity) = ($sum, 1);
} elsif ($sum == $nextmin) {
$multiplicity++;
}
}
}
print( ($nextmin) x $multiplicity);
$min = $nextmin;
}
}
At each iteration, it traverses both lists to find the next smallest possible sum, and how many times it occurs. It only needs to keep track of $min, $nextmin, $multiplicity, $i, $j.
Of course the tradeoff is the running time, which is O((NM)^{2}).
Perhaps the metric should be to minimize the product of time space complexities? For comparison, naively computing all sums and sorting uses NM space and NM log(NM) time, so it's slightly worse than mine under the combined metric.
Update: extra parens around print statement..
Re^2: Challenge: Sorting Sums Of Sorted Series by Limbic~Region (Chancellor) on Feb 02, 2010 at 23:01 UTC 
blokhead,
Your code needs some TLC and your for (0 .. $#list) should probably be for (;;) loops. I had this idea too but felt it wasn't in the spirit of what ikegami intended (though it meets my criteria just fine).
 Find the lowest sum paying attention to how many times it appears, then print
 Find the lowest sum that is greater than the previous pass paying attention to how many times it appears, then print
 Repeat until there are no new values found
The best solution I have (memory/time) is 4N + M but the most memory efficient while still having a reasonable run time is 2N + M.
 [reply] 

 [reply] [d/l] 

ikegami,
Notice I didn't say blokhead was wrong. I said should because it would make it obvious. Not everyone has a grasp of how things are implemented in all versions of perl. In fact, this is what perlop has to say on the matter.
In list context, it returns a list of values counting (up by ones) from the left value to the right value.....In the current implementation, no temporary array is created when the range operator is used as the expression in foreach loops, but older versions of Perl might burn a lot of memory when you write something like this:
Again, someone that doesn't follow perl closely might think  what version would blokhead's solution be breaking the rules or will this continue to be correct in the next version. Making it obvious eliminates any casual observer confusion.
 [reply] 

