Task — Rob the house

You are planning to rob a row of houses, always starting with the first and moving in the same direction. However, you can’t rob two adjacent houses. Write a script to find the highest possible gain that can be achieved.

Examples

Example 1:
Input: @valuables = (2, 4, 5);
Output: 7
If we rob house (index=0) we get 2 and then the only house
we can rob is house (index=2) where we have 5.
So the total valuables in this case is (2 + 5) = 7.

Example 2:
Input: @valuables = (4, 2, 3, 6, 5, 3);
Output: 13
The best choice would be to first rob house (index=0) 
then rob house (index=3) then finally house (index=5).
This would give us 4 + 6 + 3 =13.

Analysis

The first thing to ask is: how do I know the amount of swag in each house before I start? Lack of that knowledge means that any solution to the task is unlikely to be helpful to a real robber, which is a relief.

My relatively simple solution was to write a recursive function, robberies, which takes as arguments a starting house number and the amount of swag already in my bag, and checks each of the individual houses that I could rob next - ie the next but one and all the rest up to the end of the street. It then recurses for each of these until the last house is reached.

This is fine for a short street, but the effort increases order n**2 as the street length increases, and on my little computer a street longer than about 35 houses took longer than I fancied waiting.

How could one make a more efficient algorithm? For example, as the algorithm knows the best solution found to date, it could give up on the recursion if the swag to date plus the most I could collect from all the remaining houses is less than the best result already found.

I though too about ordering the houses by value, but given, say, the three most valuable - say they are numbers 14, 22 and 31 - determining which paths include these three is non-trivial, and it could still be the case that a combination not including all of these three was the most lucrative.

And in the end, maybe it's best not to provide robbers with an efficient algorithm.

Try it 

Script

#!/usr/bin/perl

# Peter Campbell Smith - 2022-02-07
# PWC 151 task 2

use v5.28;
use strict;
use utf8;

my (@tests, $test, @houses, $last, $best);

@tests = ([2, 4, 5], [4, 2, 3, 6, 5, 3],
    [32, 32, 8, 12, 46, 28, 79, 81, 84, 23, 48, 88, 38, 
    36, 44, 45, 55, 74, 33, 54, 49, 33, 54, 50, 20, 45, 
    79, 94, 48, 94, 51, 93, 88, 23, 19]);

# loop over tests
for $test (@tests) {
    
    @houses = @$test;   
    say qq[\nInput:  \@values = (] . join(', ', @$test) . ')';
    $best = 0;
    $last = scalar @houses - 1;
    
    # start at house 0 and we've got $houses[0] in the swag bag
    robberies(0, $houses[0]);
    say qq[Output: $best];
}

sub robberies {
    
    # robberies($number, $swag) updates $best with the best result starting from house $number
    # with $swag already in the bag
        
    my ($number, $swag, $next, $new_swag);
    
    ($number, $swag) = @_;  
    # try all the next allowable houses starting from $number
    for ($next = $number + 2; $next <= $last; $next ++) {
        $new_swag = $swag + $houses[$next];
        $best = $new_swag if $new_swag > $best;   # looking good!
        robberies($next, $new_swag);
    }
}

Output

Input:  @values = (2, 4, 5)
Output: 7

Input:  @values = (4, 2, 3, 6, 5, 3)
Output: 13

Input:  @values = (32, 32, 8, 12, 46, 28, 79, 81, 84, 23,
  48, 88, 38, 36, 44, 45, 55, 74, 33, 54, 49, 33, 54, 50,
  20, 45, 79, 94, 48, 94, 51, 93, 88, 23, 19)
Output: 978