Task 1: Only 100 / Insert Operators
Write a script to insert operators + or - in a string of digits e.g. 123456789 to evaluate to a target value of 100.
Example Output
1+2+3-4+5+6+78+9
12+3-4+5+67+8+9
123+4-5-6-7-8-9...
Logic
Use a recursive backtracking helper function. At each step, choose a chunk of digits, insert either a + or - before it, and recurse on the remaining digits. Once the entire string is processed, evaluate the expression and compare it to the target.
Perl Solution
ch-1.pl
sub helper {
my ( $str, $target, $expr, $results ) = @_;
if ( $str eq "" ) {
if ( eval($expr) == $target ) {
push @$results, $expr;
}
return;
}
for my $i ( 1 .. length($str) ) {
my $left = substr( $str, 0, $i );
my $right = substr( $str, $i );
helper( $right, $target, "$expr+$left", $results );
helper( $right, $target, "$expr-$left", $results );
}
}
Python Solution
ch-1.py
def insert_operators(s, target):
results = []
def helper(s, expr):
if not s:
if eval(expr) == target:
results.append(expr)
return
for i in range(1, len(s) + 1):
left, right = s[:i], s[i:]
helper(right, expr + "+" + left)
helper(right, expr + "-" + left)
helper(s, "")
return results
Task 2: Make it $200
You start with $1. You can either double the current amount or add $1. Find the minimum number of moves to reach exactly $200.
Example Output
To reach $200, you need 9 moves.
Logic
Determine the optimal strategy by working backwards or checking if doubling the current amount keeps the remaining value reachable by additions without overshooting.
Perl Solution
ch-2.pl
while ( $current < $goal ) {
if ( $current * 2 <= $goal - $current - 1 ) {
$current *= 2;
}
else {
$current += 1;
}
$moves += 1;
}
Python Solution
ch-2.py
while current < goal:
if current * 2 <= goal - current - 1:
current *= 2
else:
current += 1
moves += 1