# -*- coding: utf-8 -*-

from api import *

import math, queue
        
class Nain:
    def __init__(self, id_):
        self.id = id_
        self._reset_values()
    def _ptvalues(self):
        self.pm = NB_POINTS_DEPLACEMENT
        self.pa = NB_POINTS_ACTION
    def __repr__(self):
        return "Nain#%s(%s,%s){butin: %s, vie: %s, pm: %s, pa: %s}" % (self.id, self.x, self.y, self.butin, self.pv, self.pm, self.pa)
    def _reset_values(self):
        self.x, self.y = position_taverne(moi())[::-1]
        self.pos = (self.y, self.x)
        self.pv = VIE_NAIN
        self.pm = NB_POINTS_DEPLACEMENT
        self.pa = NB_POINTS_ACTION
        self.accroche = False
        self.butin = 0
        self.chemin = []
        self.objectif = None
    def update(self):
        nain = info_nain(moi(), self.id)
        self.pos = nain.pos
        self.y, self.x = self.pos
        self.pv = nain.vie
        self.pm = nain.pm
        self.pa = nain.pa
        self.accroche = nain.accroche
        self.butin = nain.butin
        #self.update_goal()
    def update_goal(self):
        self.chemin = find_chemin((self.x, self.y), self.objectif) if self.objectif else []
    def _update_pos(self):
        nain = info_nain(moi(), self.id)
        self.pos = nain.pos
        self.y, self.x = self.pos
    def update_pos(self, x, y):
        self.x = x
        self.y = y
        self.pos = (y, x)
    def accrocher(self):
        if self.accroche:
            return
        self.accroche = True
        agripper(self.id)
    def lacher(self):
        if not self.accroche:
            return
        self.accroche = False
        lacher(self.id)
    def mort(self):
        return self.pv <= 0
    def deplacer(self, step):
        # est possible
        self.pm -= cout_de_deplacement(self.id, step)
        deplacer(self.id, step)
        self._update_pos()
    def goal(self, objectif):
        if objectif == (self.x, self.y):
            return False
        self.objectif = objectif
        self.chemin = find_chemin((self.x, self.y), objectif)
        return True
    def step(self):
        # 0: ne peut plus rien faire
        # 1: ne peut rien faire sans l'aide d'un autre nain
        # 2: a fait ce qu'on lui a demandé de faire
        if self.mort():
            return 3
        if not self.chemin:
            return 0
        action, arg = self.chemin[0]
        self._update_pos()
        if action == "deplacer":
            if arg in {direction.GAUCHE, direction.DROITE}:
                dx, dy = dir2coords[arg]
                nx, ny = self.x+dx, self.y+dy
                if (len(self.chemin) == 1 or self.chemin[1][0] != "tomber") and not is_stable(nx, ny):
                    self.accrocher()
                elif (is_stable(self.x, self.y) and is_stable(nx, ny)) or (is_stable(self.x, self.y) and len(self.chemin) > 1 and self.chemin[1][0] == "tomber"):
                    self.lacher()
                else:
                    self.accrocher()
            else:
                self.accrocher()
            if cout_de_deplacement(self.id, arg) > self.pm:
                return 3
            self.deplacer(arg)
            self.chemin.pop(0)
            if is_stable(self.x, self.y):
                self.lacher()
            return 2
        elif action == "tomber":
            (nx, ny), dmg = fall(self.x, self.y)
            if dmg == 0:
                self.lacher()
                self._update_pos()
                if self.pos[0] >= arg[0] or self.pos[1] != arg[1]:
                    self.chemin.pop(0)
                else:
                    self.chemin.insert(0, ("miner", direction.BAS))
            else:
                self.chemin.insert(0, ("deplacer", direction.BAS))
            return 2
        elif action == "miner":
            dx, dy = dir2coords[arg]
            if is_free(self.x + dx, self.y + dy):
                self.chemin.pop(0)
                return 2
            if COUT_MINER > self.pa:
                return 1
            self.accrocher()
            miner(self.id, arg)
            self.pa -= COUT_MINER
            self.chemin.pop(0)
            self._update_pos()
            return 2
        else:
            print("FATAL - this should not happend. Who knows what happens next...")
        print("WTF %s %s" % (action, arg))
        return 2
    def purge_actions(self):
        while self.chemin and self.chemin[0][0] == "miner":
            if self.chemin[0][1] == direction.BAS and is_free(self.x, self.y+1):
                self.chemin.pop(0)
            else:
                break
    def endstep(self):
        self.purge_actions()
        (nx, ny), dmg = fall(self.x, self.y)
        if dmg == 0 and self.chemin and self.chemin[0][0] == "tomber":
            self.lacher()
        self.accrocher()


