The weekly challenge 346 - Task 2: Magic Expression

 1 #!/usr/bin/env perl
 2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-346/#TASK2
 3 #
 4 # Task 2: Magic Expression
 5 # ========================
 6 #
 7 # You are given a string containing only digits and a target integer.
 8 #
 9 # Write a script to insert binary operators +, - and * between the digits in
10 # the given string that evaluates to target integer.
11 #
12 ## Example 1
13 ##
14 ## Input: $str = "123", $target = 6
15 ## Output: ("1*2*3", "1+2+3")
16 #
17 #
18 ## Example 2
19 ##
20 ## Input: $str = "105", $target = 5
21 ## Output: ("1*0+5", "10-5")
22 #
23 #
24 ## Example 3
25 ##
26 ## Input: $str = "232", $target = 8
27 ## Output: ("2*3+2", "2+3*2")
28 #
29 #
30 ## Example 4
31 ##
32 ## Input: $str = "1234", $target = 10
33 ## Output: ("1*2*3+4", "1+2+3+4")
34 #
35 #
36 ## Example 5
37 ##
38 ## Input: $str = "1001", $target = 2
39 ## 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")
40 #
41 ############################################################
42 ##
43 ## discussion
44 ##
45 ############################################################
46 #
47 # We recursively build all possible strings with inserted operators. Then we
48 # evaluate these strings and keep the ones that calculate to the target.
49 
50 use v5.36;
51 
52 magic_expression("123", 6);
53 magic_expression("105", 5);
54 magic_expression("232", 8);
55 magic_expression("1234", 10);
56 magic_expression("1001", 2);
57 
58 sub magic_expression($str, $target) {
59     say "Input: '$str', $target";
60     my @parts = split //, $str;
61     my @result = find_magic_expressions($target, @parts);
62     say "Output: (\"" . join("\", \"", @result) . "\")";
63 }
64 
65 sub find_magic_expressions($target, $str, @list) {
66     my @result = ();
67     if(@list) {
68         foreach my $operator ("+", "-", "*", "") {
69             if($str =~ m/[-+*]0/ && $operator eq "") {
70                 next;
71             }
72             my $tmp_str = $str . $operator . $list[0];
73             push @result, find_magic_expressions($target, $tmp_str, @list[1..$#list]);
74         }
75     } else {
76         my $x;
77         eval "\$x = $str;";
78         if($x == $target) {
79             return ($str);
80         } else {
81             return ();
82         }
83     }
84     return @result;
85 }