The Weekly Challenge 044

Insert Operators and Make $200

Solutions on GitHub

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