From 100 to 200 with Raku

This is my response to the Perl Weekly Challenge #41.

Challenge #44.1: Only 100, please

We cannot place a «+» or «-» between every digit, as that would give a maximum value of 45 (try «[+] 1..9» or «(1..9).sum»). So we can have 1 or more digits after each other, before the «+» or «-» sign.

Another way of putting that, is that we can have one of these three characters between each digit (marked with «OP» in the illustration): «+» (plus), «-» (minus) and «» (an empty string),

Choosing between three choices is suitable for a number in the ternary numeral system (also called base 3), where each digit can have one of the three values 0, 1 and 2.

We need all the ternary numbers with 8 digits (from 00000000 to 22222222), for placement in the 8 «OP» boxes in the illustration. This is easy'ish:

for ^Inf                             # [1]
{
  my $value = .base(3).fmt('%08d');  # [2]

  last if $value.chars > 8;          # [3]

  say $value;                        # [4]
}

[1] From 0 to infinity, as decimal numbers.

[2] Convert the number to ternary (with «base(3)»), and add leading spaces (with «fmt('%08d')») so that the length is 8 characters.

[3] Stop when we get the first ternary number with 9 digits.

[4] Print it.

The output is too long to show (6561 lines, and that is the same as «3 ** 8»), but here is a sample to show that indeed it works:

$ raku ternary8
00000000
00000001
00000002
00000010
00000011
00000012
00000020
00000021
00000022
00000100
00000101
...
22222220
22222221
22222222

The next step is translating the individual digits in the ternary number; 0 to an empty string, 1 to a plus sign, and 2 to a minus sign:

sub conv ($char)
{
  return ""  if $char eq "0";
  return "+" if $char eq "1";
  return "-" if $char eq "2";
}

The full program:

use MONKEY-SEE-NO-EVAL;                        # [6b]

unit sub MAIN (:$verbose, :$all);              # [1] [7a]

my $input = "123456789";                       # [3]

for ^Inf                                       # [4]
{
  my $ternary = .base(3).fmt('%08d');          # [4]

  last if $ternary.chars > 8;                  # [4]

  print ": $input ~ $ternary" if $verbose;     # [1a]

  my $string = (roundrobin $input.comb,        # [5]
                           $ternary.comb.map({ conv($_) })
               ).flat.join;

  say " -> $string" if $verbose;               # [1b]

  if (EVAL $string) == 100                     # [6]
  {
    say "100 == $string";                      # [6a]
    exit unless $all;                          # [7]
  }
}

sub conv ($char)
{
  return ""  if $char eq "0";                  # [2]
  return "+" if $char eq "1";                  # [2]
  return "-" if $char eq "2";                  # [2]
}

[1] Verbose mode gives us a list of the starting number [1a], the current ternary number [1a], and the result when we merge them [1b].

The first 7 lines look like this:

$ raku 100 --verbose
: 123456789 ~ 00000000 -> 123456789
: 123456789 ~ 00000001 -> 12345678+9
: 123456789 ~ 00000002 -> 12345678-9
: 123456789 ~ 00000010 -> 1234567+89
: 123456789 ~ 00000011 -> 1234567+8+9
: 123456789 ~ 00000012 -> 1234567+8-9
: 123456789 ~ 00000020 -> 1234567-89
...

[2] The ternary digit «0» results in an empty string, «1» gives «+», and «2» gives «-».

[3] The starting number.

[4] For each 8 digit ternary number,

[5] Generate the string as shown after the «->» in the verbose output above. «roundrobbin» is a «zip» variant that tackles different length of the two arrays, when it merges them, generating pairs with one from each array. E.g.

> say <1 2 3 4 5 6 7 8 9> Z <a b c d e f g h>;     # infix operator
((1 a) (2 b) (3 c) (4 d) (5 e) (6 f) (7 g) (8 h))
	
> say zip(<1 2 3 4 5 6 7 8 9>, <a b c d e f g h>); # procedure
((1 a) (2 b) (3 c) (4 d) (5 e) (6 f) (7 g) (8 h))

