# Bio-Inspired Artificial Intelligence - Spring 2026

# Schema functions developed in class - week 3 (slightly cleaned up)

import random, math
#----------------------------------------------------------------------------

# generates a list of all binary strings of length n
def binary_strings(n):
    if n == 1:
        return ['0', '1']
    else:
        shorter_strings = binary_strings(n-1)
        with_0 = ['0'+b for b in shorter_strings]
        with_1 = ['1'+b for b in shorter_strings]
        all = with_0 + with_1
        return all

# generates a list of all binary schemas of length n
def schemas(n):
    if n == 1:
        return ['0', '1', '*']
    else:
        shorter_schemas = schemas(n-1)
        with_0 = ['0'+s for s in shorter_schemas]
        with_1 = ['1'+s for s in shorter_schemas]
        with_star = ['*'+s for s in shorter_schemas]
        all = with_0 + with_1 + with_star
        return all

# example: there are 27 binary schemas of length 3
# schemas(3)

def random_genome(length):
    bits = [random.choice("01") for i in range(length)]
    genome = ''.join(bits)
    return genome

def random_population(size, length):
    return [random_genome(length) for i in range(size)]

# returns all schemas represented by genome g
def schemas_represented(g):
    if g == '0' or g == '1':
        return [g, '*']
    else:
        shorter_schemas = schemas_represented(g[1:])
        with_first = [g[0]+s for s in shorter_schemas]
        with_star = ['*'+s for s in shorter_schemas]
        all = with_first + with_star
        return all

# example: 1101 matches/represents 16 different binary schemas
# schemas_represented('1101')

# returns all unique schemas represented by a population of genomes
def unique_schemas(population):
    all = set()
    for g in population:
        for s in schemas_represented(g):
            all.add(s)
    return all

# we can count the number of unique schemas implicitly present in a
# randomly-generated population of 100 genomes of length 15 like this:
#
# len(unique_schemas(random_population(100, 15)))

def all_schema_reps(s):
    if s == '*':
        return ['0', '1']
    elif s == '0' or s == '1':
        return [s]
    else:
        shorter_reps = all_schema_reps(s[1:])
        if s[0] == '*':
            with_0 = ['0'+r for r in shorter_reps]
            with_1 = ['1'+r for r in shorter_reps]
            all = with_0 + with_1
            return all
        elif s[0] == '0' or s[0] == '1':
            return [s[0]+r for r in shorter_reps]
        else:
            raise Exception("invalid schema")
        
# example: this generates a list of all strings that match/represent 0**1*
# all_schema_reps('0**1*')

#----------------------------------------------------------------------------
# this approach uses binary genomes to encode x values (after Riolo 1992)

def f(x):
    return x + abs(math.sin(8*x))

# converts a binary string into its decimal (base 10) equivalent
def binary_to_decimal(b):
    if b == '0' or b == '1':
        return int(b)
    else:
        return 2 * binary_to_decimal(b[:-1]) + int(b[-1])

# shorter version
def binary_to_decimal(b):
    return int(b, base=2)

# renamed for clarity
def binary_genome_to_x(g):
    x = binary_to_decimal(g) * math.pi/(2**len(g))
    return x

def fitness(g):
    return f(binary_genome_to_x(g))

def show_binary_genome_encodings(code_length):
    for g in binary_strings(code_length):
        # assumes fitness function uses binary_genome_to_x
        print(f"{g} -> {binary_genome_to_x(g):.12f} with fitness {fitness(g):.12f}")

# calculates the exact average fitness of schema s
def exact_schema_fitness(s):
    fitnesses = [fitness(g) for g in all_schema_reps(s)]
    average = sum(fitnesses) / len(fitnesses)
    return average

# examples:
# exact_schema_fitness('****************')
# exact_schema_fitness('1***************')
# exact_schema_fitness('0***************')
# exact_schema_fitness('**11**11**11**11')
# exact_schema_fitness('*****100********')

#----------------------------------------------------------------------------
# this approach uses graycode genomes to encode x values

# generates a list of all graycode strings of length n
def graycode_strings(n):
    if n == 1:
        return ['0', '1']
    else:
        shorter_strings = graycode_strings(n-1)
        with_0 = ['0'+b for b in shorter_strings]
        with_1 = ['1'+b for b in reversed(shorter_strings)]
        all = with_0 + with_1
        return all

def xor(a, b):
    return '0' if a == b else '1'

def graycode_to_binary(graycode):
    binary = ""
    prev_bit = '0'
    for bit in graycode:
        prev_bit = xor(prev_bit, bit)
        binary += prev_bit
    return binary

def show_graycode_to_binary(code_length):
    for g in graycode_strings(code_length):
        print(f"{g} -> {graycode_to_binary(g)}")

def graycode_genome_to_x(g):
    x = binary_to_decimal(graycode_to_binary(g)) * math.pi/(2**len(g))
    return x

def fitness2(g):
    return f(graycode_genome_to_x(g))

def show_graycode_genome_encodings(code_length):
    for g in graycode_strings(code_length):
        # assumes fitness function uses graycode_genome_to_x
        print(f"{g} -> {graycode_genome_to_x(g):.12f} with fitness {fitness2(g):.12f}")

#----------------------------------------------------------------------------
# converting from binary to graycode

def binary_to_graycode(binary):
    graycode = ""
    prev_bit = '0'
    for bit in binary:
        graycode += xor(prev_bit, bit)
        prev_bit = bit
    return graycode

def show_binary_to_graycode(code_length):
    for b in binary_strings(code_length):
        print(f"{b} -> {binary_to_graycode(b)}")