collatz.gno
4.43 Kb · 186 lines
1package collatz
2
3import (
4 "chain"
5 "chain/runtime/unsafe"
6 "sort"
7 "strconv"
8 "strings"
9
10 "gno.land/p/nt/avl/v0"
11)
12
13// maxIters caps the Collatz walk so a hostile / huge input cannot loop
14// forever on-chain. No known n stays below this bound and fails to reach 1.
15const maxIters = 1000000
16
17// maxSeqLen caps how many terms Render("/<n>") will print.
18const maxSeqLen = 500
19
20// Result is one recorded submission.
21type Result struct {
22 N int64
23 Steps int
24 Peak int64
25 Who address
26}
27
28// results maps a decimal-string key of N -> Result. avl.Tree keeps a
29// deterministic order for iteration inside Render.
30var results avl.Tree
31
32// stopping returns the number of steps to reach 1 and the peak value seen,
33// walking the Collatz (hailstone) map. It never mutates state.
34func stopping(n int64) (steps int, peak int64) {
35 peak = n
36 cur := n
37 for cur != 1 {
38 if steps >= maxIters {
39 break
40 }
41 if cur%2 == 0 {
42 cur = cur / 2
43 } else {
44 cur = 3*cur + 1
45 }
46 if cur > peak {
47 peak = cur
48 }
49 steps++
50 }
51 return steps, peak
52}
53
54// Compute walks the hailstone sequence for n and records the result
55// attributed to the caller. It is a crossing (state-mutating) func.
56func Compute(cur realm, n int) {
57 if n <= 0 {
58 panic("n must be > 0")
59 }
60 caller := unsafe.PreviousRealm().Address()
61 nn := int64(n)
62 steps, peak := stopping(nn)
63
64 res := Result{N: nn, Steps: steps, Peak: peak, Who: caller}
65 key := strconv.FormatInt(nn, 10)
66 results.Set(key, res)
67
68 chain.Emit(
69 "Computed",
70 "n", key,
71 "steps", strconv.Itoa(steps),
72 "peak", strconv.FormatInt(peak, 10),
73 "who", caller.String(),
74 )
75}
76
77// byLongest implements sort.Interface, ordering results by steps desc,
78// then peak desc, then n asc for stability.
79type byLongest []Result
80
81func (b byLongest) Len() int { return len(b) }
82func (b byLongest) Swap(i, j int) { b[i], b[j] = b[j], b[i] }
83func (b byLongest) Less(i, j int) bool {
84 if b[i].Steps != b[j].Steps {
85 return b[i].Steps > b[j].Steps
86 }
87 if b[i].Peak != b[j].Peak {
88 return b[i].Peak > b[j].Peak
89 }
90 return b[i].N < b[j].N
91}
92
93// Render shows the leaderboard at root, or the full hailstone sequence for a
94// given n at path "/<n>".
95func Render(path string) string {
96 p := strings.TrimPrefix(path, "/")
97 if p == "" {
98 return renderLeaderboard()
99 }
100 return renderSequence(p)
101}
102
103func renderLeaderboard() string {
104 all := make([]Result, 0, results.Size())
105 results.Iterate("", "", func(_ string, v interface{}) bool {
106 all = append(all, v.(Result))
107 return false
108 })
109
110 var sb strings.Builder
111 sb.WriteString("# Collatz Explorer\n\n")
112 sb.WriteString("Hailstone-sequence explorer. Call `Compute(n)` to record a run, ")
113 sb.WriteString("or view a full sequence at `/<n>`.\n\n")
114
115 if len(all) == 0 {
116 sb.WriteString("_No sequences submitted yet._\n")
117 return sb.String()
118 }
119
120 sort.Stable(byLongest(all))
121
122 sb.WriteString("## Leaderboard — longest sequences\n\n")
123 sb.WriteString("| # | n | steps | peak | who |\n")
124 sb.WriteString("|---|---|-------|------|-----|\n")
125 limit := len(all)
126 if limit > 20 {
127 limit = 20
128 }
129 for i := 0; i < limit; i++ {
130 r := all[i]
131 sb.WriteString("| " + strconv.Itoa(i+1) + " | ")
132 sb.WriteString("[" + strconv.FormatInt(r.N, 10) + "](/r:" + strconv.FormatInt(r.N, 10) + ") | ")
133 sb.WriteString(strconv.Itoa(r.Steps) + " | ")
134 sb.WriteString(strconv.FormatInt(r.Peak, 10) + " | ")
135 sb.WriteString(r.Who.String() + " |\n")
136 }
137 sb.WriteString("\n_" + strconv.Itoa(len(all)) + " sequence(s) recorded._\n")
138 return sb.String()
139}
140
141func renderSequence(p string) string {
142 n, err := strconv.ParseInt(p, 10, 64)
143 var sb strings.Builder
144 if err != nil || n <= 0 {
145 sb.WriteString("# Invalid n\n\n`" + p + "` is not a positive integer.\n")
146 return sb.String()
147 }
148
149 sb.WriteString("# Hailstone sequence for " + strconv.FormatInt(n, 10) + "\n\n")
150
151 seq := make([]int64, 0, 64)
152 cur := n
153 var peak int64 = n
154 truncated := false
155 for {
156 seq = append(seq, cur)
157 if cur == 1 {
158 break
159 }
160 if len(seq) >= maxSeqLen {
161 truncated = true
162 break
163 }
164 if cur%2 == 0 {
165 cur = cur / 2
166 } else {
167 cur = 3*cur + 1
168 }
169 if cur > peak {
170 peak = cur
171 }
172 }
173
174 parts := make([]string, len(seq))
175 for i, v := range seq {
176 parts[i] = strconv.FormatInt(v, 10)
177 }
178 sb.WriteString(strings.Join(parts, " → "))
179 sb.WriteString("\n\n")
180 sb.WriteString("- steps: " + strconv.Itoa(len(seq)-1) + "\n")
181 sb.WriteString("- peak: " + strconv.FormatInt(peak, 10) + "\n")
182 if truncated {
183 sb.WriteString("\n_Sequence truncated at " + strconv.Itoa(maxSeqLen) + " terms._\n")
184 }
185 return sb.String()
186}
