samedi 6 octobre 2018

counter to check if array X is subsequence of A not working (C)

I've tried following this program by hand, but I still can't get it to work. I have an Array A = [4,3,2,1,4,3,2,1,4,3,2,1,4,3,2,1,4,3,2,1] and array X = [1,2,3]. I need to find the max number i for X^i that is a subsquence of A, and do this by binary search. Since size of A is 20, and size of X is 3, the max possible i = 20/3 = 6. So my search will start at i= 3, which means that X^3 = [1,1,1,2,2,2,3,3,3]. This is not a subsequence of A, so binary search repeats for i = 1, X^1 = [1,2,3]. This is a subsequence of A, meaning it should pass and binary search should try again for i = 2. However, my condition to see if the iteration passes or not is not working properly.

Here is the code:

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

void create_initial_arrays(int size_a, int *A, int size_x, int *X);
void binary_search(int size_a, int * A, int size_x, int *X, int max_i, int min_i);

int main(){


    int size_a, size_x;
    scanf("%d", &size_a);
    scanf("%d", &size_x);

    int max_i = size_a / size_x;
    int min_i = 0;

    printf("Max: %d\n", max_i);

    int *A = (int*) malloc(size_a *sizeof(int));
    int *X = (int*) malloc(size_x *sizeof(int));

    create_initial_arrays(size_a, A, size_x, X);

    printf("Old X: ");
    for(int i = 0; i < size_x; i++){
        printf("%d ", X[i]);
    }
    printf("\n");

    binary_search(size_a, A, size_x, X, max_i, min_i);
    free(X);
    free(A);

}

void create_initial_arrays(int size_a, int *A, int size_x, int *X){
    int i, throwaway;

    for(i = 0; i < size_a; i++){
        scanf("%d", &A[i]);
    }

    scanf("%d", &throwaway);

    for(i = 0; i < size_x; i++){
        scanf("%d", &X[i]);
    }

    scanf("%d", &throwaway);
}



void binary_search(int size_a, int * A, int size_x, int *X, int max_i, int min_i){

    int j, k, max_repeat = 0;

    while(min_i <= max_i){

        int i = 0, count = 0, repeats = (max_i + min_i)/2;

        printf("\n");
        int * temp = (int*) malloc(size_x * sizeof(int) * repeats);

        for(k = 0; k < size_x; ++k){
            for(j = 0; j < repeats; ++j){
                temp[k * repeats + j] = X[k];
            }
        }

        printf("New X: ");
            for(i = 0; i < size_x * repeats; i++){
                printf("%d ", temp[i]);
            }

        printf("A: ");
        for (i = 0; i < size_a; i++){
            printf("%d ", A[i]);
        }

        for(j = 0; j < size_a; j++){
            if(A[j] == temp[i]){
                count++;
                i++;
            }
        }



        printf("Count: %d", count);


        if (count >= size_x * repeats){
            printf("Low: %d Mid %d High % d Passes\n", min_i, repeats, max_i);
            min_i = repeats + 1;
            max_repeat++;
        }
        else{
            printf("Low: %d Mid %d High % d Fails\n", min_i, repeats, max_i);
            max_i = repeats - 1;
        }

        free(temp);
    }   
        printf("Max repeat: %d", max_repeat);
}

And this is the section that I think must be problematic:

for(j = 0; j < size_a; j++){
            if(A[j] == temp[i]){
                count++;
                i++;
            }
        }

I've output both Arrays to make sure they are populated correctly (they are) and the counter after each iteration. Here is my code output:

Old X: 1 2 3 

New X: 1 1 1 2 2 2 3 3 3 A: 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 Count: 0Low: 0 Mid 3 High  6 Fails

New X: 1 2 3 A: 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 Count: 0Low: 0 Mid 1 High  2 Fails

New X: A: 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 Count: 0Low: 0 Mid 0 High  0 Passes
Max repeat: 1

Notice that count remains 0 throughout. On the first iteration for X^3 = [1,1,1,2,2,2,3,3,3], the condition is true 5 times ([1,1,1,2,2] is a subsequence of A, so count should be 5, but 5 is not >= size_x * repeats(3 * 3), so it fails as expected. Binary search reduces to Low 0 Mid 1 High 2, so i = repeats = 1.

X^1 = [1,2,3] is a subsequence of A, and count should be 5 on this iteration ([1,2,3] plus two extra counts of 3) which is >= size_x * repeats (3*1), so it should pass, and redo the search for i = 2. However, count remains zero and fails.

Why is count not updating? I know I need to keep it in the loop because I need it reset to 0 for each iteration, but I don't really understand why A[j] == temp[i] is not ever passing.

Aucun commentaire:

Enregistrer un commentaire