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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
|
#!/usr/bin/perl
use strict;
use warnings;
use English;
################################################################################
# Begin main execution
################################################################################
# The houses on multiple streets
my @streets = (
# Given cases
[ 2, 4, 5 ],
[ 4, 2, 3, 6, 5, 3 ],
# Additional test cases
[ 3, 9 ],
[ 4 ],
[ ],
# This one kind of shows the limitations
# of the starting condition...
[ 1, 50, 2, 3, 7, 4 ]
);
my $street;
print("\n");
foreach $street (@streets){
printf(
"The street with houses containing valuables: %s\n",
join(", ", @{$street})
);
printf(
" will yield a total of %d loot.\n\n",
calculate_loot_yield_on_street(@{$street})
);
}
print("DISCLAIMER: Do not actually rob houses- it's not nice!\n\n");
exit(0);
################################################################################
# End main execution; subroutines follow
################################################################################
################################################################################
# Determine the maximum amount of loot that can be gotten by robbing houses on
# a street, given certain parameters and restrictions, including a requirement
# to rob the first house on the street, and not to rob any two adjacent houses
# Takes one argument:
# * A list of the quantities of loot available in each house on the street
# Returns:
# * The maximum amount of loot that can be gotten within the restrictions
# specified, which will be zero (0) if the supplied list is empty
# Shamelessly adapted from an algorithm seen at:
# https://www.geeksforgeeks.org/find-maximum-possible-stolen-value-houses/
# DISCLAIMER: Do not actually rob houses- it's not nice!
################################################################################
sub calculate_loot_yield_on_street{
use List::Util qw(max);
# Empty list, no houses to rob
return(0)
unless(@ARG);
my @loot;
my $loot_initial;
my $i;
# We always start with the first house, as
# specified (though this seems limiting...)
$loot_initial = $ARG[0];
# Strip off the first two houses- we've
# robbed the first and can't rob the second
splice(@ARG, 0, 2);
# Edge cases- zero or one houses left
return($loot_initial)
unless(@ARG);
if(scalar(@ARG) == 1){
return($loot_initial + $ARG[0]);
}
# Proceed as normal(?)
$loot[0] = $ARG[0];
$loot[1] = max($ARG[0], $ARG[1]);
for($i = 2; $i < scalar(@ARG); $i++){
$loot[$i] = max($ARG[$i] + $loot[$i - 2], $loot[$i - 1]);
}
return($loot_initial + $loot[$#loot]);
}
|
