Task — Magic expression

You are given a string containing only digits and a target integer. Write a script to insert binary operators +, - and * between the digits in the given string that evaluates to target integer.

Examples

Example 1
Input: $str = '123', $target = 6
Output: ('1*2*3', '1+2+3')

Example 2
Input: $str = '105', $target = 5
Output: ('1*0+5', '10-5')

Example 3
Input: $str = '232', $target = 8
Output: ('2*3+2', '2+3*2')

Example 4
Input: $str = '1234', $target = 10
Output: ('1*2*3+4', '1+2+3+4')

Example 5
Input: $str = '1001', $target = 2
Output: ('1+0*0+1', '1+0+0+1', '1+0-0+1', '1-0*0+1',
   '1-0+0+1', '1-0-0+1')

Analysis

I could see no obvious way to do this other than to try inserting each variation of 4 operators between each pair of numbers in $str. These 4 operators are the given +, - and * and also null, which has the effect of concatenating the digits on either side.

To generate these variations I used nmy favourite module Algorithm::Combinatorics, selecting the method variations_with_repetition, which generates exactly what is needed.

It's then just a case of using eval() to evaluate the resulting string as an expression, and comparing it to $target.

An additional condition derived from the examples is that numbers with leading zeroes are not allowed, otherwise example 2 above would allow 1 + 05 as an answer. So there is an additional line in my code to reject those.

This solution works fast enough up to around a 9 digit target, after which it get progressively slower.

Try it 

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2025-11-03
use utf8;     # Week 346 - task 2 - Magic expression
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Encode;
use Algorithm::Combinatorics 'variations_with_repetition';

magic_expression(123, 6);
magic_expression(105, 5);
magic_expression(232, 8);
magic_expression(1234, 10);
magic_expression(13579, 115);
magic_expression(314159265, 868140);

sub magic_expression {
    
    my (@ints, $target, $gaps, @ops, $iterator, $p, $trial, $g, $value, $output);
    
    # initialise
    @ints = split('', $_[0]);
    $target = $_[1];
    $gaps = $#ints;
    @ops = (' + ', ' - ', ' * ', '');
    $output = '';
    
    # loop over variations of @ops
    $iterator = variations_with_repetition([0, 1, 2, 3], $gaps);
    while ($p = $iterator->next) {
        
        # create string of digits with every perm of @ops
        $trial = '';
        for $g (0 .. $gaps - 1) {
            $trial .= $ints[$g] . $ops[$p->[$g]];
        }
        $trial .= $ints[$gaps];
        
        # eliminate ones containing leadng 0s eg 05
        next if $trial =~ m{( 0\d|\(0\d)};
        
        # evaluate the string and see if it matches $target
        $value = eval($trial);
        next unless $value == $target;
        
        # it does
        $output .= qq[($trial), ];
    }
        
    say qq[\nInput:  \$str = '$_[0]', \$target = $target];
    say qq[Output: \$output = ] . ($output ? substr($output, 0, -2) : 'not possible');
}

Output

Input:  $str = '123', $target = 6
Output: $output = (1 + 2 + 3), (1 * 2 * 3)

Input:  $str = '105', $target = 5
Output: $output = (1 * 0 + 5), (10 - 5)

Input:  $str = '232', $target = 8
Output: $output = (2 + 3 * 2), (2 * 3 + 2)

Input:  $str = '1234', $target = 10
Output: $output = (1 + 2 + 3 + 4), (1 * 2 * 3 + 4)

Input:  $str = '13579', $target = 115
Output: $output = (1 + 3 * 5 * 7 + 9), (1 + 35 + 79)

Input:  $str = '314159265', $target = 868140
Output: $output = (3 * 14 * 159 * 2 * 65),
   (3 * 14 * 159 * 26 * 5)