2 files changed, 138 insertions, 0 deletions
diff --git a/src/utils/lambdas.ts b/src/utils/lambdas.ts
new file mode 100644
index 0000000..ef6b399
--- /dev/null
+++ b/src/utils/lambdas.ts
@@ -0,0 +1,35 @@
+const succ = "(λ n.(λ f.(λ x.(f ((n f) x)))))";
+const zero = "(λ g.(λ y.y))";
+const one = "(λ g.(λ y.(g y)))";
+const two = "(λ g.(λ y.(g (g y))))";
+const three = "(λ g.(λ y.(g (g (g y)))))";
+const four = "(λ g.(λ y.(g (g (g (g y))))))";
+const five = "(λ g.(λ y.(g (g (g (g (g y)))))))";
+const mult = "(λ m.(λ n.(λ f.(m (n f)))))";
+const trueL = "(λ a.(λ b.a))";
+const falseL = "(λ a.(λ b.b))";
+const ifL = "(λ b.(λ n.(λ m.((b n) m))))";
+const iszero = "(λ num.((num (λ x.false)) true))";
+const not = "(λ b.((b false) true))";
+const and = "(λ b.(λ c.((b c) false)))";
+const or = "(λ b.(λ c.((b true) c)))";
+const Y = "(λ h.((λ z.(h (z z))) (λ z.(h (z z)))))";
+
+export const baseDefinitions = {
+  iszero,
+  succ,
+  zero,
+  one,
+  two,
+  three,
+  four,
+  five,
+  mult,
+  true: trueL,
+  false: falseL,
+  if: ifL,
+  not,
+  and,
+  or,
+  Y,
+};
diff --git a/src/utils/levenshtein.ts b/src/utils/levenshtein.ts
new file mode 100644
index 0000000..87bfd9d
--- /dev/null
+++ b/src/utils/levenshtein.ts
@@ -0,0 +1,103 @@
+export enum EditOperation {
+  Insert = "insert",
+  Delete = "delete",
+  Edit = "edit",
+  None = "none",
+}
+
+interface Diff {
+  old: string;
+  new: string;
+}
+
+interface Edit {
+  operation: EditOperation;
+  diff: Diff;
+}
+
+export const calculateLevenshteinOperations = (
+  str1: string,
+  str2: string
+): Edit[] => {
+  const len1 = str1.length;
+  const len2 = str2.length;
+  const dp: number[][] = Array.from({ length: len1 + 1 }, () =>
+    Array(len2 + 1).fill(0)
+  );
+
+  // Initialize DP table
+  for (let i = 0; i <= len1; i++) dp[i][0] = i;
+  for (let j = 0; j <= len2; j++) dp[0][j] = j;
+
+  // Fill DP table
+  for (let i = 1; i <= len1; i++) {
+    for (let j = 1; j <= len2; j++) {
+      const cost = str1[i - 1] === str2[j - 1] ? 0 : 1;
+      dp[i][j] = Math.min(
+        dp[i - 1][j] + 1, // Deletion
+        dp[i][j - 1] + 1, // Insertion
+        dp[i - 1][j - 1] + cost // Substitution (Edit)
+      );
+    }
+  }
+
+  // Backtrack to find operations
+  let operations: Edit[] = [];
+  let i = len1,
+    j = len2;
+  while (i > 0 || j > 0) {
+    if (
+      i > 0 &&
+      j > 0 &&
+      dp[i][j] === dp[i - 1][j - 1] &&
+      str1[i - 1] === str2[j - 1]
+    ) {
+      // No operation needed
+      operations.unshift({
+        operation: EditOperation.None,
+        diff: { old: str1[i - 1], new: str2[j - 1] },
+      });
+      i--;
+      j--;
+    } else if (i > 0 && dp[i][j] === dp[i - 1][j] + 1) {
+      // Delete operation
+      operations.unshift({
+        operation: EditOperation.Delete,
+        diff: { old: str1[i - 1], new: "" },
+      });
+      i--;
+    } else if (j > 0 && dp[i][j] === dp[i][j - 1] + 1) {
+      // Insert operation
+      operations.unshift({
+        operation: EditOperation.Insert,
+        diff: { old: "", new: str2[j - 1] },
+      });
+      j--;
+    } else if (i > 0 && j > 0) {
+      // Edit operation
+      operations.unshift({
+        operation: EditOperation.Edit,
+        diff: { old: str1[i - 1], new: str2[j - 1] },
+      });
+      i--;
+      j--;
+    }
+  }
+
+  // Simplify consecutive "none" operations into single operations
+  const simplifiedOperations = operations.reduce<Edit[]>((acc, op) => {
+    if (
+      acc.length > 0 &&
+      op.operation === EditOperation.None &&
+      acc[acc.length - 1].operation === EditOperation.None
+    ) {
+      acc[acc.length - 1].diff.old += op.diff.old;
+      acc[acc.length - 1].diff.new += op.diff.new;
+    } else {
+      acc.push(op);
+    }
+    return acc;
+  }, []);
+
+  return simplifiedOperations;
+};