#ifndef lint
static char *rcsid = "$Header: /tmp_mnt/vida/disk5/users/terry/r/gassy/busy_beavers/RCS/busy_beavers.c,v 1.1 1992/08/09 22:29:37 terry Exp terry $";
#endif

/*
 * This program uses a GA to solve the Busy Beaver problem
 * for binary Turing Machines. The description of that problem
 * is beyond me at this point, though one will be put here
 * before the real release of Gassy 3.0.
 *
 * The fitness function treats the individual as a TM and runs
 * it (if it's not already in the hash table & if it can't
 * figure out what the machine will do from simply looking at
 * its rules. Fitness is the number of ones left on the tape
 * when the machine halts, and 0 if the machine does not halt
 * within some specified time or runs off the edge of the simulated
 * tape.
 *
 * This program illustrates a lot of ways that an application can
 * customize Gassy. It has several options, it has its own
 * crossover functions, the possible alleles at each locus are
 * not the same, and it dumps state variables when an interrupt 
 * is taken.
 */

#include "types.h"
#include "utility.h"
#include "options.h"
#include "busy_beavers.h"

#include <string.h>
#include <strings.h>

typedef struct {
    STRING machine;
    FITNESS value;
    INT *how_it_finished;
} HASH_DATA;

LONG hash_hits;
LONG hash_misses;
INT start_state = START_STATE - '0';
CHAR final_state_char;
INT start_head_position;
INT ran_off_tape = 0;
INT exceeded_step_limit = 0;
INT had_no_final_state = 0;
INT halted = 0;
INT total_steps = 0;
INT state_zero_loop = 0;
INT string_length;
INT nstates = 0;
INT tape_length = DEFAULT_TAPE_LENGTH;
INT step_limit = DEFAULT_TAPE_LENGTH;
STRING tape;
BOOLEAN print_as_string = FALSE;

VOID half_state_crossover_function();
VOID full_state_crossover_function();

OPTION app_options[] = {
    
    { "states",          "sta", INT_OPT,    TRUE, LLIMIT(1.0),
       VADDR(nstates), "The number of states for the Turing Machine." },
       
    { "step_limit",      "sl",  INT_OPT,    FALSE, LLIMIT(1.0),
       VADDR(nstates), "The maximum number of steps to run the Turing Machine." },
       
    { "tape_length",     "tl",  INT_OPT,    FALSE, LLIMIT(1.0),
       VADDR(nstates), "The number of states for the Turing Machine." },
       
    { "print_as_string", "ps",  BOOLEAN_OPT,    FALSE, NO_LIMITS(),
       VADDR(print_as_string), "Have TMs print as normal strings." },
       
    /* DO NOT CHANGE THE NEXT LINE - IT MARKS THE END OF YOUR OPTIONS! */
    { (STRING) 0, "", 0, FALSE, NO_LIMITS(), (VOID *) 0, "" }
};

INT
app_individual_size()
{
    return (string_length = nstates * 6);
}

VOID
app_initialize(context)
CONTEXT *context;
{
    tape = Malloc(tape_length);
    final_state_char = '0' + nstates;
    start_head_position = tape_length >> 1;
    if (context->hashing == TRUE){
	hash_hits = (LONG) 0;
	hash_misses = (LONG) 0;
    }
    return;
}


VOID
app_allele_possibilities(alleles)
LOCUS *alleles;
{
    register INT state;
    STRING state_alleles;
    static STRING movements = "lr";
    static STRING states = "01";

    /* 
     * Make room for the state alleles. 
     * One for each regular state, plus the Halt state, plus a terminator.
     */
    state_alleles = Malloc((nstates + 1 + 1) * sizeof(CHAR));

    /* Now fill it in. */
    for (state = 0; state <= nstates; state++){
	state_alleles[state] = '0' + state;
    }
    state_alleles[nstates + 1] = '\0';

    /* Make the appropriate loci point to the appropriate possible alleles. */
    for (state = 0; state < nstates; state++){
	INT register symbol;
	
	for (symbol = 0; symbol < 2; symbol++){
	    INT base = state * 6 + symbol * 3;
	    
	    alleles[base + SYMBOL_OFFSET].possible_alleles = states;
	    alleles[base + DIRECTION_OFFSET].possible_alleles = movements;
	    alleles[base + STATE_OFFSET].possible_alleles = state_alleles;
	} 
    } 
    
    return;
}

