import math
from random import randint, choice as rand_choice, random

CELL_SIZE = 5
WORLD_SIZE = 160

DIRECTS = {
    0: (0, -1),
    1: (1, 0),
    2: (0, 1),
    3: (-1, 0),
}

COMMANDS = 'b↑→↓←FEWs'
MUTATE_PROB = 0.003

ACT_GO, ACT_BITE, ACT_BREED, ACT_SHIELD = range(4)


def mutate_code(code):
    v = randint(0, 2 if len(code) > 0 else 0)
    pos = randint(0, len(code))
    if v == 0:
        # insert symbol
        return code[:pos] + rand_choice(COMMANDS) + code[pos:]
    elif v == 1:
        # replace symbol
        return code[:pos] + rand_choice(COMMANDS) + code[pos+1:]
    else:
        # remove symbol
        return code[:pos] + code[pos+1:]


def levenstein_distance(a, b):
    M, N = len(a), len(b)
    dmat = {}

    def compute_d(i, j):
        if i == 0 and j == 0:
            return 0
        if j == 0:
            return i
        if i == 0:
            return j
        return min(
            dmat[(i, j - 1)] + 1,
            dmat[(i - 1, j)] + 1,
            dmat[(i - 1, j - 1)] + (0 if a[i - 1] == b[j - 1] else 1)
        )

    for i in range(len(a) + 1):
        for j in range(len(b) + 1):
            dmat[(i, j)] = compute_d(i, j)

    return dmat[(M, N)]


def force_range(v, _min, _max):
    if v < _min:
        v = _min
    elif v > _max:
        v = _max
    return v


def code_color(code):
    r, g, b = 0, 0, 0
    lcmd = len(COMMANDS)
    for char in code:
        val = COMMANDS.index(char) / lcmd
        r += min(abs(0.000 - val), abs(1.000 - val))
        g += min(abs(0.333 - val), abs(1.333 - val))
        b += min(abs(0.667 - val), abs(-0.333 - val))
    mx = max(r, g, b)
    if mx < 0.1:
        mx = 0.1
    return (
        force_range(r / mx * 0.6, 0.0, 1.0),
        force_range(g / mx * 0.6, 0.0, 1.0),
        force_range(b / mx * 0.6, 0.0, 1.0),
    )


class LifeForm:
    def __init__(self, world, code, x, y):
        self.world = world
        self.x = x % WORLD_SIZE
        self.y = y % WORLD_SIZE
        self.age = 0
        self.age_vel = 1.0
        self.hp = 10
        # 0 - up, 1 - right, 2 - down, 3 - left
        self.direct = 0

        self.code = code
        self.color = code_color(code)
        self.len = len(code)
        self.codeptr = 0
        self.cond = None

        self.lastact = None

    def age_tick(self):
        self.age += 1
        if self.age_vel > -0.1:
            self.age_vel -= 0.003
        self.hp += self.age_vel

    def brain_tick(self):
        if self.age % 50 == 0 and self.hp >= 100:
            if self.world.try_to_breed(self):
                self.lastact = ACT_BREED
                return

        char = self.code[self.codeptr]
        if self.cond is None:
            if char in 'FEW':
                self.cond = False  # enter condition mode
        else:
            if char not in 'FEW':
                if not self.cond:
                    char = None  # skip command since condition is false
                self.cond = None  # exit condition mode
            else:
                if self.cond:
                    char = None  # skip unneccessary condition checks

        if char == '↑':
            if self.world.try_to_go(self):
                self.lastact = ACT_GO
        elif char == '→':
            self.direct = (self.direct + 1) % 4
        elif char == '↓':
            if self.world.try_to_go(self, True):
                self.lastact = ACT_GO
        elif char == '←':
            self.direct = (self.direct - 1) % 4
        elif char == 'b':
            self.lastact = ACT_BITE
        elif char == 's':
            self.lastact = ACT_SHIELD
        elif char == 'F':
            if self.world.is_friend(self):
                self.cond = True
        elif char == 'E':
            if self.world.is_enemy(self):
                self.cond = True
        elif char == 'W':
            if self.world.is_wall(self):
                self.cond = True

        self.codeptr = (self.codeptr + 1) % self.len


