collatz.gno
5.74 Kb · 222 lines
1package collatz
2
3import (
4 "chain"
5 "sort"
6 "strconv"
7 "strings"
8
9 "gno.land/p/moul/md/v0"
10 "gno.land/p/nt/avl/v0"
11)
12
13// selfPath is this realm's own page. A root-relative link resolves against
14// the domain, not the realm, so every link back into it names it in full.
15const selfPath = "/r/moul/x/daily/collatz/v1"
16
17// maxIters caps the Collatz walk so a hostile / huge input cannot loop
18// forever on-chain. No known n stays below this bound and fails to reach 1.
19const maxIters = 1000000
20
21// MaxResults bounds the leaderboard's state: anyone may Compute, and each new
22// n is a new entry the root page sorts.
23const MaxResults = 1000
24
25// maxSeqLen caps how many terms Render("/<n>") will print.
26const maxSeqLen = 500
27
28// Result is one recorded submission.
29type Result struct {
30 N int64
31 Steps int
32 Peak int64
33 Who address
34}
35
36// results maps a decimal-string key of N -> Result. avl.Tree keeps a
37// deterministic order for iteration inside Render.
38var results avl.Tree
39
40// maxOdd is the largest odd term whose successor 3n+1 still fits in an
41// int64. Past it the step wraps: 6148914691236517205 maps to exactly 2^64,
42// which is 0, and the walk then spins on 0 until maxIters.
43const maxOdd = (1<<63 - 1 - 1) / 3
44
45// stopping returns the number of steps to reach 1 and the peak value seen,
46// walking the Collatz (hailstone) map. ok is false when a term would overflow
47// int64, in which case steps and peak describe the walk up to that term. It
48// never mutates state.
49func stopping(n int64) (steps int, peak int64, ok bool) {
50 peak = n
51 cur := n
52 for cur != 1 {
53 if steps >= maxIters {
54 break
55 }
56 if cur%2 == 0 {
57 cur = cur / 2
58 } else {
59 if cur > maxOdd {
60 return steps, peak, false
61 }
62 cur = 3*cur + 1
63 }
64 if cur > peak {
65 peak = cur
66 }
67 steps++
68 }
69 return steps, peak, true
70}
71
72// Compute walks the hailstone sequence for n and records the result
73// attributed to the caller. It is a crossing (state-mutating) func.
74func Compute(cur realm, n int) {
75 if !cur.IsCurrent() {
76 panic("collatz: spoofed realm")
77 }
78 caller := cur.Previous().Address()
79 if n <= 0 {
80 panic("n must be > 0")
81 }
82 nn := int64(n)
83 steps, peak, ok := stopping(nn)
84 if !ok {
85 // Recording it would put a wrapped walk on the leaderboard, forever.
86 panic("collatz: the walk from " + strconv.FormatInt(nn, 10) + " overflows int64")
87 }
88
89 res := Result{N: nn, Steps: steps, Peak: peak, Who: caller}
90 key := strconv.FormatInt(nn, 10)
91 if !results.Has(key) && results.Size() >= MaxResults {
92 panic("collatz: the leaderboard is full at " + strconv.Itoa(MaxResults) + " entries")
93 }
94 results.Set(key, res)
95
96 chain.Emit(
97 "Computed",
98 "n", key,
99 "steps", strconv.Itoa(steps),
100 "peak", strconv.FormatInt(peak, 10),
101 "who", caller.String(),
102 )
103}
104
105// byLongest implements sort.Interface, ordering results by steps desc,
106// then peak desc, then n asc for stability.
107type byLongest []Result
108
109func (b byLongest) Len() int { return len(b) }
110func (b byLongest) Swap(i, j int) { b[i], b[j] = b[j], b[i] }
111func (b byLongest) Less(i, j int) bool {
112 if b[i].Steps != b[j].Steps {
113 return b[i].Steps > b[j].Steps
114 }
115 if b[i].Peak != b[j].Peak {
116 return b[i].Peak > b[j].Peak
117 }
118 return b[i].N < b[j].N
119}
120
121// Render shows the leaderboard at root, or the full hailstone sequence for a
122// given n at path "/<n>".
123func Render(path string) string {
124 p := strings.TrimPrefix(path, "/")
125 if p == "" {
126 return renderLeaderboard()
127 }
128 return renderSequence(p)
129}
130
131func renderLeaderboard() string {
132 all := make([]Result, 0, results.Size())
133 results.Iterate("", "", func(_ string, v interface{}) bool {
134 all = append(all, v.(Result))
135 return false
136 })
137
138 var sb strings.Builder
139 sb.WriteString("# Collatz Explorer\n\n")
140 sb.WriteString("Hailstone-sequence explorer. Call `Compute(n)` to record a run, ")
141 sb.WriteString("or view a full sequence at `/<n>`.\n\n")
142
143 if len(all) == 0 {
144 sb.WriteString("_No sequences submitted yet._\n")
145 return sb.String()
146 }
147
148 sort.Stable(byLongest(all))
149
150 sb.WriteString("## Leaderboard — longest sequences\n\n")
151 sb.WriteString("| # | n | steps | peak | who |\n")
152 sb.WriteString("|---|---|-------|------|-----|\n")
153 limit := len(all)
154 if limit > 20 {
155 limit = 20
156 }
157 for i := 0; i < limit; i++ {
158 r := all[i]
159 sb.WriteString("| " + strconv.Itoa(i+1) + " | ")
160 sb.WriteString("[" + strconv.FormatInt(r.N, 10) + "](" + selfPath + ":" + strconv.FormatInt(r.N, 10) + ") | ")
161 sb.WriteString(strconv.Itoa(r.Steps) + " | ")
162 sb.WriteString(strconv.FormatInt(r.Peak, 10) + " | ")
163 sb.WriteString(r.Who.String() + " |\n")
164 }
165 sb.WriteString("\n_" + strconv.Itoa(len(all)) + " sequence(s) recorded._\n")
166 return sb.String()
167}
168
169func renderSequence(p string) string {
170 n, err := strconv.ParseInt(p, 10, 64)
171 var sb strings.Builder
172 if err != nil || n <= 0 {
173 sb.WriteString("# Invalid n\n\n" + md.InlineCode(p) + " is not a positive integer.\n")
174 return sb.String()
175 }
176
177 sb.WriteString("# Hailstone sequence for " + strconv.FormatInt(n, 10) + "\n\n")
178
179 seq := make([]int64, 0, 64)
180 cur := n
181 var peak int64 = n
182 truncated := false
183 overflow := false
184 for {
185 seq = append(seq, cur)
186 if cur == 1 {
187 break
188 }
189 if len(seq) >= maxSeqLen {
190 truncated = true
191 break
192 }
193 if cur%2 == 0 {
194 cur = cur / 2
195 } else {
196 if cur > maxOdd {
197 overflow = true
198 break
199 }
200 cur = 3*cur + 1
201 }
202 if cur > peak {
203 peak = cur
204 }
205 }
206
207 parts := make([]string, len(seq))
208 for i, v := range seq {
209 parts[i] = strconv.FormatInt(v, 10)
210 }
211 sb.WriteString(strings.Join(parts, " → "))
212 sb.WriteString("\n\n")
213 sb.WriteString("- steps: " + strconv.Itoa(len(seq)-1) + "\n")
214 sb.WriteString("- peak: " + strconv.FormatInt(peak, 10) + "\n")
215 if overflow {
216 sb.WriteString("\n_Stopped: the next term would overflow int64._\n")
217 }
218 if truncated {
219 sb.WriteString("\n_Sequence truncated at " + strconv.Itoa(maxSeqLen) + " terms._\n")
220 }
221 return sb.String()
222}