def is_free(x, y):
    return type_case((y, x)) == case_type.LIBRE and nain_sur_case((y, x)) != adversaire()

def is_stable(x, y):
    return y == TAILLE_MINE - 1 or not is_free(x, y+1)

def is_not_et(x, y):
    return position_taverne(adversaire()) != (y, x)


def grav_dmg(dy):
    if dy <= 3:
        return 0
    else:
        return 2**(dy-4)
        
def fall(x, y, dy=0):
    while not is_stable(x, y+dy):
        dy += 1
    
    return (x, y+dy), grav_dmg(dy) if is_not_et(x, y+dy) else (VIE_NAIN + 1)

def compute_pac(resistance):
    if resistance == -1:
        return COUT_MINER
    else:
        return COUT_MINER * resistance

def compute_nain_resistance(pos):
    vie = 0
    for nain in (info_nain(adversaire(), id_) for id_ in range(6)):
        if nain.pos == pos:
            vie = max(vie, nain.vie)
    return math.ceil(vie/DEGAT_PIOCHE)

def extend_movements(x, y):
    moves = []
    # Bas
    if y < TAILLE_MINE - 1:
        go = True if is_not_et(x, y+1) else False
        if type_case((y+1, x)) == case_type.GRANITE:
            if corde_sur_case((y, x)):
                pmc = 1
            else:
                pmc = 2
            pac = compute_pac(info_minerai((y+1, x)).resistance)
        elif is_free(x, y+1):
            if corde_sur_case((y, x)):
                pmc = 1
            else:
                pmc = 2
            pac = 0
        elif nain_sur_case((y+1, x)) == adversaire():
            if corde_sur_case((y, x)):
                pmc = 1
            else:
                pmc = 2
            pac = COUT_MINER * compute_nain_resistance((y+1, x))
        else:
            go = False
        if go:
            moves.append((pac, pmc, (x, y+1)))
            if type_case((y+1, x)) == case_type.GRANITE:
                (nx, ny), dmg = fall(x, y+1, dy=1)
            else:
                (nx, ny), dmg = fall(x, y)
            if dmg == 0: moves.append((pac, 0, (nx, ny)))
    # Haut
    if y > 0:
        go = True
        if corde_sur_case((y, x)) and corde_sur_case((y-1, x)):
            pmc = COUT_ESCALADER_CORDE
        else:
            pmc = COUT_ESCALADER
        if type_case((y-1, x)) == case_type.GRANITE:
            pac = compute_pac(info_minerai((y-1, x)).resistance)
        elif is_free(x, y-1):
            pac = 0
        elif nain_sur_case((y-1, x)) == adversaire():
            pac = COUT_MINER * compute_nain_resistance((y+1, x))
        else:
            go = False
        if go:
            moves.append((pac, pmc, (x, y-1)))


    # Droite
    if x < TAILLE_MINE - 1:
        go = True if is_not_et(x+1, y) else False
        if is_stable(x, y) and is_stable(x+1, y):
            pmc = 1
        else:
            pmc = 2
        if type_case((y, x+1)) == case_type.GRANITE:
            pac = compute_pac(info_minerai((y, x+1)).resistance)
        elif is_free(x+1, y):
            pac = 0
        elif nain_sur_case((y, x+1)) == adversaire():
            pac = COUT_MINER * compute_nain_resistance((y+1, x))
        else:
            go = False
        if go:
            moves.append((pac, pmc, (x+1, y)))
            if not is_stable(x+1, y):
                (nx, ny), dmg = fall(x+1, y)
                if dmg == 0: moves.append((pac, 1, (x+1, y)))
                    
    # Gauche
    if x > 0:
        go = True if is_not_et(x-1, y) else False
        if is_stable(x, y) and is_stable(x-1, y):
            pmc = COUT_DEPLACEMENT
        else:
            pmc = COUT_ESCALADER
        if type_case((y, x-1)) == case_type.GRANITE:
            pac = compute_pac(info_minerai((y, x-1)).resistance)
        elif is_free(x-1, y):
            pac = 0
        elif nain_sur_case((y, x-1)) == adversaire():
            pac = COUT_MINER * compute_nain_resistance((y+1, x))
        else:
            go = False
        if go:
            moves.append((pac, pmc, (x-1, y)))
            if not is_stable(x-1, y):
                (nx, ny), dmg = fall(x-1, y)
                if dmg == 0: moves.append((pac, 1, (x-1, y)))

    return moves