VOID *
half_state_crossover(selections, nselected, nreproducers, new_population, context)
INT *selections;
INT nselected;
INT nreproducers;
POPULATION new_population;
CONTEXT *context;
{
    general_crossover(half_state_crossover_function, selections, nselected, nreproducers, new_population, context);
}

VOID
half_state_crossover_function(parent_1, parent_2, child_1, child_2, context)
INDIVIDUAL_TYPE parent_1;
INDIVIDUAL_TYPE parent_2;
INDIVIDUAL_TYPE child_1;
INDIVIDUAL_TYPE child_2;
CONTEXT *context;
{
    register INT pos;
    register INT crossover_point;
    
    /* Get to the start of a 1/2 state */
    crossover_point = 3 * uniform(nstates * 2);
	    
    /* Copy up to the crossover point. */
    for (pos = 0; pos < crossover_point; pos++){
	child_1[pos] = parent_1[pos];
	child_2[pos] = parent_2[pos];
    }
    
    /* Swap the 3 locations. */
    for (pos = crossover_point; pos < crossover_point + 3; pos++){
	child_1[pos] = parent_2[pos];
	child_2[pos] = parent_1[pos];
    }
    
    /* Copy after the 3 crossover locations. */
    for (pos = crossover_point + 3; pos < string_length; pos++){
	child_1[pos] = parent_1[pos];
	child_2[pos] = parent_2[pos];
    }
    
    return;
}
	
VOID *
full_state_crossover(selections, nselected, nreproducers, new_population, context)
INT *selections;
INT nselected;
INT nreproducers;
POPULATION new_population;
CONTEXT *context;
{
    general_crossover(full_state_crossover_function, selections, nselected, nreproducers, new_population, context);
}

VOID
full_state_crossover_function(parent_1, parent_2, child_1, child_2, context)
INDIVIDUAL_TYPE parent_1;
INDIVIDUAL_TYPE parent_2;
INDIVIDUAL_TYPE child_1;
INDIVIDUAL_TYPE child_2;
CONTEXT *context;
{
    register INT pos;
    register INT crossover_point;
    
    /* Get to the start of a full state */
    crossover_point = 6 * uniform(nstates); 
    
    /* Copy up to the crossover point. */
    for (pos = 0; pos < crossover_point; pos++){
	child_1[pos] = parent_1[pos];
	child_2[pos] = parent_2[pos];
    }
    
    /* Swap the 6 locations. */
    for (pos = crossover_point; pos < crossover_point + 6; pos++){
	child_1[pos] = parent_2[pos];
	child_2[pos] = parent_1[pos];
    }
    
    /* Copy after the 6 crossover locations. */
    for (pos = crossover_point + 6; pos < string_length; pos++){
	child_1[pos] = parent_1[pos];
	child_2[pos] = parent_2[pos];
    }
    
    return;
}
	    

FUNCTION app_crossover_functions[] = {
    
	{ "half_state", half_state_crossover, (PFV) 0,
"Two point crossover in which the first crossover point is always chosen so\n\
as to not fall in the middle of an area which specifies what the TM does when\n\
it is in a certain state and looking at a certain symbol. Only 3 loci are\n\
exchanged (the information about what to do if you are in this state and\n\
looking at this symbol). Seeing as a TM can be looking at one of two symbols,\n\
I think of this as crossing over half a state."  },

	{ "full_state", full_state_crossover, (PFV) 0,
"Two point crossover in which the first crossover point is always chosen so\n\
as to not fall in the middle of an area which specifies what the TM does when\n\
it is in a certain state. The second crossover point taken to be 6 loci further\n\
on, so this crossover exchanges everything the TM does when it is in a certain\n\
state, as opposed to the half state crossover which just exchanges what the\n\
machine does in a certain state AND when it is looking at a certain symbol." },
    
    { (STRING) 0, (PFPV) 0, (PFV) 0, (STRING) 0 }

};

