diff options
| -rw-r--r-- | challenge-076/walt-mankowski/perl/ch-1.pl | 62 |
1 files changed, 62 insertions, 0 deletions
diff --git a/challenge-076/walt-mankowski/perl/ch-1.pl b/challenge-076/walt-mankowski/perl/ch-1.pl index bd19d3acfb..d4c8673a2d 100644 --- a/challenge-076/walt-mankowski/perl/ch-1.pl +++ b/challenge-076/walt-mankowski/perl/ch-1.pl @@ -3,6 +3,7 @@ use strict; use warnings; use feature qw(:5.32); use experimental qw(signatures); +use List::Util qw(sum); # TASK #1 › Prime Sum # Submitted by: Mohammad S Anwar @@ -36,5 +37,66 @@ sub primes_upto($n) { return grep {$is_prime[$_]} 2..$n; } +sub value($c, $cnt) { + my $sum = 0; + for my $i (0..$#$c) { + $sum += $c->[$i] * $cnt->[$i]; + } + return $sum; +} + +sub sums($s, @c) { + my @solutions; + + my @cnt = map {0} 0..$#c; + while (1) { + my $val = value(\@c, \@cnt); + if ($val >= $s) { + if ($val == $s) { + my @tmp = @cnt; + push @solutions, \@tmp; + } + + # rotate "odometer" + $cnt[-1] = 0; + my $i = -2; + $cnt[$i]++; + while ($i >= -@c && value(\@c, \@cnt) > $s) { + $cnt[$i] = 0; + $i--; + $cnt[$i]++ if $i >= -@c; + } + last if $i < -@c; + } else { + $cnt[-1]++; + } + } + return @solutions; +} + my $n = shift @ARGV; my @primes = primes_upto($n); +my @solutions = sums($n, @primes); +say "primes: @primes"; + +# find indices of best solution +my $min = 1e300; +my @best; +for my $i (0..$#solutions) { + my $sum = sum $solutions[$i]->@*; + if ($sum < $min) { + $min = $sum; + @best = ($i); + } elsif ($sum == $min) { + push @best, $i; + } +} + +# print out the solutions +for my $i (@best) { + my @p; + for my $j (0..$#primes) { + push @p, ($primes[$j]) x $solutions[$i][$j] if $solutions[$i][$j]; + } + say join " + ", @p; +} |