Robbie Hatley's Solutions To The Weekly Challenge #224

For those not familiar with "The Weekly Challenge", it is a weekly programming puzzle, usually with two parts, cycling every Sunday. You can find it here:

The Weekly Challenge

This week (2023-07-02 through 2023-07-08) is weekly challenge #224.

Task 1 is as follows:

Task 1: Special Notes
Submitted by: Mohammad S Anwar
Given two strings, $source and $target, write a script to determine if 
using the characters (only once) from $source, $target can be created.

Example 1:
Input:  $source = "abc", $target = "xyz"
Output: false

Example 2:
Input:  $source = "scriptinglanguage", $target = "perl"
Output: true

Example 3:
Input:  $source = "aabbcc", $target = "abc"
Output: true

This problem basically asks "can poison pen letter 'target' be made from source 'source'?". I think I'll use the following algorithm:

sub ppl ($source, $target) { # ppl = "Poison Pen Letter"
   for each character in target {
      if char is in source {
         remove char from source
      }
      else {
         return 0
      }
   }
   return 1
}

The script I came up with is this:

Robbie Hatley's Solution to The Weekly Challenge 224-1

Task 2 is as follows:

Task 2: Additive Number
Submitted by: Mohammad S Anwar
Given a string containing digits 0-9 only, write a script to 
find out if the given string is an "additive number". 
An "additive number" is a string whose digits can form an 
"additive sequence". An "additive sequence" is a sequence 
(finite or infinite) of integers, containing at least 3 numbers, 
such that except the first 2 numbers, each subsequent number in 
the sequence is the sum of the preceding two.

Example 1:  Input: $string = "112358"  Output: true
The additive sequence can be created using the given string digits: 1,1,2,3,5,8
1 + 1 => 2
1 + 2 => 3
2 + 3 => 5
3 + 5 => 8

Example 2:  Input: $string = "12345"  Output: false
No additive sequence can be created using the given string digits.

Example 3:  Input: $string = "199100199"  Output: true
The additive sequence can be created using the given string digits: 1,99,100,199
 1 +  99 => 100
99 + 100 => 199

This is a "partitions of a string" problem. String partitions are collections of substrings which are non-duplicating (injective), non-gapping (surjective), non-crossing, and non-overlapping.

String partitions are tantalizingly close to being "non-crossing partitions", given by Catalan numbers, but are not quite the same thing, as "non-crossing" partitions can overlap, whereas string partitions can't.

Given a string of length n, each "part" of one of its partitions is a substring determined by its starting and one-past-end indices. The possible "one-past-end" indices are (1..n). 0 can't be a one-past-end because no strings start before 0, and no empty parts are allowed. And n will ALWAYS be the one-past-end for the last part (which may also be the first and only part). So the only one-past-end indices which are "in question" are (1..n-1). Therefore, the total number of possible partitions is the number of subsets of (1..n-1), which is 2^(n-1).

This suggests an algorithm that bypasses recursion and bypasses CPAN, and is determined only by the 2^(n-1) possible sets of one-past-end indices described by the following binary-number signatures:

   my @signatures=(0..2**($n-1)-1);

Algorithm: For each such signature, form a partition using those one-past-end indices, and see if that partition is additive.

The script I came up with is this:

Robbie Hatley's Solution to The Weekly Challenge 224-2

That's it for 224; see you on 225!