VOID
app_end_of_run(fp, context)
FILE *fp;
CONTEXT *context;
{
    return;
}

VOID
app_end(fp, context)
FILE *fp;
CONTEXT *context;
{
    fprintf(fp, "Number of states = %d Step limit = %d, Tape length = %d\n", nstates, step_limit, tape_length);
    fprintf(fp, "Run TM was called a total of %d times. Breakup was:\n", 
	    had_no_final_state + halted + ran_off_tape + exceeded_step_limit);
    fprintf(fp, "Had no final state %d times.\n", had_no_final_state);
    fprintf(fp, "Halted %d times. (Average of %d steps before halting).\n", 
	    halted, total_steps / (halted == 0 ? 1 : halted));
    fprintf(fp, "Ran off tape %d times.\n", ran_off_tape);
    fprintf(fp, "Exceeded step limit %d times.\n", exceeded_step_limit);
    fprintf(fp, "Trivial state zero loop detected %d times.\n", state_zero_loop);
    if (context->hashing == TRUE){
	fprintf(fp, "Hashing had %d hits out of %d (%d%%).\n", hash_hits, 
		hash_hits + hash_misses, (INT)((DOUBLE)hash_hits / (DOUBLE)(hash_hits + hash_misses) * 100.0));
    }
    
    return;
}

VOID 
app_print_individual(fp, individual)
FILE *fp;
INDIVIDUAL *individual;
{
    INT state;

    if (print_as_string == TRUE){
	fprintf(fp, "%s", individual->genome);
    }
    else {
	for (state = 0; state < nstates; state++){
	    INT symbol;
	    
	    for (symbol = 0; symbol < 2; symbol++){
		INT base = state * 6 + symbol * 3;
		fprintf(fp, "In state %d if you see a %c, write a %c, move %c and go into state %c\n", 
			state, symbol + '0', 
			individual->genome[base + SYMBOL_OFFSET],
			individual->genome[base + DIRECTION_OFFSET],
			individual->genome[base + STATE_OFFSET]);
	    } 
	} 
    }

    Fflush(fp);
    return;
}


VOID
app_dump_state(fp, context)
FILE *fp;
CONTEXT *context;
{
    fprintf(fp, "%s : %d\n", STRING_LENGTH, string_length);
    fprintf(fp, "%s : %d\n", RAN_OFF_TAPE, ran_off_tape);
    fprintf(fp, "%s : %d\n", EXCEEDED_STEP_LIMIT, exceeded_step_limit);
    fprintf(fp, "%s : %d\n", HAD_NO_FINAL_STATE, had_no_final_state);
    fprintf(fp, "%s : %d\n", HALTED, halted);
    fprintf(fp, "%s : %d\n", TOTAL_STEPS, total_steps);
    fprintf(fp, "%s : %d\n", STATE_ZERO_LOOP, state_zero_loop);
    fprintf(fp, "%s : %d\n", NSTATES, nstates);
    fprintf(fp, "%s : %d\n", TAPE_LENGTH, tape_length);
    fprintf(fp, "%s : %d\n", STEP_LIMIT, step_limit);

    return;
}

#define readline if (!(fgets(line, 1024, fp))) error("fgets fails in app_restore_state.")

