blob: 54043e40b076e14b9cd2bb805502e4f8efd636a2 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
Solutions by James Smith.
# Challenge 1 - Coins Sum
This is just begging for a recursive solution.
```perl
sub csm {
my $t = shift;
return @{$mem{"$t @_"}||=[map {my $a=$_; $t==$a?[$a]:
map {[$a,@{$_}]} csm($t-$a,grep {$a<=$_&&$_<=$t} @_)} @_] };
}
```
Notes:
* %mem is a memoisation cache as it helps to not need to re-compute higher totals more than once - speeds up searches for large coin sums... not essential but nice to have
How it works:
* Loop through all coin values available
* if the coin is the same as the amount required return a single array containing that value;
* if not remove that from the amount required and call again. For all values returned prepend the coin value to each array in the list
* when calling again remove any coins which are less than the "current coin" and greater than the amount required
Caveats & assumptions:
* No input checking is performed - assumes the options passed are all valid and greater than 0;
# Challenge 2 - Histogram rectangle
Much simpler this time.
First we get the size of the box (max value) and render chart then we look for the maximum rectangle size - which is computed as the maximum value of the distance between any two points (inclusive) multiplied by the lowest value in between the two values. (Maxi-min problem)
|
