Burglary Tools

Wherein we take what we can and leave the rest

THE WEEKLY CHALLENGE – PERL & RAKU #151 — Task 2

---

“The faults of the burglar are the qualities of the financier.”

— George Bernard Shaw

---

Rob The House

Submitted by: Mohammad S Anwar

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.

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.

Method

In this implementation of the Traveling Burglar Problem… wait, is that a thing? I thought that was a thing¹. Oh well, in any case, the goal here is to optimize our selection along an ordered sequence governed by a set of rules:

1. we can ony proceed forward
2. we must skip the next element in any movement.
3. the goal is the highest sum of gathered elements

There is no further governance on the selection of elements, but some optimal emergent behavior can be derived to guide us to a winning strategy. For example, from any element we should move forward either 2 or 3 positions. We cannot move one, and any position greater than 3 can be arrived at by some combination of intermediatary steps: position 4 can be broken down into 2 + 2, 5 as 2 + 3 or 3 + 2. As all values are positive (or at least 0, but not negative) there is never a downside to adding an intermediate stopover.

So 2 or 3 it is.

After 2 or 3, however, there is a problem with looking ahead, as the element at position n+4 is always dependant on the choices made previously, as it can only be arrived at in one specific manner. Furthermore, this predicate dependency can be indefinitely extended to the chain of all 2-separate values, which can only be achieved by making the 2-selection from the very beginning. More so there are two such sequences in every list, corresponding to the odd- and even-numbered indices, that maximize the number of elements selected, and these can only be arrived at by making specific mutually-exclusive choices at the beginning of the run.

In short, in order to sum these sequences, each needs to be started separately and run through completely, examining every element. As one to the other is likely to also contain the maximal sum, then therefore we need to look at every value before we can make the determination of which pattern maximizes the sum. This logic also applies to every subsequence of 2-separate elements and its n+1 complement, so these need to be considered too.

So there’s no way around it: we need to look at all the patterns first. By looking at all the 2-step chains the 3-step sequences will be the holes between them. Pruning the search tree will be tricky if it’s even possible, which frankly I don’t see. It looks like we will need at look at every pattern of 2- and 3-jumps, starting at both the 0th and 1st positions.

As we are tasked with robbing real imaginary houses along a real imaginary block we can assume the number of houses to be finite and not excessively large. The algorithm will bog down eventually, just to put that out front, but only after an unrealistically long day of thieving.

---

¹ There actually is a variation of the Traveling Salesman Problem called the Traveling Thief Problem, where we combine the TSP with the Knapsack Problem: the goal is to visit a tour of cities exactly once and return, while filling a backpack by removing items from each city along the way, constrained both by the maximum weight of the backpack and the order of the cities visited. A total value to be maximized, or a time to be minimized, may also be included as objectives. The rationale behind these sorts of problems is to study the interdependence of the solutions to each of the subproblem components and how the the combination of the two problems more closely models real-world conditions.

The theory here is that real world conditions are messy and are more accurately thought of as the combination of several independently intractable NP-hard concepts, and our best-choice optimization strategies should reflect that.

This task is not that problem. This one may require a brute-force solution to examine the whole of the data set before coming to a conclusion, but it’s only a child’s toy version of the number a variables a real-world burglar should consider in planning a string of heists like this. Probably wouldn’t — that’s another story —  but should. Most criminals aren’t very thorough in my experience, and are looking for quick solutions to complex problems.

The smart criminals don’t rob banks, they become bankers.

---

PERL 5 SOLUTION

We are asked in the description for the gain, not the means of getting it. Thus we don’t need to keep track of the actual house addresses visited, which strikes me as rather negligent for a burglar trying to be efficient. After finding the maximal solution they would just need to do it again and write down the plan this time. D’oh! However like I said, most criminals don’t seem to be very good at planning ahead — looking at the big picture — so this does, for what it’s worth, do a good job of modeling real-world behavior. Frank Sinatra, or George Clooney, might be really cool as Danny Ocean and all that but those aren’t exactly documentaries, even if some people seem to think of life that way. These are the kind of people who take to burgling houses, looking for big payouts without much work. Like I said before: not very good at seeing the big picture. Just remember kids, Ocean’s plan, for all that effort, didn’t account for enough variables in the end.

So all we need to do is build a recursive function that chooses first a 2-step skip from the current position and then a 3, returning the cumulative sum after running out of houses. As the recursions collapse the largest sum from the two decisions is propagated backwards up the chain until we are left with the largest possible gain.

It seems to handle 60 house blocks well, just beginning to show signs of slowing down with that length. As no allowance is stated for crossing the street, I will assume we are only doing one side at a time, so 60 is more than enough. Apartment buildings add a whole next level of complexity outside the scope of this study.

use warnings;
use strict;
use utf8;
use feature ":5.26";
use feature qw(signatures);
no warnings 'experimental::signatures';


our @arr = (1, 2, 3, 6, 5, 3, 8, 1, 1, 1, 2, 3, 6, 5, 3, 8, 1, 1, 1, 2, 3, 6, 5, 3, 8, 1, 1, 1, 2, 3, 6, 5, 3, 8, 1, 1);

say lookahead( );

sub lookahead ( $pos = -2, $sum = 0 ) {
    return $sum if $pos > $#arr;
    $sum += $arr[ $pos ] if $pos >= 0;
    my $two   = lookahead( $pos + 2, $sum ) ;
    my $three = lookahead( $pos + 3, $sum ) ;
    return $two > $three ? $two : $three ;
}

raku solution

In Raku things are predictably more compact, as we can consider the two recursive cases to return an anonymous list, from which we can pick the largest element to return. Being able to place the for loop as part of a list comprehension, calling a method on the result, is really nice.

unit sub MAIN ( *@arr ) ;


## test data
@arr = 1,2,3,4 if @arr.elems == 0;

say lookahead();

sub lookahead( $pos = -2, $sum is copy = 0) {
    return $sum if $pos > @arr.end;
    $pos >= 0 && $sum += @arr[$pos];
    ( lookahead( $pos + $_, $sum ) for 2, 3 ).max
}

---