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.

This post blends practical implementation knowledge with sophisticated algorithms. Peter demonstrates a solid foundation in computer science and carefully weighs the pros and cons of various strategies.

This review may cover either or both challenges for this week.

Try it 

Try running the script with any input:

Your $str =

example: 314159265 (max 9 digits please)

Your $target =

example: 868140

⤡

#!/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');
}

19 lines of code

Output from script

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)