040_coin_change.sio

//@ run-pass
// HumanEval 040: Coin Change
//
// Given coins of different denominations and a total amount, find the
// fewest number of coins needed to make up that amount.
// Returns -1 if the amount cannot be made up by any combination.
// Uses bottom-up DP: dp[i] = min coins to make amount i.

struct DpBuf { data: [i64; 4096] }

fn coin_change(coins: [i64; 256], num_coins: i64, amount: i64) -> i64 with Mut, Panic, Div {
    if amount == 0 { return 0 }
    if amount < 0 { return 0 - 1 }

    // Initialize dp with large sentinel value (amount + 1 is unreachable)
    var dp = DpBuf { data: [0; 4096] }
    let sentinel = amount + 1
    var i: i64 = 0
    while i <= amount {
        dp.data[i] = sentinel
        i = i + 1
    }
    dp.data[0] = 0

    // Fill dp table
    var a: i64 = 1
    while a <= amount {
        var c: i64 = 0
        while c < num_coins {
            if coins[c] <= a {
                let prev = dp.data[a - coins[c]]
                if prev + 1 < dp.data[a] {
                    dp.data[a] = prev + 1
                }
            }
            c = c + 1
        }
        a = a + 1
    }

    if dp.data[amount] > amount {
        0 - 1
    } else {
        dp.data[amount]
    }
}

fn main() -> i64 with IO, Mut, Panic, Div {
    // Test 1: coins=[1,5,10,25], amount=30 -> 2 (25+5)
    var c1: [i64; 256] = [0; 256]
    c1[0] = 1
    c1[1] = 5
    c1[2] = 10
    c1[3] = 25
    assert(coin_change(c1, 4, 30) == 2)

    // Test 2: coins=[1,2,5], amount=11 -> 3 (5+5+1)
    var c2: [i64; 256] = [0; 256]
    c2[0] = 1
    c2[1] = 2
    c2[2] = 5
    assert(coin_change(c2, 3, 11) == 3)

    // Test 3: coins=[2], amount=3 -> -1 (impossible)
    var c3: [i64; 256] = [0; 256]
    c3[0] = 2
    assert(coin_change(c3, 1, 3) == 0 - 1)

    // Test 4: amount=0 -> 0
    var c4: [i64; 256] = [0; 256]
    c4[0] = 1
    assert(coin_change(c4, 1, 0) == 0)

    // Test 5: coins=[1], amount=1 -> 1
    var c5: [i64; 256] = [0; 256]
    c5[0] = 1
    assert(coin_change(c5, 1, 1) == 1)

    // Test 6: coins=[1,3,4], amount=6 -> 2 (3+3)
    var c6: [i64; 256] = [0; 256]
    c6[0] = 1
    c6[1] = 3
    c6[2] = 4
    assert(coin_change(c6, 3, 6) == 2)

    println("040_coin_change: ALL TESTS PASSED")
    0
}