Add solutions to 065 by E. Choroba

There are two solutions for 065/1 Digits Sum. The first one is the
naive one which uses the brute force. The second solution generates
only the possible numbers and seems to be much faster: on my machine,
it runs 3 times faster for length 7 and sum 42.

The Palindrome Partition adds one more solution to the "aabaab" case:
["aa", "aa"]. It's not clear why this solution is invalid (Must the
solutions be adjacent? Should each solution be never part of another
solution?) Fixing the algorithm might not be straight forward, as
additional constraints might need information that's not available in
the current implementation.

3 files changed, 77 insertions, 0 deletions

diff --git a/challenge-065/e-choroba/perl/ch-1.pl b/challenge-065/e-choroba/perl/ch-1.pl
new file mode 100755
index 0000000000..8ffa2635f9
--- /dev/null
+++ b/challenge-065/e-choroba/perl/ch-1.pl
@@ -0,0 +1,16 @@
+#!/usr/bin/perl
+use warnings;
+use strict;
+use feature qw{ say };
+
+use List::Util qw{ sum };
+
+sub digits_sum {
+    my ($digits, $sum) = @_;
+    grep $sum == sum(split //), 1 . (0 x ($digits - 1)) .. 9 x $digits
+}
+
+say for digits_sum(2, 4);
+
+# This takes 14.5 seconds.
+# say for digits_sum(7, 42);
diff --git a/challenge-065/e-choroba/perl/ch-1b.pl b/challenge-065/e-choroba/perl/ch-1b.pl
new file mode 100755
index 0000000000..d251be643c
--- /dev/null
+++ b/challenge-065/e-choroba/perl/ch-1b.pl
@@ -0,0 +1,20 @@
+#!/usr/bin/perl
+use warnings;
+use strict;
+use feature qw{ say };
+
+sub digits_sum {
+    my ($digits, $sum, $min) = @_;
+    return $sum ? () : "" if 0 == $digits;
+    $min //= 1;
+    my $max = $sum > 9 ? 9 : $sum;
+    map {
+        my $start = $_;
+        map "$start$_", digits_sum($digits - 1, $sum - $start, 0)
+    } $min .. $max
+}
+
+say for digits_sum(2, 4);
+
+# This takes 5.5 seconds.
+# say for digits_sum(7, 42);
diff --git a/challenge-065/e-choroba/perl/ch-2.pl b/challenge-065/e-choroba/perl/ch-2.pl
new file mode 100755
index 0000000000..2793083533
--- /dev/null
+++ b/challenge-065/e-choroba/perl/ch-2.pl
@@ -0,0 +1,41 @@
+#!/usr/bin/perl
+use warnings;
+use strict;
+
+sub is_palindrome {
+    my ($s) = @_;
+    $s eq reverse $s
+}
+
+my %solved;
+sub palindrome_partition {
+    my ($string, $from) = @_;
+    my @palindromes;
+    for my $start ($from // 0.. length($string) - 1) {
+        for my $length (2 .. length($string) - $start) {
+            my $substr = substr $string, $start, $length;
+            my $rest = substr $string, $start + length $substr;
+            next unless is_palindrome($substr);
+
+            next if $solved{$start}{$length}++;
+            my $recurse = palindrome_partition($string, $start + $length);
+            if (@$recurse) {
+                push @palindromes, map [ $substr, @$_ ], @$recurse;
+            } else {
+                push @palindromes, [$substr];
+            }
+        }
+    }
+    return \@palindromes
+}
+
+use Test::More;
+use Test::Deep;
+
+cmp_deeply palindrome_partition('aabaab'),
+    bag(['aabaa'], ['aa', 'baab'], ['aba'], ['aa', 'aa']);
+
+cmp_deeply palindrome_partition('abbaba'),
+    bag(['abba'], ['bb', 'aba'], ['bab']);
+
+done_testing();