sounio-benchmarks/049_count_inversions.sio at main · Sounio-lang/sounio-benchmarks · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
//@ run-pass
// HumanEval 049: Count Inversions (Merge Sort)
//
// Count the number of inversions in an array. An inversion is a pair
// (i, j) where i < j but arr[i] > arr[j].
// Uses merge sort to count inversions in O(n log n).
// Struct wrapper for mutable arrays.

struct Buf { data: [i64; 256] }

fn merge_count(arr: &!Buf, tmp: &!Buf, lo: i64, hi: i64) -> i64 with Mut, Panic, Div {
    if lo >= hi { return 0 }

    let mid = lo + (hi - lo) / 2
    var count: i64 = 0
    count = count + merge_count(arr, tmp, lo, mid)
    count = count + merge_count(arr, tmp, mid + 1, hi)

    // Merge arr[lo..mid] and arr[mid+1..hi] into tmp, counting split inversions
    var i: i64 = lo
    var j: i64 = mid + 1
    var k: i64 = lo

    while i <= mid {
        if j > hi { break }
        if arr.data[i] <= arr.data[j] {
            tmp.data[k] = arr.data[i]
            i = i + 1
        } else {
            tmp.data[k] = arr.data[j]
            // All remaining elements in left half are > arr[j]
            count = count + (mid - i + 1)
            j = j + 1
        }
        k = k + 1
    }

    // Copy remaining from left half
    while i <= mid {
        tmp.data[k] = arr.data[i]
        k = k + 1
        i = i + 1
    }

    // Copy remaining from right half
    while j <= hi {
        tmp.data[k] = arr.data[j]
        k = k + 1
        j = j + 1
    }

    // Copy merged back to arr
    var m: i64 = lo
    while m <= hi {
        arr.data[m] = tmp.data[m]
        m = m + 1
    }

    count
}

fn count_inversions(arr: [i64; 256], n: i64) -> i64 with Mut, Panic, Div {
    if n <= 1 { return 0 }
    var buf = Buf { data: [0; 256] }
    var tmp = Buf { data: [0; 256] }
    // Copy input into buf
    var i: i64 = 0
    while i < n {
        buf.data[i] = arr[i]
        i = i + 1
    }
    merge_count(&!buf, &!tmp, 0, n - 1)
}

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

    // Test 2: sorted [1,2,3,4] -> 0 inversions
    var a2: [i64; 256] = [0; 256]
    a2[0] = 1
    a2[1] = 2
    a2[2] = 3
    a2[3] = 4
    assert(count_inversions(a2, 4) == 0)

    // Test 3: reverse sorted [4,3,2,1] -> 6 inversions (n*(n-1)/2)
    var a3: [i64; 256] = [0; 256]
    a3[0] = 4
    a3[1] = 3
    a3[2] = 2
    a3[3] = 1
    assert(count_inversions(a3, 4) == 6)

    // Test 4: single element -> 0
    var a4: [i64; 256] = [0; 256]
    a4[0] = 42
    assert(count_inversions(a4, 1) == 0)

    // Test 5: [1, 5, 4, 8, 10, 2, 6] -> inversions:
    // (5,4),(5,2),(4,2),(8,2),(8,6),(10,2),(10,6) = 7
    var a5: [i64; 256] = [0; 256]
    a5[0] = 1
    a5[1] = 5
    a5[2] = 4
    a5[3] = 8
    a5[4] = 10
    a5[5] = 2
    a5[6] = 6
    assert(count_inversions(a5, 7) == 7)

    // Test 6: [3, 1, 2] -> inversions: (3,1),(3,2) = 2
    var a6: [i64; 256] = [0; 256]
    a6[0] = 3
    a6[1] = 1
    a6[2] = 2
    assert(count_inversions(a6, 3) == 2)

    println("049_count_inversions: ALL TESTS PASSED")
    0
}