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

int* propagate_naive(int* current, int length) {
    int* next = (int*) calloc(length, sizeof(int));
    
    int nb_new = 0;
    for (int i = 0; i < length; i++) {
        if (current[i] > 0) {
            next[i] = current[i] - 1;
        } else {
            next[i] = 6;
            nb_new++;
        }
    }
    
    next = (int*) realloc(next, length+nb_new);
    for (int i = length; i < nb_new; i++) {
        next[i] = 8;
    }
    
    return next;
}

long long* propagate_map(long long* start) {
    long long* next = (long long*) calloc(9, sizeof(long long));       
    
    next[0] = start[1];
    next[1] = start[2];
    next[2] = start[3];
    next[3] = start[4];
    next[4] = start[5];
    next[5] = start[6];
    next[6] = start[7] + start[0];
    next[7] = start[8];
    next[8] = start[0];
    
    return (next);
}

long long* count_raw(int* x, int length) {
    long long* counts = (long long*) malloc(9 * sizeof(long long));
    
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < length; j++) {
            if (x[j] == i) {
                counts[i]++;
            }
        }
    }
    return counts;
}


long long sum_vector(long long* x) {
    long long sum = 0;
    for (int i = 0; i < 9; i++) {
        sum += x[i];
    }
    return sum;
}

int* generate_random_input(int length) {
    srand(0);
    int* input = (int*) malloc(length * sizeof(int));
    for(int i = 0 ; i < length; i++) {
        input[i] = rand() % 9;
    }
    return input;
}

int main() {

    for (int length = 1; length < 1000000000; length *= 10) {
        for (int replicate = 0; replicate < 10; replicate++) {
            int* input = generate_random_input(length);
            
            
            // Naive way
            clock_t t_naive = clock();
            int* next = propagate_naive(input, length);
            t_naive = clock() - t_naive;
            
            // Matrix multiplication way
            long long* counts = count_raw(input, length);
            clock_t t_map = clock();
            long long* counts_next = propagate_map(counts);
            t_map = clock() - t_map;
            
            // Result
            printf("%i, %i, %i\n", length, t_naive, t_map);
        }
    }
    return 0;
}