TL;DR

On with TASK #2 from The Weekly Challenge #223. Enjoy!

# The challenge

You are given an array representing box coins, @box.

Write a script to collect the maximum coins until you took out all boxes. If we pick box[i] then we collect the coins $box[i-1] *$box[i] * $box[i+1]. If $box[i+1] or $box[i-1] is out of bound then treat it as 1 coin. Example 1: Input: @box = (3, 1, 5, 8) Output: 167 Step 1: pick box [i=1] and collected coins 3 * 1 * 5 => 15. Boxes available (3, 5, 8). Step 2: pick box [i=1] and collected coins 3 * 5 * 8 => 120. Boxes available (3, 8). Step 3: pick box [i=0] and collected coins 1 * 3 * 8 => 24. Boxes available (8). Step 4: pick box [i=0] and collected coins 1 * 8 * 1 => 8. No more box available.  Example 2: Input: @box = (1, 5) Output: 10 Step 1: pick box [i=0] and collected coins 1 * 1 * 5 => 5. Boxes available (5). Step 2: pick box [i=0] and collected coins 1 * 5 * 1 => 5. No more box available.  # The questions This definitely sounds like an interview puzzle question, which might mean that we can propose a very basic and brute-force solution, then weasel out with a lot of possible ways of investigating further. Well, I donâ€™t know, I never did an interview for a programmer job. Anyway, the brute-force approach is fantastic for small inputs, and anything else is a waste of time right? Then, coming to the questions: • how many elements are we expecting to receive in the box? • do we have constraints on computing power? # The solution Assuming that the answer to the first question is a handful, itâ€™s perfectly fine to go with a brute-force approach, which in this case has a disastrous factorial complexity. Ugh. But even in case we have to go for something more optimized, it still makes a lot of sense to code the brute-force solution, to be used as our reference for checking results of more clever solutions. This is because cleverness might often hideâ€¦ dumb bugs. So, even as a tool of investigation, hereâ€™s the Perl solution for the brute-force approach, filled with investigation hints to show us the process in addition to the result: #!/usr/bin/env perl use v5.24; use warnings; use experimental 'signatures'; use Data::Dumper; my ($best, $trail) = box_coins(@ARGV); say {*STDERR} Dumper($trail);
say $best; sub box_coins (@box) { local$" = ' ';

return (0, []) unless @box;
return ($box[0], [{input => "(@box)", take => 0, score =>$box[0], left => '()'}])
if @box == 1;

my $best = 0; my$trail = [];
my @pre;
my @post = @box;
while (@post) {
my $item = shift @post; my ($run, $windown) = __SUB__->(@pre, @post); my$val = (@pre ? $pre[-1] : 1) *$item * (@post ? $post[0] : 1);$run += $val; if ($run > $best) {$best  = $run;$trail = [
{
input => "(@box)",
take  => scalar(@pre),
score => $val, left => "(@{[@pre, @post]})", },$windown->@*
];
} ## end if ($run >$best)
push @pre, $item; } ## end while (@post) return ($best, $trail); } ## end sub box_coins  Itâ€™s as dumb as it could get: for a give box, try to focus on each item individually, then keep the result for the best of them. This involves recurring, with __SUB__. The solution would be much more compact without all the investigation tooling, like this one in Raku that only gets us the result: #!/usr/bin/env raku use v6; sub MAIN (*@args) { put box-coins(@args) } sub box-coins ($box) {
return 0 unless $box.elems; return$box[0] if $box.elems == 1; my @pre; my @post = @$box;
return max gather while @post {
my $item = @post.shift; take samewith([|@pre, |@post]) + (@pre ?? @pre[*-1] !! 1) *$item * (@post ?? @post[0] !! 1);
@pre.push: \$item;
}
}


At this point, if a more efficient solution is needed, there are some ideas that might be investigated further:

• from a crude implementation point of view, memoizing the solutions might give a good boost. The same arrangement might be investigated multiple times, e.g. consider that starting from (A, B, C, D)", we might try to get A at one level and C at the following one, or the other way around. In both cases, we're left with (B, D)` to analyze. On the other hand, we have to take care not to eat up all the available memory!

• My initial thought is that big values should stay in the box as long as possible, but this is not a universal take and the challenge example makes it very clear (we take the 5 before the 3). There might still be something to understand better though.

OK, enough for todayâ€¦ stay safe!

Comments? Octodon, , GitHub, Reddit, or drop me a line!