Solution to 076 Task 1, PrimeSum

8 files changed, 1513 insertions, 64 deletions

diff --git a/challenge-076/bob-lied/perl/ch-1.pl b/challenge-076/bob-lied/perl/ch-1.pl
index b02867877d..e3fb5b9348 100644..100755
--- a/challenge-076/bob-lied/perl/ch-1.pl
+++ b/challenge-076/bob-lied/perl/ch-1.pl
@@ -1,31 +1,33 @@
 #!/usr/bin/env perl
 # vim:set ts=4 sw=4 sts=4 et ai wm=0 nu:
 #=============================================================================
-# ch-2.pl
+# ch-1.pl
 #=============================================================================
 # Copyright (c) 2020, Bob Lied
 #=============================================================================
-# Perl Weekly Challenge 000 Task #1 > xxx
+# Perl Weekly Challenge 000 Task #1 > Prime Sum
+# You are given a number $N.
+# Write a script to find the minimum number of prime numbers required, whose summation gives you $N.
+# For the sake of this task, please assume 1 is not a prime number.
 #=============================================================================
 
 use strict;
 use warnings;
 use v5.30;
 
-us feature qw/ signatures /;
+use feature qw/ signatures /;
 no warnings qw/ experimental::signatures /;
 
+
 use lib "lib";
-use Task1;
+use PrimeSum;
 
-sub Usage { "Usage: $0 args" };
+sub Usage { "Usage: $0 N\n\t2 <= N <= 10000" };
 
-my $arg = shift;
-my @list = @ARGV;
+my $N = shift;
 
-die Usage() unless $arg;
-die Usage() unless @list;
+die Usage() unless $N && $N > 1 && $N <= 10000;
 
