Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
8.6 kB
3
Indexable
Never
import random
from Visualizer import visualize_path, visualize_generation

boardsize = 16
random.seed()







add = 1/boardsize
sub = 1/boardsize
change = 1/(2*boardsize)
replace = 0.7

class Path:
    def __init__(self, string_length, S, E):
        self.length = random.randrange(string_length)
        self.string = self._random_string(string_length, self.length)
        self.distance = self.calc_distance(S, E)
        self.fitness = self.calc_fitness(self.length, self.distance)

    def _random_string(self, length, num_n):
        characters = 'udlr'
        random_string = [random.choice(characters) for _ in range(num_n)]
        random_string += ['n'] * (length - num_n)
        return random_string
    
    def _print(self):
        print("length: " + str(self.length))
        print("string: " + ''.join(self.string))
        print("distance: " + str(self.distance))
        print("fitness: " + str(self.fitness))

    def calc_distance(self, S, E):
        x, y = S
        for move in self.string:
            if move == "u":
                y = (y - 1) % boardsize
            elif move == "d":
                y = (y + 1) % boardsize
            elif move == "l":
                x = (x - 1) % boardsize
            elif move == "r":
                x = (x + 1) % boardsize
        return min((E[0] - x)%boardsize, (x-E[0])%boardsize) + min((E[1] - y)%boardsize, (y - E[1])%boardsize)
    
    def calc_fitness(self, len, dist):
        return len + dist*2
    
    def update(self, new_string, S, E):
        self.string = new_string
        self.length = len([char for char in new_string if char != 'n'])
        self.distance = self.calc_distance(S, E)
        self.fitness = self.calc_fitness(self.length, self.distance)

class Generation:
    def __init__(self, num_paths, string_length, S, E, existing_paths=None):
        if existing_paths:
            self.paths = existing_paths
        else:
            self.paths = [Path(string_length, S, E) for _ in range(num_paths)]
        self.size = num_paths
        self.paths.sort(key=lambda x: x.fitness)  # Sorting paths based on fitness in ascending order
        self.lowest_fitness_path1 = self.paths[0]

    def update_fitness(self):
        self.paths.sort(key=lambda x: x.fitness)
        self.lowest_fitness_path1 = self.paths[0]

    def _print(self):
        for path in self.paths:
            path._print()
            print()

def create_chessboard(position1, position2, path):
    # Check if positions are valid
    if not is_valid_position(position1) or not is_valid_position(position2):
        raise ValueError("Invalid positions. Each position should be a tuple (x, y) where 0 <= x, y <= boardsize.")

    # Create an empty 8x8 chessboard
    chessboard = [['_ ' for _ in range(boardsize)] for _ in range(boardsize)]

    # Mark the destination position
    chessboard[position2[1]][position2[0]] = 'E '

    # Initialize position with starting coordinates
    x, y = position1

    # Mark the starting position
    chessboard[y][x] = 'S '
    # Perform the movements and mark the path with the number of moves
    move_count = 1
    for move in path.string:
        if move == "u":
            y = (y-1) % boardsize
            move_count += 1
        elif move == "d":
            y = (y+1) % boardsize
            move_count += 1
        elif move == "l":
            x = (x-1) % boardsize
            move_count += 1
        elif move == "r":
            x = (x+1) % boardsize
            move_count += 1
        if move_count < 10:
            chessboard[y][x] = str(move_count) + " "
        elif move_count >= 10:
            chessboard[y][x] = str(move_count)

    return chessboard

def is_valid_position(position):
    x, y = position
    return 0 <= x <= (boardsize-1) and 0 <= y <= (boardsize-1)

def display_chessboard(chessboard):
    print("  x  " + "   ".join(str(i) for i in range(boardsize)))
    print(" y +" + "+".join(["---" for _ in range(boardsize)]) + "+")
    for i, row in enumerate(chessboard):
        row_str = f"{i:2d} | {'| '.join(row)}|"
        print(row_str)
        print("   +" + "+".join(["---" for _ in range(boardsize)]) + "+")

def mutate_replace(paths, S, E, dist):
    s = list(paths[0].string)
    curr = min(1/replace, (dist - paths[0].distance)/dist * ((dist+1)/(paths[0].length+1)))
    for path in paths:
        if random.random() <= replace*curr:
            path.update(s, S, E)
    return paths

