Strings and sequences

Weekly challenge 224 — 3 July 2023

Week 224 - 3 Jul 2023

Task 2

You are 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. A valid additive sequence should contain at least 3 numbers. Except the first 2 numbers, each subsequent number in the sequence must be the sum of the preceding two.

This is another challenge that can be solved by recursion, or maybe a stack-based method which avoids recursion per se. However, as we shall see, the maximum depth of recursion is limited to the number of digits in string, and in most cases is much less. Moreover, we are not required to find the best solution (for some value of 'best') but merely a solution - though I have not pondered the question of whether it's possible to create a string which can be parsed as additive more than one way .

At each step in the process we take successively the first 1, 2, 3 .. all of the (remaining) digits in $string, and see if the number thus composed is additive with respect to any numbers already in our array of additive numbers. We don't need to make an additivity test on the first two numbers, as any 2 numbers could potentially start an additive series. If we have success in finding additivity we add the new number to our array and take its digits away from $string. And if that leaves $string empty we have a solution and can stop.

The challenge is silent on the subject of leading zeroes, so I have assumed that they are allowed, and so for example 1002003 is additive as 1 + 002 = 003.

Because of the factors mentioned above, this algorithm handles a 40 member series in milliseconds, but that gets close to bigint territory, where we shall not pursue it.

#!/usr/bin/perl use v5.16; # The Weekly Challenge - 2023-07-03 use utf8; # Week 224 task 2 - Additive number use strict; # Peter Campbell Smith use warnings; # Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge my ($solution, @string, $j); additive_number('12354782'); additive_number('199100199299498'); additive_number('0030047'); additive_number('314159'); # create a long one @string = (28,74);; for $j (0 .. 19) { push @string, $string[-1] + $string[-2]; } additive_number(join('', @string)); sub additive_number { my $string; # initialise $solution = ''; $string = shift @_; # start recursion test([], $string); # results say qq[\nInput: \$string = '$string']; say qq[Output: ] . ($solution ? $solution : 'false'); } sub test { # test 1 further number (maybe several digits) along $string my (@numbers, $string, $count, $length, $j, @new_numbers, $new_string, $keep_going); # we can stop if a solution has been found return if $solution; # initialise @numbers = @{$_[0]}; $string = $_[1]; $count = scalar @numbers; # if we have only 1 or 2 numbers they must be valid and we don't need to test them if ($count < 3) { $keep_going = 1; # we check that the last 3 numbers are additive, and if the string is now empty we have a solution } else { $keep_going = $numbers[-3] + $numbers[-2] == $numbers[-1]; if ($keep_going and $string eq '') { $solution = join(', ', @numbers); return; } } # $keep_going is true if the sequence of @numbers is good but incomplete return unless $keep_going; # try using the next 1, 2, 3 ... digits from $string $length = length($string); for $j (1 .. $length) { @new_numbers = (@numbers, substr($string, 0, $j)); $new_string = $j == $length ? '' : substr($string, $j); # and recurse with those test(\@new_numbers, $new_string); } }

Input: $string = '12354782' Output: 12, 35, 47, 82 Input: $string = '199100199299498' Output: 1, 99, 100, 199, 299, 498 Input: $string = '0030047' Output: 003, 004, 7 Input: $string = '314159' Output: false Input: $string = '2874102176278454732118619183104502281261314821274344225569690118145814235932381746617678999424' Output: 28, 74, 102, 176, 278, 454, 732, 1186, 1918, 3104, 5022, 8126, 13148, 21274, 34422, 55696, 90118, 145814, 235932, 381746, 617678, 999424

Peter Campbell Smith is hereby placed in the public domain