more useful options PerlMonks

### comment on

 Need Help??
here another approach, it calculates the possible partial sums in %step with increasing possible \$delta.

the solutions are than printed by walking back from \$target to zero.

NB: it creates two kind of outputs, a tree with partial solutions and a result hash.

unfortunately this only works efficiently for unique deltas, I'll probably try to fix it tomorrow.

(or better leave it open for the interested reader ;)

```use strict;
use warnings;
use Data::Dump qw/pp dd/;
use Data::Dumper;

# --- input
my @input  = (1,99,2,40,50,60,90,3,5,95,100);
my \$target = 100;

my %steps = ( 0 => []);

# --- processing
my @deltas = sort { \$a <=> \$b } @input ;
for my \$delta ( @deltas ) {
for my \$last (keys %steps) {
my \$next = \$last + \$delta;
unshift @{\$steps{\$next}},\$last
if \$next <= \$target-\$delta    # \$delta grows!
or \$next == \$target;        # goal
}
#    pp \$delta, \%steps;
}

pp \%steps;

# --- output
my %free;
\$free{\$_}++ for @deltas;

our \$level = -1;

sub walk_back {
my (\$target,\$h_path)=@_;
local \$level = \$level +1;
for my \$last (@{\$steps{\$target}}) {
my \$delta = \$target-\$last;
next unless \$free{\$delta};
local \$free{\$delta} = \$free{\$delta}-1;
print "\t" x \$level , "+\$delta\n";
my \$sub_path = \$h_path->{\$delta} = {};
if ( \$last>0 ) {
walk_back(\$last,\$sub_path)
} else {
print "\n\n";
}
}
}

my %path;

walk_back(\$target,\%path);
pp \@deltas;
print Dumper \%path;

```
{
"0"   => [],
"1"   => [0],
"2"   => [0],
"3"   => [0, 1],
"4"   => [1],
"5"   => [0, 2],
"6"   => [1, 3],
"7"   => [2],
"8"   => [3],
"9"   => [4],
"10"  => [5],
"11"  => [6],
"40"  => [0],
"41"  => [1],
"42"  => [2],
"43"  => [3],
"44"  => [4],
"45"  => [5],
"46"  => [6],
"47"  => [7],
"48"  => [8],
"49"  => [9],
"50"  => [0, 10],
"51"  => [11],
"100" => [0, 1, 5, 10, 40, 50],
}
[1, 2, 3, 5, 40, 50, 60, 90, 95, 99, 100]
+100

+99
+1

+95
+5

+3
+2

+90
+5
+3
+2

+60
+40

+50
+40
+5
+3
+2

\$VAR1 = {
'99' => {
'1' => {}
},
'50' => {
'40' => {
'5' => {
'3' => {
'2' => {}
}
}
}
},
'95' => {
'5' => {},
'3' => {
'2' => {}
}
},
'100' => {},
'60' => {
'40' => {}
},
'90' => {
'5' => {
'3' => {
'2' => {}
}
}
}
};

Cheers Rolf
(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":

• Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
• Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
• Read Where should I post X? if you're not absolutely sure you're posting in the right place.
• Posts may use any of the Perl Monks Approved HTML tags:
a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
• You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
 For: Use: & & < < > > [ [ ] ]
• Link using PerlMonks shortcuts! What shortcuts can I use for linking?

Create A New User
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others imbibing at the Monastery: (4)
As of 2021-01-25 01:45 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
The STEM quote I most wish I'd made is:

Results (263 votes). Check out past polls.

Notices?