[Practice] House Robbers

[lpatmo]

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Input: [1,2,3,1] Output: 4 Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4.

Input: [2,7,9,3,1] Output: 12 Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1). Total amount you can rob = 2 + 9 + 1 = 12.

Source: https://leetcode.com/problems/house-robber/

[lpatmo]

A javascript solution using tabulation:

function houseRobber(arr) {
  if (arr.length === 0) {
    return 0;
  }
  if (arr.length < 2) {
    return arr[0];
  }
  if (arr.length === 2) {
    return Math.max(arr[0], arr[1])
  }
  const result = [];
  result[0] = arr[0];
  result[1] = Math.max(arr[0], arr[1])
  for (let i = 2; i < arr.length; i++) {
    console.log(i)
    let value = Math.max(result[i-1], arr[i] + result[i-2]);
    result.push(value);
  }
  console.log(result)
  return result[result.length-1];
}

console.log(houseRobber([1,2,3]));

[cs-cordero]

class Solution:
    def rob(self, nums: List[int]) -> int:
        # Handle edge cases
        if len(nums) == 0:
            return 0
        elif len(nums) < 3:
            return max(nums)

        nums[2] += nums[0]
        for i in range(3, len(nums)):
            three_behind = nums[i - 3]
            two_behind = nums[i - 2]
            nums[i] += max(three_behind, two_behind)
        return max(nums[-2:])

[ArcTanSusan]

I even wrote unit tests. 😜

def max_amount(input_list):
    if len(input_list) <= 2:
        return 0

    input_list_odd_indices = [index for index in range(len(input_list)) if index % 2 ==1]
    input_list_even_indices = [index for index in range(len(input_list)) if index % 2 ==0]

    sum_odd_indices = 0
    for index in input_list_odd_indices:
        sum_odd_indices += input_list[index]

    sum_even_indices = 0
    for index in input_list_even_indices:
        sum_even_indices += input_list[index]

    return max(sum_odd_indices, sum_even_indices)

import unittest
class Test(unittest.TestCase):
    def test_bad_inputs(self):
        self.assertEqual(max_amount([1]), 0)
        self.assertEqual(max_amount([1,2]), 0)

    def test_good_inputs(self):
        self.assertEqual(max_amount([1,2,1]), 2)
        self.assertEqual(max_amount([1,2,1,2,1,2,1]), 6)
        self.assertEqual(max_amount([1,2,3,1]), 4)
        self.assertEqual(max_amount([2,7,9,3,1]), 12)

unittest.main(verbosity=2)

[ArcTanSusan]

@lpatmo i just now realized -- could the input of positive integers be a list of lists?

[stain88]

I don't think it's as simple as "just" comparing even and odd indices: what if the input were e.g. [7,2,3,9,1]?

[ArcTanSusan]

@stain88 then the answer is 11.

[stain88]

Why? The problem just states "it will automatically contact the police if two adjacent houses were broken into on the same night", not "you have to break into alternate houses". So you could break into houses 1 and 4, and come away with 16