def nturns(pacsof, pmcsof):
    return max(pacsof/(NB_POINTS_ACTION-1), pmcsof/NB_POINTS_DEPLACEMENT)

def find_chemin(start, end):
    come_from = find_shortest_path(start, end)
    chemin = path2chemin(start, end, come_from)
    return chemin

def path2chemin(start, end, come_from):
    next_ = end
    chemin = []
    while next_ != start:
        n2 = come_from[next_]
        x, y = n2
        nx, ny = next_
        step_hor = {0: None, 1: direction.DROITE, -1: direction.GAUCHE}[nx - x]
        dy = ny - y
        dirs_ver = {-1: direction.HAUT, 1: direction.BAS}
        if step_hor:
            if dy:
                chemin.insert(0, ("tomber", (ny, nx)))
            chemin.insert(0, ("deplacer", step_hor))
            if type_case((ny, nx)) == case_type.GRANITE:
                chemin.insert(0, ("miner", step_hor))
        else:
            if dy == 1:
                if is_stable(nx, ny):
                    chemin.insert(0, ("tomber", (ny, nx)))
                else:
                    chemin.insert(0, ("deplacer", dirs_ver[dy]))
            elif dy == -1:
                chemin.insert(0, ("deplacer", dirs_ver[dy]))
            else:
                chemin.insert(0, ("tomber", (ny, nx)))
            if dy in {-1, 1}:
                if type_case((ny, nx))== case_type.GRANITE:
                    chemin.insert(0, ("miner", dirs_ver[dy]))
            else:
                if type_case((y+1, x)) == case_type.GRANITE:
                    chemin.insert(0, ("miner", dirs_ver[1]))
            
        next_ = n2
    return chemin

def compute_csof(start, now, come_from, pac_so_far, pmc_so_far):
    next_ = now
    pacsof = 0
    pmcsof = 0
    while next_ != start:
        pacsof += pac_so_far[next_]
        pmcsof += pmc_so_far[next_]
        next_ = come_from[next_]
    return pacsof, pmcsof

def generate_value_map(nain):
    map_ = [[0 for i in range(TAILLE_MINE)] for j in range(TAILLE_MINE)]
    y, x = position_taverne(adversaire())
    map_[x][y] = float("-inf")
    map_[nain.x][nain.y] = float("-inf") # le nain veut TRAVAILLER!!
    for pos in liste_minerais():
        y, x = pos
        minerai = info_minerai(pos)
        rend = 100*min(minerai.rendement, BUTIN_MAX - nain.butin) / (compute_pac(minerai.resistance) * 2 *(manhatan_heuristic(nain.pos, pos))+1)
        map_[x][y] += rend
        for dx in {-1, +1}:
            for dy in {-1, +1}:
                if 0 <= x+dx < TAILLE_MINE and 0 <= y+dy < TAILLE_MINE: map_[x+dx][y+dy] += rend/4
        for dx in {-2, +2}:
            for dy in {-2, +2}:
                if 0 <= x+dx < TAILLE_MINE and 0 <= y+dy < TAILLE_MINE: map_[x+dx][y+dy] += rend/8
    for minerai_recalcitrant in (info_nain(adversaire(), id_) for id_ in range(NB_NAINS)):
        rend = 100*(minerai_recalcitrant.butin + min(minerai_recalcitrant.butin, BUTIN_MAX - nain.butin))/(compute_pac(math.ceil(minerai_recalcitrant.vie/DEGAT_PIOCHE)) * 6 * manhatan_heuristic(nain.pos, minerai_recalcitrant.pos)+1)
        map_[x][y] += rend
        for dx in {-1, +1}:
            for dy in {-1, +1}:
                if 0 <= x+dx < TAILLE_MINE and 0 <= y+dy < TAILLE_MINE: map_[x+dx][y+dy] += rend/4
        for dx in {-2, +2}:
            for dy in {-2, +2}:
                if 0 <= x+dx < TAILLE_MINE and 0 <= y+dy < TAILLE_MINE: map_[x+dx][y+dy] += rend/8
        y, x = position_taverne(moi())
        map_[x][y] += 10 / ((25-nain.butin) * 2 * manhatan_heuristic(nain.pos, (y, x)) + 1)
    for y, x in not_map:
        map_[x][y] = float("-inf")
    return map_
        
