comment on

After a long time, I checked the list of tasks not implemented in Perl on RosettaCode. One of them was "Sum to 100", kind of similar to mjd's Simple but difficult arithmetic puzzle:

In the string 123456789, you can prepend + or - before any digit to form an expression. You should

list all the possible expressions that evaluate to 100
show the number that is a result of the maximal number of expressions
show the lowest positive number that can't be expressed
show the ten highest numbers that can be expressed

Here's my solution:

#!/usr/bin/perl
use warnings;
use strict;
use feature qw{ say };

my $string = '123456789';
my $length = length $string;
my @possible_ops = ("" , '+', '-');

{
    my @ops;
    sub Next {
        return @ops = (0) x ($length) unless @ops;

        my $i = 0;
        while ($i < $length) {
            if ($ops[$i]++ > $#possible_ops - 1) {
                $ops[$i++] = 0;
                next
            }
            # + before the first number
            next if 0 == $i && '+' eq $possible_ops[ $ops[0] ];

            return @ops
        }
        return
    }
}

sub evaluate {
    my ($expression) = @_;
    my $sum;
    $sum += $_ for $expression =~ /([-+]?[0-9]+)/g;
    return $sum
}

my %count = ( my $max_count = 0 => 0 );

say 'Show all solutions that sum to 100';

while (my @ops = Next()) {
    my $expression = "";
    for my $i (0 .. $length - 1) {
        $expression .= $possible_ops[ $ops[$i] ];
        $expression .= substr $string, $i, 1;
    }
    my $sum = evaluate($expression);
    ++$count{$sum};
    $max_count = $sum if $count{$sum} > $count{$max_count};
    say $expression if 100 == $sum;
}

say 'Show the sum that has the maximum number of solutions';
say "sum: $max_count; solutions: $count{$max_count}";

my $n = 1;
++$n until ! exists $count{$n};
say "Show the lowest positive sum that can't be expressed";
say $n;

say 'Show the ten highest numbers that can be expressed';
say for (sort { $b <=> $a } keys %count)[0 .. 9];
[download]

I tried to avoid eval to evaluate the expressions, at the same time, I didn't want to implement the traditional full math expression parser as there were only two operations of the same precedence in use.

$sum += $_ for $expression =~ /([-+]?[0-9]+)/g;
[download]

Feel free to comment on perlishness, effectiveness, golfness, or beauty of the solution, or propose your own.

Note: Those interested in Perl 6 can read the solution just below mine.

($q=q:Sq=~/;[c](.)(.)/;chr(-||-|5+lengthSq)`"S|oS2"`map{chr |+ord
}map{substrSq`S_+|`|}3E|-|`7**2-3:)=~y+S|`+$1,++print+eval$q,q,a,
[download]

In reply to Sum to 100 at Rosetta Code by choroba

Are you posting in the right place? Check out Where do I post X? to know for sure.
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
Want more info? How to link or How to display code and escape characters are good places to start.


go ahead... be a heretic
	PerlMonks