From 5045026f0fe4bf7ba93d00350f8bb6bbde68f5be Mon Sep 17 00:00:00 2001 From: Abigail Date: Tue, 8 Feb 2022 11:51:15 +0100 Subject: Week 151: Simplified algorithm for part 2. By adding two dummy 0's to the "best" array, and not bothering the calculate the best values for the first two houses, we don't have a case study inside the main loop. --- challenge-151/abigail/awk/ch-2.awk | 12 +++++------- challenge-151/abigail/bash/ch-2.sh | 34 +++++++--------------------------- challenge-151/abigail/c/ch-2.c | 17 ++++++++--------- challenge-151/abigail/lua/ch-2.lua | 21 +++++++-------------- challenge-151/abigail/node/ch-2.js | 15 ++++++--------- challenge-151/abigail/perl/ch-2.pl | 27 ++++++++++----------------- 6 files changed, 43 insertions(+), 83 deletions(-) diff --git a/challenge-151/abigail/awk/ch-2.awk b/challenge-151/abigail/awk/ch-2.awk index 73d9b19812..65428f81e8 100644 --- a/challenge-151/abigail/awk/ch-2.awk +++ b/challenge-151/abigail/awk/ch-2.awk @@ -14,13 +14,11 @@ function max (a, b) { { 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]) + best [NF + 1] = 0 + best [NF + 2] = 0 + for (i = NF; i > 2; i --) { + best [i] = max($i + best [i + 2], best [i + 1]) } - print best [1] + print $1 + best [3] } diff --git a/challenge-151/abigail/bash/ch-2.sh b/challenge-151/abigail/bash/ch-2.sh index 0b8f213fca..6a9eceec29 100644 --- a/challenge-151/abigail/bash/ch-2.sh +++ b/challenge-151/abigail/bash/ch-2.sh @@ -13,34 +13,14 @@ set -f declare -a best while read -a houses -do if [[ ${#houses[@]} -lt 2 ]] - then echo ${houses[0]} - continue - fi - - size=${#houses[@]} - for ((i = size - 1; i >= 0; i --)) - do ((i1 = i + 1)) - ((i2 = i + 2)) - if ((i == size - 1)) - then best[$i]=${houses[$i]} - continue - fi - - if ((i == 0)) - then best[$i]=$((${houses[$i]} + ${best[$i2]})) - continue - fi - - if ((i == size - 2)) - then val1=${houses[$i]} - val2=${best[$i1]} - else val1=$((${houses[$i]} + ${best[$i2]})) - val2=${best[$i1]} - fi - +do size=${#houses[@]} + best[$((size + 0))]=0 + best[$((size + 1))]=0 + for ((i = size - 1; i >= 2; i --)) + do ((val1 = ${houses[$i]} + ${best[$((i + 2))]})) + ((val2 = ${best[$((i + 1))]})) best[$i]=$((val1 < val2 ? val2 : val1)) done - echo ${best[0]} + echo $((${houses[0]} + ${best[2]})) done diff --git a/challenge-151/abigail/c/ch-2.c b/challenge-151/abigail/c/ch-2.c index c2a62f6c92..34e7e24ac1 100644 --- a/challenge-151/abigail/c/ch-2.c +++ b/challenge-151/abigail/c/ch-2.c @@ -37,21 +37,20 @@ int main (void) { line_ptr += offset; } - if ((best = (int *) malloc (nr_of_houses * sizeof (int))) == NULL) { + if ((best = (int *) + malloc ((nr_of_houses + 2) * sizeof (int))) == NULL) { perror ("Malloc failed"); exit (1); } - for (int i = nr_of_houses - 1; i >= 0; i --) { - best [i] = nr_of_houses < 2 ? houses [i] - : i == nr_of_houses - 1 ? houses [i] - : i == 0 ? houses [i] + best [i + 2] - : i == nr_of_houses - 2 ? max (houses [i], best [i + 1]) - : max (houses [i] + best [i + 2], - best [i + 1]); + best [nr_of_houses + 0] = 0; + best [nr_of_houses + 1] = 0; + + for (int i = nr_of_houses - 1; i >= 2; i --) { + best [i] = max (houses [i] + best [i + 2], best [i + 1]); } - printf ("%d\n", best [0]); + printf ("%d\n", houses [0] + best [2]); free (houses); free (best); diff --git a/challenge-151/abigail/lua/ch-2.lua b/challenge-151/abigail/lua/ch-2.lua index 98df0aae1d..0e644d0a6c 100644 --- a/challenge-151/abigail/lua/ch-2.lua +++ b/challenge-151/abigail/lua/ch-2.lua @@ -15,19 +15,12 @@ for line in io . lines () do houses [#houses + 1] = val end - for i = #houses, 1, -1 do - if 2 >= #houses then - best [i] = houses [i] - elseif i == #houses then - best [i] = houses [i] - elseif i == 0 then - best [i] = houses [i] + best [i + 2] - elseif i == #houses - 1 then - best [i] = math . max (houses [i], best [i + 1]) - else - best [i] = math . max (houses [i] + best [i + 2], - best [i + 1]) - end + best [#houses + 1] = 0 + best [#houses + 2] = 0 + + for i = #houses, 3, -1 do + best [i] = math . max (houses [i] + best [i + 2], best [i + 1]) end - print (best [1]) + + print (houses [1] + best [3]) end diff --git a/challenge-151/abigail/node/ch-2.js b/challenge-151/abigail/node/ch-2.js index f4d698ec49..079c61e0ce 100644 --- a/challenge-151/abigail/node/ch-2.js +++ b/challenge-151/abigail/node/ch-2.js @@ -13,14 +13,11 @@ . on ('line', line => { let houses = line . trim () . split (/ +/) . map (n => +n) let best = [] - for (let i = houses . length - 1; i >= 0; i --) { - best [i] = - 2 > houses . length ? houses [i] - : i == houses . length - 1 ? houses [i] - : i == 0 ? houses [i] + best [i + 2] - : i == houses . length - 2 ? Math . max (houses [i], best [i + 1]) - : Math . max (houses [i] + best [i + 2], - best [i + 1]) + let size = houses . length + best [size + 0] = 0 + best [size + 1] = 0 + for (let i = size - 1; i >= 2; i --) { + best [i] = Math . max (houses [i] + best [i + 2], best [i + 1]) } - console . log (best [0]) + console . log (houses [0] + best [2]) }) diff --git a/challenge-151/abigail/perl/ch-2.pl b/challenge-151/abigail/perl/ch-2.pl index 5f5519381f..9c1e1d3b60 100644 --- a/challenge-151/abigail/perl/ch-2.pl +++ b/challenge-151/abigail/perl/ch-2.pl @@ -26,29 +26,22 @@ use List::Util qw [max]; # 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. +# the next house. We'll add two empty houses to make everything work +# out nicely. # -# 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. +# Note that we don't have to calculate the best option starting +# from the second house, as we will always skip the second house. +# And we must always pick the first house. # 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 [$#$houses + 1] = 0; + $best [$#$houses + 2] = 0; + for (my $i = $#$houses; $i >= 2; $i --) { + $best [$i] = max $$houses [$i] + $best [$i + 2], $best [$i + 1]; } - $best [0]; + $$houses [0] + $best [2]; } -- cgit