I have two arrays, A and X, where A >= X. I want to find the max interleaving factor i for X^i such that X^i is a subsequence of A. For example, if A = [4,3,2,1,4,3,2,1,4,3,2,1,4,3,2,1], and X = [1,2,3], then i = 1, because X^1 = [1,2,3] and that sequence is in A. My program should use a binary search to find this max interleaving factor i and trace whether or not each iteration is a sequence of A. So using binary search for the above example, i would start = 3 (as max possible for A/X = 6), and X^3 = [1,1,1,2,2,2,3,3,3] and that is not a sequence in A.
Here is my code so far:
#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); //practice reallocating size of array
//for(int i = 0; i < size_x; i++){
// printf("%d ", A[i]);
//}
}
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 i, j, k, count = 0, max_repeat = 0;
while(min_i <= max_i){
int repeats = (max_i + min_i)/2;
printf("\n");
int * temp = realloc(X, size_x * sizeof(int) * repeats);
X = temp;
for(k = 0; k < size_x; ++k){
int idx = size_x - k -1;
temp = &X[idx];
for(j = 0; j < repeats; ++j){
X[idx * repeats + j] = *temp;
}
}
printf("New X: ");
for(i = 0; i < size_x * repeats; i++){
printf("%d ", X[i]);
}
for(i = 0; i < size_x * repeats; i++){
for(j = 0; j < size_a; j++){
if(A[j] == X[i]){
count++;
i++;
}
}
}
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;
}
printf("Max repeat: %d", max_repeat);
}
Here is my current output:
New X: 1 1 1 2 2 2 3 3 3 Low: 0 Mid 3 High 6 Fails
New X: 1 1 1 Low: 0 Mid 1 High 2 Fails
New X: Low: 0 Mid 0 High 0 Fails
I am expecting this:
New X: 1 1 1 2 2 2 3 3 3 Low: 0 Mid 3 High 6 Fails
New X: 1 2 3 Low: 0 Mid 1 High 2 Passes
New X: Low: 2 Mid 2 High 2 Fails
Max i = 1.
Meaning, that my code is not creating the correct array on the second iteration. X^1 should equal [1,2,3] not [1,1,1]. Why is it not creating the array properly on the second iteration but it does on the first?
Why is it not creating the array properly on the second iteration but it does on the first?
In the first loop you take X which is {1, 2, 3} and change it into {1, 1, 1, 2, 2, 2, 3, 3, 3} by repeating the first number 3 times, repeating the second number 3 times and repeating the third number 3 times.
In the second loop you start with X being {1, 1, 1, 2, 2, 2, 3, 3, 3}. Now you construct a new X by repeating the first number 1 time, repeating the second number 1 time and repeating the third number 1 time.
As the first, the second and the third numbers are all 1 you end up with {1, 1, 1}
In other words: Your first loop changed X and therefore you second loop use another value for X than the first loop. Consequently, the second loop produce an unexpected value for X