VOID
app_restore_state(fp, context)
FILE *fp;
CONTEXT *context;
{
    extern INT atoi();
    CHAR line[1024];

    readline; string_length = atoi(line + strlen(STRING_LENGTH) + 3);
    readline; ran_off_tape = atoi(line + strlen(RAN_OFF_TAPE) + 3);
    readline; exceeded_step_limit = atoi(line + strlen(EXCEEDED_STEP_LIMIT) + 3);
    readline; had_no_final_state = atoi(line + strlen(HAD_NO_FINAL_STATE) + 3);
    readline; halted = atoi(line + strlen(HALTED) + 3);
    readline; total_steps = atoi(line + strlen(TOTAL_STEPS) + 3);
    readline; state_zero_loop = atoi(line + strlen(STATE_ZERO_LOOP) + 3);
    readline; nstates = atoi(line + strlen(NSTATES) + 3);
    readline; tape_length = atoi(line + strlen(TAPE_LENGTH) + 3);
    readline; step_limit = atoi(line + strlen(STEP_LIMIT) + 3);

    tape = Malloc(tape_length);

    return;
}


FITNESS
app_evaluate_individual(who, context)
INT who;
CONTEXT *context;
{
    register INDIVIDUAL_TYPE machine = context->population[who].genome;
    register FITNESS number_of_ones = (FITNESS) 0;
    register INT head_position = start_head_position;
    register INT steps = (INT) 0;
    register INT i;
    register INT state = start_state;
    HASH_DATA *hdata;
    VOID *hash_return;
    
    /* If state 0 and seeing a 0 leaves the machine in state 0, then it does not halt. */
    if (machine[STATE_OFFSET] == START_STATE){
	if (tape_length - head_position > step_limit){
	    exceeded_step_limit++;
	}
	else {
	    ran_off_tape++;
	}
	state_zero_loop++;
	return (FITNESS) 0;
    }
    
    /* Check to see if there is any mention of a final state. */
    if (!index(machine, final_state_char)){
	had_no_final_state++;
	return (FITNESS) 0;
    }
    
    if (context->hashing == TRUE){
	/* Look in the hash table to see if we already know the value for this machine. */
    
	if ((hash_return = hash_search(context->ht, machine, 0, 0)) == 0){
	    hash_misses++;
	}
	else {
	    hash_hits++;
	    (*(((HASH_DATA *)hash_return)->how_it_finished))++;
	    return (FITNESS) ((HASH_DATA *)hash_return)->value;
	}
    }


    for (i = 0; i < tape_length; i++){
	tape[i] = BLANK;
    } 
    
    while (state != nstates && steps < step_limit && head_position >= 0 && head_position < tape_length){
	register INT base;
	register INT next_state; 
	register CHAR symbol;
	
	steps++;
	
	base = (state * 6) + ((INT)tape[head_position] - '0') * 3;
	next_state = machine[base + STATE_OFFSET] - '0';
	
	if ((symbol = machine[base + SYMBOL_OFFSET]) == ONE){
	    if (tape[head_position] != ONE){
		number_of_ones++;
	    }
	}
	else {
	    if (tape[head_position] == ONE){
		number_of_ones--;
	    }
	}

	tape[head_position] = symbol;

	if (machine[base + DIRECTION_OFFSET] == LEFT){
	    head_position--;
	}
	else {
	    head_position++;
	}
	
	state = next_state;
    }
    
    /* *steps_taken = steps; */
    
    if (context->hashing == TRUE){
	hdata = (HASH_DATA *)Malloc(sizeof(HASH_DATA));
	hdata->machine = strdup(machine);
    }

    if (steps >= step_limit){
	exceeded_step_limit++;
	number_of_ones = (FITNESS) 0;
	if (context->hashing == TRUE){
	    hdata->how_it_finished = &exceeded_step_limit;
	}
    }
    else if (head_position < 0 || head_position >= tape_length){
	ran_off_tape++;
	number_of_ones = (FITNESS) 0;
	if (context->hashing == TRUE){
	    hdata->how_it_finished = &ran_off_tape;
	}
    }
    else {
	halted++;
	total_steps += steps;
	if (context->hashing == TRUE){
	    hdata->how_it_finished = &halted;
	}
    }

    if (context->hashing == TRUE){
	hdata->value = number_of_ones;
	/* Insert it. */
	hash_search(context->ht, machine, (VOID *)hdata, 0);
    }
    
    return (FITNESS) number_of_ones;
}