037_jump_game.sio

//@ run-pass
// HumanEval 037: Jump Game
//
// Given an array where each element represents the maximum jump length
// from that position, determine if you can reach the last index.
// Greedy approach: track the farthest reachable index.
// Returns 1 if reachable, 0 otherwise.

fn can_jump(nums: [i64; 256], n: i64) -> i64 with Mut, Panic, Div {
    var farthest: i64 = 0
    var i: i64 = 0
    while i < n {
        if i > farthest {
            return 0
        }
        let reach = i + nums[i]
        if reach > farthest {
            farthest = reach
        }
        i = i + 1
    }
    1
}

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

    // Test 2: [3, 2, 1, 0, 4] -> stuck at index 3
    var a2: [i64; 256] = [0; 256]
    a2[0] = 3
    a2[1] = 2
    a2[2] = 1
    a2[3] = 0
    a2[4] = 4
    assert(can_jump(a2, 5) == 0)

    // Test 3: single element [0] -> already at end
    var a3: [i64; 256] = [0; 256]
    a3[0] = 0
    assert(can_jump(a3, 1) == 1)

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

    // Test 5: [0, 1] -> stuck at index 0
    var a5: [i64; 256] = [0; 256]
    a5[0] = 0
    a5[1] = 1
    assert(can_jump(a5, 2) == 0)

    // Test 6: [5, 0, 0, 0, 0, 0] -> big first jump
    var a6: [i64; 256] = [0; 256]
    a6[0] = 5
    assert(can_jump(a6, 6) == 1)

    println("037_jump_game: ALL TESTS PASSED")
    0
}