C ile Örüntü Tanıma / Pattern Recognotion

21 Feb 2022

Öncelikle eğer direkt videoya ulaşmak istiyorsanız: LINK

Bu problemi ilk etapta “python’da bundan 50 kere çözdük ne var ya :D” diyerek küçümsedim. Çok yanılmışım arkadaşlar. C’nin ne kadar gudubet bela bir şey olabileceğini unutmuşum… Neyse ki üstesinden bir şekilde gelebildik. Video da söylüyorum ama burada tekrar söylemekte fayda olduğunu düşünüyorum. Veri yapıları teoride herkesin bir sonuç üretebileceği ancak genelin daha verimli sonuçlar istediği bir problem çözme yeteneğidir, geliştirilebilir. Elimden geldiğince keşfettiğim şekilde verimli çözmeye çalışıyorum teşekkürler.

Probleme bir bakalım;

-> Elimizde 0 ve 1’lerden oluşan n uzunluğunda bir array var, birde elimizde bir desenimiz var. Bu arrayin içindeki bu desenleri bulup çıkarmamız gerek.

İskeletimiz;

#include <stdio.h>
#include <stdlib.h>

void solve(char *arr, char pattern[]);

int main()
{
    char arr1[] = "1010110101101100010101011101010110110001010101111101101011011000101010101101100010101011110111100010101011101"; // 110
    char pattern[] = "101011011000101010111";
    int i;
    solve(arr, pattern);
    for (i = 0; arr[i] != '\0'; i++)
    {
        printf("%c", arr[i]);
    }
    printf(" %d ", i);
}

Yukarıda görüldüğü üzere bir adet ‘solve’ fonksiyonu tanımladım, bu fonksiyon arrayimizi ve desenimizi parametre olarak alıyor. Buradan sonrasında arrayimizin elemanını tek tek gezmemiz gerekiyor.

void solve(char *arr, char pattern[])
{
    int i = 0;

    for (; arr[i] != '\0'; i++)
    {
    }
}

Şu anda arrayimizi tek tek geziyoruz ancak yeterli değil arrayin her elemanının desenimizle uyuşmasına bakmalıyız.

void solve(char *arr, char pattern[])
{
    int i = 0;

    for (; arr[i] != '\0'; i++)
    {
        int j;
        for (j = 0; pattern[j] != '\0'; j++)
        {
            if (arr[i + j] != pattern[j])
            {
                break;
            }
        }
    }
}

Arrayimiz ve desenimiz tek tek inceleniyor ve eğer uyuşmazlarsa döngü kırılıyor, peki ya eşleşirlerse? Bu noktada eşleştikleri durumu da kodumuza ekleyelim.

void solve(char *arr, char pattern[])
{
    int i = 0;

    for (; arr[i] != '\0'; i++)
    {
        int j;
        for (j = 0; pattern[j] != '\0'; j++)
        {
            if (arr[i + j] != pattern[j])
            {
                break;
            }
        }

        if (pattern[j] == '\0')
        {
            int q;
            for (q = i; arr[q] != '\0'; q++)
            {
                arr[q] = arr[q + j];
            }
            arr[q] = '\0';
            solve(arr, pattern);
        }
    }
}

Varsayalım ki kodumuz eşleşti, bu durumda eşleştiği elemanın yerini desenin bittiği yerdeki eleman alması gerekiyor. Birazcık netleştirelim

//Desen bulundu

10101(101011011000101010111)01010110110001010101111101101011011000101010101101100010101011110111100010101011101

// Desen (parantezli olan) yerinden çıkarıldı ve geri kalan yerine yerleştirildi.

10101-01010110110001010101111101101011011000101010101101100010101011110111100010101011101

/* Son olarak arrayimiz küçülmüş olarak gözüküyor olabilir ancak küçülmedi,
*baştaki boyutu 110 ise hala 110 yani ben ben desenimi çıkardığımda 89 tane
*kalmadı hala 110 adet var ancak 89 dan sonrası çıkarılan desen sayısına ait
*yani aslında şu şekilde bir arrayimiz var; 
*('--' olanlar 89 - 110 arası
*gözükmüyorsa biraz kaydırmak gerekiyor :())
*/

10101-01010110110001010101111101101011011000101010101101100010101011110111100010101011101--1110111100010101011101--

Bunun üzerine sürekli olarak bu işlemi yapmasını istediğimiz için kendisini tekrar tekrar çağırıyoruz ta ki içinde desen bulunmayana kadar. İlk part için bu kadar bundan sonrası bir dosyadan okuma üzerine.

