Task — Box coins

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.

Analysis

I had a little difficulty interpreting the challenge, although the examples do help to clarify it. The numbers in the boxes are not quite sums of money; rather you multiply them together in 3s and the result of that is a number of 'coins'. I'm not quite sure what this represents in real life, but then who said it had to.

It's another challenge which suggests recursion. I wondered about using the recursive closure technique advocated by Flavio Poletti, but decided I didn't have time to investigate it, although I think it might be more efficient.

Instead, I went with my tried and tested method of having a sub that took one step at a time, recursively calling itself for the next step and so on. The depth of recursion will be the number of boxes, but the number of times we have to descend to that depth is an alarmingly increasing number. My algorithm works in a few seconds for up to about 10 boxes, after which it gets rather tedious.

After giving it some thought I could not think of an easy way of improving performance by predicting the best order to pick the boxes, but maybe someone else will.

Try it 

#!/usr/bin/perl

use v5.16;    # The Weekly Challenge - 2023-06-26
use utf8;     # Week 223 task 2 - Box coins
use strict;   # Peter Campbell Smith
use warnings; # Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

my ($max_cash, $best_explain);

box_coins(3, 1, 5, 8);
box_coins(1, 5);
box_coins(3, 8, 6, 9, 2, 4, 5, 9, 2);

sub box_coins {
    
    my (@boxes, $step);
    
    # initialise
    @boxes = @_;
    $step = 1;
    $max_cash = 0;
    $best_explain = '';
    
    # start first step
    make_step($step, \@boxes, 0, '');
    
    # display result
    say qq[\nInput:  \@box = (] . join(', ', @boxes) . q[)];
    say qq[Output: $max_cash\n$best_explain];
}

sub make_step {
    
    my ($step, $boxes, $cash, $explain, $last, $j, $coin1, $coin2, $coin3,
        $new_cash, $new_explain, $b, @new_boxes);

    # initialise
    ($step, $boxes, $cash, $explain) = @_;
    $last = scalar @$boxes - 1;

    # loop over picked box
    for ($j = 0; $j <= $last; $j ++) {
        
        # get 3 sets of coins and calculate gain
        $coin1 = $j != 0 ? $boxes->[$j - 1] : 1;
        $coin2 = $boxes->[$j];
        $coin3 = $j != $last ? $boxes->[$j + 1] : 1;
        $new_cash = $coin1 * $coin2 * $coin3;
        
        # explain results
        $new_explain = qq[Step $step: pick box [i=$j] and ];
        $new_explain .= qq[collect coins $coin1 * $coin2 * $coin3 => $new_cash.\n];
        
        # take another step
        if ($last > 0) {
            @new_boxes = ();
            for ($b = 0; $b <= $last; $b ++) { 
                push @new_boxes, $boxes->[$b] if $b != $j;
            }
            $new_explain .= qq[   Boxes remaining (] . join(', ', @new_boxes) . qq[).\n];
            make_step($step + 1, \@new_boxes, $cash + $new_cash, $explain . $new_explain);

        # reached bottom of recursion
        } else {
            $cash += $new_cash;
            if ($cash > $max_cash) {
                $max_cash = $cash;
                $best_explain = $explain . $new_explain . qq[   No boxes remaining.];
            }
        }
    }
    return;
}

Output

Input:  @box = (3, 1, 5, 8)
Output: 167
Step 1: pick box [i=1] and collect coins 3 * 1 * 5 => 15.
   Boxes remaining (3, 5, 8).
Step 2: pick box [i=1] and collect coins 3 * 5 * 8 => 120.
   Boxes remaining (3, 8).
Step 3: pick box [i=0] and collect coins 1 * 3 * 8 => 24.
   Boxes remaining (8).
Step 4: pick box [i=0] and collect coins 1 * 8 * 1 => 8.
   No boxes remaining.

Input:  @box = (1, 5)
Output: 10
Step 1: pick box [i=0] and collect coins 1 * 1 * 5 => 5.
   Boxes remaining (5).
Step 2: pick box [i=0] and collect coins 1 * 5 * 1 => 5.
   No boxes remaining.

Input:  @box = (3, 8, 6, 9, 2, 4, 5, 9, 2)
Output: 2016
Step 1: pick box [i=2] and collect coins 8 * 6 * 9 => 432.
   Boxes remaining (3, 8, 9, 2, 4, 5, 9, 2).
Step 2: pick box [i=3] and collect coins 9 * 2 * 4 => 72.
   Boxes remaining (3, 8, 9, 4, 5, 9, 2).
Step 3: pick box [i=3] and collect coins 9 * 4 * 5 => 180.
   Boxes remaining (3, 8, 9, 5, 9, 2).
Step 4: pick box [i=3] and collect coins 9 * 5 * 9 => 405.
   Boxes remaining (3, 8, 9, 9, 2).
Step 5: pick box [i=2] and collect coins 8 * 9 * 9 => 648.
   Boxes remaining (3, 8, 9, 2).
Step 6: pick box [i=1] and collect coins 3 * 8 * 9 => 216.
   Boxes remaining (3, 9, 2).
Step 7: pick box [i=1] and collect coins 3 * 9 * 2 => 54.
   Boxes remaining (3, 2).
Step 8: pick box [i=1] and collect coins 3 * 2 * 1 => 6.
   Boxes remaining (3).
Step 9: pick box [i=0] and collect coins 1 * 3 * 1 => 3.
   No boxes remaining.