FC 2020 (phil's version) BFS like to be continued

import math
import random
import sys
import time
from copy import copy
from typing import Tuple, List, Optional
from collections import deque
from numpy import array, where


def idebug(*args):
    return
    print(*args, file=sys.stderr, flush=True)


def debug(*args):
    # return
    print(*args, file=sys.stderr, flush=True)


class Potion:
    def __init__(self, potion_id, delta, price):
        self.potion_id = potion_id
        self.delta = delta
        self.price = price

    def __eq__(self, other):
        return self.potion_id == other.potion_id

    def __repr__(self):
        return f'{self.potion_id} {str(self.delta)} {self.price}'


class Spell:
    def __init__(self, cast_id, delta, castable):
        self.cast_id = cast_id
        self.delta = delta
        self.castable = castable

    def __copy__(self):
        return Spell(self.cast_id, self.delta.copy(), self.castable)

    def __hash__(self):
        return hash((str(self.delta), self.castable))

    def __repr__(self):
        return f'{self.cast_id} {str(self.delta)} {self.castable}'


class Action:
    def __init__(self, action_type, action_id=None, delta=None):
        self.action_type = action_type
        self.action_id = action_id
        self.delta = delta

    def __hash__(self):
        # return hash((self.action_type, self.action_id, tuple(map(tuple, self.delta))))
        return hash((self.action_type, self.action_id))

    def __repr__(self):
        if self.action_type == 'CAST':
            return f'CAST {self.action_id}'
        elif self.action_type == 'BREW':
            return f'BREW {self.action_id}'
        else:
            return 'REST'


def bfs_paths(witch_id: int, potion: Potion):
    if witch_id == 0:
        inv: array = my_inv.copy()
        spells: List = [copy(s) for s in my_spells]
    else:
        inv: array = op_inv.copy()
        spells: List = [copy(s) for s in op_spells]
    queue = deque([(spells, inv, [])])
    nodes_count = 0
    # new_start = time.time()
    visited_states = []
    while queue and (time.time() - start) * 1000 < 50:
        spells, inv, path = queue.popleft()
        actions = [Action('CAST', s.id, s.delta) for s in spells if s.castable and all((s.delta + inv >= 0))]
        # if not any([s.castable for s in spells]):
        actions.append(Action('REST'))
        # debug(f'actions: {actions}')
        # la petite fourmi se deplace pour chercher son chemin
        actions = random.sample(actions, min(2, len(actions)))
        # actions = random.choice(actions)
        for action in actions:
            new_spells: List = [copy(s) for s in spells]
            if action.action_type == 'CAST':
                # if inventory is not full after cast, add new recipe, and set castable flag to False
                new_inv: array = inv + action.delta
                if sum(new_inv) > 10:
                    continue
                for s in new_spells:
                    if action.action_id == s.id:
                        s.castable = False
            else:  # action.action_type == REST
                new_inv = inv
                for s in new_spells:
                    s.castable = True
            # gamestate = hash((action, frozenset(new_spells), str(new_inv)))
            # # gamestate = (action, frozenset(new_spells), str(new_inv))
            # if gamestate in visited_states:
            #     continue
            if all((new_inv + potion.delta >= 0)):
                debug(f'BFS player {witch_id} - nodes_count = {nodes_count}')
                # debug(f'remaining time after BFS witch_id {witch_id} = {round((time.time() - new_start) * 1000, 2)} ms')
                brew_action = Action('BREW', potion.potion_id)
                # debug(f'{str(new_inv)} + {str(potion.delta)} = {new_inv + potion.delta}')
                yield path + [action, brew_action]
            else:
                node = (new_spells, new_inv, path + [action])
                queue.append(node)
                # visited_states.append(gamestate)
                # debug(f'node = {node}')
                # debug(f'game state = {gamestate}')
                nodes_count += 1
    debug(f'witch {witch_id} = no solution found!')


def shortest_path(witch_id: int, potion: Potion):
    try:
        return next(bfs_paths(witch_id, potion))
    except StopIteration:
        return None


def get_action_ia(inv, potion, last_turn_brewed):
    action = None
    if all((inv + potion.delta >= 0)):
        action = f'BREW {potion.potion_id}'
        last_turn_brewed = True
    elif last_turn_brewed:
        action = 'REST'
        last_turn_brewed = False
    else:
        actions = shortest_path(witch_id=0, potion=potion)
        if actions:
            action = actions[0]
            debug(f'path to potion {potion} = {actions}')
        else:
            action
    return action


# somme = lambda a, b: [[sum(x) for x in list(zip(a, b))]]

last_turn_brewed = False
unbrewable_potions = []
# game loop
while True:
    action_count = int(input())  # the number of spells and recipes in play
    start = time.time()
    idebug(action_count)
    my_spells, op_spells = [], []
    my_inv, op_inv = [], []
    potions = []
    for i in range(action_count):
        line = input()
        idebug(line)
        inputs = line.split()
        action_id = int(inputs[0])  # the unique ID of this spell or recipe
        action_type = inputs[1]  # in the first league: BREW; later: CAST, OPPONENT_CAST, LEARN, BREW
        delta = array([int(inputs[2]), int(inputs[3]), int(inputs[4]), int(inputs[5])])
        price = int(inputs[6])  # the price in rupees if this is a potion
        tome_index = int(inputs[
                             7])  # in the first two leagues: always 0; later: the index in the tome if this is a tome spell, equal to the read-ahead tax; For brews, this is the value of the current urgency bonus
        tax_count = int(inputs[
                            8])  # in the first two leagues: always 0; later: the amount of taxed tier-0 ingredients you gain from learning this spell; For brews, this is how many times you can still gain an urgency bonus
        castable = inputs[9] != "0"  # in the first league: always 0; later: 1 if this is a castable player spell
        repeatable = inputs[10] != "0"  # for the first two leagues: always 0; later: 1 if this is a repeatable player spell
        if action_type == 'CAST':
            my_spells.append(Spell(action_id, delta, castable))
        elif action_type == 'OPPONENT_CAST':
            op_spells.append(Spell(action_id, delta, castable))
        elif action_type == 'BREW':
            potions.append(Potion(action_id, delta, price))
    for i in range(2):
        # inv_0: tier-0 ingredients in inventory
        # score: amount of rupees
        line = input()
        idebug(line)
        inv_0, inv_1, inv_2, inv_3, score = [int(j) for j in line.split()]
        if i == 0:
            my_inv, my_score = array([inv_0, inv_1, inv_2, inv_3]), score
        else:
            op_inv, op_score = array([inv_0, inv_1, inv_2, inv_3]), score

    # debug(f'my spells = {my_spells}')

    # in the first league: BREW <id> | WAIT; later: BREW <id> | CAST <id> [<times>] | LEARN <id> | REST | WAIT
    # potion_to_brew = random.choice(potions)
    potions_candidates = [p for p in potions if p not in unbrewable_potions]
    if not potions_candidates:
        potions_candidates = potions
    potion_to_brew = min(potions_candidates, key=lambda p: p.price)

    debug(f'potion to brew: {potion_to_brew}')

    action = get_action_ia(my_inv, potion_to_brew, last_turn_brewed)

    if action is None:
        unbrewable_potions.append(potion_to_brew)

    print(action if action else Action('REST'))
    debug(f'elapsed time = {round((time.time() - start) * 1000)} ms')