The weekly challenge 223 - Task 2: Box Coins

 1 #!/usr/bin/perl
 2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-223/#TASK2
 3 #
 4 # Task 2: Box Coins
 5 # =================
 6 #
 7 # You are given an array representing box coins, @box.
 8 #
 9 # Write a script to collect the maximum coins until you took out all boxes. If
10 # we pick box[i] then we collect the coins $box[i-1] * $box[i] * $box[i+1]. If
11 # $box[i+1] or $box[i-1] is out of bound then treat it as 1 coin.
12 #
13 ## Example 1:
14 ##
15 ## Input: @box = (3, 1, 5, 8)
16 ## Output: 167
17 ##
18 ## Step 1: pick box [i=1] and collected coins 3 * 1 * 5 => 15.  Boxes available (3, 5, 8).
19 ## Step 2: pick box [i=1] and collected coins 3 * 5 * 8 => 120. Boxes available (3, 8).
20 ## Step 3: pick box [i=0] and collected coins 1 * 3 * 8 => 24.  Boxes available (8).
21 ## Step 4: pick box [i=0] and collected coins 1 * 8 * 1 => 8.   No more box available.
22 #
23 ## Example 2:
24 ##
25 ## Input: @box = (1, 5)
26 ## Output: 10
27 ##
28 ## Step 1: pick box [i=0] and collected coins 1 * 1 * 5 => 5. Boxes available (5).
29 ## Step 2: pick box [i=0] and collected coins 1 * 5 * 1 => 5. No more box available.
30 #
31 ############################################################
32 ##
33 ## discussion
34 ##
35 ############################################################
36 #
37 # To find the maximum, we basically try to take each index, collect the coins, and
38 # run recursively with what remains to find the maximum.
39 
40 use strict;
41 use warnings;
42 
43 box_coins(3, 1, 5, 8);
44 box_coins(1, 5);
45 
46 sub box_coins {
47    my @box = @_;
48    print "Input: (" . join(", ", @box) . ")\n";
49    print "Output: " . box_coins_recursive(@box) . "\n";
50 }
51 
52 sub box_coins_recursive {
53    my @box = @_;
54    my $elements = scalar(@box);
55    if($elements == 0) {
56       return 0;
57    }
58    if($elements == 1) {
59       return $box[0];
60    }
61    my $max = 0;
62    foreach my $index (0..$#box) {
63       my $prod = 1;
64       if($index > 0) {
65          $prod = $box[$index-1];
66       }
67       $prod *= $box[$index];
68       if($index < $#box) {
69          $prod *= $box[$index+1];
70       }
71       my $this = $prod + box_coins_recursive(@box[0..$index-1], @box[$index+1..$#box]);
72       $max = $this if $this > $max;
73    }
74    return $max;
75 }