#!/usr/bin/python

import numpy as np
from tronproblem import *
from trontypes import CellType, PowerupType
import random, math
from queue import Queue, LifoQueue, PriorityQueue

# Throughout this file, ASP means adversarial search problem.


class StudentBot:
    def __init__(self):
        self.resetCounter = 0
        self.turns_elapsed = 0
        self.clutch_gene = 0
        self.pseudo_clutch_gene = 0


    def decide(self, asp):

        cutoff = 3
        #cutoff = min(4, self.turns_elapsed/3)
        if self.turns_elapsed <= 5:
            cutoff = 3
        self.player = asp.get_start_state().ptm

        eval_function = self.eval_function_2
        if self.clutch_gene >= 12:
            #print("clutch")

            return self.conserve(asp)
        if asp.get_start_state().get_remaining_turns_speed(self.player) > 0:
            return self.conserve(asp)
        #elif self.pseudo_clutch_gene >=12:
        #    return self.pseudo_clutch(asp)

        a = self.ab_cut(asp, cutoff, eval_function)

        return a



    def ab_cut(self, asp, cutoff_ply, eval_func):
        #print(asp.get_start_state().board[1][1])
        #print(asp.get_start_state().board[1][2] == " ")
        #print("s")
        start = asp.get_start_state()
        v = float('-inf')
        self.armored = False
        action = "D"
    #    print("ab")
    #    print(start.ptm)
        if start.player_has_armor(start.ptm):
            actions = self.armored_actions(start.board, start.player_locs[start.ptm])
        else:
            actions = asp.get_safe_actions(start.board, start.player_locs[start.ptm])
        for a in actions:
            val = self.cutoff_min(asp, asp.transition(start, a), v,  float('inf'), cutoff_ply-1, eval_func)
            #val += self.powerup_value(asp, a)
        #    print(val)
        #    print(a)
            val += self.powerup_value(asp, a)
            if val > v:
                v = val
                action = a


        self.turns_elapsed += 1
        nextsquare = asp.move(start.player_locs[start.ptm], action)
        if start.board[nextsquare[0]][nextsquare[1]] == CellType.BOMB:
            self.turns_elapsed = 0
        #    print("y")
        return action

    def cutoff_max(self, asp, state, alfa, balfa, cutoff, e):
    ##    print("max")
    #    print(state.ptm)
        if asp.is_terminal_state(state):
            e = asp.evaluate_state(state)[state.ptm]
            if e < 0.1:
                return float('-inf')
            return float('inf')
        if cutoff <= 0:
            return e(asp, state)
        v  = float('-inf')
        if state.player_has_armor(state.ptm):
            #print('y')
            actions = self.armored_actions(state.board, state.player_locs[state.ptm])
        else:
            actions = asp.get_safe_actions(state.board, state.player_locs[state.ptm])
        for a in actions:
            v  = max(v, self.cutoff_min(asp, asp.transition(state, a), alfa, float('inf'), cutoff-1, e))
            if v >= balfa:
                return v
            alfa = max(v, alfa)
        return v

    def cutoff_min(self, asp, state, alfa, balfa, cutoff, e):
        #print("min")
        #print(state.ptm)
        if asp.is_terminal_state(state):
            e = asp.evaluate_state(state)[1-state.ptm]
            if e < 0.1:
                return float('-inf')
            return float('inf')
        if cutoff <= 0:
            return e(asp, state)
        v  = float('inf')
        if state.player_has_armor(state.ptm):
            #print('y')
            actions = self.armored_actions(state.board, state.player_locs[state.ptm])
        else:
            actions = asp.get_safe_actions(state.board, state.player_locs[state.ptm])
        for a in actions:

            v  = min(v, self.cutoff_max(asp, asp.transition(state, a), float('-inf'), balfa, cutoff-1, e))
            if v <= alfa:
                return v
            balfa = min(v, balfa)
        return v
    """
    Gets the difference between # accessible spaces for bot 1 and bot 2
    """


    def powerup_value(self, asp, action):
        board = asp.get_start_state().board
        ploc = asp.get_start_state().player_locs[self.player]
        p2loc = asp.get_start_state().player_locs[1-self.player]
        next_loc = asp.move(ploc, action)
        powerup = board[next_loc[0]][next_loc[1]]
        separation = (ploc[0]-p2loc[0])**2 + (ploc[1]-p2loc[1])**2

        if powerup == '!':
            return 0
            return separation/3
        if powerup == '^':

            return 1
        if powerup == '@':
            if not asp.get_start_state().player_has_armor(self.player):
                return 2
            else:
                return 0
        if powerup == '*':
            if separation < 25:
                return -1
            else:
                return 3

        else:
            return 0




    #Bugged attempt at BDS:
    def eval_function_2(self, asp, state):
        board = state.board
        ptm = self.player
    #    print("eval")
    #    print(ptm)
        q1 = Queue()
        q2 = Queue()
        our_util = 0
        their_util = 0
        q1.put(state.player_locs[ptm])
        q2.put(state.player_locs[1-ptm])
        our_space = {}
        their_space = {}
        armored = state.player_has_armor(ptm)
        self.clutch_gene += 1
        #self.pseudo_clutch_gene += 1
        while not q1.empty() and not q2.empty():
            if not q1.empty():
                front = q1.get()
                #if armored:
            #        steps = self.armored_actions(board, front)
                #    armored = False
                #else:
                steps = asp.get_safe_actions(board, front)
                for a in steps:
                    curr = asp.move(front, a)
                    item = board[curr[0]][curr[1]]
                    d = self.to_1d(curr, board)
                    if item == CellType.WALL:
                        our_util -= 3
                    if d not in our_space:
                        if d not in their_space:
                            q1.put(curr)
                            our_space[d] = item
                            our_util +=1

                            if item == '!':

                                counter = 0
                                for k in range(curr[0]-3, curr[0]+3):
                                    for l in range(curr[1] -3, curr[1] + 3):
                                        if k > 0 and k < len(board):
                                            if l > 0 and l < len(board[0]):
                                                 if board[k][l] == CellType.BARRIER:
                                                     counter += 1
                                our_util += counter
                            if item == CellType.SPEED:
                                our_util += 3
                            if item == CellType.ARMOR:
                                our_util += 1
                            #    self.clutch_gene = 0
                            if item == CellType.TRAP:
                                our_util += 3
                        else:
                            self.clutch_gene = 0

            if not q2.empty():
                back = q2.get()
                steps = asp.get_safe_actions(board, back)
                for b in steps:
                    curr = asp.move(back, b)
                    item = board[curr[0]][curr[1]]
                    d = self.to_1d(curr, board)
                    if d not in their_space:
                        if d not in our_space:
                            q2.put(curr)
                            their_space[d] = item
                            their_util +=1

                            if item == CellType.BOMB:
                                counter = 0
                                for k in range(curr[0]-3, curr[0]+3):
                                    for l in range(curr[1] -3, curr[1] + 3):
                                        if k > 0 and k < len(board):
                                            if l > 0 and l < len(board[0]):
                                                 if board[k][l] == CellType.BARRIER:
                                                     counter += 1
                                their_util += counter                        #self.clutch_gene = 0
                            if item == CellType.SPEED:
                                their_util += 0
                            if item == CellType.ARMOR:
                                their_util += 1
                                #self.clutch_gene = 0
                            if item == CellType.TRAP:

                                their_util += 3
                                #self.clutch_gene = 0
                        else:
                            self.clutch_gene = 0

        if our_util < 150:
            self.resetCounter += 1
        else:
            self.resetCounter = 0
            self.cutoff = 3
        if self.resetCounter >= 12:
            self.cutoff = 4
        #if self.clutch_gene == 12:
        #    print('clutch')

        #print("ourspacec")
        #print(len(our_space))

        return our_util - their_util

    def armored_actions(self, board, loc):
        safe = set()
        for action in {U, D, L, R}:
            r1, c1 = TronProblem.move(loc, action)
            if not (
                #board[r1][c1] == CellType.BARRIER
                board[r1][c1] == CellType.WALL
                or TronProblem.is_cell_player(board, (r1, c1))
            ):
                safe.add(action)
        return safe




    def to_1d(self, location, board):
        return len(board)*location[0]+location[1]

    def to_2d(self, location, board):

        a = location/len(board[0])
        return (int(a), location%len(board[0]))

    def conserve(self, asp):

        state = asp.get_start_state()
        allActions = asp.get_available_actions(state)
        pq = PriorityQueue()
        ptm = self.player
    #    print("conserve")
    #    print(ptm)
        board = state.board
        p1 = state.player_locs[ptm]
        armored = state.player_has_armor(ptm)
        #pq.put((0, p1))
        locDic = {}
        best = float('inf')
        safety = False
        armored = False
        immediate_actions = asp.get_safe_actions(board, p1)
        if armored:
            immediate_actions = self.armored_actions(board, p1)
        if len(immediate_actions) == 0:
            return self.panic(board, p1,asp)
            bigA = 'D'
        else:
            bigA = random.sample(immediate_actions,1)[0]
        for act in immediate_actions:

            loc = asp.move(p1, act)
            index = self.to_1d(loc, board)
            locDic[index] = act
            costDict = {}
            #costDict[self.to_1d(p1, board)] = 100
            julio = len(asp.get_safe_actions(board, loc))
            if julio == 1 or julio == 2:
                safety = True
                costDict[index] = -2+len(asp.get_safe_actions(board, loc))
            else:
                #print(act)
                if not safety:
                    if julio == 3:
                        bigA = act
                continue

            immediate_item = board[loc[0]][loc[1]]
            immediate_val = -1
            if immediate_item == '!':

                immediate_val = -100
            if immediate_item == '@' and not armored:
                immediate_val = -2
            if immediate_item == '^':
                immediate_val = 3
            if immediate_item == '*':
                immediate_val = -3
            pq.put((immediate_val, index))

            while not pq.empty():
                popped = pq.get()[1]
                currLoc = self.to_2d(popped, board)
                if popped == self.to_1d(p1, board):
                    continue

                actions = asp.get_safe_actions(board, currLoc)
                nextLocs = []
                for a in actions:
                    nl = asp.move(currLoc, a)
                    nextLoc = self.to_1d(nl, board)
                    if nextLoc not in costDict:
                        heur = -1
                        nextItem = board[self.to_2d(nextLoc, board)[0]][self.to_2d(nextLoc, board)[1]]
                        if nextItem == '*':
                            heur = -1
                        if nextItem == '!':
                            heur = -10
                        if nextItem == '@':
                            heur = -1
                        #if nextItem ==

                        costDict[nextLoc] = heur + costDict[popped]
                        total_cost = heur + costDict[popped]
                        pq.put((total_cost, nextLoc))
                        costDict[index] = min(costDict[index], total_cost)
                for act in allActions:
                    nl = asp.move(currLoc, a)

                    if asp.is_cell_player(board, nl) and self.to_1d(board, p1) != self.to_1d(board, nextloc):
                        print('ye')
                        self.clutch_gene = 0
        #    print(costDict[index])
        #    print(locDic[index])
            #print(costDict[index])
            #print(locDic[index])
            if costDict[index] < best:
                best = costDict[index]
                bestLocation = index
                bigA = locDic[index]

    #    print(best)
        return bigA

    def panic(self, board, location, asp):
        actions = self.armored_actions(board, location)
        v = float('inf')
        s = set()
        best = 'L'
        for a in actions:
            state = asp.transition(asp.get_start_state(), a)
            if self.eval_function_2(asp, state) > v:
                v = self.eval_function_2(asp, state)
                best = a
        return a




    def cleanup(self):

        """
        Input: None
        Output: None

        This function will be called in between
        games during grading. You can use it
        to reset any variables your bot uses during the game
        (for example, you could use this function to reset a
        turns_elapsed counter to zero). If you don't need it,
        feel free to leave it as "pass"
        """
        self.turns_elapsed = 0
        self.clutch_gene = 0
        self.cutoff = 3
        self.resetCounter = 0


