Levenshtein edit distance

// Levenshtein edit distance, Zero 0.1.2 direct backend.
//
// Same input convention as tasks 001 and 002: arguments come from argv
// because Zero 0.1.2 has no exposed stdin capability. A comes from
// argv[1] and B from argv[2]. All logic stays inside `pub fun main` to
// avoid the Span/MutSpan-as-parameter restriction.
//
// Two rolling [51]u32 buffers form the DP row (current and previous).
// Spec caps each string at 50 characters so a 51-cell row covers it.
pub fun main(world: World) -> Void raises {
    let a_opt = std.args.get(1)
    let b_opt = std.args.get(2)
    if a_opt.has == false || b_opt.has == false {
        check world.err.write("usage: pass A as argv[1] and B as argv[2] (Zero 0.1.2 has no stdin capability)\n")
        return
    }

    let a_bytes: Span<u8> = std.mem.span(a_opt.value)
    let b_bytes: Span<u8> = std.mem.span(b_opt.value)
    let a_len: usize = std.mem.len(a_bytes)
    let b_len: usize = std.mem.len(b_bytes)
    if a_len > 50 || b_len > 50 {
        check world.err.write("each string must be at most 50 characters\n")
        return
    }

    let mut prev: [51]u32 = [0_u32; 51]
    let mut curr: [51]u32 = [0_u32; 51]

    let mut j: usize = 0
    while j <= b_len {
        prev[j] = j as u32
        j = j + 1
    }

    let mut i: usize = 0
    while i < a_len {
        curr[0] = (i + 1) as u32
        let ai: u8 = a_bytes[i]
        let mut k: usize = 0
        while k < b_len {
            let bk: u8 = b_bytes[k]
            let del_cost: u32 = prev[k + 1] + 1_u32
            let ins_cost: u32 = curr[k] + 1_u32
            let mut sub_cost: u32 = prev[k]
            if ai != bk {
                sub_cost = sub_cost + 1_u32
            }
            let mut best: u32 = del_cost
            if ins_cost < best {
                best = ins_cost
            }
            if sub_cost < best {
                best = sub_cost
            }
            curr[k + 1] = best
            k = k + 1
        }
        let mut copy_i: usize = 0
        while copy_i <= b_len {
            prev[copy_i] = curr[copy_i]
            copy_i = copy_i + 1
        }
        i = i + 1
    }

    let distance: u32 = prev[b_len]

    let mut buf: [16]u8 = [0_u8; 16]
    let mut written: usize = 0
    if distance == 0_u32 {
        buf[0] = 48_u8
        buf[1] = 10_u8
        written = 2
    } else {
        let mut digits: [16]u8 = [0_u8; 16]
        let mut rem: u32 = distance
        let mut digit_count: usize = 0
        while rem > 0_u32 {
            let dq: u32 = rem / 10_u32
            let dr: u32 = rem % 10_u32
            digits[digit_count] = (dr as u8) + 48_u8
            rem = dq
            digit_count = digit_count + 1
        }
        let mut o: usize = 0
        while o < digit_count {
            buf[o] = digits[digit_count - 1 - o]
            o = o + 1
        }
        buf[digit_count] = 10_u8
        written = digit_count + 1
    }
    let out: Span<u8> = buf[0..written]
    check world.out.write(out)
    return
}

// Levenshtein edit distance, TypeScript reference.
// Reads A and B from stdin (one per line), runs a two-row DP.
import { readFileSync } from "node:fs";

const raw = readFileSync(0, "utf8");
const lines = raw.split("\n");
const a = lines[0] ?? "";
const b = lines[1] ?? "";
if (a.length > 50 || b.length > 50) {
  process.stderr.write("each string must be at most 50 characters\n");
  process.exit(1);
}

const m = a.length;
const n = b.length;
let prev = new Array<number>(n + 1);
let curr = new Array<number>(n + 1);
for (let j = 0; j <= n; j++) prev[j] = j;
for (let i = 0; i < m; i++) {
  curr[0] = i + 1;
  const ai = a.charCodeAt(i);
  for (let k = 0; k < n; k++) {
    const delCost = prev[k + 1] + 1;
    const insCost = curr[k] + 1;
    const subCost = prev[k] + (ai === b.charCodeAt(k) ? 0 : 1);
    curr[k + 1] = Math.min(delCost, insCost, subCost);
  }
  [prev, curr] = [curr, prev];
}
process.stdout.write(`${prev[n]}\n`);

