const std = @import("std");

pub fn main() void {
    const start = "hello";
    const end = "hal";

    const dist: u8 = edit_distance(start, end);
    std.debug.print("The minimum edit distance between {s} and {s} is {}\n", .{start, end, dist});
}

fn edit_distance(comptime start: []const u8, comptime end: []const u8) u8 {
    // Figure out why x and y are switched here.
    const x_dim = start.len + 1;
    const y_dim = end.len + 1;
    var matrix: [y_dim][x_dim]u8 = .{.{0} ** x_dim} ** y_dim;

    var n: u8 = 0;
    while (n < x_dim) : (n += 1) {
        matrix[0][n] = n;
    }

    n = 0;
    while (n < y_dim) : (n += 1) {
        matrix[n][0] = n;
    }

    var i: u8 = 1;
    while (i < x_dim): (i += 1) {
        const letter_i = start[i-1];
        var j: u8 = 1;
        while (j < y_dim): (j += 1) {
            const letter_j = end[j-1];
            if (letter_i == letter_j) {
                matrix[j][i] = matrix[j-1][i-1];
            }
            else {
                const delete: u8 = matrix[j][i-1] + 1;
                const insert: u8 = matrix[j-1][i] + 1;
                const substitute: u8 = matrix[j-1][i-1] + 1;
                var minimum: u8 = delete;
                if (insert < minimum) {
                    minimum = insert;
                }
                if (substitute < minimum) {
                    minimum = substitute;
                }
                matrix[j][i] = minimum;
            }
        }
    }

    for (matrix) |row, row_index| {
        for (row) |cell, column_index| {
            std.debug.print("{} ", .{cell});
        }
        std.debug.print("\n", .{});
    }

    return matrix[y_dim-1][x_dim-1];
}