RogerBW's Blog

I’ve been doing the Perl Weekly Challenges. The latest involved generating large numbers and splitting strings into palindromes.

You 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.

Well what do you know, it's another breadth-first search with a FIFO buffer. This time each buffer entry contains the digits so far, ending with their sum.

my @out;
my @l;
do {
  my $n=[0];
  if (@l) {
    $n=shift @l;
  }
  my $s=pop @{$n};

This is where we get sneaky. If we already have all-but-one of the digits, there's only one possible value the last digit can have.

  if (scalar @{$n} == $N-1) {
    my $digit=$S-$s;
    if ($digit>=0 && $digit<=9) {
      push @out,join('',@{$n},$digit);
    }
  } else {

Otherwise, append each digit that doesn't make the sum too large. (We can always end with a string of zeroes.)

    foreach my $digit (($s==0?1:0)..min($S-$s,9)) {
      push @l,[@{$n},$digit,$s+$digit];
    }
  }
} while (@l);

print join(', ',sort @out),"\n";

Perl6 is basically the same, with the trick to get it to put a plain list in my list.

push @l,(map {$_},@n,$digit,$s+$digit);

(What's the precedence of map vs comma? It doesn't matter.)

You 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.

Well, I started this, but then I realised that the examples were inconsistent with the problem statement. The second example makes it clear that you don't have to include all characters in the string in your output (a valid answer for "abbaba" is "abba"); but then why do the valid answers for "aabaab" not include "aabaa"? Therefore my answer is:

The problem is underspecified and cannot be solved unambiguously.

(Also the obvious way to do this is yet another BFS with FIFO buffer and I am bored with every problem having basically the same solution. It's like those stories they tell kids in the sort of metachurchy things that are meant to persuade them of the wonderfulness of God: if you are not entirely stupid, you rapidly notice that the answer is always Jesus so the story was just an excuse.)