> say roundrobin(<1 2 3 4 5 6 7 8 9>, <a b c d e f g h>);
((1 a) (2 b) (3 c) (4 d) (5 e) (6 f) (7 g) (8 h) (9))

Both «Z» and «zip» ignore the last digit (9, the 9th element), as the right hand side has only 8 elements. «roundrobin» handles it.

The result is a list of lists, and we apply «flat» to turn it into a one dimentional list. And finally, «join» turns that list into a string.

> say roundrobin(<1 2 3 4 5 6 7 8 9>, <a b c d e f g h>).flat;
(1 a 2 b 3 c 4 d 5 e 6 f 7 g 8 h 9)
	
> say roundrobin(<1 2 3 4 5 6 7 8 9>, <a b c d e f g h>).flat.join;
1a2b3c4d5e6f7g8h9

The left hand side is a list of digits in the input value 123456789, which we get with «$input.comb». The right hand side is a list of operators (plus, minus) or empty strings. We start with the ternary number as list of digits with «$ternary.comb», converts the numbers to the strings with «map({ conv($_) })». Both lists are fed to «roundrobin», and the result is the aforementioned string.

[6] Then we feed that string to «EVAL» for evaluation, as this will execute the content of the string as program code. Note that this is a potential security nightmare, so we have to enable it explicitly with the «use MONKEY-SEE-NO-EVAL» pragma (in [6b]). If the result is 100, we have a winner. Say so [6a].

[7] Exit after reporting the first result, unless we have used the «--all» [7a] command line option to indicate that we want them all.

Running it:

$ raku 100
100 == 123+45-67+8-9

Verbose mode, abridged:

$ raku 100 --verbose
: 00000000 -> 123456789
: 00000001 -> 12345678+9
: 00000002 -> 12345678-9
: 00000010 -> 1234567+89
: 00000011 -> 1234567+8+9
: 00000012 -> 1234567+8-9
: 00000020 -> 1234567-89
: 00000021 -> 1234567-8+9
: 00000022 -> 1234567-8-9
...
: 00101221 -> 123+45+6-7-8+9
: 00101222 -> 123+45+6-7-8-9
: 00102000 -> 123+45-6789
: 00102001 -> 123+45-678+9
: 00102002 -> 123+45-678-9
: 00102010 -> 123+45-67+89
: 00102011 -> 123+45-67+8+9
: 00102012 -> 123+45-67+8-9
100 == 123+45-67+8-9

There are 11 different solutions:

$ raku 100 --all
100 == 123+45-67+8-9
100 == 123+4-5+67-89
100 == 123-45-67+89
100 == 123-4-5-6-7+8-9
100 == 12+3+4+5-6-7+89
100 == 12+3-4+5+67+8+9
100 == 12-3-4+5-6+7+89
100 == 1+23-4+56+7+8+9
100 == 1+23-4+5+6+78-9
100 == 1+2+34-5+67-8+9
100 == 1+2+3-4+5+6+78+9

Challenge #44.2: Make it $200

If we assume that greed is allowed, we can simply go for the highest amount equal to or greater than 200 we can get with the smallest number of steps. That is done by doubling the values:

my $money = 1;

for 1 .. Inf -> $move
{
  $money *= 2;
  if $money >= 200
  {
    say "Amount $money after $move moves.";
    last;
  }
}

The program shouldn't need any explanation.

Running it:

$ raku 256
Amount 256 after 8 moves.

If you find the value 256 familiar, it is beacasue it is the number of different values representable by an 8-bit number.

That was too easy. I do think that the challenge wants us to stop at the exact value 200, and that is much harder.

I thought about sequences and recursive procedures, but settled on the same approach as in the first challenge; using a number. In this case the action is either double («*») or add-one («+»), so a binary number is sufficient.

A hand coded example. It may or may not be the shortest:

Note that this one used 10 steps to arrive at $200, two more than the money grabbing version which gave us a whopping $256.

I'll generate binary numbers from 1 and up, and use multiplication if the digit is 1, and addition otherwise (when the digit is 0).

