The weekly challenge 224 - Task 2: Additive Number

 1 #!/usr/bin/perl
 2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-224/#TASK2
 3 #
 4 # Task 2: Additive Number
 5 # =======================
 6 #
 7 # You are given a string containing digits 0-9 only.
 8 #
 9 # Write a script to find out if the given string is additive number. An
10 # additive number is a string whose digits can form an additive sequence.
11 #
12 ### A valid additive sequence should contain at least 3 numbers. Except the
13 ### first 2 numbers, each subsequent number in the sequence must be the sum of
14 ### the preceding two.
15 #
16 ## Input: $string = "112358"
17 ## Output: true
18 ##
19 ## The additive sequence can be created using the given string digits: 1,1,2,3,5,8
20 ## 1 + 1 => 2
21 ## 1 + 2 => 3
22 ## 2 + 3 => 5
23 ## 3 + 5 => 8
24 #
25 ## Example 2:
26 ##
27 ## Input: $string = "12345"
28 ## Output: false
29 ##
30 ## No additive sequence can be created using the given string digits.
31 #
32 ## Example 3:
33 ##
34 ## Input: $string = "199100199"
35 ## Output: true
36 ##
37 ## The additive sequence can be created using the given string digits: 1,99,100,199
38 ##  1 +  99 => 100
39 ##  99 + 100 => 199
40 #
41 ############################################################
42 ##
43 ## discussion
44 ##
45 ############################################################
46 #
47 # We start by selecting a substring of length l as the first number, with
48 # 1 <= l <= 1/3*length(string). Then we select another substring starting after
49 # the first one with the same length restriction. Then, the rest remains as our
50 # reminder of the string. We now add up the first two strings and compare the
51 # result to the beginning of the rest with the same length. If that matches,
52 # our current second string becomes our new first one, the subtring we just cut
53 # out of the rest is our new second string, and the remainder of the rest after
54 # cutting out this new second string will be our new rest. If it has zero
55 # length, we have found an additive number. We recurse down with this function
56 # until the first two numbers don't match the beginning of the rest or the
57 # length of the rest is no longer long enough to match the sum, in which cases
58 # we return 0 and therfore short-curcuit the execution, or we have reached the
59 # end of the rest with all sums in between matching, so we can return 1.
60 
61 use strict;
62 use warnings;
63 
64 additive_number("112358");
65 additive_number("12345");
66 additive_number("199100199");
67 additive_number("991100101");
68 
69 sub additive_number {
70    my $string = shift;
71    my $max_len = length($string) / 3;
72    print "Input: $string\n";
73    my ($first, $second, $rest);
74    foreach my $len1 (1..$max_len) {
75       $first = substr($string,0,$len1);
76       foreach my $len2 (1..$max_len) {
77          $second = substr($string,$len1,$len2);
78          $rest = substr($string,$len1+$len2);
79          if(is_additive($first, $second, $rest)) {
80             print "Output: true\n";
81             return;
82          }
83       }
84    }
85    print "Output: false\n";
86 }
87 
88 sub is_additive {
89    my ($first, $second, $rest) = @_;
90    my $sum = $first+$second;
91    return 0 unless length($rest) >= length($sum);
92    my $tmp = substr($rest,0,length($sum));
93    my $tmp_rest = substr($rest,length($sum));
94    if($tmp != $sum) {
95       return 0;
96    }
97    return 1 if length($tmp_rest) == 0;
98    return is_additive($second, $tmp, $tmp_rest);
99 }