-my $task = Task1->new();
-my $result = task->run();
-say $result;
+my $task = PrimeSum->new($N);
+my ($result, $list) = $task->run();
+say "$N ==> $result [ ", join(', ', @$list), " ]";
diff --git a/challenge-076/bob-lied/perl/ch-2.pl b/challenge-076/bob-lied/perl/ch-2.pl
index 6a1a88fe38..6a1a88fe38 100644..100755
--- a/challenge-076/bob-lied/perl/ch-2.pl
+++ b/challenge-076/bob-lied/perl/ch-2.pl
diff --git a/challenge-076/bob-lied/perl/lib/PrimeSum.pm b/challenge-076/bob-lied/perl/lib/PrimeSum.pm
new file mode 100644
index 0000000000..77529ce9dc
--- /dev/null
+++ b/challenge-076/bob-lied/perl/lib/PrimeSum.pm
@@ -0,0 +1,114 @@
+# vim:set ts=4 sw=4 sts=4 et ai wm=0 nu:
+#=============================================================================
+# PrimeSum.pm
+#=============================================================================
+# Copyright (c) 2020, Bob Lied
+#=============================================================================
+# Description:
+#=============================================================================
+
+package PrimeSum;
+
+use strict;
+use warnings;
+use v5.30;
+
+use feature qw/ signatures /;
+no warnings qw/ experimental::signatures /;
+
+
+require Exporter;
+our @ISA = qw(Exporter);
+our @EXPORT = qw();
+our @EXPORT_OK = qw(_loadPrimeList);    # Export for testing
+
+my @PrimeList; # Class variable, lazy evaluation.
+
+# Assuming that finding the primes is not part of the exercise.
+# Make the list in descending order.
+# Could replace this with a sieve if we wanted to find primes ourselves.
+sub _loadPrimeList($n, $pathToList)
+{
+    if ( ! @PrimeList )
+    {
+        use File::Slurper 'read_lines';
+        # https://www.mathsisfun.com/numbers/prime-number-lists.html
+        @PrimeList = sort { $b <=> $a }  read_lines($pathToList);
+    }
+    return [  grep { $_ <= $n } @PrimeList ];
+}
+
+sub new($class, @args)
+{
+    $class = ref($class) || $class;
+    my $self = {
+        _n => $args[0],
+        _pathToPrimes => $args[1], 
+        _primeList => undef,
+
+        _numPrimesRequired => int($args[0] / 2),
+        _comboList => undef,
+    };
+
+    $self->{_pathToPrimes} //= "lib/primes-to-10k.txt";
+    $self->{_primeList} = _loadPrimeList( $self->{_n}, $self->{_pathToPrimes} ); 
+    bless $self, $class;
+    return $self;
+}
+
+sub run($self)
+{
+    my @primes = @{$self->{_primeList}};
+    while ( @primes )
+    {
+        $self->_primeSum(1, $self->{_n}, \@primes, $primes[0], [ $primes[0] ] );
+
+        # Not going to get a shorter list than 1 (if N is prime)
+        last if ( $self->{_numPrimesRequired} == 1 );
+        shift @primes;
+    }
+
+    my $clist = $self->{_comboList};
+    my $min = $self->{_numPrimesRequired};
+
+
+    # Select the rows of $clist that have minimum length
+    # and make a smaller list by taking that slice.
+    my @shortList = @{$clist}[ grep { scalar(@{$clist->[$_]}) == $min } 0 .. scalar(@$clist)-1 ];
+
+    return $min, $shortList[0];
+}
+
+sub _primeSum($self, $depth, $target, $primeList, $prime, $combo)
+{
+    # say "$depth: $target, $prime, [ @$combo ]";
+    my $diff = $target - $prime;
+    if ( $diff == 0 )
+    {
+        push @{$self->{_comboList}}, [ @$combo ];
+        $self->{_numPrimesRequired} = $depth if $depth < $self->{_numPrimesRequired};
+        return 0;
+    }
+    if ( $diff < 0 )
+    {
+        pop @$combo;
+        return $diff;
+    }
+
+    # If the combo would become bigger than a solution we already found,
+    # no need to go down this path.
+    if ( $depth >= $self->{_numPrimesRequired} )
+    {
+        return $diff;
+    }
+    my @remainingPrime = grep { $_ <= $diff } @$primeList;
+    for my $p ( @remainingPrime )
+    {
+        push @$combo, $p;
+        $self->_primeSum($depth+1, $diff, \@remainingPrime, $p, $combo );
+        pop @$combo
+    }
+}
+
+1;
+
diff --git a/challenge-076/bob-lied/perl/lib/Task1.pm b/challenge-076/bob-lied/perl/lib/Task1.pm
deleted file mode 100644
index 13e942cf56..0000000000
--- a/challenge-076/bob-lied/perl/lib/Task1.pm
+++ /dev/null
@@ -1,38 +0,0 @@
-# vim:set ts=4 sw=4 sts=4 et ai wm=0 nu:
-#=============================================================================
-# Task1.pm
-#=============================================================================
-# Copyright (c) 2020, Bob Lied
-#=============================================================================
-# Description:
-#=============================================================================
-
-package Task1;
-
-use strict;
-use warnings;
-
-require Exporter;
-our @ISA = qw(Exporter);
-our @EXPORT = qw();
-our @EXPORT_OK = qw();
-
-sub new
-{
-    my $class = shift;
-    $class = ref($class) || $class;
-    my $self = {
-        _name1 => $_[0],
-    };
-    bless $self, $class;
-    return $self;
-}
-
-sub run
-{
-    my $self = shift;
-    return undef;
-}
-
-1;
-
diff --git a/challenge-076/bob-lied/perl/lib/primes-to-10k.txt b/challenge-076/bob-lied/perl/lib/primes-to-10k.txt
new file mode 100644
index 0000000000..936db32669
--- /dev/null
+++ b/challenge-076/bob-lied/perl/lib/primes-to-10k.txt
@@ -0,0 +1,1229 @@
+2
+3
+5
+7
+11
+13
+17
+19
+23
+29
+31
+37
+41
+43
+47
+53
+59
+61
+67
+71
+73
+79
+83
+89
+97
+101
+103
+107
+109
+113
+127
+131
+137
+139
+149
+151
+157
+163
+167
+173
+179
+181
+191
+193
+197
+199
+211
+223
+227
+229
+233
+239
+241
+251
+257
+263
+269
+271
+277
+281
+283
+293
+307
+311
+313
+317
+331
+337
+347
+349
+353
+359
+367
+373
+379
+383
+389
+397
+401
+409
+419
+421
+431
+433
+439
+443
+449
+457
+461
+463
+467
+479
+487
+491
+499
+503
+509
+521
+523
+541
+547
+557
+563
+569
+571
+577
+587
+593
+599
+601
+607
+613
+617
+619
+631
+641
+643
+647
+653
+659
+661
+673
+677
+683
+691
+701
+709
+719
+727
+733
+739
+743
+751
+757
+761
+769
+773
+787
+797
+809
+811
+821
+823
+827
+829
+839
+853
+857
+859
+863
+877
+881
+883
+887
+907
+911
+919
+929
+937
+941
+947
+953
+967
+971
+977
+983
+991
+997
+1009
+1013
+1019
+1021
+1031
+1033
+1039
+1049
+1051
+1061
+1063
+1069
+1087
+1091
+1093
+1097
+1103
+1109
+1117
+1123
+1129
+1151
+1153
+1163
+1171
+1181
+1187
+1193
+1201
+1213
+1217
+1223
+1229
+1231
+1237
+1249
+1259
+1277
+1279
+1283
+1289
+1291
+1297
+1301
+1303
+1307
+1319
+1321
+1327
+1361
+1367
+1373
+1381
+1399
+1409
+1423
+1427
+1429
+1433
+1439
+1447
+1451
+1453
+1459
+1471
+1481
+1483
+1487
+1489
+1493
+1499
+1511
+1523
+1531
+1543
+1549
+1553
+1559
+1567
+1571
+1579
+1583
+1597
+1601
+1607
+1609
+1613
+1619
+1621
+1627
+1637
+1657
+1663
+1667
+1669
+1693
+1697
+1699
+1709
+1721
+1723
+1733
+1741
+1747
+1753
+1759
+1777
+1783
+1787
+1789
+1801
+1811
+1823
+1831
+1847
+1861
+1867
+1871
+1873
+1877
+1879
+1889
+1901
+1907
+1913
+1931
+1933
+1949
+1951
+1973
+1979
+1987
+1993
+1997
+1999
+2003
+2011
+2017
+2027
+2029
+2039
+2053
+2063
+2069
+2081
+2083
+2087
+2089
+2099
+2111
+2113
+2129
+2131
+2137
+2141
+2143
+2153
+2161
+2179
+2203
+2207
+2213
+2221
+2237
+2239
+2243
+2251
+2267
+2269
+2273
+2281
+2287
+2293
+2297
+2309
+2311
+2333
+2339
+2341
+2347
+2351
+2357
+2371
+2377
+2381
+2383
+2389
+2393
+2399
+2411
+2417
+2423
+2437
+2441
+2447
+2459
+2467
+2473
+2477
+2503
+2521
+2531
+2539
+2543
+2549
+2551
+2557
+2579
+2591
+2593
+2609
+2617
+2621
+2633
+2647
+2657
+2659
+2663
+2671
+2677
+2683
+2687
+2689
+2693
+2699
+2707
+2711
+2713
+2719
+2729
+2731
+2741
+2749
+2753
+2767
+2777
+2789
+2791
+2797
+2801
+2803
+2819
+2833
+2837
+2843
+2851
+2857
+2861
+2879
+2887
+2897
+2903
+2909
+2917
+2927
+2939
+2953
+2957
+2963
+2969
+2971
+2999
+3001
+3011
+3019
+3023
+3037
+3041
+3049
+3061
+3067
+3079
+3083
+3089
+3109
+3119
+3121
+3137
+3163
+3167
+3169
+3181
+3187
+3191
+3203
+3209
+3217
+3221
+3229
+3251
+3253
+3257
+3259
+3271
+3299
+3301
+3307
+3313
+3319
+3323
+3329
+3331
+3343
+3347
+3359
+3361
+3371
+3373
+3389
+3391
+3407
+3413
+3433
+3449
+3457
+3461
+3463
+3467
+3469
+3491
+3499
+3511
+3517
+3527
+3529
+3533
+3539
+3541
+3547
+3557
+3559
+3571
+3581
+3583
+3593
+3607
+3613
+3617
+3623
+3631
+3637
+3643
+3659
+3671
+3673
+3677
+3691
+3697
+3701
+3709
+3719
+3727
+3733
+3739
+3761
+3767
+3769
+3779
+3793
+3797
+3803
+3821
+3823
+3833
+3847
+3851
+3853
+3863
+3877
+3881
+3889
+3907
+3911
+3917
+3919
+3923
+3929
+3931
+3943
+3947
+3967
+3989
+4001
+4003
+4007
+4013
+4019
+4021
+4027
+4049
+4051
+4057
+4073
+4079
+4091
+4093
+4099
+4111
+4127
+4129
+4133
+4139
+4153
+4157
+4159
+4177
+4201
+4211
+4217
+4219
+4229
+4231
+4241
+4243
+4253
+4259
+4261
+4271
+4273
+4283
+4289
+4297
+4327
+4337
+4339
+4349
+4357
+4363
+4373
+4391
+4397
+4409
+4421
+4423
+4441
+4447
+4451
+4457
+4463
+4481
+4483
+4493
+4507
+4513
+4517
+4519
+4523
+4547
+4549
+4561
+4567
+4583
+4591
+4597
+4603
+4621
+4637
+4639
+4643
+4649
+4651
+4657
+4663
+4673
+4679
+4691
+4703
+4721
+4723
+4729
+4733
+4751
+4759
+4783
+4787
+4789
+4793
+4799
+4801
+4813
+4817
+4831
+4861
+4871
+4877
+4889
+4903
+4909
+4919
+4931
+4933
+4937
+4943
+4951
+4957
+4967
+4969
+4973
+4987
+4993
+4999
+5003
+5009
+5011
+5021
+5023
+5039
+5051
+5059
+5077
+5081
+5087
+5099
+5101
+5107
+5113
+5119
+5147
+5153
+5167
+5171
+5179
+5189
+5197
+5209
+5227
+5231
+5233
+5237
+5261
+5273
+5279
+5281
+5297
+5303
+5309
+5323
+5333
+5347
+5351
+5381
+5387
+5393
+5399
+5407
+5413
+5417
+5419
+5431
+5437
+5441
+5443
+5449
+5471
+5477
+5479
+5483
+5501
+5503
+5507
+5519
+5521
+5527
+5531
+5557
+5563
+5569
+5573
+5581
+5591
+5623
+5639
+5641
+5647
+5651
+5653
+5657
+5659
+5669
+5683
+5689
+5693
+5701
+5711
+5717
+5737
+5741
+5743
+5749
+5779
+5783
+5791
+5801
+5807
+5813
+5821
+5827
+5839
+5843
+5849
+5851
+5857
+5861
+5867
+5869
+5879
+5881
+5897
+5903
+5923
+5927
+5939
+5953
+5981
+5987
+6007
+6011
+6029
+6037
+6043
+6047
+6053
+6067
+6073
+6079
+6089
+6091
+6101
+6113
+6121
+6131
+6133
+6143
+6151
+6163
+6173
+6197
+6199
+6203
+6211
+6217
+6221
+6229
+6247
+6257
+6263
+6269
+6271
+6277
+6287
+6299
+6301
+6311
+6317
+6323
+6329
+6337
+6343
+6353
+6359
+6361
+6367
+6373
+6379
+6389
+6397
+6421
+6427
+6449
+6451
+6469
+6473
+6481
+6491
+6521
+6529
+6547
+6551
+6553
+6563
+6569
+6571
+6577
+6581
+6599
+6607
+6619
+6637
+6653
+6659
+6661
+6673
+6679
+6689
+6691
+6701
+6703
+6709
+6719
+6733
+6737
+6761
+6763
+6779
+6781
+6791
+6793
+6803
+6823
+6827
+6829
+6833
+6841
+6857
+6863
+6869
+6871
+6883
+6899
+6907
+6911
+6917
+6947
+6949
+6959
+6961
+6967
+6971
+6977
+6983
+6991
+6997
+7001
+7013
+7019
+7027
+7039
+7043
+7057
+7069
+7079
+7103
+7109
+7121
+7127
+7129
+7151
+7159
+7177
+7187
+7193
+7207
+7211
+7213
+7219
+7229
+7237
+7243
+7247
+7253
+7283
+7297
+7307
+7309
+7321
+7331
+7333
+7349
+7351
+7369
+7393
+7411
+7417
+7433
+7451
+7457
+7459
+7477
+7481
+7487
+7489
+7499
+7507
+7517
+7523
+7529
+7537
+7541
+7547
+7549
+7559
+7561
+7573
+7577
+7583
+7589
+7591
+7603
+7607
+7621
+7639
+7643
+7649
+7669
+7673
+7681
+7687
+7691
+7699
+7703
+7717
+7723
+7727
+7741
+7753
+7757
+7759
+7789
+7793
+7817
+7823
+7829
+7841
+7853
+7867
+7873
+7877
+7879
+7883
+7901
+7907
+7919
+7927
+7933
+7937
+7949
+7951
+7963
+7993
+8009
+8011
+8017
+8039
+8053
+8059
+8069
+8081
+8087
+8089
+8093
+8101
+8111
+8117
+8123
+8147
+8161
+8167
+8171
+8179
+8191
+8209
+8219
+8221
+8231
+8233
+8237
+8243
+8263
+8269
+8273
+8287
+8291
+8293
+8297
+8311
+8317
+8329
+8353
+8363
+8369
+8377
+8387
+8389
+8419
+8423
+8429
+8431
+8443
+8447
+8461
+8467
+8501
+8513
+8521
+8527
+8537
+8539
+8543
+8563
+8573
+8581
+8597
+8599
+8609
+8623
+8627
+8629
+8641
+8647
+8663
+8669
+8677
+8681
+8689
+8693
+8699
+8707
+8713
+8719
+8731
+8737
+8741
+8747
+8753
+8761
+8779
+8783
+8803
+8807
+8819
+8821
+8831
+8837
+8839
+8849
+8861
+8863
+8867
+8887
+8893
+8923
+8929
+8933
+8941
+8951
+8963
+8969
+8971
+8999
+9001
+9007
+9011
+9013
+9029
+9041
+9043
+9049
+9059
+9067
+9091
+9103
+9109
+9127
+9133
+9137
+9151
+9157
+9161
+9173
+9181
+9187
+9199
+9203
+9209
+9221
+9227
+9239
+9241
+9257
+9277
+9281
+9283
+9293
+9311
+9319
+9323
+9337
+9341
+9343
+9349
+9371
+9377
+9391
+9397
+9403
+9413
+9419
+9421
+9431
+9433
+9437
+9439
+9461
+9463
+9467
+9473
+9479
+9491
+9497
+9511
+9521
+9533
+9539
+9547
+9551
+9587
+9601
+9613
+9619
+9623
+9629
+9631
+9643
+9649
+9661
+9677
+9679
+9689
+9697
+9719
+9721
+9733
+9739
+9743
+9749
+9767
+9769
+9781
+9787
+9791
+9803
+9811
+9817
+9829
+9833
+9839
+9851
+9857
+9859
+9871
+9883
+9887
+9901
+9907
+9923
+9929
+9931
+9941
+9949
+9967
+9973
diff --git a/challenge-076/bob-lied/perl/t/PrimeSum.t b/challenge-076/bob-lied/perl/t/PrimeSum.t
new file mode 100644
index 0000000000..f6c1449586
--- /dev/null
+++ b/challenge-076/bob-lied/perl/t/PrimeSum.t
@@ -0,0 +1,56 @@
+# vim:set ts=4 sw=4 sts=4 et ai wm=0 nu:
+#
+#===============================================================================
+# FILE: Task1.t
+# DESCRIPTION: Unit test for Task1
+#===============================================================================
+
+use strict;
+use warnings;
+use v5.30;
+
+use Test2::V0;
+
+use lib "lib";
+use PrimeSum qw/_loadPrimeList/;
+
+my $task = PrimeSum->new(15);
+
+my $primeRef = _loadPrimeList(15, "t/primes-for-testing.txt");
+is( $primeRef, [ 13, 11, 7, 5, 3, 2], "load primes descending");
+
+my $N;
+my $result;
+my $list;
+
+$N = 2;
+($result, $list) = PrimeSum->new($N)->run();
+is( $result, 1,          "Min for prime $N" );
+is( $list,   [  2 ],     "List for prime $N" );
+
+$N = 4;
+($result, $list) = PrimeSum->new($N)->run();
+is( $result, 2,          "Min for prime $N" );
+is( $list,   [  2, 2 ],  "List for prime $N" );
+
+$N = 17;
+($result, $list) = PrimeSum->new($N)->run();
+is( $result, 1,         "Min for prime $N" );
+is( $list,   [ 17 ],    "List for prime $N" );
+
+$N = 15;
+($result, $list) = $task->run();
+is( $result, 2,         "Min for $N" );
+is( $list,   [ 13, 2 ], "List for $N" );
+
+$N = 27;
+($result, $list) = PrimeSum->new($N)->run();
+is( $result, 3,         "Min for $N" );
+is( $list,   [ 23, 2, 2 ], "List for $N" );
+
+$N = 51;
+($result, $list) = PrimeSum->new($N)->run();
+is( $result, 3,         "Min for $N" );
+is( $list,   [ 47, 2, 2 ], "List for $N" );
+
+done_testing();
diff --git a/challenge-076/bob-lied/perl/t/Task1.t b/challenge-076/bob-lied/perl/t/Task1.t
deleted file mode 100644
index 51dd7729c0..0000000000
--- a/challenge-076/bob-lied/perl/t/Task1.t
+++ /dev/null
@@ -1,14 +0,0 @@
-# vim:set ts=4 sw=4 sts=4 et ai wm=0 nu:
-#
-#===============================================================================
-# FILE: Task1.t
-# DESCRIPTION: Unit test for Task1
-#===============================================================================
-
-use strict;
-use warnings;
-use v5.30;
-
-use Test2::V0;
-
-done_testing();
diff --git a/challenge-076/bob-lied/perl/t/primes-for-testing.txt b/challenge-076/bob-lied/perl/t/primes-for-testing.txt
new file mode 100644
index 0000000000..11d32e9682
--- /dev/null
+++ b/challenge-076/bob-lied/perl/t/primes-for-testing.txt
@@ -0,0 +1,100 @@
+2
+3
+5
+7
+11
+13
+17
+19
+23
+29
+31
+37
+41
+43
+47
+53
+59
+61
+67
+71
+73
+79
+83
+89
+97
+101
+103
+107
+109
+113
+127
+131
+137
+139
+149
+151
+157
+163
+167
+173
+179
+181
+191
+193
+197
+199
+211
+223
+227
+229
+233
+239
+241
+251
+257
+263
+269
+271
+277
+281
+283
+293
+307
+311
+313
+317
+331
+337
+347
+349
+353
+359
+367
+373
+379
+383
+389
+397
+401
+409
+419
+421
+431
+433
+439
+443
+449
+457
+461
+463
+467
+479
+487
+491
+499
+503
+509
+521
+523
+541