061_product_except_self.sio

//@ run-pass
// HumanEval 061: Product of Array Except Self
//
// Given an array of integers, return an array where each element is the
// product of all other elements. Solve without division.
// Uses two passes: left prefix products and right suffix products.

struct Buf { data: [i64; 256] }

fn product_except_self(arr: [i64; 256], n: i64, out: &!Buf) with Mut, Panic {
    // Pass 1: out[i] = product of arr[0..i-1]
    out.data[0] = 1
    var i: i64 = 1
    while i < n {
        out.data[i] = out.data[i - 1] * arr[i - 1]
        i = i + 1
    }

    // Pass 2: multiply by product of arr[i+1..n-1]
    var right: i64 = 1
    var j: i64 = n - 1
    while j >= 0 {
        out.data[j] = out.data[j] * right
        right = right * arr[j]
        j = j - 1
    }
}

fn main() -> i64 with IO, Mut, Panic, Div {
    // Test 1: [1, 2, 3, 4] -> [24, 12, 8, 6]
    var a1: [i64; 256] = [0; 256]
    a1[0] = 1
    a1[1] = 2
    a1[2] = 3
    a1[3] = 4
    var o1 = Buf { data: [0; 256] }
    product_except_self(a1, 4, &!o1)
    assert(o1.data[0] == 24)
    assert(o1.data[1] == 12)
    assert(o1.data[2] == 8)
    assert(o1.data[3] == 6)

    // Test 2: [2, 3, 5] -> [15, 10, 6]
    var a2: [i64; 256] = [0; 256]
    a2[0] = 2
    a2[1] = 3
    a2[2] = 5
    var o2 = Buf { data: [0; 256] }
    product_except_self(a2, 3, &!o2)
    assert(o2.data[0] == 15)
    assert(o2.data[1] == 10)
    assert(o2.data[2] == 6)

    // Test 3: [1, 1, 1, 1] -> [1, 1, 1, 1]
    var a3: [i64; 256] = [0; 256]
    a3[0] = 1
    a3[1] = 1
    a3[2] = 1
    a3[3] = 1
    var o3 = Buf { data: [0; 256] }
    product_except_self(a3, 4, &!o3)
    assert(o3.data[0] == 1)
    assert(o3.data[1] == 1)
    assert(o3.data[2] == 1)
    assert(o3.data[3] == 1)

    // Test 4: [2, 0, 3] -> [0, 6, 0] (contains zero)
    var a4: [i64; 256] = [0; 256]
    a4[0] = 2
    a4[1] = 0
    a4[2] = 3
    var o4 = Buf { data: [0; 256] }
    product_except_self(a4, 3, &!o4)
    assert(o4.data[0] == 0)
    assert(o4.data[1] == 6)
    assert(o4.data[2] == 0)

    // Test 5: single element [5] -> [1]
    var a5: [i64; 256] = [0; 256]
    a5[0] = 5
    var o5 = Buf { data: [0; 256] }
    product_except_self(a5, 1, &!o5)
    assert(o5.data[0] == 1)

    // Test 6: two elements [3, 7] -> [7, 3]
    var a6: [i64; 256] = [0; 256]
    a6[0] = 3
    a6[1] = 7
    var o6 = Buf { data: [0; 256] }
    product_except_self(a6, 2, &!o6)
    assert(o6.data[0] == 7)
    assert(o6.data[1] == 3)

    println("061_product_except_self: ALL TESTS PASSED")
    0
}