// Levenshtein edit distance, Rust reference.
// Reads A and B from stdin (one per line), runs a two-row DP.
use std::io::{self, Read, Write};
use std::process::ExitCode;

fn main() -> ExitCode {
    let mut input = String::new();
    if io::stdin().read_to_string(&mut input).is_err() {
        let _ = writeln!(io::stderr(), "failed to read stdin");
        return ExitCode::from(1);
    }
    let mut lines = input.split('\n');
    let a = lines.next().unwrap_or("");
    let b = lines.next().unwrap_or("");
    if a.chars().count() > 50 || b.chars().count() > 50 {
        let _ = writeln!(io::stderr(), "each string must be at most 50 characters");
        return ExitCode::from(1);
    }
    let a_bytes = a.as_bytes();
    let b_bytes = b.as_bytes();
    let m = a_bytes.len();
    let n = b_bytes.len();
    let mut prev: Vec<u32> = (0..=n as u32).collect();
    let mut curr: Vec<u32> = vec![0; n + 1];
    for i in 0..m {
        curr[0] = (i + 1) as u32;
        for k in 0..n {
            let del_cost = prev[k + 1] + 1;
            let ins_cost = curr[k] + 1;
            let sub_cost = prev[k] + if a_bytes[i] == b_bytes[k] { 0 } else { 1 };
            curr[k + 1] = del_cost.min(ins_cost).min(sub_cost);
        }
        std::mem::swap(&mut prev, &mut curr);
    }
    let _ = writeln!(io::stdout(), "{}", prev[n]);
    ExitCode::SUCCESS
}

// Levenshtein edit distance, Go reference.
// Reads A and B from stdin (one per line), runs a two-row DP.
package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"strings"
)

func main() {
	raw, err := io.ReadAll(bufio.NewReader(os.Stdin))
	if err != nil {
		fmt.Fprintln(os.Stderr, "failed to read stdin")
		os.Exit(1)
	}
	lines := strings.SplitN(string(raw), "\n", 3)
	var a, b string
	if len(lines) >= 1 {
		a = lines[0]
	}
	if len(lines) >= 2 {
		b = lines[1]
	}
	if len(a) > 50 || len(b) > 50 {
		fmt.Fprintln(os.Stderr, "each string must be at most 50 characters")
		os.Exit(1)
	}
	m, n := len(a), len(b)
	prev := make([]int, n+1)
	curr := make([]int, n+1)
	for j := 0; j <= n; j++ {
		prev[j] = j
	}
	for i := 0; i < m; i++ {
		curr[0] = i + 1
		for k := 0; k < n; k++ {
			delCost := prev[k+1] + 1
			insCost := curr[k] + 1
			subCost := prev[k]
			if a[i] != b[k] {
				subCost++
			}
			best := delCost
			if insCost < best {
				best = insCost
			}
			if subCost < best {
				best = subCost
			}
			curr[k+1] = best
		}
		prev, curr = curr, prev
	}
	fmt.Print(prev[n], "\n")
}

"""Levenshtein edit distance, Python reference.

Reads two lines from stdin (A and B), computes the classic two-row DP,
and writes the distance plus a trailing newline.
"""
import sys


def main() -> None:
    data = sys.stdin.read().split("\n")
    a = data[0] if len(data) >= 1 else ""
    b = data[1] if len(data) >= 2 else ""
    if len(a) > 50 or len(b) > 50:
        sys.stderr.write("each string must be at most 50 characters\n")
        sys.exit(1)
    m, n = len(a), len(b)
    prev = list(range(n + 1))
    curr = [0] * (n + 1)
    for i in range(m):
        curr[0] = i + 1
        ai = a[i]
        for k in range(n):
            del_cost = prev[k + 1] + 1
            ins_cost = curr[k] + 1
            sub_cost = prev[k] + (0 if ai == b[k] else 1)
            curr[k + 1] = min(del_cost, ins_cost, sub_cost)
        prev, curr = curr, prev
    sys.stdout.write(f"{prev[n]}\n")


if __name__ == "__main__":
    main()