I'll start with sample verbose output (with manually added tabulation to make it look nicer), and explain from that:

$ raku 200 --verbose
:  0 ->     0  |     + ->  2
:  1 ->     1  |     * ->  2
:  2 ->    10  |    *+ ->  3
:  3 ->    11  |    ** ->  4
:  4 ->   100  |   *++ ->  4
:  5 ->   101  |   *+* ->  6
:  6 ->   110  |   **+ ->  5
:  7 ->   111  |   *** ->  8
:  8 ->  1000  |  *+++ ->  5
:  9 ->  1001  |  *++* ->  8
: 10 ->  1010  |  *+*+ ->  7
: 11 ->  1011  |  *+** -> 12
: 12 ->  1100  |  **++ ->  6
: 13 ->  1101  |  **+* -> 10
: 14 ->  1110  |  ***+ ->  9
: 15 ->  1111  |  **** -> 16
: 16 ->  10000 | *++++ ->  6

The first value is the decimal number (from 0 to Infinity). The next value is the same one, in binary. The string following is this binary number converted to the operators (0 gives «+», and 1 gives «*»), and the final number is the result of applying the operators (one after each other).

Note that the first operation can be either «+» (plus) or «*» (multiplication), but that gives the same result (as 1+1 == 1*2 == 2). My algorithm will always choose multiplication, as I haven't added leading zeroes to the value (as I did in Challenge #44.1). But this doesn't affect the result.

Note that the first numbers are way too low, so I could have saved some time by starting from a higher value than 0. The problem is choosing that value, which we really cannot do before looking at the verbose output above. By then we have a working program, and it felt OK to leave the starting value. The extra calculations take some time, but not that much. (The lowest decimal value is actually 256, which we saw in the program with the same name. We could perhaps have guessed, but it would have been a guess.)

The program:

unit sub MAIN (:$verbose, :$infinite);     # [16] [21]

my $lowest-match = Inf;                    # [1]

my %found;                                 # [2]

for ^Inf                                   # [3]
{
  my $binary = .base(2);                   # [4]

  print ": $_ -> $binary " if $verbose;    # [22]

  my $val  = 1;                            # [5]
  my $path = "";                           # [6]
  
  for $binary.comb -> $digit               # [7]
  {
    $digit == 1                            # [8]
      ?? ( $val += $val; $path ~= "*" )    # [8a]
      !! ( $val += 1;    $path ~= "+" );   # [8b]

    last if %found{$path};                 # [9]

    say " | $path -> $val" if $val >= 200 && $verbose;              # [23]

    if $val == 200                         # [10]
    {
      %found{$path} = True;                # [11]

      say "Match: $val at { $path.chars } steps (path: $path).";    # [12]

      $lowest-match = $path.chars;         # [13]

      if $verbose                          # [24]
      { 
        my $curr = 1;                      # [25]
	my $step = 1;                      # [26]
	say ": Initial value: 1";          # [27]
        for $path.comb -> $operator        # [28]
	{
          $operator eq "+" ?? ( $curr += 1 ) !! ( $curr += $curr ); # [29]
	  say ": Step { $step++ }: $operator -> $curr";             # [30]
        }
      }
    }

    last if $val >= 200;                                            # [14]

    exit if !$infinite && $path.chars > $lowest-match;              # [15]
  }
  
  say " | $path -> $val" if  $val < 200 && $verbose;                # [31]
}

Comments 21 to 31 deal with verbose mode. Ignore them for now.

[1] The lowest number of steps before we get a result (arrive at 200). The initial value is Inf, so that the first match will be lower - regardless of the actual value.

