Counting primes and

maximising cash

Weekly challenge 223 — 26 June 2023

Week 223 - 26 Jun 2023

Task 2

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.

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.

#!/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; }

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.

The content of this website which has been created by

Peter Campbell Smith is hereby placed in the public domain

Peter Campbell Smith is hereby placed in the public domain