039_house_robber.sio

//@ run-pass
// HumanEval 039: House Robber
//
// Given an array of non-negative integers representing money at each house,
// determine the maximum amount you can rob without robbing two adjacent houses.
// DP recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i])
// Uses O(1) space with two rolling variables.

fn rob(nums: [i64; 256], n: i64) -> i64 with Mut, Panic, Div {
    if n == 0 { return 0 }
    if n == 1 { return nums[0] }

    var prev2: i64 = nums[0]
    var prev1: i64 = nums[1]
    if prev2 > prev1 {
        prev1 = prev2
    }

    var i: i64 = 2
    while i < n {
        let take = prev2 + nums[i]
        var current: i64 = prev1
        if take > current {
            current = take
        }
        prev2 = prev1
        prev1 = current
        i = i + 1
    }
    prev1
}

fn main() -> i64 with IO, Mut, Panic, Div {
    // Test 1: [1, 2, 3, 1] -> rob houses 0,2 = 4
    var a1: [i64; 256] = [0; 256]
    a1[0] = 1
    a1[1] = 2
    a1[2] = 3
    a1[3] = 1
    assert(rob(a1, 4) == 4)

    // Test 2: [2, 7, 9, 3, 1] -> rob houses 0,2,4 = 12
    var a2: [i64; 256] = [0; 256]
    a2[0] = 2
    a2[1] = 7
    a2[2] = 9
    a2[3] = 3
    a2[4] = 1
    assert(rob(a2, 5) == 12)

    // Test 3: [5] -> 5
    var a3: [i64; 256] = [0; 256]
    a3[0] = 5
    assert(rob(a3, 1) == 5)

    // Test 4: [3, 10] -> 10
    var a4: [i64; 256] = [0; 256]
    a4[0] = 3
    a4[1] = 10
    assert(rob(a4, 2) == 10)

    // Test 5: [2, 1, 1, 2] -> rob houses 0,3 = 4
    var a5: [i64; 256] = [0; 256]
    a5[0] = 2
    a5[1] = 1
    a5[2] = 1
    a5[3] = 2
    assert(rob(a5, 4) == 4)

    // Test 6: empty -> 0
    var a6: [i64; 256] = [0; 256]
    assert(rob(a6, 0) == 0)

    // Test 7: [10, 1, 1, 10, 1, 1, 10] -> rob houses 0,3,6 = 30
    var a7: [i64; 256] = [0; 256]
    a7[0] = 10
    a7[1] = 1
    a7[2] = 1
    a7[3] = 10
    a7[4] = 1
    a7[5] = 1
    a7[6] = 10
    assert(rob(a7, 7) == 30)

    println("039_house_robber: ALL TESTS PASSED")
    0
}