30 October 2026

Challenge 044

Several Hundreds

• Task 1: Only 100, please
• Task 2: Make it $200

Task 1: Only 100, please

You are given a string “123456789”. Write a script that would insert ”+” or ”-“ in between digits so that when you evaluate, the result should be 100.

---

Solution

Here is my solution dated 30 Mar 2023:

use Math::Prime::Util qw(forcomp todigits vecsum vecprod lastfor);
use List::MoreUtils qw(zip6 zip);
use experimental 'signatures';

sub combine_to ($digits, $sum) {
    my $len = length $digits;
    my @out;
    # Iterate over integer compositions.
	forcomp {
        # Split the digits into parts according to the current
        # composition.
        my @parts = $digits =~ /^@{[join('', map "(.{$_})", @_)]}$/;
        # Loop over the signs for all but the first part (having a fixed
        # sign of +1), represented by a number with the first bit of one
        # in its binary representation.
        for my $sb (2 ** (@_ - 1) .. 2 ** @_ - 1) {
            # Convert number to signs.
            my @signs = map $_ ? 1 : -1, todigits $sb, 2, @_;
            # Multiply all parts with their sign and sum.  Report a
            # match.
            if (vecsum(map vecprod(@$_), zip6 @parts, @signs) == $sum) {
                # Convert 1/-1 to +/- removing the first.
                my @ops = (map(chr(44 - $_), @signs[1..$#signs]), '');
                push @out, "@{[zip @parts, @ops]}= $sum";
            }
        }
    } $len, {amax => $len - 1};
    @out;
}

See the full solution to task 1.

Task 2: Make it $200

You have only $1 left at the start of the week. You have been given an opportunity to make it $200. The rule is simple with every move you can either double what you have or add another $1. Write a script to help you get $200 with the smallest number of moves.

---

Solution

Consider an arbitrary number \(n\) as the target.

There is a short and a long solution to this task.

The number of steps to reach \(n\) cannot be smaller than \(\log_2 n\), where every step would be “double”. If \(n\) is not a power of \(2\), additional “add one” steps are required: one step for every but the leading \(1\) in \(n\)’s binary representation. Let \(\operatorname{bcnt}(n)\) be the number of \(1\)-bits in \(n\)’s binary representation. Then \(n\) can be reached with \(\lfloor \log_2 n\rfloor + \operatorname{bcnt}(n) - 1\) steps and there is no way to reach it with fewer steps. This is the short solution.

The long solution constructs the the steps:

• starting with \(n\), we subtract \(1\) if \(n\) is odd or we halve \(n\) otherwise
• stop when \(n = 1\)
• reverse the intermediate results for \(n\)

This is very similar to an algorithm that converts \(n\) to its binary representation.

Perl

Using unpack to count the one-bits.

use strict;
use warnings;
use experimental 'signatures';
use List::Gather;

sub make_it_long ($n) {
    reverse gather {
        while ($n) {
            take $n;
            $n = $n % 2 ? $n - 1 : $n / 2;
        }
    };
}

sub make_it_short ($n) {
    int(log($n) / log(2)) - 1 + unpack "%32b*", pack "I", $n;
}

See the full solution to task 2.

J

   make_it_long =: ([: |. ] , {{ (] [ 1 Z: 1&=) y }} F: (-:`<:@.(2&|))) : [:
   make_it_short =: <:@<.@(2&^.) + [: +/ #: : [:
   make_it_long 200
1 2 3 6 12 24 25 50 100 200
   make_it_short 200
9

See the full solution.