Only 100, please

This post is part of a series on Mohammad Anwar’s excellent Weekly Challenge, where hackers submit solutions in Perl, Raku, or any other language, to two different challenges every week. (It’s a lot of fun, if you’re into that sort of thing.)

Challenge #1 this week is as follows:

You are given a string “123456789”. Write a script that would insert ”+” or ”-” in between digits so that when you evaluate, the result should be 100.

I am going to add the additional constraint that we want all possible solutions, because that is a much stronger statement, and not that difficult to do. There are a few ways we could go about it, but one way that will ensure we traverse the entire search tree is to try every permutation of +, -, and ” (i.e., nothing) in between each decimal digit. As a minimal example, given the string 12, we would have the following expressions:

+1      +1-2    -1+2    +12
+1+2    -1      -1-2    -12

Recursion gives us a search tree for free, so we’ll use that.

Raku

In Raku, I used substr to partition the string into left and right ($l and $r) parts in a loop, so we get every possible 2-partition of the string. Consider the following:

my $num = 123456789;
for 1..$num.chars {
    my ($l, $r) = ($num.substr(0, $_), $num.substr($_))».Int;
    printf "%-9s:%9s\n", $l, $r;
}

The output from that will be as follows:

        1:23456789 
       12:3456789  
      123:456789   
     1234:56789    
    12345:6789     
   123456:789      
  1234567:89       
 12345678:9        
123456789:0        

Don’t worry about that zero on the last line; that will serve an important purpose in the final function.

Now that we have a way to partition our input, we need to decide how we’re going to recurse. Perhaps the most obvious way is to add ±$l to our expression, and then recurse on the leftover characters in $r.

How are we going to know what the value of the expression is? We could use EVAL, and it wouldn’t be too crazy, since our input is tightly constrained. But eval is slow, and there’s no need, since we can keep track of our partial sum and combine that with the recursion results. So our subroutine signature looks like this:

sub expr-split( Int $sum, Int $num, Str $exp = '', Int $psum = 0 ) { ... }

Note that only $sum and $num are required, so when someone calls expr-split, they don’t have to know about our recursion bookkeeping. Finally, we just need a good base case or two. First, we want to output the expression if the expression’s sum ($psum) equals our target sum, $sum, but only if there are no numbers left (that’s why that zero is important). Second, we return empty-handed if there are no numbers left.

    say $exp if $num == 0 and $psum == $sum;
    return   if $num == 0;

The full routine looks like this:

#| Insert +/- into $num such that the expression = $sum; output all
sub expr-split( Int $sum, Int $num, Str $exp = '', Int $psum = 0 ) {
    say $exp if $num == 0 and $psum == $sum;
    return   if $num == 0;

    for 1..$num.chars {
        my ($l, $r) = ($num.substr(0, $_), $num.substr($_))».Int;
        expr-split($sum, $r, "$exp+$l", $psum + $l);
        expr-split($sum, $r, "$exp-$l", $psum - $l);
    }
}

When called with expr-split(100, 123456789), the results are as follows:

+1+2+3-4+5+6+78+9       +12+3-4+5+67+8+9
+1+2+34-5+67-8+9        +12-3-4+5-6+7+89
+1+23-4+5+6+78-9        +123+4-5+67-89
+1+23-4+56+7+8+9        +123-4-5-6-7+8-9
-1+2-3+4+5+6+78+9       +123+45-67+8-9
+12+3+4+5-6-7+89        +123-45-67+89

Perl

In Perl, the same algorithm works just as well. Instead of using substr, though, I opted to use unpack. (unpack exists in Raku, but is still experimental.) We could also use split (comb in Raku), or regexes, or modulo arithmetic, but, hey, we’re just chopping up a number, here. Sometimes it’s best not to think too hard about something.

I decided to get a little fancy with the Perl solution, because I wondered how many more solutions there would be if I allowed more operations, such as multiplication or division. So I define a custom set of operators, as well as operators which also work as prefix operators, so we can start with a negative number:

my        @ops = qw( + - );
my @prefix_ops = qw( + - ); # Ops which are also prefix ops

Then the recursion step looks very similar to the Raku solution, except we are just appending to the expression, not calculating the partial sum:

    for (1..length $o{num}) {
        my ($l, $r) = unpack "A$_ A*", $o{num};
        my @cur_ops = length($o{exp}) > 0 ? @ops : @prefix_ops;
        sum_split(%o, num => $r, exp => "$o{exp}$_$l") for @cur_ops;
    }

And our base case is the same as before, except I am going to use string eval here. It is reasonably efficient in Perl, the inputs are safe, and it makes our lives a lot easier in this case. Here is the entire routine:

sub sum_split {
    my %o = @_;

    say $o{exp} if $o{exp};
    if (0 == length $o{num}) {
        my $sum = eval $o{exp} // return;
        say "$sum == $o{exp}" if $sum == $o{sum};
        return
    }

    # Partition $num and recurse
    for (1..length $o{num}) {
        my ($l, $r) = unpack "A$_ A*", $o{num};
        my @cur_ops = length($o{exp}) > 0 ? @ops : @prefix_ops;
        sum_split(%o, num => $r, exp => "$o{exp}$_$l") for @cur_ops;
    }
}

With @ops = qw( + - ), the output is the same as the Raku output. However, if we add * and /, things get a lot more interesting very quickly: 162 solutions! And it doesn’t end there:

@ops = qw( - * / % >> << & | ) gives 22,675 solutions, and a lot of them are quite creative (at least in appearance), such as: 100 = +1 + 2 + 3 / 4 << 5 | 6 & 78 - 9.

Operator Precedence Challenge

Now I have a challenge for you.

Since we’re running these through Perl’s eval, these expressions follow Perl’s operator precedence. I’ve found they double as helpful flash cards to sharpen my own memory of operator precedence, especially in weird cases like the one above, where I would certainly have added brackets for clarity:

100 = (1 + 2 + (3 / 4) << 5) | (6 & (78 - 9))

Here is the complete list of solutions (573KiB), or as a .gz download (68KiB), if you want to have a go. Just pick a line, add brackets, and run it through perl -E say '<expr>' to see if the result is still 100.

Complexity

Using this method, the search space grows exponentially. An n-digit number gives us n spaces, and each of those spaces can be any one of m = @ops, or the empty string. Each of the n spaces can be any of m + 1 things, giving us a total complexity of O([m+1]ⁿ). This, for a 9-digit number, here is the total search space for a given number of operators:

Can we do better? Yes. For a start, we could trade space for time by caching some results, so we can prune early and use the cached result rather than repeating the same sub-calculations over and over again. But as the problem only called for two operators, I’ll save the hardcore algorithmics for a tougher challenge!