1 files changed, 97 insertions, 0 deletions
diff --git a/graphs/piscine/dlist/dlist-4.c b/graphs/piscine/dlist/dlist-4.c
new file mode 100644
index 0000000..9ed7aaa
--- /dev/null
+++ b/graphs/piscine/dlist/dlist-4.c
@@ -0,0 +1,97 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "dlist.h"
+
+size_t max(size_t a, size_t b)
+{
+    if (a >= b)
+    {
+        return a;
+    }
+    return b;
+}
+
+size_t min(size_t a, size_t b)
+{
+    if (a <= b)
+    {
+        return a;
+    }
+    return b;
+}
+
+size_t min_3(size_t a, size_t b, size_t c)
+{
+    if (a <= b)
+    {
+        if (a <= c)
+        {
+            return a;
+        }
+        return c;
+    }
+    else
+    {
+        if (b <= c)
+        {
+            return b;
+        }
+        return c;
+    }
+}
+
+size_t my_strlen(const int *s)
+{
+    size_t i;
+    for (i = 0; s[i] != -1; i++)
+    {
+        continue;
+    }
+    return i;
+}
+
+size_t levenshtein(const int *s1, const int *s2)
+{
+    size_t l1 = my_strlen(s1);
+    size_t l2 = my_strlen(s2);
+    if (min(l1, l2) == 0)
+    {
+        return max(l1, l2);
+    }
+
+    if (s1[0] == s2[0])
+    {
+        return levenshtein(s1 + 1, s2 + 1);
+    }
+
+    size_t lev1 = levenshtein(s1 + 1, s2);
+    size_t lev2 = levenshtein(s1, s2 + 1);
+    size_t lev3 = levenshtein(s1 + 1, s2 + 1);
+
+    return 1 + min_3(lev1, lev2, lev3);
+}
+
+int *to_str(const struct dlist *l)
+{
+    int *res = malloc((l->size + 1) * sizeof(int));
+    res[l->size] = -1;
+    size_t j = 0;
+    for (struct dlist_item *i = l->head; i; i = i->next, j++)
+    {
+        res[j] = i->data;
+    }
+    return res;
+}
+
+unsigned int dlist_levenshtein(const struct dlist *list1,
+                               const struct dlist *list2)
+{
+    int *l1 = to_str(list1);
+    int *l2 = to_str(list2);
+
+    unsigned int res = levenshtein(l1, l2);
+    free(l1);
+    free(l2);
+    return res;
+}