class World:
    def __init__(self):
        self.lifeforms = []
        self.worldmap = {(x, y): None for x in range(WORLD_SIZE) for y in range(WORLD_SIZE)}
        self.frame = 0
        self.levenstein_cache = {}

    def get_lev(self, a, b):
        median_len = (len(a) + len(b)) / 2
        if median_len < 1:
            median_len = 1
        k = '{}|{}'.format(a, b) if a > b else '{}|{}'.format(b, a)
        dist = self.levenstein_cache.get(k, None)
        if dist is None:
            dist = (levenstein_distance(a, b), self.frame)
            self.levenstein_cache[k] = dist
        elif dist[1] != self.frame:
            self.levenstein_cache[k] = (dist[0], self.frame)
        return dist[0] / median_len

    def cleanup_lev(self):
        removelist = []
        for k, v in self.levenstein_cache.items():
            if self.frame - v[1] >= 100:
                removelist.append(k)
        for k in removelist:
            del self.levenstein_cache[k]

    def someone_in_front(self, form):
        dx, dy = DIRECTS[form.direct]
        rx = form.x + dx
        ry = form.y + dy
        if (rx, ry) not in self.worldmap:
            return True  # Wall
        return self.worldmap[(rx, ry)]

    def is_friend(self, form):
        t = self.someone_in_front(form)
        if isinstance(t, LifeForm):
            return self.get_lev(t.code, form.code) < 0.3
        return False

    def is_enemy(self, form):
        t = self.someone_in_front(form)
        if isinstance(t, LifeForm):
            return self.get_lev(t.code, form.code) >= 0.3
        return False

    def is_wall(self, form):
        t = self.someone_in_front(form)
        return t is False

    def try_to_go(self, form, back=False):
        dx, dy = DIRECTS[form.direct]
        if back:
            dx = -dx
            dy = -dy
        rx = force_range(form.x + dx, 0, WORLD_SIZE - 1)
        ry = force_range(form.y + dy, 0, WORLD_SIZE - 1)
        if self.worldmap[(rx, ry)] is None:
            self.worldmap[(form.x, form.y)] = None
            form.x = rx
            form.y = ry
            self.worldmap[(rx, ry)] = form
            return True
        return False

    def try_to_breed(self, form):
        dx, dy = DIRECTS[form.direct]
        rx = force_range(form.x - dx, 0, WORLD_SIZE - 1)
        ry = force_range(form.y - dy, 0, WORLD_SIZE - 1)
        if self.worldmap[(rx, ry)] is None:
            new_code = form.code
            for i in range(len(form.code)):
                if random() < MUTATE_PROB:
                    new_code = mutate_code(new_code)
            form.hp -= 50
            child = LifeForm(self, new_code, rx, ry)
            self.worldmap[(rx, ry)] = child
            self.lifeforms.append(child)
            return True
        return False

    def check_bites(self):
        for form in self.lifeforms:
            if form.hp <= 0:
                continue
            if form.lastact != ACT_BITE:
                continue
            dx, dy = DIRECTS[form.direct]
            rx = form.x + dx
            ry = form.y + dy
            target = self.worldmap.get((rx, ry), None)
            if target is None:
                continue
            if target.lastact == ACT_SHIELD and (target.direct + 2) % 4 == form.direct:
                continue
            val = force_range(50, 0, max(0, target.hp))
            target.hp -= val
            form.hp += val // 2

    def check_deaths(self):
        for i in range(len(self.lifeforms) - 1, -1, -1):
            form = self.lifeforms[i]
            if form.hp <= 0:
                self.worldmap[(form.x, form.y)] = None
                self.lifeforms.pop(i)

    def tick(self):
        for form in self.lifeforms:
            form.lastact = None
            form.age_tick()
            for i in range(10):
                form.brain_tick()
                if form.lastact is not None:
                    break
        self.check_bites()
        self.check_deaths()
        if self.frame % 100 == 0:
            self.cleanup_lev()
        self.frame += 1

    def create_random_form(self):
        code = ''
        for i in range(randint(4, 15)):
            code += rand_choice(COMMANDS)
        tries = 5
        while tries > 0:
            x = randint(0, WORLD_SIZE - 1)
            y = randint(0, WORLD_SIZE - 1)
            if self.worldmap[(x, y)] is None:
                form = LifeForm(self, code, x, y)
                self.lifeforms.append(form)
                self.worldmap[(x, y)] = form
                break
            tries -= 1