def mutate_change(paths, S, E, dist):
    letters = ['u', 'd', 'l', 'r']
    curr = min(1/replace, (1-(paths[0].distance)/1+dist))#*(1 - paths[0].length/(dist+1)))
    if (paths[0].distance == 0 and paths[0].length == dist):
        curr = 0
    for path in paths:
        for i in range(path.length):
            if random.random() <= change*curr:
                random_index = random.randint(0, 2)
                letters_without_n = [letter for letter in letters if letter != path.string[i]]
                path.string[i] = letters_without_n[random_index]
                path.update(list(path.string), S, E)
    return paths

def mutate_add(paths, S, E, dist):
    letters = ['u', 'd', 'l', 'r']
    curr = min(1/add, 1-paths[0].length/dist)
    for path in paths:
        if path.length < boardsize:
            if random.random() <= curr:
                random_index = random.randint(0, 3)
                path.string[path.length] = letters[random_index]
                path.update(list(path.string), S, E)
    return paths

def mutate_sub(paths, S, E, dist):
    curr = min(1/sub, (paths[0].length/dist-1))
    for path in paths:
        if path.length - 1 >= 0:
            if random.random() <= curr:
                random_index = random.randint(0, path.length-1)
                path.string.pop(random_index)
                path.string.append('n')
                path.update(list(path.string), S, E)
    return paths

def mutate(gen, S, E):
    dist = min((E[0] - S[0])%boardsize, (S[0]-E[0])%boardsize) + min((E[1] - S[1])%boardsize, (S[1]-E[1])%boardsize)
    print(dist)
    path = mutate_replace(gen.paths, S, E, dist)
    path = mutate_change(path, S, E, dist)
    path = mutate_add(path, S, E, dist)
    path = mutate_sub(path, S, E, dist)
    return path
    
def evolve(gen, n, start, end):
    if (n == 1 or n % 5 == 0):
        print("Generation", n, ": ")
        gen._print()
        visualize_path(start, end, boardsize, gen.lowest_fitness_path1.string, n)
        visualize_generation(gen, boardsize, start, end, n)
        key = input("Press m to mutate the fittest path for a new generation or 'x' to stop: ")

        if key == 'm':
            print("Mutating fittest path...")
            next_gen_paths = mutate(gen, start, end)
            #for path in next_gen_paths:
            #    path.update(path.string, start, end)
            next_gen = Generation(gen.size, boardsize, start, end, next_gen_paths)
            evolve(next_gen, n+1, start, end)
        elif key == 'x':
            visualize_path(start, end, boardsize, gen.lowest_fitness_path1.string, n)
            visualize_generation(gen, boardsize, start, end, n)
            print("Stopping evolution")
    else:
        print("Mutating fittest path...")
        next_gen_paths = mutate(gen, start, end)
        #for path in next_gen_paths:
            #path.update(path.string, start, end)
        next_gen = Generation(gen.size, boardsize, start, end, next_gen_paths)
        evolve(next_gen, n+1, start, end)


if __name__ == "__main__":
    #random.seed(0)
    try:
        pos1_x = random.randrange(boardsize)#int(input("Enter the x-coordinate for the starting position (0-(boardsize-1)): "))
        pos1_y = random.randrange(boardsize)#int(input("Enter the y-coordinate for the starting position (0-(boardsize-1): "))
        pos2_x = random.randrange(boardsize)#int(input("Enter the x-coordinate for the destination position (0-(boardsize-1): "))
        pos2_y = random.randrange(boardsize)#int(input("Enter the y-coordinate for the destination position (0-(boardsize-1): "))
        #movements_str = #input("Enter the movement directions (u, d, l, r, n): ")
        start = (pos1_x, pos1_y)
        end = (pos2_x, pos2_y)


        gen1 = Generation(20, boardsize, start, end)
        #gen1._print()
        evolve(gen1, 1, start, end)
        #visualize_generation(gen1, boardsize, start, end, 1)
        #gen2_paths = mutate(gen1, start, end)
        #gen2 = Generation(5, boardsize, start, end, gen2_paths)
        #gen2._print()
        #visualize_generation(gen2, boardsize, start, end, 2)


    except ValueError as e:
        print(f"Error: {e}")