void get_array(char **arr)
{
    FILE *ptr;
    char ch;
    int counter;

    ptr = fopen("pattern.txt", "r");

    if (NULL == ptr)
    {
        printf("File can not open");
    }

    fseek(ptr, 0, SEEK_END);
    counter = ftell(ptr);
    printf("%d ", counter);

    ptr = fopen("pattern.txt", "r");

    *arr = (char *)realloc(*arr, counter + 1);

    while (fgets(*arr, counter + 1, ptr) != NULL)
    {
        // printf("%s ", *arr);
    }
    fclose(ptr);
}

Tam olarak yukarıdaki fonksiyonu yazıyoruz, dosya açma/kapama bunları geçiyor ve ‘fseek’ kısmına kadar geliyorum.

// fseek(), pointerımızı en son elemente götürüyor, null hariç.
fseek(ptr, 0, SEEK_END);

// counter değişkenimize kaçıncı element olduğunu alıyoruz
counter = ftell(ptr);

printf("%d ", counter);

Bunun üzerine ‘ptr’ pointerımız dosyanın sonunda olduğundan kendisini tekrar tanımlayıp arrayimizi ‘realloc’ ediyoruz, bununla birlikte counterımıza null karakterini de ekleyip (+1) string olarak verimizi çekiyoruz, ardından pointerımızı kapatıyoruz.

ptr = fopen("pattern.txt", "r");

    *arr = (char *)realloc(*arr, counter + 1);

    while (fgets(*arr, counter + 1, ptr) != NULL)
    {
        // printf("%s ", *arr);
    }
    fclose(ptr);

Bunun üzerine main() üzerinde değişiklikler yapıyoruz. Bu değişiklikler şu şekilde;

void solve(char *arr, char pattern[]);
void get_array(char **arr);

int main()
{
    char arr1[] = "1010110101101100010101011101010110110001010101111101101011011000101010101101100010101011110111100010101011101"; // 110
    char pattern[] = "101011011000101010111";
    int i;

    char *arr = (char *) malloc(20);
    get_array(&arr);

    solve(arr, pattern);
    for (i = 0; arr[i] != '\0'; i++)
    {
        printf("%c", arr[i]);
    }
    printf(" %d ", i);
}

get_array()’daki çift pointer **arr olayi önemli şundan dolayı, get_array() içinde ‘realloc’ yapıyoruz bunun için pointer atmamız gerekiyor tek *arr ile sadece stringimizin adrresini atabiliyoruz o yüzden bu şekilde yapıyoruz. Daha fazla okumak istersen bu konu ile alakalı LINK

Son olarak kod şu şekilde

#include <stdio.h>
#include <stdlib.h>

/*
 *
 *
 * YOU CAN NOT DEFINE NEW ARRAY
 *
 */

void solve(char *arr, char pattern[]);
void get_array(char **arr);

int main()
{
    char arr1[] = "1010110101101100010101011101010110110001010101111101101011011000101010101101100010101011110111100010101011101"; // 110
    char pattern[] = "101011011000101010111";
    int i;

    char *arr = (char *) malloc(20);
    get_array(&arr);

    solve(arr, pattern);
    for (i = 0; arr[i] != '\0'; i++)
    {
        printf("%c", arr[i]);
    }
    printf(" %d ", i);
}

void get_array(char **arr)
{
    FILE *ptr;
    char ch;
    int counter;

    ptr = fopen("pattern.txt", "r");

    if (NULL == ptr)
    {
        printf("File can not open");
    }

    fseek(ptr, 0, SEEK_END);
    counter = ftell(ptr);
    printf("%d ", counter);

    ptr = fopen("pattern.txt", "r");

    *arr = (char *)realloc(*arr, counter + 1);

    while (fgets(*arr, counter + 1, ptr) != NULL)
    {
        // printf("%s ", *arr);
    }
    fclose(ptr);
}

void solve(char *arr, char pattern[])
{
    int i = 0;

    for (; arr[i] != '\0'; i++)
    {
        int j;
        for (j = 0; pattern[j] != '\0'; j++)
        {
            if (arr[i + j] != pattern[j])
            {
                break;
            }
        }

        if (pattern[j] == '\0')
        {
            int q;
            for (q = i; arr[q] != '\0'; q++)
            {
                arr[q] = arr[q + j];
            }
            arr[q] = '\0';
            solve(arr, pattern);
        }
    }
}

Gönderiler