#!/usr/bin/perl
use strict;
use warnings;
use Benchmark qw(:all :hireswallclock);
    
my @list1 = qw(  1 3 5 7 );
my @list2 = qw(  2 4 6 8 );
#my @list1 = (1 .. 100);
#my @list2 = (1 .. 100);

my $count = 10000;
my $routines = {
                Baseline    => sub { baseline(\@list1, \@list2) },
                Integers    => sub { solution_0(\@list1, \@list2) },
                Queue       => sub { solution_1(\@list1, \@list2) },
                LR_1        => sub { LR_solution_1(\@list1, \@list2) },
                LR_2        => sub { LR_solution_2(\@list1, \@list2) },
                blokhead    => sub { print_sums(\@list1, \@list2) },
               };

my $buffer;
open OUT, '>', \$buffer or die "Can't open STDOUT: $!";

my $results = timethese($count, $routines);

cmpthese($results);

sub baseline {
    # Simple solution
    # O(N*M) memory, O(N*M) time
    my @list1 = @{shift()};
    my @list2 = @{shift()};
    
    my @result = ();
    for my $val1 (@list1) {
        for my $val2 (@list2) {
            push @result, $val1+$val2;
        }
    }
    print OUT join "\n", (sort {$a <=> $b} @result);
}

sub solution_0 {
    # Integer solution
    # O(N+M) memory, O(N*M*len()) time
    my @list1 = @{shift()};
    my @list2 = @{shift()};
    
    my $value = $list1[0]+$list2[0];
    while ($value <= $list1[-1]+$list2[-1]) {
        for my $scalar1 (@list1) {
            for my $scalar2 (@list2) {
                print OUT "$value\n" if $value == $scalar1 + $scalar2;
            }
        }
        $value++;
    }
}

sub solution_1 {
    # queue solution
    # O(2*N+M) memory, O(N^2*M) time
    my ($list_ref1, $list_ref2) = @_;
    my @list1;
    my @list2;
    if (@$list_ref1 <= @$list_ref2) {
       @list1 = @$list_ref1;
       @list2 = @$list_ref2;
    } else {
       @list1 = @$list_ref2;
       @list2 = @$list_ref1;
    }
    
    my @queue = map $_+$list2[0], @list1;
    push @queue, $list1[-1]+$list2[-1];
    shift @list1;
    for my $element1 (@list1) {
        for (@list2) {
            print OUT shift(@queue), "\n";
            my $sum = $_+$element1;
            my $count = 0;
            $count++ until $sum <= $queue[$count];
            splice @queue, $count, 0, $sum;
        }
    }
    pop @queue;
    print OUT join "\n", @queue;
}

sub LR_solution_1 {
    #Limbic~Region's first posted solution
    use constant VAL => 0;
    use constant IDX => 1;
    use constant SUM => 2;
    my ($list_ref1, $list_ref2) = @_;
    my @list1;
    my @list2;
    if (@$list_ref1 <= @$list_ref2) {
       @list1 = @$list_ref1;
       @list2 = @$list_ref2;
    } else {
       @list1 = @$list_ref2;
       @list2 = @$list_ref1;
    }

    my @merge_list = map {[$_, 0, $_ + $list2[0]]} @list1; # Map over smaller 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 OUT "$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]];
        }
    }

}

sub LR_solution_2 {
    #Limbic~Region's second posted solution
    my ($list_ref1, $list_ref2) = @_;
    my @list1;
    my @list2;
    if (@$list_ref1 <= @$list_ref2) {
       @list1 = @$list_ref1;
       @list2 = @$list_ref2;
    } else {
       @list1 = @$list_ref2;
       @list2 = @$list_ref1;
    }
    
    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 OUT "$min\n";
        $merge_list[$idx]++;
    }
}

sub print_sums {
    # blokhead's solution
    my ($listA, $listB) = @_;

    my $min = $listA->[0] + $listB->[0] - 1;

    while ($min < $listA->[-1] + $listB->[-1]) {
        my $nextmin = undef;
        my $multiplicity = 0;

        no warnings; # Throws warnings on uninitialized value comparisons
        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 $nextmin)) {
                    ($nextmin, $multiplicity) = ($sum, 1);
                } elsif ($sum == $nextmin) {
                    $multiplicity++;
                }
            }
        }

        print OUT ( ($nextmin) x $multiplicity);
        $min = $nextmin;
    }
}