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!