diff options
Diffstat (limited to 'challenge-151')
| -rw-r--r-- | challenge-151/abigail/awk/ch-2.awk | 26 | ||||
| -rw-r--r-- | challenge-151/abigail/perl/ch-2.pl | 38 |
2 files changed, 40 insertions, 24 deletions
diff --git a/challenge-151/abigail/awk/ch-2.awk b/challenge-151/abigail/awk/ch-2.awk index 3eb76a8e05..73d9b19812 100644 --- a/challenge-151/abigail/awk/ch-2.awk +++ b/challenge-151/abigail/awk/ch-2.awk @@ -8,21 +8,19 @@ # Run as: awk -f ch-2.awk < input-file # -function best (i, max, sum, k) { - if (!(i in cache)) { - max = 0 - for (k = i + 2; k <= NF; k ++) { - sum = best(k) - if (sum > max) { - max = sum - } - } - cache [i] = $i + max - } - return cache [i] +function max (a, b) { + return a < b ? b : a } { - delete cache - print best(1) + delete best + for (i = NF; i > 0; i --) { + best [i] = NF <= 2 ? $i \ + : i == NF ? $i \ + : i == 1 ? $i + best [i + 2] \ + : i == NF - 1 ? max($i, best [i + 1]) \ + : max($i + best [i + 2], best [i + 1]) + } + print best [1] } + diff --git a/challenge-151/abigail/perl/ch-2.pl b/challenge-151/abigail/perl/ch-2.pl index 263bede352..5f5519381f 100644 --- a/challenge-151/abigail/perl/ch-2.pl +++ b/challenge-151/abigail/perl/ch-2.pl @@ -20,17 +20,35 @@ use experimental 'lexical_subs'; use List::Util qw [max]; # -# An algorithm we've seen many times before. For each house, we either -# rob it, or skip it. And we always have to skip the next house. -# Skipping more than two houses in succession is never a good idea, but -# work we'll do extra in the beginning (by skipping more than two house) -# we get back later on, as we're caching all results. +# We'll calculate the best way to rob the houses by working backwards. +# For each house, there are two options: rob the house, or skip it. +# The maximum value we get for robbing the house is the sum of +# the value of the current house, plus the maximum we can get +# if we started two houses down. The maximum value we can get by +# not robbing this house is the best we can get by starting from +# the next house. # -sub best; -sub best ($vals, $i = 0) { - state $cache; - $i or $cache = []; - $$cache [$i] ||= $$vals [$i] + max 0, map {best $vals, $_} $i + 2 .. $#$vals +# We need some fiddling around the edges: +# - Maximizing the value starting from the last house is by robbing it. +# - Maximizing the value starting from the penultimate house is +# robbing the most valuable of the last two houses. +# - If there are only two houses, rob the current house. +# - The first house should always be robbed (a requirement); the +# maximum value which can be achieved we get by starting from the +# third house, adding the value of the first. +# + +sub best ($houses) { + my @best; + foreach my $i (reverse keys @$houses) { + $best [$i] = @$houses < 2 ? $$houses [$i] + : $i == $#$houses ? $$houses [$i] + : $i == 0 ? $$houses [$i] + $best [$i + 2] + : $i == $#$houses - 1 ? max $$houses [$i], $best [$i + 1] + : max $$houses [$i] + $best [$i + 2], + $best [$i + 1]; + } + $best [0]; } |