A reactive notebook for Python — run reproducible experiments, query with SQL, execute as a script, deploy as an app, and version with git. Stored as pure Python. All in a modern, AI-native editor.
Python artificial-intelligencedagdata-sciencedata-visualizationdataflowdeveloper-toolsmachine-learningnotebookspipelinepythonreactivesqlweb-app
/* Copyright 2026 Marimo. All rights reserved. */
import { describe, expect, it } from "vitest";
import {
applyOperationsWithStub,
type EditOperation,
editDistance,
editDistanceGeneral,
mergeArray,
OperationType,
} from "../edit-distance";
describe("editDistance", () => {
it("should return distance 0 for identical arrays", () => {
const arr1 = ["a", "b", "c"];
const arr2 = ["a", "b", "c"];
const result = editDistance(arr1, arr2);
expect(result.distance).toBe(0);
expect(result.operations).toHaveLength(3);
expect(
result.operations.every((op) => op.type === OperationType.MATCH),
).toBe(true);
});
it("should handle empty arrays", () => {
const result1 = editDistance([], []);
expect(result1.distance).toBe(0);
expect(result1.operations).toHaveLength(0);
const result2 = editDistance(["a"], []);
expect(result2.distance).toBe(1);
expect(result2.operations).toHaveLength(1);
expect(result2.operations[0].type).toBe(OperationType.DELETE);
const result3 = editDistance([], ["a"]);
expect(result3.distance).toBe(1);
expect(result3.operations).toHaveLength(1);
expect(result3.operations[0].type).toBe(OperationType.INSERT);
});
it("should handle single element differences", () => {
const arr1 = ["a", "b", "c"];
const arr2 = ["a", "b", "d"];
const result = editDistance(arr1, arr2);
expect(result.distance).toBe(1);
expect(result.operations).toHaveLength(3);
expect(result.operations[0].type).toBe(OperationType.MATCH);
expect(result.operations[1].type).toBe(OperationType.MATCH);
expect(result.operations[2].type).toBe(OperationType.SUBSTITUTE);
});
it("should handle insertions and deletions", () => {
const arr1 = ["a", "b", "c"];
const arr2 = ["a", "x", "b", "c"];
const result = editDistance(arr1, arr2);
expect(result.distance).toBe(1);
expect(result.operations).toHaveLength(4);
expect(result.operations[0].type).toBe(OperationType.MATCH);
expect(result.operations[1].type).toBe(OperationType.INSERT);
expect(result.operations[2].type).toBe(OperationType.MATCH);
expect(result.operations[3].type).toBe(OperationType.MATCH);
});
it("should work with custom equality function", () => {
const arr1 = [
{ id: 1, name: "a" },
{ id: 2, name: "b" },
];
const arr2 = [
{ id: 1, name: "a" },
{ id: 3, name: "c" },
];
const result = editDistanceGeneral(arr1, arr2, (a, b) => a.id === b.id);
expect(result.distance).toBe(1);
expect(result.operations).toHaveLength(2);
expect(result.operations[0].type).toBe(OperationType.MATCH);
expect(result.operations[1].type).toBe(OperationType.SUBSTITUTE);
});
// Test the specific example mentioned by the user
it("should handle the specific example: abcde -> aczeg", () => {
const arr1 = ["a", "b", "c", "d", "e"];
const arr2 = ["a", "c", "z", "e", "g"];
const result = editDistance(arr1, arr2);
expect(result.distance).toBe(3);
expect(result.operations).toHaveLength(6);
// Expected operations: match, delete, match, sub, match, insert
expect(result.operations[0].type).toBe(OperationType.MATCH); // 'a'
expect(result.operations[1].type).toBe(OperationType.DELETE); // 'b'
expect(result.operations[2].type).toBe(OperationType.MATCH); // 'c'
expect(result.operations[3].type).toBe(OperationType.SUBSTITUTE); // 'd' -> 'z'
expect(result.operations[4].type).toBe(OperationType.MATCH); // 'e'
expect(result.operations[5].type).toBe(OperationType.INSERT); // 'g'
});
});
describe("applyOperationsWithStub", () => {
it("should apply match operations correctly", () => {
const original = ["a", "b", "c"];
const operations: EditOperation[] = [
{ type: OperationType.MATCH, position: 0 },
{ type: OperationType.MATCH, position: 1 },
{ type: OperationType.MATCH, position: 2 },
];
const result = applyOperationsWithStub(original, operations, "stub");
expect(result).toEqual(["a", "b", "c"]);
});
it("should apply delete operations correctly", () => {
const original = ["a", "b", "c"];
const operations: EditOperation[] = [
{ type: OperationType.MATCH, position: 0 },
{ type: OperationType.DELETE, position: 1 },
{ type: OperationType.MATCH, position: 2 },
];
const result = applyOperationsWithStub(original, operations, "stub");
expect(result).toEqual(["a", "c"]);
});
it("should apply insert operations correctly", () => {
const original = ["a", "c"];
const operations: EditOperation[] = [
{ type: OperationType.MATCH, position: 0 },
{ type: OperationType.INSERT, position: 1 },
{ type: OperationType.MATCH, position: 1 },
];
const result = applyOperationsWithStub(original, operations, "stub");
expect(result).toEqual(["a", "stub", "c"]);
});
it("should apply substitute operations correctly", () => {
const original = ["a", "b", "c"];
const operations: EditOperation[] = [
{ type: OperationType.MATCH, position: 0 },
{
type: OperationType.SUBSTITUTE,
position: 1,
},
{ type: OperationType.MATCH, position: 2 },
];
const result = applyOperationsWithStub(original, operations, "stub");
expect(result).toEqual(["a", "stub", "c"]);
});
it("should handle complex operations with position offsets", () => {
const original = ["a", "b", "c", "d"];
const operations: EditOperation[] = [
{ type: OperationType.MATCH, position: 0 },
{ type: OperationType.DELETE, position: 1 },
{ type: OperationType.INSERT, position: 1 },
{ type: OperationType.MATCH, position: 2 },
{ type: OperationType.DELETE, position: 3 },
];
const result = applyOperationsWithStub(original, operations, "stub");
expect(result).toEqual(["a", "stub", "c"]);
});
// Test the specific example mentioned by the user
it("should handle the specific example: abcde -> ac_e_ (with stub)", () => {
const original = ["a", "b", "c", "d", "e"];
const operations: EditOperation[] = [
{ type: OperationType.MATCH, position: 0 },
{ type: OperationType.DELETE, position: 1 },
{ type: OperationType.MATCH, position: 2 },
{
type: OperationType.SUBSTITUTE,
position: 3,
},
{ type: OperationType.MATCH, position: 4 },
{ type: OperationType.INSERT, position: 5 },
];
const result = applyOperationsWithStub(original, operations, "_");
expect(result).toEqual(["a", "c", "_", "e", "_"]);
});
it("should handle multiple consecutive operations correctly", () => {
const original = ["a", "b", "c"];
const operations: EditOperation[] = [
{ type: OperationType.DELETE, position: 0 },
{ type: OperationType.INSERT, position: 0 },
{
type: OperationType.SUBSTITUTE,
position: 1,
},
{ type: OperationType.DELETE, position: 2 },
];
const result = applyOperationsWithStub(original, operations, "stub");
// After DELETE at position 0: ["b", "c"] (offset = -1)
// After INSERT at position 0: ["stub", "b", "c"] (offset = 0)
// After SUBSTITUTE at position 1: ["stub", "stub", "c"] (offset = 0)
// After DELETE at position 2: ["stub", "stub"] (offset = -1)
expect(result).toEqual(["stub", "stub"]);
});
it("should handle operations that affect array length", () => {
const original = ["a", "b"];
const operations: EditOperation[] = [
{ type: OperationType.INSERT, position: 0 },
{ type: OperationType.INSERT, position: 1 },
{ type: OperationType.MATCH, position: 2 },
{ type: OperationType.MATCH, position: 3 },
{ type: OperationType.INSERT, position: 4 },
];
const result = applyOperationsWithStub(original, operations, "stub");
// After INSERT at position 0: ["stub", "a", "b"] (offset = 1)
// After INSERT at position 1: ["stub", "stub", "a", "b"] (offset = 2)
// After MATCH at position 2: ["stub", "stub", "a", "b"] (offset = 2)
// After MATCH at position 3: ["stub", "stub", "a", "b"] (offset = 2)
// After INSERT at position 4: ["stub", "stub", "a", "b", "stub"] (offset = 3)
expect(result).toEqual(["stub", "stub", "a", "b", "stub"]);
});
});
describe("mergeArray", () => {
it("should merge arrays with matching elements", () => {
const arr1 = ["a", "b", "c"];
const arr2 = ["a", "b", "c"];
const stub = "stub";
const result = mergeArray(arr1, arr2, (a, b) => a === b, stub);
expect(result.merged).toEqual(["a", "b", "c"]);
expect(result.edits.distance).toBe(0);
});
it("should merge arrays with different elements", () => {
const arr1 = ["a", "b", "c"];
const arr2 = ["a", "x", "c"];
const stub = "stub";
const result = mergeArray(arr1, arr2, (a, b) => a === b, stub);
expect(result.merged).toEqual(["a", "stub", "c"]);
expect(result.edits.distance).toBe(1);
});
it("should handle empty arrays", () => {
const arr1: string[] = [];
const arr2: string[] = [];
const stub = "stub";
const result = mergeArray(arr1, arr2, () => false, stub);
expect(result.merged).toEqual([]);
expect(result.edits.distance).toBe(0);
});
it("should handle one empty array", () => {
const arr1 = ["a", "b"];
const arr2: string[] = [];
const stub = "stub";
const result = mergeArray(arr1, arr2, () => false, stub);
expect(result.merged).toEqual([]);
expect(result.edits.distance).toBe(2);
});
it("should handle complex merging scenarios", () => {
const arr1 = ["a", "b", "c"];
const arr2 = ["a", "x", "y", "c"];
const stub = "stub";
const result = mergeArray(arr1, arr2, (a, b) => a === b, stub);
expect(result.merged).toEqual(["a", "stub", "stub", "c"]);
expect(result.edits.distance).toBe(2);
});
it("should handle the specific example: abcde -> aczeg", () => {
const arr1 = ["a", "b", "c", "d", "e"];
const arr2 = ["a", "c", "z", "e", "g"];
const stub = "_";
const result = mergeArray(arr1, arr2, (a, b) => a === b, stub);
// For abcde -> aczeg:
// a matches a -> keep a
// b is deleted -> skip b
// c matches c -> keep c
// d is substituted with z -> use stub _
// e matches e -> keep e
// g is inserted -> use stub _
expect(result.merged).toEqual(["a", "c", "_", "e", "_"]);
expect(result.edits.distance).toBe(3);
});
});