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

typedef unsigned char CHROMOSOME;
typedef unsigned char FITNESS;
typedef CHROMOSOME *POPULATION;

void initialize_pop (POPULATION, int);
CHROMOSOME crossover (CHROMOSOME, CHROMOSOME);
FITNESS fitness (CHROMOSOME);
CHROMOSOME mutate (CHROMOSOME);
CHROMOSOME get_parent (POPULATION, FITNESS [], int);
void print_pop (POPULATION, int);

int main (void)
{
    size_t pop_size;
    unsigned i, gen, final_gen;
    unsigned mut_prob = 101;
    POPULATION pop, prev_pop;
    CHROMOSOME mom, dad;
    FITNESS *fit_arr;

    srand(time(0));
    printf("Enter desired population size: ");
    scanf("%u", &pop_size);
    while ((mut_prob < 0) || (mut_prob > 100)) {
        printf("Enter desired mutation probability as an integral percentage: ");
        scanf("%u", &mut_prob);
    }
    printf("Enter desired number of generations: ");
    scanf("%u", &final_gen);

    if (!(pop = malloc(sizeof(CHROMOSOME) * pop_size))) {
        printf("Couldn't allocate enough memory for population.");
        return 0;
    }
    initialize_pop(pop, pop_size);
    printf("Initial population:\n");
    print_pop(pop, pop_size);

    for (gen = 1; gen <= final_gen; ++gen) {
        if (!(fit_arr = malloc(sizeof(FITNESS) * pop_size))) {
            printf("Couldn't allocate enough memory for fitness array.");
            return 0;
        }
        for (i = 0; i < pop_size; ++i)
            fit_arr[i] = fitness(pop[i]);
        prev_pop = pop;
        if (!(pop = malloc(sizeof(CHROMOSOME) * pop_size))) {
            printf("Couldn't allocate enough memory for population.");
            return 0;
        }
        for (i = 0; i < pop_size; ++i) {
            mom = get_parent(prev_pop, fit_arr, pop_size);
            dad = get_parent(prev_pop, fit_arr, pop_size);
            pop[i] = crossover(mom, dad);
            if (rand() % 100 < mut_prob)
                pop[i] = mutate(pop[i]);
        }
        free(fit_arr);
        free(prev_pop);
    }

    /* here we have our final population */
    printf("Final population:\n");
    print_pop(pop, pop_size);
    free(pop);
    return 0;
}

void initialize_pop (POPULATION pop, int size)
{
    int i;
    for (i = 0; i < size; ++i)
        pop[i] = rand() % ((int)((CHROMOSOME) (~0)) + 1);
}

CHROMOSOME crossover (CHROMOSOME mom, CHROMOSOME dad)
{
    /* select random crossover point and generate offspring */
    int xovr_point = rand() % (sizeof(CHROMOSOME) * 8 + 1);
    return (mom & ~(~0 << xovr_point)) | (dad & (~0 << xovr_point));
}

FITNESS fitness (CHROMOSOME chr)
{
    /* for this example we will assume that more bits set = higher fitness */
    int i;
    FITNESS fit = 0;
    for (i = 0; i < sizeof(CHROMOSOME) * 8; ++i) {
        fit += (chr >> i) & 0x01;
    }
    return fit;
}

CHROMOSOME mutate (CHROMOSOME chr)
{
    /* toggle randomly selected bit in chromosome */
    unsigned flip_bit = rand() % (sizeof(CHROMOSOME) * 8);
    return (~chr & (0x01 << flip_bit)) | (chr & ~(0x01 << flip_bit));
}

CHROMOSOME get_parent (POPULATION pop, FITNESS fit_arr[], int size)
{
    /* roulette wheel selection by proportional fitness */
    int i, sel_fit, tot_fit = 0;
    for (i = 0; i < size; tot_fit += fit_arr[i++]);
    sel_fit = rand() % (tot_fit + 1);
    for (i = 0, tot_fit = 0; tot_fit < sel_fit; tot_fit += fit_arr[i++]);
    return pop[i - 1];
}

void print_pop (POPULATION pop, int pop_size)
{
    int i, tot_fit = 0;
    CHROMOSOME best = (CHROMOSOME) 0;
    for (i = 0; i < pop_size; ++i) {
        tot_fit += fitness(pop[i]);
        if (fitness(pop[i]) > fitness(best))
            best = pop[i];
        printf("%x|", pop[i]);
    }
    printf("\n");
    printf("Total fitness: %d\n", tot_fit);
    printf("Best chromosome: %x\tFitness: %d\n", best, fitness(best));
}