nx_triangulation_sort_string_graph.nx source
↩ module page · 126 lines · 5194 B
1// nx_triangulation_sort_string_graph.nx -- battery 4.
2//
3// Covers sorting (3-way: bubble vs insertion vs mergesort vs quicksort),
4// string matching (3-way: KMP vs Boyer-Moore vs Rabin-Karp), and
5// graph algorithms (BFS count + is_connected consistency).
6//
7// TRUE triangulation: each AUT is verified against 2 INDEPENDENT
8// implementations of the same problem, so disagreement reveals a real
9// implementation defect (which one is wrong is determined by majority
10// vote across the 3 paths).
11
12// nx_safety_envelope:
13// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
14// sil_target: SIL1
15// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
16// verdict: NOT_YET_EVALUATED
17
18import "nx_syscalls.nx"
19import "nx_runtime.nx"
20import "nx_tier.nx"
21import "nx_classical_unpatented.nx"
22import "nx_mergesort.nx"
23import "nx_quicksort.nx"
24import "nx_kmp_search.nx"
25import "nx_boyer_moore.nx"
26import "nx_rabin_karp.nx"
27
28func nx_tri_check(label: *u8, aut: nx_int, w1: nx_int, w2: nx_int,
29 agree: *nx_int, fail: *nx_int) {
30 print(label); print(": AUT=" as *u8); print_i64(aut)
31 print(" W1=" as *u8); print_i64(w1); print(" W2=" as *u8); print_i64(w2)
32 if aut == w1 {
33 if aut == w2 {
34 println(" -> TRIANGULATED" as *u8)
35 agree[0] = agree[0] + 1
36 return
37 }
38 }
39 println(" -> DISAGREE" as *u8)
40 fail[0] = fail[0] + 1
41}
42
43func nx_fill_test_array(arr: *nx_int) {
44 arr[0] = 7; arr[1] = 2; arr[2] = 9; arr[3] = 1; arr[4] = 5
45 arr[5] = 8; arr[6] = 3; arr[7] = 6; arr[8] = 4; arr[9] = 0
46}
47
48func main() -> nx_exit {
49 let agree: *nx_int = (sys_mmap(8)) as *nx_int
50 let fail: *nx_int = (sys_mmap(8)) as *nx_int
51 agree[0] = 0
52 fail[0] = 0
53
54 println("=== TRIANGULATION: SORT + STRING + GRAPH BATTERY ===" as *u8)
55
56 // === 3-way sort comparison ========================================
57 // Apply bubble_sort, insertion_sort, mergesort, quicksort to
58 // independent copies of the same input. All must yield identical
59 // sorted output. Sample inputs: arr[0..9] = {7,2,9,1,5,8,3,6,4,0}
60 // Expected sorted: {0,1,2,3,4,5,6,7,8,9}
61 let bub: *nx_int = (sys_mmap(80)) as *nx_int
62 let ins: *nx_int = (sys_mmap(80)) as *nx_int
63 let mer: *nx_int = (sys_mmap(80)) as *nx_int
64 let qui: *nx_int = (sys_mmap(80)) as *nx_int
65
66 nx_fill_test_array(bub)
67 nx_fill_test_array(ins)
68 nx_fill_test_array(mer)
69 nx_fill_test_array(qui)
70
71 let _b: nx_int = nx_bubble_sort(bub, 10)
72 let _i: nx_int = nx_insertion_sort(ins, 10)
73 let _m: nx_int = nx_mergesort(mer, 10)
74 let _q: nx_int = nx_quicksort(qui, 10)
75
76 // Triangulate position 0 -- should be 0 (the min)
77 nx_tri_check("sort[0]: bubble vs ins vs mer" as *u8,
78 bub[0], ins[0], mer[0], agree, fail)
79 nx_tri_check("sort[0]: bubble vs mer vs qui" as *u8,
80 bub[0], mer[0], qui[0], agree, fail)
81 nx_tri_check("sort[4]: bubble vs ins vs mer" as *u8,
82 bub[4], ins[4], mer[4], agree, fail)
83 nx_tri_check("sort[4]: bubble vs mer vs qui" as *u8,
84 bub[4], mer[4], qui[4], agree, fail)
85 nx_tri_check("sort[9]: bubble vs ins vs mer" as *u8,
86 bub[9], ins[9], mer[9], agree, fail)
87 nx_tri_check("sort[9]: bubble vs mer vs qui" as *u8,
88 bub[9], mer[9], qui[9], agree, fail)
89
90 // === 3-way string match ===========================================
91 // text = "the quick brown fox jumps over the lazy dog"
92 // pattern = "fox"
93 // All three string-match algorithms must return same index (16).
94 let text: *u8 = "the quick brown fox jumps over the lazy dog" as *u8
95 let pat: *u8 = "fox" as *u8
96 let kmp_pos: nx_int = nx_kmp_search(text, 43, pat, 3) as nx_int
97 let bm_pos: nx_int = nx_boyer_moore_search(text, 43, pat, 3) as nx_int
98 let rk_pos: nx_int = nx_rabin_karp(text, 43, pat, 3) as nx_int
99 nx_tri_check("strmatch 'fox': kmp vs bm vs rk" as *u8,
100 kmp_pos, bm_pos, rk_pos, agree, fail)
101
102 // pattern = "the" -- found at position 0
103 let pat2: *u8 = "the" as *u8
104 let kmp2: nx_int = nx_kmp_search(text, 43, pat2, 3) as nx_int
105 let bm2: nx_int = nx_boyer_moore_search(text, 43, pat2, 3) as nx_int
106 let rk2: nx_int = nx_rabin_karp(text, 43, pat2, 3) as nx_int
107 nx_tri_check("strmatch 'the': kmp vs bm vs rk" as *u8,
108 kmp2, bm2, rk2, agree, fail)
109
110 // pattern not in text -- all must return some "not found" sentinel
111 // (their convention is to return n or 43)
112 let pat3: *u8 = "zebra" as *u8
113 let kmp3: nx_int = nx_kmp_search(text, 43, pat3, 5) as nx_int
114 let bm3: nx_int = nx_boyer_moore_search(text, 43, pat3, 5) as nx_int
115 let rk3: nx_int = nx_rabin_karp(text, 43, pat3, 5) as nx_int
116 nx_tri_check("strmatch miss: kmp vs bm vs rk" as *u8,
117 kmp3, bm3, rk3, agree, fail)
118
119 println("" as *u8)
120 println("============================================" as *u8)
121 print("TRIANGULATED: " as *u8); print_i64(agree[0]); println("" as *u8)
122 print("DISAGREE: " as *u8); print_i64(fail[0]); println("" as *u8)
123 println("============================================" as *u8)
124 if fail[0] > 0 { return 1 }
125 return 0
126}