#@cache
def find_shortest_path(start, end):
    pmc_so_far = {start: 0}
    pac_so_far = {start: 0}
    come_from = {start: start}
    x, y = end
    boundary = queue.PriorityQueue()
    boundary.put_nowait((0, start))
    end_turns = float("inf")
    while not boundary.empty():
        next_ = boundary.get_nowait()[1]
        for move in extend_movements(*next_):
            dpac, dpmc, nmov = move
            
            pacsof, pmcsof = compute_csof(start, next_, come_from, pac_so_far, pmc_so_far)
            pacsof += dpac
            pmcsof += dpmc
            nb_turns = nturns(pacsof, pmcsof)
            if nmov in come_from.keys():
                if nb_turns >= nturns(*compute_csof(start, nmov, come_from, pac_so_far, pmc_so_far)):
                    continue
            pmc_so_far[nmov] = dpmc
            pac_so_far[nmov] = dpac
            come_from[nmov] = next_
            if nmov == end:
                end_turns = min(end_turns, nturns(pacsof, pmcsof))
            elif nturns(pacsof, pmcsof) < end_turns:
                boundary.put_nowait((nturns(pacsof, pmcsof) + manhatan_heuristic(nmov, end), nmov)) #  
                if len(boundary.queue) > MAXLEN:
                    boundary.queue.pop(-1)
    #return (come_from, pac_so_far, pmc_so_far), come_from
    return come_from



def draw_map(start):
    pmc_so_far = {start: 0}
    pac_so_far = {start: 0}
    come_from = {start: start}
    boundary = queue.PriorityQueue()
    boundary.put_nowait((0, start))
    while not boundary.empty():
        next_ = boundary.get_nowait()[1]
        for move in extend_movements(*next_):
            dpac, dpmc, nmov = move
            pacsof, pmcsof = compute_csof(start, next_, come_from, pac_so_far, pmc_so_far)
            pacsof += dpac
            pmcsof += dpmc
            nb_turns = nturns(pacsof, pmcsof)
            if nmov in come_from.keys():
                if nb_turns >= nturns(*compute_csof(start, nmov, come_from, pac_so_far, pmc_so_far)):
                    continue
            pmc_so_far[nmov] = dpmc
            pac_so_far[nmov] = dpac
            come_from[nmov] = next_
            boundary.put_nowait((nturns(pacsof, pmcsof), nmov))
            if len(boundary.queue) > MAXLEN:
                debug("cutting")
                boundary.queue.pop(-1)
    return come_from, pac_so_far, pmc_so_far


manhatan_heuristic = lambda a, b: (abs(a[0]-b[0])+abs(a[1]-b[1]))
# Fonction appelée au début de la partie.

def neighboors(pos):
    x, y = pos
    for dx in {-1, +1}:
        for dy in {-1, +1}:
           if 0 <= x+dx < TAILLE_MINE and 0 <= y+dy < TAILLE_MINE: yield (x+dx, y+dy)

def partie_init():
    global nains, dir2coords, MAXLEN, not_map
    nains = [Nain(nain) for nain in range(NB_NAINS)]
    dir2coords = {
        direction.HAUT: (0, -1),
        direction.DROITE: (1, 0),
        direction.BAS: (0, 1),
        direction.GAUCHE: (-1, 0)
    }
    boundary = queue.PriorityQueue()
    boundary.put_nowait(position_taverne(moi()))
    not_map = [a for a in generate_coords()]
    MAXLEN = 200
    while not boundary.empty():
        next_ = boundary.get_nowait()
        for pos in neighboors(next_):
            if pos in not_map and type_case(pos) in {case_type.LIBRE, case_type.GRANITE}:
                not_map.remove(pos)
                boundary.put_nowait(pos)
    a = draw_map(position_taverne(moi())[::-1])
    
def print_value_map(map_):
    for colonne in map_:
        for ligne in colonne:
            print("%5s" % round(ligne, 2), end="")
        print()
    print()

def generate_coords():
    for x in range(TAILLE_MINE):
        for y in range(TAILLE_MINE):
            yield (x, y)
    
def jouer_tour():
    global nains
    #if tour_actuel() == 10: print_value_map(generate_value_map(nains[0]))
    need_to_play = [nain for nain in nains]
    updated = True
    while need_to_play and updated:
        for nain in need_to_play:
            updated = False
            nain.update()
            while True:
                res = nain.step()
                if res == 2:
                    updated = True
                    nain.update()
                    continue
                elif res == 3:
                    need_to_play.remove(nain)
                    break
                elif res == 0:
                    if nain.butin >= 20:
                        updated = nain.goal(position_taverne(moi())[::-1])
                    else:
                        value_map = generate_value_map(nain)
                        goal = max(generate_coords(), key=lambda pos: value_map[pos[0]][pos[1]])
                        updated = nain.goal(goal)
                    nain.update()
                elif res == 1:
                    break
            [n.endstep() for n in need_to_play]

def partie_fin():
    pass

