# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     language: python
#     name: python3
# ---

# +
from __future__ import print_function, division
from collections import deque
import math
import sys
import time
BOARD_SIZE = 16
INPUT_FILE = './input.txt'
INFINITY = sys.maxsize
NEGATIVE_INFINITY = -1*sys.maxsize
DIRECTIONS = [(1, 1), (1, -1), (1, 0), (0, 1), (0, -1), (-1, 0), (-1, 1), (-1, -1)]
CAMP = {}
CAMP['W'] = [(11, 14), (11, 15), (12, 13), (12, 14), (12, 15), (13, 12), (13, 13), (13, 14), (13, 15), (14, 11), (14, 12), (14, 13), (14, 14), (14, 15), (15, 11), (15, 12), (15, 13), (15, 14), (15, 15)]
CAMP['B'] = [(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (2, 0), (2, 1), (2, 2), (2, 3), (3, 0), (3, 1), (3, 2), (4, 0), (4, 1)]
CAMP_CORNER = {}
CAMP_CORNER['W'] = (15, 15)
CAMP_CORNER['B'] = (0, 0)
MY_COLOR = None


def read_input():
    # reading input.txt
    with open(INPUT_FILE, 'r') as file:
        line = file.readline()
        mode = line.strip()
        line = file.readline()
        player_color = line.strip()
        line = file.readline()
        total_play_time = float(line.strip())
        
        board = []
        for i in range(BOARD_SIZE):
            line = file.readline()
            board.append(line.strip())
        return mode, player_color, total_play_time, board

def save_output(x):
    path = x.get_parent_move()+'\n'
    while x.parent != None:
        x = x.parent
        path = x.get_parent_move() + '\n' + path
    with open('output.txt', 'w') as file:
        file.write(path)
    return path

class Node:
    def __init__(self, pawn_positions, current_pawn, parent=None):
        self.state = pawn_positions
        self.current_pawn = current_pawn
        self.parent = parent

    def get_single_jump_options(self):
        options = []
        for direction in DIRECTIONS:
            neighbor = (self.current_pawn[0] + direction[0], self.current_pawn[1] + direction[1])
            neighbors_neighbor = (neighbor[0] + direction[0], neighbor[1] + direction[1])
            if(neighbors_neighbor[0] < 0 or neighbors_neighbor[0] >= BOARD_SIZE or neighbors_neighbor[1] >= BOARD_SIZE or neighbors_neighbor[1] < 0):
                continue
            if(neighbor in self.state and not neighbors_neighbor in self.state):# neighbors_neighbor != self.parent.pawn_position
                pawn_color = self.state[self.current_pawn]
                temp = self.state.copy()
                del temp[self.current_pawn]
                temp[neighbors_neighbor] = pawn_color
                options.append((temp, neighbors_neighbor))

        return options


    def get_parent_move(self):
        pass
    
    def print_path(self):
        x = self
        path = ""
        while x != None:
            path = "(" + str(x.current_pawn[0]) + "," + str(x.current_pawn[1]) + ")" + path
            x = x.parent
            
        return path
    
    def __repr__(self):
        board = ['................']*16
        for position, color in self.state.items():
            temp = list(board[position[0]])
            temp[position[1]] = color
            board[position[0]] = "".join(temp)
            
        return "*0123456789012345\n"+"\n".join([str(i%10)+e for i, e in enumerate(board)]) + "\n" + self.print_path()


def utility(state, max_player):
    distances = []
    for position, color in state.items():
        if(color == MY_COLOR):
            opponent_color = 'W' if MY_COLOR == 'B' else 'B'
            opponent_corner = CAMP_CORNER[opponent_color]
            distances.append(SLD(position, opponent_corner))
    if(max_player):
        return 1/sum(distances)*len(distances)*1000
    else:
        return -1/sum(distances)*len(distances)*1000


def DFS(start_state, current_pawn):
    q = deque()
    start_state = Node(start_state, current_pawn, None)
    q.append(start_state)
    visited = []
    possible_moves = []
    while len(q) != 0:
        currnode = q.pop()
        options = currnode.get_single_jump_options()
        visited.append(currnode.state)
        if(currnode.parent != None):
            possible_moves.append(currnode)
        for option in options:
            if(option[0] in visited):
                continue
            n = Node(option[0], option[1], currnode)
            q.append(n)

    return possible_moves

def get_action_for_single_pawn(state, position):
    # adding moves
    node = Node(state, position, parent=None)
    moves = []
    for direction in DIRECTIONS:
        neighbor = (position[0] + direction[0], position[1] + direction[1])
        if(neighbor[0] < 0 or neighbor[0] >= BOARD_SIZE or neighbor[1] >= BOARD_SIZE or neighbor[1] < 0):
            continue
        if(not neighbor in state):
            pawn_color = state[position]
            temp = state.copy()
            del temp[position]
            temp[neighbor] = pawn_color
            moves.append(Node(temp, neighbor, parent=node))
            
    
    
    jump_moves = DFS(state, position)
#     print("jump moves", jump_moves)
    moves = moves+jump_moves
    
    return moves

def SLD(curr, goal):
    # straight line distance
    x = math.pow(goal[0] - curr[0], 2)
    y = math.pow(goal[1] - curr[1], 2)
    return math.sqrt(x + y)

def actions(state, player_color):
    moves = []
    # if something in camp move it out first
    for position in CAMP[player_color]:
        if(position in state and state[position] == player_color):
            proposed_moves = get_action_for_single_pawn(state, position)
            moves_out_of_camp = []
            moves_away_from_corner = []
            for move in proposed_moves:
                if(not move.current_pawn in CAMP[player_color]): #moves out of camp
                    moves_out_of_camp.append(move)
                elif(SLD(position, CAMP_CORNER[player_color]) < SLD(move.current_pawn, CAMP_CORNER[player_color])): #moves away from the camp corner
                    moves_away_from_corner.append(move)
            if(len(moves_out_of_camp) == 0 and len(moves) == 0):
                moves = moves+moves_away_from_corner
            else:
                moves = moves+moves_out_of_camp
    
    if(len(moves) != 0):
        return moves
    
    for position, color in state.items():
        if(color == player_color):
            proposed_moves = get_action_for_single_pawn(state, position)
            
            for move in proposed_moves:
                if(not move.current_pawn in CAMP[player_color]):#does not return to camp
                    moves.append(move)

    return moves


def terminate(depth):
    if(depth >= 4):
        return True
    else:
        return False

def alpha_beta_search(state, player_color):
    v, move = max_value(state, NEGATIVE_INFINITY, INFINITY, player_color, depth=0)
    return v, move

def max_value(state, alpha, beta, player_color, depth=0):
    if(terminate(depth)):
        return utility(state, max_player=True), None

    v = NEGATIVE_INFINITY
    v_move = None
    for move in actions(state, player_color):
        next_player = 'W' if player_color == 'B' else 'B'
        min_v, _ = min_value(move.state, alpha, beta, next_player, depth=depth+1)
        if(min_v > v):
            v = min_v
            v_move = move
        if(v >= beta):
            return v, v_move

        alpha = max(alpha, v)

    return v, v_move

def min_value(state, alpha, beta, player_color, depth=0):
    if(terminate(depth)):
        return utility(state, max_player=False), None

    v = INFINITY
    v_move = None
    for move in actions(state, player_color):
        next_player = 'W' if player_color == 'B' else 'B'
        max_v, max_move = max_value(move.state, alpha, beta, next_player, depth=depth+1)
        if(max_v < v):
            v = max_v
            v_move = move
        if(v <= beta):
            return v, v_move

        beta = min(beta, v)
        

    return v, v_move
# -

SLD((0, 0), (1,1))

SLD((0,0), (2,2))



# +
mode, player_color, total_play_time, board = read_input()
positions = {}

for i in range(0, len(board)):
    for j in range(0, len(board[0])):
        if(board[i][j] != '.'):
            positions[(i, j)] = board[i][j]
            
print(positions)

if(player_color == 'WHITE'):
    player_color = 'W'
else:
    player_color = 'B'
MY_COLOR = player_color
t = time.time()
# %time action = alpha_beta_search(positions, player_color)
print("CPU time", time.time()-t)
print(action[0])
print(action[1])
# -

m = actions({(6, 6): 'W', (8, 8): 'W', (9, 9): 'W'}, 'W')
print(len(m))
for a in m:
    print(a)
    print()

# +
import numpy as np

x = np.zeros((16, 16))

# +
import math
def SLD(curr, goal):
    # straight line distance
    x = math.pow(goal[0] - curr[0], 2)
    y = math.pow(goal[1] - curr[1], 2)
    
    return math.sqrt(x + y)

precomputed_distances = {}

def get_distances(position):
    distances = {}
    for i in range(len(x)):
        for j in range(len(x[0])):
            distances[(i, j)] = SLD(position, (i, j))
            
    return distances

for i in range(len(x)):
    for j in range(len(x[0])):
        precomputed_distances[(i, j)] = get_distances((i, j))
# -

import pickle
with open("distances.pkl", "wb") as f:
    pickle.dump(precomputed_distances, f)

with open("distances.pkl", "rb") as f:
    PRECOMPUTED_DISTANCES = pickle.load(f)

# %time SLD((0,0), (15, 15))

# %time PRECOMPUTED_DISTANCES[(1,5)][(10,10)]



StarcoderdataJupyterScriptsDedupFiltered