diff options
| -rwxr-xr-x | challenge-151/wlmb/perl/ch-2.pl | 24 |
1 files changed, 15 insertions, 9 deletions
diff --git a/challenge-151/wlmb/perl/ch-2.pl b/challenge-151/wlmb/perl/ch-2.pl index 28fe08d2e2..34b6778e17 100755 --- a/challenge-151/wlmb/perl/ch-2.pl +++ b/challenge-151/wlmb/perl/ch-2.pl @@ -5,19 +5,25 @@ # See https://wlmb.github.io/2022/02/07/PWC151/#task-2-rob-the-house use v5.12; use warnings; +use Memoize; +memoize("optimize"); die "Usage: ./ch-1.pl V0 [V1]...\n" . "to optimize the robery of houses 0, 1,... with valuables V0, V1..." unless @ARGV; -my ($value,@houses)=optimize(0,@ARGV); -say "Output: $value Houses: ", join ", ", @houses; +my @values=@ARGV; +my ($value,@houses)=optimize(0); +say "Input: ", join ", ", @values; +say "Output: $value"; +say "Houses: ", join ", ", @houses; sub optimize { - my ($this, $value, @rest)=@_; - return (0) unless defined $value; # No more houses - return ($value, $this) unless @rest; # Only one house left - my ($v1, @h1)=optimize($this+1, @rest); # what if I skip this house? - my ($v2, @h2)=optimize($this+2, @rest[1..@rest-1]); # what if I rob this and skip next? + my $first=shift; + my $value=$values[$first]; + return (0) if $first >= @values; # No more houses + return ($value, $first) if $first==@values-1; # Only one house left + my ($v1, @h1)=optimize($first+1); # what if I skip first house? + my ($v2, @h2)=optimize($first+2,); # what if I rob first and skip next? my $v3=$value+$v2; $v3>$v1 # which option is best? - ?($v3, $this, @h2) # This one and skip next - :($v1, @h1); # or skip this one + ?($v3, $first, @h2) # First one and skip next + :($v1, @h1); # or skip first one } |