def start_gtk():
    from gi.repository import Gtk, GObject
    import cairo

    world = World()
    for i in range(10):
        world.create_random_form()

    def OnDraw(w, cr):
        cr.set_line_width(1)
        for form in world.lifeforms:
            cr.rectangle(
                CELL_SIZE * form.x,
                CELL_SIZE * form.y,
                CELL_SIZE,
                CELL_SIZE,
            )
            cr.set_source_rgb(*form.color)
            cr.fill()
            if False and form.lastact is not None and form.lastact != ACT_GO:
                direct = form.direct
                if form.lastact == ACT_BREED:
                    direct = (direct + 2) % 4
                if direct == 0:
                    cr.move_to(CELL_SIZE * form.x, CELL_SIZE * form.y + 1)
                    cr.rel_line_to(CELL_SIZE, 0)
                elif direct == 1:
                    cr.move_to(CELL_SIZE * form.x + CELL_SIZE - 1, CELL_SIZE * form.y)
                    cr.rel_line_to(0, CELL_SIZE)
                elif direct == 2:
                    cr.move_to(CELL_SIZE * form.x, CELL_SIZE * form.y + CELL_SIZE - 1)
                    cr.rel_line_to(CELL_SIZE, 0)
                elif direct == 3:
                    cr.move_to(CELL_SIZE * form.x + 1, CELL_SIZE * form.y)
                    cr.rel_line_to(0, CELL_SIZE)
                if form.lastact == ACT_BITE:
                    cr.set_source_rgb(1, 0, 0)
                elif form.lastact == ACT_BREED:
                    cr.set_source_rgb(0, 1, 0)
                elif form.lastact == ACT_SHIELD:
                    cr.set_source_rgb(0, 0, 1)
                cr.stroke()

    def on_timeout(x):
        world.tick()
        if world.frame % 100 == 0:
            ml = ''
            codemap = {}
            for form in world.lifeforms:
                if len(form.code) > len(ml):
                    ml = form.code
                codemap[form.code] = codemap.get(form.code, 0) + 1
            pc = 1
            best = []
            for k, v in reversed(sorted(codemap.items(), key=lambda x: x[1])):
                best.append('{}: {} ({})'.format(pc, k, v))
                pc += 1
                if pc > 3:
                    break
            print('Best: {} ::: Longest: {} ::: lev {}'.format(' ::: '.join(best), ml, len(world.levenstein_cache)))
        a.queue_draw_area(0, 0, WORLD_SIZE * CELL_SIZE, WORLD_SIZE * CELL_SIZE)
        GObject.timeout_add(10, on_timeout, None)

    w = Gtk.Window()
    w.set_default_size(WORLD_SIZE * CELL_SIZE, WORLD_SIZE * CELL_SIZE)
    a = Gtk.DrawingArea()
    w.add(a)
    w.connect('destroy', Gtk.main_quit)
    a.connect('draw', OnDraw)
    w.show_all()

    on_timeout(None)
    Gtk.main()


if __name__ == '__main__':
    start_gtk()