class RandBot:
    """Moves in a random (safe) direction"""

    def decide(self, asp):
        """
        Input: asp, a TronProblem
        Output: A direction in {'U','D','L','R'}
        """
        state = asp.get_start_state()
        locs = state.player_locs
        board = state.board
        ptm = state.ptm
        loc = locs[ptm]
        possibilities = list(TronProblem.get_safe_actions(board, loc))
        if possibilities:
            return random.choice(possibilities)
        return "U"

    def cleanup(self):
        pass


class WallBot:
    """Hugs the wall"""

    def __init__(self):
        order = ["U", "D", "L", "R"]
        random.shuffle(order)
        self.order = order

    def cleanup(self):
        order = ["U", "D", "L", "R"]
        random.shuffle(order)
        self.order = order

    def decide(self, asp):
        """
        Input: asp, a TronProblem
        Output: A direction in {'U','D','L','R'}
        """
        state = asp.get_start_state()
        locs = state.player_locs
        board = state.board
        ptm = state.ptm
        loc = locs[ptm]
        possibilities = list(TronProblem.get_safe_actions(board, loc))
        if not possibilities:
            return "U"
        decision = possibilities[0]
        for move in self.order:
            if move not in possibilities:
                continue
            next_loc = TronProblem.move(loc, move)
            if len(TronProblem.get_safe_actions(board, next_loc)) < 3:
                decision = move
                break
        return decision