[2] We collect the paths (the strings with +/*) where the result is 200.

[3] For all the integers from 0 to Infinity,

[4] • convert the number to binary (base 2).

[5] The value starts with 1.

[6] The path is empty before we add plusses and/or stars. We need this to show how we arrived at the number.

[7] We iterate over the binary digits.

[8] • If it is 1, we double the value - and add «*» to the path.

[9] • If not (i.e. it is 0), we add 1 to the value - and add «+» to the path.

[10] If the value is 200,

[11] • save the path. (The idea is that if we have a match at e.g. «101010» a future iteration over «10101010» will be stopped when it reaches 200 before considering the two extra digits.)

[12] • Show the match (number of steps, and the path).

[13] Note this as the lowest match.

[14] If the current value is > 200, we have missed the target and can abort this number (and any remaining binary digits).

[15] Exit the program if the number of steps («$path.chars») is larger than the shortest match («$lowest-match»). See [16] for an explanation of the «!$infinite» part.

Running it:

$ raku 200 
Match: 200 at 9 steps (path: *+***+***).

Note that the functionality in [1], [2] and [15] is there to stop the program from showing solutions that are longer than the shortest answer. If there are more with the same (shortest) length, all will be shown. But as the program output shows, there is only one result.

[16] We can ask the program to go on, after finding a match with the «--infinite» command line option. The program will go on indefinitely (by disabling the conditional «exit» in [15]), so you must kill it off manually when you get tired of it.

$ raku 200 --infinite
Match: 200 at  9 steps (path: *+***+***).
Match: 200 at 10 steps (path: *+****++**).
Match: 200 at 10 steps (path: **++**+***).
Match: 200 at 11 steps (path: *++++**+***).
Match: 200 at 11 steps (path: *+****+*++*).
Match: 200 at 11 steps (path: **++***++**).
Match: 200 at 11 steps (path: **+*++*+***).
Match: 200 at 12 steps (path: *++++***++**).
Match: 200 at 12 steps (path: *+++*++*+***).
Match: 200 at 12 steps (path: *+****+*+*++).
Match: 200 at 12 steps (path: *+*****++++*).
Match: 200 at 12 steps (path: **++***+*++*).
Match: 200 at 12 steps (path: **+*++**++**).
Match: 200 at 12 steps (path: **+*+*+++***).
Match: 200 at 12 steps (path: ***++++*+***).
Match: 200 at 13 steps (path: *++++***+*++*).
^C

(The longest match has 199 steps, all of which are «+».)

Verbose mode gives us this output (abridged):

$ raku 200 --verbose
: 0 -> 0  | + -> 2
: 1 -> 1  | * -> 2
: 2 -> 10  | *+ -> 3
: 3 -> 11  | ** -> 4
: 4 -> 100  | *++ -> 4
: 5 -> 101  | *+* -> 6
...
: 373 -> 101110101  | *+***+*+* -> 102
: 374 -> 101110110  | *+***+**+ -> 101
: 375 -> 101110111  | *+***+*** -> 200
Match: 200 at 9 steps (path: *+***+***).
: Initial value: 1
: Step 1: * -> 2
: Step 2: + -> 3
: Step 3: * -> 6
: Step 4: * -> 12
: Step 5: * -> 24
: Step 6: + -> 25
: Step 7: * -> 50
: Step 8: * -> 100
: Step 9: * -> 200
: 376 -> 101111000  | *+****+++ -> 51
: 377 -> 101111001  | *+****++* -> 100
: 378 -> 101111010  | *+****+*+ -> 99
...
: 510 -> 111111110  | ******** -> 256
: 511 -> 111111111  | ******** -> 256
: 512 -> 1000000000 

Note that the last line in the output doesn't end with a newline. That is not very nice, but I haven't bothered fixing it.

[21] Enable verbose mode with the «--verbose» command line argument.

[22] This prints the part before the «|» on the verbose output line.

[23] And this one prints the second part, if we have arrived at 200 or passed it. (If not, we have to do the next iteration before arriving there.)

[24] We have a match, show it more, er, verbose. (As shown after the «Match» line in the output above.)

[25] The current value.

[26] The number of steps.

[27] Show the initial value (which is «1»).

[28] Iterate over the characters in the path (the string with the stars and pluses).

[29] Do the calculation (multiplication or addition) depending in the operator.

[30] Print the step, the operator, and the new value.

[31] This one bails us out (print the second part) if we do not reach 200 in the «for» loop (in [7]), as that stops the second half from beeing printed in [23].

And that's it.