Programming challenge: insert signs between digits

Here’s another drill offered by the Perl Weekly Challenge on Week 44. The task is to get a string 123456789 and insert the signs + and - between the digits so that the evaluated value of the new string equals 100. Actually, the problem is formulated a bit vague, as you may have less the 8 signs to get the result, for example: 1+23-4+56+7+8+9 = 100. The fun fact is that if you insert the signs between all the digits, you cannot find the solution.

The first step is obvious: split the string into characters:

my $string = '123456789';

my @nums = $string.comb; # 1 2 3 4 5 6 7 8 9

Then, you need an idea. My idea is to generate a sequence of numbers from 0 to 3⁸ and present them as numbers in base 3. Here, 3 is the number of operators we want: +, -, and no operation (or concatenation). 8 is the number of such positions (one less than the length of the string).

my $len = $string.chars - 1;
my $span = 3 ** $len;

Now, prepare the sequences of operators:

for ^$span {
    my $mask = $_.base(3).fmt('%0' ~ $len ~ 'd');
    my @signs = $mask.trans('0' => ' ', '1' => '+', '2' => '-').comb;

    . . .
}

Inside the loop body, the $mask variable and the @signs array pass through the following combinations:

00000000 =>                
00000001 =>               +
00000002 =>               -
00000010 =>             +  
00000011 =>             + +
00000012 =>             + -
00000020 =>             -  
00000021 =>             - +
00000022 =>             - -
00000100 =>           +    
00000101 =>           +   +
00000102 =>           +   -
. . .
12111121 => + - + + + + - +
12111122 => + - + + + + - -
12111200 => + - + + + -    
12111201 => + - + + + -   +
12111202 => + - + + + -   -
12111210 => + - + + + - +  
12111211 => + - + + + - + +
12111212 => + - + + + - + -
. . .
22222122 => - - - - - + - -
22222200 => - - - - - -    
22222201 => - - - - - -   +
22222202 => - - - - - -   -
22222210 => - - - - - - +  
22222211 => - - - - - - + +
22222212 => - - - - - - + -
22222220 => - - - - - - -  
22222221 => - - - - - - - +
22222222 => - - - - - - - -

Having this done, the rest is straightforward. Zip the two arrays and remove the spaces. (The space in @signs is required to keep the length of this array constant. If you replace 0 with an empty string: '0' => '', you get less positions and some digits will be skipped.)

my $expr = zip(@nums, @signs).flat.join('') ~ @nums[*-1];
$expr ~~ s:g/' '//;

Evaluate the expression and wait until it gives the desired result:

say $expr if EVAL($expr) == 100;

That’s it.

The program finds all the 11 possible solutions:

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

For the reference, here is the whole program, which you can also find on GitHub.

use MONKEY-SEE-NO-EVAL;

my $string = '123456789';

my @nums = $string.comb;

my $len = $string.chars - 1;
my $span = 3 ** $len;

for ^$span {
    my $mask = $_.base(3).fmt('%0' ~ $len ~ 'd');
    my @signs = $mask.trans('0' => ' ', '1' => '+', '2' => '-').comb;

    my $expr = zip(@nums, @signs).flat.join('') ~ @nums[*-1];
    $expr ~~ s:g/' '//;

    say $expr if EVAL($expr) == 100;
}

P. S. In Raku, you must confirm that you are using EVAL by adding the use MONKEY-SEE-NO-EVAL; instruction. You may also notice that evaluating the expression so many times is relatively slow (1.5 minutes for the given input). To speed it up, you may try implementing the loop to go through the arrays and to perform the operations directly in the code.

→ Navigation to the Raku challenges post series