#include <stdio.h>
#include <string.h>

int lowest(int values[], int n) { /* 整数の配列の中から最小値を返す */
    int lowest = values[0];
    int i = 0;
    for (i = 1; i < n; i++) {
        if (values[i] < lowest) {
            lowest = values[i];
        }
    }
    return lowest;
}

int eddist(char *str1, char *str2, int pos1, int pos2) {
    /* 編集距離（レーベンシュタイン距離）を計算する関数
    str1, str2 は対象の文字列
    pos1, pos2 は現在見ている文字の位置（添え字+1）*/
    int opt[3];
    if (pos1 == 0) { /* str1の終わりに到達した場合、str2の残りの文字数を返す */
        return pos2;
    } else if (pos2 == 0) { /* str2の終わりに到達した場合、str1の残りの文字数を返す */
        return pos1;
    } else if (str1[pos1-1] == str2[pos2-1]) { /* 両方の文字列が対象の位置に同じ文字を持つ場合、次の位置に移動する */
        return eddist(str1, str2, pos1-1, pos2-1);
    } else {  
        opt[0] = eddist(str1, str2, pos1-1, pos2); /* str1から1文字を削除することと同じ */
        opt[1] = eddist(str1, str2, pos1, pos2-1); /* str1に1文字を挿入することと同じ */
        opt[2] = eddist(str1, str2, pos1-1, pos2-1); /* str1の1文字を置き換えることと同じ */
        return 1 + lowest(opt, 3);
    }
}

int main()
{
    int dist;
    char str1[] = "programming";
    char str2[] = "promising";
    dist = eddist(str1, str2, strlen(str1), strlen(str2));
    printf("Edit distance: %d\n", dist);
}