### Perl Weekly Challenge: Week 65

#### Challenge 1:

Digits SumYou are given two positive numbers

`$N`

and`$S`

.Write a script to list all positive numbers having exactly

`$N`

digits where sum of all digits equals to`$S`

.## Example

Input: $N = 2 $S = 4

Output: 13, 22, 31, 40

I'll show the raku solution first because it is practically a one-liner though I spread it over multiple lines for greater legibility.

The `xx`

operator repeats a list a number of times. `[X]`

applied to the lists
produces a list of lists containing the cross product. By adding `~`

to make
`[X~]`

, the elements of the cross-product lists are concatenated. The upshot of
all this is that we end up with a list (assuming `$N`

= 2 as in the example) of
numbers from 00 to 99. If `$N`

was 3 we would get 000 to 999 and so on.

([X~] ([0 .. 9] xx $N))

But there numbers that start with 0. In the case of `$N`

= 2, `$S`

= 4, for example,
04 is actually 4 so it should not be included as a successful match. So this next
step filters out numbers beginning with 0. Actually, as I write this, I realize
that I've made a mistake; the regex shoulw be `/^0+/`

to deal with e.g `$N`

= 3
which produces 004 which is also really just 4. Luckily it doesn't make a practical
difference as the leading 0 means such numbers still get filtered out.

```
.grep({ !/^0/ })
```

Now we filter yet again. Each number that survived the last step is split into
digits with `.comb()`

and the digits are summed together with `[+]`

. If the result
equals `$S`

then we have a successful match.

```
.grep({ ([+] $_.comb) == $S })
```

All that remains is to print the list of successfull matches delimited by commas to look nicer.

```
.join(q{, })
.say;
```

The Perl version is more verbose as it lacks some of the handy features of Raku.
Most notable are the `xx`

and `X`

operators. The former can be readily simulated
with a loop, the latter is harder. Luckily I had already written a replacement
for challenge 44
which I reused. One unexpected benefit over Raku, is that by initially making `@digits`

1 to 9, I could omit the filtering out of numbers with leading 0's.

```
my @digits = 1 .. 9;
for (1 .. $N - 1) {
@digits = X(\@digits, [0 .. 9]);
}
```

The elegent `.grep`

from the Raku version had to be replaced by a `map`

, `grep`

,
and another `grep`

.

```
@digits = map { join q{}, @{$_}; }
grep { my $accum; map {$accum += $_; } @{$_}; $accum == $S; }
@digits;
```

But printing out the results is more or less the same.

```
say join q{, }, @digits;
```

#### Challenge 2:

Palindrome PartitionYou are given a string

`$S`

. Write a script print all possible partitions that gives Palindrome. Return -1 if none found.Please make sure, partition should not overlap. For example, for given string “abaab”, the partition “aba” and “baab” would not be valid, since they overlap.

## Example 1:

Input: $S = 'aabaab'

Output: There are 3 possible solutions. a) 'aabaa' b) 'aa', 'baab' c) 'aba'

## Example 2:

Input: $S = 'abbaba'

Output: There are 3 possible solutions. a) 'abba' b) 'bb', 'aba' c) 'bab'

A palindrome is a string that reads the same backwards and forwards. Detecting if a string is a palindrome is very easy in Perl.

```
sub is_palindrome {
my ($s) = @_;
return $s eq reverse $s;
}
```

We want to check each partition of a string for palindromeness (palindromosity?) An initial bit of confusion I had was that you can have more than two partitions. In fact if you think about it each separate character of a string can be considered a 'partition'. However for a palindrome you need at least two characters.

```
sub get_palindromes {
my ($s) = @_;
my @palindromes;
```

So my code takes the initial 2 to `length`

characters of the string and checks if
it is a palindrome. If it is, it adds it to the list of results and recursively
does the same check to the rest of the string. If it isn't, it adds 1 to the length
of the part it is checking and tries again.

```
for my $l (2 .. length $s ) {
my $possible = substr $s, 0, $l;
if (is_palindrome($possible)) {
push @palindromes, $possible;
push @palindromes, get_palindromes(substr $s, $l);
}
}
```

When all possible sequences have been searched, we can return the found palindromes.

```
return @palindromes;
}
```

Now the list returned from the function above might include duplicates. So before I print it out, I add the values as keys to a hash which are by definition unique.

```
for my $n (0 .. (length $S) - 1) {
for my $palindrome (get_palindromes(substr $S, $n)) {
$results{$palindrome}++;
}
}
say scalar keys %results ? join q{, }, keys %results : '-1';
```

The Raku version works the same way. Note Raku Strings have a `.flip()`

method
to do the reversing.

```
sub is_palindrome(Str $s) {
return $s eq $s.flip;
}
sub get_palindromes(Str $s) {
my @palindromes;
for 2 .. $s.chars -> $l {
my $possible = $s.substr(0, $l);
if $possible.chars && is_palindrome($possible) {
@palindromes.push($possible);
@palindromes.push(get_palindromes($s.substr($l)));
}
}
return @palindromes;
}
```

For reasons I don't fully understand, using `.substr()`

in Raku ends up with extra
whitespace around each palindrome. Luckily strings have a `.trim()`

method which
can get rid of it before we add it to the hash.

```
for 0 ..^ $S.chars -> $n {
for get_palindromes($S.substr($n)) -> $palindrome {
if ($palindrome.trim ne q{}) {
%results{$palindrome.trim}++;
}
}
}
say %results.keys.elems ?? %results.keys.join(q{, }) !! '-1';
}
```