levenshteindemo.gno

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