Skip to content Search Apps Documentation Source Content Run Reset Eval Playground File Folder Download Copy Actions State String Boolean Number Struct Map Slice Pointer Function Closure Reference Nil Package Type Interface Unknown

Community realm. Read the code first. Community realm, deployed by its author. Read the code before you interact or send coins.

levenshteindemo.gno

4.94 Kb · 148 lines
  1// Package levenshteindemo is a small gnoweb demo of the Levenshtein edit-distance
  2// library provided by [p/moul/x/daily/levenshtein](/p/moul/x/daily/levenshtein/v0):
  3// it renders an explanation, worked examples, and an interactive distance
  4// calculator with the full dynamic-programming table.
  5//
  6// It contains no distance logic of its own — everything comes from
  7// `levenshtein.Distance`, `levenshtein.Matrix` and `levenshtein.Similarity`.
  8package levenshteindemo
  9
 10import (
 11	"strconv"
 12	"strings"
 13
 14	"gno.land/p/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/kit/ui/v0"
 15	"gno.land/p/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/md/v0"
 16	"gno.land/p/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/x/daily/levenshtein/v0"
 17)
 18
 19// Render implements the gnoweb view.
 20//
 21//   - "" or "/"            : explanation + examples.
 22//   - "/<a>/<b>"           : distance between a and b, with the DP table.
 23func Render(path string) string {
 24	path = strings.TrimPrefix(path, "/")
 25	if path == "" {
 26		return renderHome()
 27	}
 28
 29	parts := strings.SplitN(path, "/", 2)
 30	if len(parts) != 2 {
 31		var sb strings.Builder
 32		sb.WriteString("# Levenshtein\n\n")
 33		sb.WriteString("Provide two words as `/<a>/<b>`, e.g. [`/kitten/sitting`](/r/moul/x/daily/levenshteindemo/v1:kitten/sitting).\n\n")
 34		sb.WriteString("[← back](/r/moul/x/daily/levenshteindemo/v1)\n")
 35		return sb.String()
 36	}
 37
 38	a := parts[0]
 39	b := parts[1]
 40	dist := levenshtein.Distance(a, b)
 41	sim := levenshtein.Similarity(a, b)
 42
 43	var sb strings.Builder
 44	sb.WriteString("# Levenshtein distance\n\n")
 45	sb.WriteString("Transforming **" + md.InlineCode(a) + "** → **" + md.InlineCode(b) + "**\n\n")
 46	sb.WriteString("- **Edit distance:** `")
 47	sb.WriteString(strconv.Itoa(dist))
 48	sb.WriteString("` single-character edits (insert / delete / substitute)\n")
 49	sb.WriteString("- **Similarity:** `")
 50	sb.WriteString(strconv.Itoa(sim))
 51	sb.WriteString("%`\n\n")
 52
 53	sb.WriteString("## DP table\n\n")
 54	sb.WriteString("Each cell `d[i][j]` is the distance between the first *i* runes of ")
 55	sb.WriteString(md.InlineCode(a))
 56	sb.WriteString(" and the first *j* runes of ")
 57	sb.WriteString(md.InlineCode(b))
 58	sb.WriteString(". The bottom-right cell is the answer.\n\n")
 59	sb.WriteString(renderTable(a, b))
 60	sb.WriteString("\n[← back](/r/moul/x/daily/levenshteindemo/v1)\n")
 61	return sb.String()
 62}
 63
 64func renderHome() string {
 65	var sb strings.Builder
 66	sb.WriteString("# Levenshtein edit distance\n\n")
 67	sb.WriteString("Demo of the [`p/moul/x/daily/levenshtein`](/p/moul/x/daily/levenshtein/v0) library. ")
 68	sb.WriteString("The **Levenshtein distance** between two strings is the minimum number of ")
 69	sb.WriteString("single-character edits — *insertions*, *deletions*, or *substitutions* — ")
 70	sb.WriteString("needed to turn one string into the other. The library implements the classic ")
 71	sb.WriteString("dynamic-programming algorithm (à la Go's `agext/levenshtein`) fully rune-aware and on-chain.\n\n")
 72
 73	sb.WriteString("## Try it\n\n")
 74	sb.WriteString("Append two words as `/<a>/<b>`:\n\n")
 75	examples := [][2]string{
 76		{"kitten", "sitting"},
 77		{"flaw", "lawn"},
 78		{"sunday", "saturday"},
 79		{"gno", "gnoland"},
 80	}
 81	for _, ex := range examples {
 82		a, b := ex[0], ex[1]
 83		d := levenshtein.Distance(a, b)
 84		sb.WriteString("- [`/")
 85		sb.WriteString(a)
 86		sb.WriteString("/")
 87		sb.WriteString(b)
 88		sb.WriteString("`](/r/moul/x/daily/levenshteindemo/v1:")
 89		sb.WriteString(a)
 90		sb.WriteString("/")
 91		sb.WriteString(b)
 92		sb.WriteString(") → distance **")
 93		sb.WriteString(strconv.Itoa(d))
 94		sb.WriteString("**\n")
 95	}
 96
 97	sb.WriteString("\n## The classic example\n\n")
 98	sb.WriteString("`kitten` → `sitting` = **3**:\n\n")
 99	sb.WriteString("1. `kitten` → `sitten` (substitute *k* → *s*)\n")
100	sb.WriteString("2. `sitten` → `sittin` (substitute *e* → *i*)\n")
101	sb.WriteString("3. `sittin` → `sitting` (insert *g* at the end)\n\n")
102
103	sb.WriteString("## API\n\n")
104	sb.WriteString("- `Distance(a, b string) int` — the edit distance.\n")
105	sb.WriteString("- `Matrix(a, b string) [][]int` — the full DP matrix.\n")
106	sb.WriteString("- `Similarity(a, b string) int` — a 0..100 similarity percentage.\n")
107	return sb.String()
108}
109
110// renderTable formats the DP matrix as a Markdown table with a and b as headers.
111func renderTable(a, b string) string {
112	ra := []rune(a)
113	rb := []rune(b)
114	d := levenshtein.Matrix(a, b)
115
116	var sb strings.Builder
117	// Header row: blank | "" | each rune of b.
118	sb.WriteString("|   | ε |")
119	for _, r := range rb {
120		sb.WriteString(" ")
121		sb.WriteString(ui.Cell(string(r)))
122		sb.WriteString(" |")
123	}
124	sb.WriteString("\n")
125	// Separator.
126	sb.WriteString("|---|")
127	for j := 0; j <= len(rb); j++ {
128		sb.WriteString("---|")
129	}
130	sb.WriteString("\n")
131	// Data rows.
132	for i := 0; i <= len(ra); i++ {
133		if i == 0 {
134			sb.WriteString("| **ε** |")
135		} else {
136			sb.WriteString("| **")
137			sb.WriteString(ui.Cell(string(ra[i-1])))
138			sb.WriteString("** |")
139		}
140		for j := 0; j <= len(rb); j++ {
141			sb.WriteString(" ")
142			sb.WriteString(strconv.Itoa(d[i][j]))
143			sb.WriteString(" |")
144		}
145		sb.WriteString("\n")
146	}
147	return sb.String()
148}