Playground
collatz.gno
package collatz
import (
"chain"
"sort"
"strconv"
"strings"
"gno.land/p/moul/md/v0"
"gno.land/p/nt/avl/v0"
)
// selfPath is this realm's own page. A root-relative link resolves against
// the domain, not the realm, so every link back into it names it in full.
const selfPath = "/r/moul/x/daily/collatz/v1"
// maxIters caps the Collatz walk so a hostile / huge input cannot loop
// forever on-chain. No known n stays below this bound and fails to reach 1.
const maxIters = 1000000
// MaxResults bounds the leaderboard's state: anyone may Compute, and each new
// n is a new entry the root page sorts.
const MaxResults = 1000
// maxSeqLen caps how many terms Render("/<n>") will print.
const maxSeqLen = 500
// Result is one recorded submission.
type Result struct {
N int64
Steps int
Peak int64
Who address
}
// results maps a decimal-string key of N -> Result. avl.Tree keeps a
// deterministic order for iteration inside Render.
var results avl.Tree
// maxOdd is the largest odd term whose successor 3n+1 still fits in an
// int64. Past it the step wraps: 6148914691236517205 maps to exactly 2^64,
// which is 0, and the walk then spins on 0 until maxIters.
const maxOdd = (1<<63 - 1 - 1) / 3
// stopping returns the number of steps to reach 1 and the peak value seen,
// walking the Collatz (hailstone) map. ok is false when a term would overflow
// int64, in which case steps and peak describe the walk up to that term. It
// never mutates state.
func stopping(n int64) (steps int, peak int64, ok bool) {
peak = n
cur := n
for cur != 1 {
if steps >= maxIters {
break
}
if cur%2 == 0 {
cur = cur / 2
} else {
if cur > maxOdd {
return steps, peak, false
}
cur = 3*cur + 1
}
if cur > peak {
peak = cur
}
steps++
}
return steps, peak, true
}
// Compute walks the hailstone sequence for n and records the result
// attributed to the caller. It is a crossing (state-mutating) func.
func Compute(cur realm, n int) {
if !cur.IsCurrent() {
panic("collatz: spoofed realm")
}
caller := cur.Previous().Address()
if n <= 0 {
panic("n must be > 0")
}
nn := int64(n)
steps, peak, ok := stopping(nn)
if !ok {
// Recording it would put a wrapped walk on the leaderboard, forever.
panic("collatz: the walk from " + strconv.FormatInt(nn, 10) + " overflows int64")
}
res := Result{N: nn, Steps: steps, Peak: peak, Who: caller}
key := strconv.FormatInt(nn, 10)
if !results.Has(key) && results.Size() >= MaxResults {
panic("collatz: the leaderboard is full at " + strconv.Itoa(MaxResults) + " entries")
}
results.Set(key, res)
chain.Emit(
"Computed",
"n", key,
"steps", strconv.Itoa(steps),
"peak", strconv.FormatInt(peak, 10),
"who", caller.String(),
)
}
// byLongest implements sort.Interface, ordering results by steps desc,
// then peak desc, then n asc for stability.
type byLongest []Result
func (b byLongest) Len() int { return len(b) }
func (b byLongest) Swap(i, j int) { b[i], b[j] = b[j], b[i] }
func (b byLongest) Less(i, j int) bool {
if b[i].Steps != b[j].Steps {
return b[i].Steps > b[j].Steps
}
if b[i].Peak != b[j].Peak {
return b[i].Peak > b[j].Peak
}
return b[i].N < b[j].N
}
// Render shows the leaderboard at root, or the full hailstone sequence for a
// given n at path "/<n>".
func Render(path string) string {
p := strings.TrimPrefix(path, "/")
if p == "" {
return renderLeaderboard()
}
return renderSequence(p)
}
func renderLeaderboard() string {
all := make([]Result, 0, results.Size())
results.Iterate("", "", func(_ string, v interface{}) bool {
all = append(all, v.(Result))
return false
})
var sb strings.Builder
sb.WriteString("# Collatz Explorer\n\n")
sb.WriteString("Hailstone-sequence explorer. Call `Compute(n)` to record a run, ")
sb.WriteString("or view a full sequence at `/<n>`.\n\n")
if len(all) == 0 {
sb.WriteString("_No sequences submitted yet._\n")
return sb.String()
}
sort.Stable(byLongest(all))
sb.WriteString("## Leaderboard — longest sequences\n\n")
sb.WriteString("| # | n | steps | peak | who |\n")
sb.WriteString("|---|---|-------|------|-----|\n")
limit := len(all)
if limit > 20 {
limit = 20
}
for i := 0; i < limit; i++ {
r := all[i]
sb.WriteString("| " + strconv.Itoa(i+1) + " | ")
sb.WriteString("[" + strconv.FormatInt(r.N, 10) + "](" + selfPath + ":" + strconv.FormatInt(r.N, 10) + ") | ")
sb.WriteString(strconv.Itoa(r.Steps) + " | ")
sb.WriteString(strconv.FormatInt(r.Peak, 10) + " | ")
sb.WriteString(r.Who.String() + " |\n")
}
sb.WriteString("\n_" + strconv.Itoa(len(all)) + " sequence(s) recorded._\n")
return sb.String()
}
func renderSequence(p string) string {
n, err := strconv.ParseInt(p, 10, 64)
var sb strings.Builder
if err != nil || n <= 0 {
sb.WriteString("# Invalid n\n\n" + md.InlineCode(p) + " is not a positive integer.\n")
return sb.String()
}
sb.WriteString("# Hailstone sequence for " + strconv.FormatInt(n, 10) + "\n\n")
seq := make([]int64, 0, 64)
cur := n
var peak int64 = n
truncated := false
overflow := false
for {
seq = append(seq, cur)
if cur == 1 {
break
}
if len(seq) >= maxSeqLen {
truncated = true
break
}
if cur%2 == 0 {
cur = cur / 2
} else {
if cur > maxOdd {
overflow = true
break
}
cur = 3*cur + 1
}
if cur > peak {
peak = cur
}
}
parts := make([]string, len(seq))
for i, v := range seq {
parts[i] = strconv.FormatInt(v, 10)
}
sb.WriteString(strings.Join(parts, " → "))
sb.WriteString("\n\n")
sb.WriteString("- steps: " + strconv.Itoa(len(seq)-1) + "\n")
sb.WriteString("- peak: " + strconv.FormatInt(peak, 10) + "\n")
if overflow {
sb.WriteString("\n_Stopped: the next term would overflow int64._\n")
}
if truncated {
sb.WriteString("\n_Sequence truncated at " + strconv.Itoa(maxSeqLen) + " terms._\n")
}
return sb.String()
}
collatz_test.gno
package collatz
import (
"strings"
"testing"
"gno.land/p/nt/testutils/v0"
"gno.land/p/nt/uassert/v0"
)
func TestStopping(t *testing.T) {
cases := []struct {
n int64
steps int
peak int64
}{
{1, 0, 1},
{2, 1, 2},
{6, 8, 16},
{7, 16, 52},
{27, 111, 9232},
}
for _, c := range cases {
steps, peak, _ := stopping(c.n)
uassert.Equal(t, c.steps, steps)
uassert.Equal(t, c.peak, peak)
}
}
func TestComputeAndLeaderboard(cur realm, t *testing.T) {
addr := testutils.TestAddress("alice")
testing.SetRealm(testing.NewUserRealm(addr))
Compute(cross(cur), 27)
Compute(cross(cur), 6)
out := Render("")
uassert.True(t, strings.Contains(out, "Leaderboard"), "has leaderboard")
uassert.True(t, strings.Contains(out, "9232"), "shows peak of 27")
// 27 has more steps than 6, so it must appear first (rank 1).
i27 := strings.Index(out, "[27]")
i6 := strings.Index(out, "[6]")
uassert.True(t, i27 >= 0 && i6 >= 0, "both rows present")
uassert.True(t, i27 < i6, "27 ranked above 6")
}
func TestComputeRejectsNonPositive(cur realm, t *testing.T) {
addr := testutils.TestAddress("bob")
testing.SetRealm(testing.NewUserRealm(addr))
uassert.AbortsWithMessage(t, cur, "n must be > 0", func() {
Compute(cross(cur), 0)
})
}
func TestRenderSequence(t *testing.T) {
out := Render("/6")
uassert.True(t, strings.Contains(out, "6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1"), "full seq for 6")
uassert.True(t, strings.Contains(out, "steps: 8"), "reports 8 steps")
bad := Render("/abc")
uassert.True(t, strings.Contains(bad, "Invalid"), "rejects non-numeric path")
}
// 3n+1 for this n is exactly 2^64, which wraps to 0. Recording it would put a
// million-step walk on 0 at the top of the leaderboard, forever.
func TestComputeRefusesAnOverflowingWalk(cur realm, t *testing.T) {
uassert.AbortsContains(t, cur, "overflows int64", func() { Compute(cross(cur), 6148914691236517205) })
_, _, ok := stopping(27)
uassert.True(t, ok, "an ordinary walk is unaffected")
out := Render("/6148914691236517205")
uassert.True(t, strings.Contains(out, "would overflow int64"), out)
uassert.False(t, strings.Contains(out, "→ 0"), "no wrapped term rendered")
}
gnomod.toml
module = "gno.land/r/moul/x/daily/collatz/v1" gno = "0.9" private = true [addpkg] creator = "g1manfred47kzduec920z88wfr64ylksmdcedlf5" height = 592215 max_deposit = "6000000ugnot"
zz_bounds_test.gno
package collatz
import (
"strconv"
"testing"
"gno.land/p/nt/uassert/v0"
)
// Anyone may Compute, and each new n is an entry the root page sorts: the
// leaderboard refuses a new n once it is full, and still updates an old one.
func TestLeaderboardIsBounded(cur realm, t *testing.T) {
var added []string
for i := 1; results.Size() < MaxResults; i++ {
k := strconv.Itoa(1_000_000 + i)
results.Set(k, Result{N: int64(1_000_000 + i)})
added = append(added, k)
}
// One realm state per package run: leave the board as it was found.
defer func() {
for _, k := range added {
results.Remove(k)
}
}()
uassert.AbortsContains(t, cur, "leaderboard is full", func() { Compute(cross(cur), 999_999_937) })
Compute(cross(cur), 1_000_001) // an n already recorded is refreshed, not refused
}
zz_escape_test.gno
package collatz
import (
"strings"
"testing"
"gno.land/p/moul/md/v0"
"gno.land/p/nt/uassert/v0"
)
// A path that is not a valid input is echoed back. It is the visitor's text,
// so a backtick in it must not close a code span and let a link through.
func TestInvalidPathIsEscaped(t *testing.T) {
out := Render("/x` [claim](https://evil.example) `")
// Still there, but inside a span md.InlineCode widened past its backticks.
uassert.True(t, strings.Contains(out, md.InlineCode("x` [claim](https://evil.example) `")), out)
}
zz_links_test.gno
package collatz
import (
"strings"
"testing"
"gno.land/p/nt/testutils/v0"
"gno.land/p/nt/uassert/v0"
)
// The leaderboard links each n to this realm's own sequence page. It once
// linked to the malformed gno.land/r:<n>.
func TestLeaderboardLinksNameThisRealm(cur realm, t *testing.T) {
testing.SetRealm(testing.NewUserRealm(testutils.TestAddress("linker")))
Compute(cross(cur), 7)
out := Render("")
uassert.True(t, strings.Contains(out, "](/r/moul/x/daily/collatz/v1:7)"), out)
}