gno.land/r/moul/x/daily/collatz/v0⧉

1package collatz23import (4	"chain"5	"chain/runtime/unsafe"6	"sort"7	"strconv"8	"strings"910	"gno.land/p/nt/avl/v0"11)1213// maxIters caps the Collatz walk so a hostile / huge input cannot loop14// forever on-chain. No known n stays below this bound and fails to reach 1.15const maxIters = 10000001617// maxSeqLen caps how many terms Render("/<n>") will print.18const maxSeqLen = 5001920// Result is one recorded submission.21type Result struct {22	N     int6423	Steps int24	Peak  int6425	Who   address26}2728// results maps a decimal-string key of N -> Result. avl.Tree keeps a29// deterministic order for iteration inside Render.30var results avl.Tree3132// 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 = n36	cur := n37	for cur != 1 {38		if steps >= maxIters {39			break40		}41		if cur%2 == 0 {42			cur = cur / 243		} else {44			cur = 3*cur + 145		}46		if cur > peak {47			peak = cur48		}49		steps++50	}51	return steps, peak52}5354// Compute walks the hailstone sequence for n and records the result55// 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)6364	res := Result{N: nn, Steps: steps, Peak: peak, Who: caller}65	key := strconv.FormatInt(nn, 10)66	results.Set(key, res)6768	chain.Emit(69		"Computed",70		"n", key,71		"steps", strconv.Itoa(steps),72		"peak", strconv.FormatInt(peak, 10),73		"who", caller.String(),74	)75}7677// byLongest implements sort.Interface, ordering results by steps desc,78// then peak desc, then n asc for stability.79type byLongest []Result8081func (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].Steps86	}87	if b[i].Peak != b[j].Peak {88		return b[i].Peak > b[j].Peak89	}90	return b[i].N < b[j].N91}9293// Render shows the leaderboard at root, or the full hailstone sequence for a94// 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}102103func 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 false108	})109110	var sb strings.Builder111	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")114115	if len(all) == 0 {116		sb.WriteString("_No sequences submitted yet._\n")117		return sb.String()118	}119120	sort.Stable(byLongest(all))121122	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 = 20128	}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}140141func renderSequence(p string) string {142	n, err := strconv.ParseInt(p, 10, 64)143	var sb strings.Builder144	if err != nil || n <= 0 {145		sb.WriteString("# Invalid n\n\n`" + p + "` is not a positive integer.\n")146		return sb.String()147	}148149	sb.WriteString("# Hailstone sequence for " + strconv.FormatInt(n, 10) + "\n\n")150151	seq := make([]int64, 0, 64)152	cur := n153	var peak int64 = n154	truncated := false155	for {156		seq = append(seq, cur)157		if cur == 1 {158			break159		}160		if len(seq) >= maxSeqLen {161			truncated = true162			break163		}164		if cur%2 == 0 {165			cur = cur / 2166		} else {167			cur = 3*cur + 1168		}169		if cur > peak {170			peak = cur171		}172	}173174	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}187